87 |
88 |
88 IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map); |
89 IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map); |
89 for (int i=0; i<a; ++i) bipartite_map.insert(s_nodes[i], false); |
90 for (int i=0; i<a; ++i) bipartite_map.insert(s_nodes[i], false); |
90 for (int i=0; i<b; ++i) bipartite_map.insert(t_nodes[i], true); |
91 for (int i=0; i<b; ++i) bipartite_map.insert(t_nodes[i], true); |
91 |
92 |
92 // Graph::Node u; |
|
93 // std::cout << "These nodes will be in S:\n"; |
|
94 // //FIXME azert kellene ++, es invalid vizsgalat u-bol, hogy ezt le lehessen |
|
95 // //irni 1etlen FOR_EACH-csel. |
|
96 // for (bipartite_map.first(u, false); g.valid(u); bipartite_map.next(u)) |
|
97 // std::cout << u << " "; |
|
98 // std::cout << "\n"; |
|
99 // std::cout << "These nodes will be in T:\n"; |
|
100 // for (bipartite_map.first(u, true); g.valid(u); bipartite_map.next(u)) |
|
101 // std::cout << u << " "; |
|
102 // std::cout << "\n"; |
|
103 |
|
104 typedef BipartiteGraphWrapper<Graph> BGW; |
93 typedef BipartiteGraphWrapper<Graph> BGW; |
105 BGW bgw(g, bipartite_map); |
94 BGW bgw(g, bipartite_map); |
106 |
|
107 // std::cout << "Nodes by NodeIt:\n"; |
|
108 // FOR_EACH_LOC(BGW::NodeIt, n, bgw) { |
|
109 // std::cout << n << " "; |
|
110 // } |
|
111 // std::cout << "\n"; |
|
112 // std::cout << "Nodes in S by ClassNodeIt:\n"; |
|
113 // FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.S_CLASS) { |
|
114 // std::cout << n << " "; |
|
115 // } |
|
116 // std::cout << "\n"; |
|
117 // std::cout << "Nodes in T by ClassNodeIt:\n"; |
|
118 // FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.T_CLASS) { |
|
119 // std::cout << n << " "; |
|
120 // } |
|
121 // std::cout << "\n"; |
|
122 // std::cout << "Edges of the bipartite graph:\n"; |
|
123 // FOR_EACH_LOC(BGW::EdgeIt, e, bgw) { |
|
124 // std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl; |
|
125 // } |
|
126 |
95 |
127 BGW::NodeMap<int> dbyj(bgw); |
96 BGW::NodeMap<int> dbyj(bgw); |
128 BGW::EdgeMap<int> dbyxcj(bgw); |
97 BGW::EdgeMap<int> dbyxcj(bgw); |
129 |
98 |
130 typedef stGraphWrapper<BGW> stGW; |
99 typedef stGraphWrapper<BGW> stGW; |
131 stGW stgw(bgw); |
100 stGW stgw(bgw); |
132 ConstMap<stGW::Edge, int> const1map(1); |
101 ConstMap<stGW::Edge, int> const1map(1); |
133 // stGW::NodeMap<int> ize(stgw); |
|
134 |
|
135 // BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw); |
|
136 // Graph::NodeIt si; |
|
137 // Graph::Node s; |
|
138 // s=g.first(si); |
|
139 // bfs.pushAndSetReached(BGW::Node(s)); |
|
140 // while (!bfs.finished()) { ++bfs; } |
|
141 |
|
142 // FOR_EACH_LOC(stGW::NodeIt, n, stgw) { |
|
143 // std::cout << "out-edges of " << n << ":\n"; |
|
144 // FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) { |
|
145 // std::cout << " " << e << "\n"; |
|
146 // std::cout << " aNode: " << stgw.aNode(e) << "\n"; |
|
147 // std::cout << " bNode: " << stgw.bNode(e) << "\n"; |
|
148 // } |
|
149 // std::cout << "in-edges of " << n << ":\n"; |
|
150 // FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) { |
|
151 // std::cout << " " << e << "\n"; |
|
152 // std::cout << " aNode: " << stgw.aNode(e) << "\n"; |
|
153 // std::cout << " bNode: " << stgw.bNode(e) << "\n"; |
|
154 // } |
|
155 // } |
|
156 // std::cout << "Edges of the stGraphWrapper:\n"; |
|
157 // FOR_EACH_LOC(stGW::EdgeIt, n, stgw) { |
|
158 // std::cout << " " << n << "\n"; |
|
159 // } |
|
160 |
|
161 // stGW::NodeMap<bool> b(stgw); |
|
162 // FOR_EACH_LOC(stGW::NodeIt, n, stgw) { |
|
163 // std::cout << n << ": " << b[n] <<"\n"; |
|
164 // } |
|
165 |
|
166 // std::cout << "Bfs from s: \n"; |
|
167 // BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw); |
|
168 // bfs_stgw.pushAndSetReached(stgw.S_NODE); |
|
169 // while (!bfs_stgw.finished()) { |
|
170 // std::cout << " " << stGW::OutEdgeIt(bfs_stgw) << "\n"; |
|
171 // ++bfs_stgw; |
|
172 // } |
|
173 |
|
174 |
102 |
175 Timer ts; |
103 Timer ts; |
176 ts.reset(); |
104 ts.reset(); |
177 stGW::EdgeMap<int> max_flow(stgw); |
105 stGW::EdgeMap<int> max_flow(stgw); |
178 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > |
106 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > |