50 IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map); |
54 IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map); |
51 for (int i=0; i<3; ++i) bipartite_map.insert(nodes[i], false); |
55 for (int i=0; i<3; ++i) bipartite_map.insert(nodes[i], false); |
52 for (int i=3; i<6; ++i) bipartite_map.insert(nodes[i], true); |
56 for (int i=3; i<6; ++i) bipartite_map.insert(nodes[i], true); |
53 |
57 |
54 Graph::Node u; |
58 Graph::Node u; |
55 std::cout << "These nodes will be in S:\n"; |
59 cout << "These nodes will be in S:" << endl; |
56 //FIXME azert kellene ++, es invalid vizsgalat u-bol, hogy ezt le lehessen |
60 //FIXME azert kellene ++, es invalid vizsgalat u-bol, hogy ezt le lehessen |
57 //irni 1etlen FOR_EACH-csel. |
61 //irni 1etlen FOR_EACH-csel. |
58 for (bipartite_map.first(u, false); g.valid(u); bipartite_map.next(u)) |
62 for (bipartite_map.first(u, false); u!=INVALID; bipartite_map.next(u)) |
59 std::cout << u << " "; |
63 cout << g.id(u) << " "; |
60 std::cout << "\n"; |
64 cout << endl; |
61 std::cout << "These nodes will be in T:\n"; |
65 cout << "These nodes will be in T:" << endl; |
62 for (bipartite_map.first(u, true); g.valid(u); bipartite_map.next(u)) |
66 for (bipartite_map.first(u, true); u!=INVALID; bipartite_map.next(u)) |
63 std::cout << u << " "; |
67 cout << g.id(u) << " "; |
64 std::cout << "\n"; |
68 cout << endl; |
65 |
69 |
66 typedef BipartiteGraphWrapper<Graph> BGW; |
70 typedef BipartiteGraphWrapper<Graph> BGW; |
67 BGW bgw(g, bipartite_map); |
71 BGW bgw(g, bipartite_map); |
68 |
72 |
69 std::cout << "Nodes by NodeIt:\n"; |
73 cout << "Nodes by NodeIt:" << endl; |
70 FOR_EACH_LOC(BGW::NodeIt, n, bgw) { |
74 for (BGW::NodeIt n(bgw); n!=INVALID; ++n) |
71 std::cout << n << " "; |
75 cout << g.id(n) << " "; |
72 } |
76 cout << endl; |
73 std::cout << "\n"; |
77 |
74 std::cout << "Nodes in S by ClassNodeIt:\n"; |
78 cout << "Nodes in S by ClassNodeIt:" << endl; |
75 FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.S_CLASS) { |
79 for (BGW::ClassNodeIt n(bgw, bgw.S_CLASS); n!=INVALID; ++n) |
76 std::cout << n << " "; |
80 cout << g.id(n) << " "; |
77 } |
81 cout << endl; |
78 std::cout << "\n"; |
82 |
79 std::cout << "Nodes in T by ClassNodeIt:\n"; |
83 cout << "Nodes in T by ClassNodeIt:" << endl; |
80 FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.T_CLASS) { |
84 for (BGW::ClassNodeIt n(bgw, bgw.T_CLASS); n!=INVALID; ++n) |
81 std::cout << n << " "; |
85 cout << g.id(n) << " "; |
82 } |
86 cout << endl; |
83 std::cout << "\n"; |
87 |
84 std::cout << "Edges of the bipartite graph:\n"; |
88 cout << "Edges of the bipartite graph:" << endl; |
85 FOR_EACH_LOC(BGW::EdgeIt, e, bgw) { |
89 for (BGW::EdgeIt e(bgw); e!=INVALID; ++e) |
86 std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl; |
90 cout << g.id(bgw.tail(e)) << "->" << g.id(bgw.head(e)) << endl; |
87 } |
|
88 |
91 |
89 BGW::NodeMap<int> dbyj(bgw); |
92 BGW::NodeMap<int> dbyj(bgw); |
90 BGW::EdgeMap<int> dbyxcj(bgw); |
93 BGW::EdgeMap<int> dbyxcj(bgw); |
91 |
94 |
92 typedef stBipartiteGraphWrapper<BGW> stGW; |
95 // typedef stBipartiteGraphWrapper<BGW> stGW; |
93 stGW stgw(bgw); |
96 // stGW stgw(bgw); |
94 ConstMap<stGW::Edge, int> const1map(1); |
97 // ConstMap<stGW::Edge, int> const1map(1); |
95 stGW::NodeMap<int> ize(stgw); |
98 // stGW::NodeMap<int> ize(stgw); |
96 stGW::EdgeMap<int> flow(stgw); |
99 // stGW::EdgeMap<int> flow(stgw); |
97 |
100 |
98 BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw); |
101 // BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw); |
99 Graph::NodeIt si; |
102 // Graph::NodeIt si; |
100 Graph::Node s; |
103 // Graph::Node s; |
101 s=g.first(si); |
104 // s=g.first(si); |
102 bfs.pushAndSetReached(BGW::Node(s)); |
105 // bfs.pushAndSetReached(BGW::Node(s)); |
103 while (!bfs.finished()) { ++bfs; } |
106 // while (!bfs.finished()) { ++bfs; } |
104 |
107 |
105 FOR_EACH_LOC(stGW::NodeIt, n, stgw) { |
108 // FOR_EACH_LOC(stGW::NodeIt, n, stgw) { |
106 std::cout << "out-edges of " << n << ":\n"; |
109 // cout << "out-edges of " << n << ":" << endl; |
107 FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) { |
110 // FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) { |
108 std::cout << " " << e << "\n"; |
111 // cout << " " << e << endl; |
109 std::cout << " aNode: " << stgw.aNode(e) << "\n"; |
112 // cout << " aNode: " << stgw.aNode(e) << endl; |
110 std::cout << " bNode: " << stgw.bNode(e) << "\n"; |
113 // cout << " bNode: " << stgw.bNode(e) << endl; |
111 } |
114 // } |
112 std::cout << "in-edges of " << n << ":\n"; |
115 // cout << "in-edges of " << n << ":" << endl; |
113 FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) { |
116 // FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) { |
114 std::cout << " " << e << "\n"; |
117 // cout << " " << e << endl; |
115 std::cout << " aNode: " << stgw.aNode(e) << "\n"; |
118 // cout << " aNode: " << stgw.aNode(e) << endl; |
116 std::cout << " bNode: " << stgw.bNode(e) << "\n"; |
119 // cout << " bNode: " << stgw.bNode(e) << endl; |
117 } |
120 // } |
118 } |
121 // } |
119 std::cout << "Edges of the stGraphWrapper:\n"; |
122 // cout << "Edges of the stGraphWrapper:" << endl; |
120 FOR_EACH_LOC(stGW::EdgeIt, n, stgw) { |
123 // FOR_EACH_LOC(stGW::EdgeIt, n, stgw) { |
121 std::cout << " " << n << "\n"; |
124 // cout << " " << n << endl; |
122 } |
125 // } |
123 |
126 |
124 stGW::NodeMap<bool> b(stgw); |
127 // stGW::NodeMap<bool> b(stgw); |
125 FOR_EACH_LOC(stGW::NodeIt, n, stgw) { |
128 // FOR_EACH_LOC(stGW::NodeIt, n, stgw) { |
126 std::cout << n << ": " << b[n] <<"\n"; |
129 // cout << n << ": " << b[n] << endl; |
127 } |
130 // } |
128 |
131 |
129 std::cout << "Bfs from s: \n"; |
132 // cout << "Bfs from s:" << endl; |
130 BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw); |
133 // BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw); |
131 bfs_stgw.pushAndSetReached(stgw.S_NODE); |
134 // bfs_stgw.pushAndSetReached(stgw.S_NODE); |
132 while (!bfs_stgw.finished()) { |
135 // while (!bfs_stgw.finished()) { |
133 std::cout << " " << stGW::OutEdgeIt(bfs_stgw) << "\n"; |
136 // cout << " " << stGW::OutEdgeIt(bfs_stgw) << endl; |
134 ++bfs_stgw; |
137 // ++bfs_stgw; |
135 } |
138 // } |
136 |
139 |
137 AugmentingFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > |
140 // AugmentingFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > |
138 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow); |
141 // max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow); |
139 while (max_flow_test.augmentOnShortestPath()) { } |
142 // while (max_flow_test.augmentOnShortestPath()) { } |
140 |
143 |
141 std::cout << max_flow_test.flowValue() << std::endl; |
144 // cout << max_flow_test.flowValue() << std::endl; |
142 |
145 |
143 return 0; |
146 return 0; |
144 } |
147 } |