41 // }; |
41 // }; |
42 |
42 |
43 template <typename Graph, typename EdgeCap, typename NodeCap, |
43 template <typename Graph, typename EdgeCap, typename NodeCap, |
44 typename EdgeFlow, typename NodeFlow> |
44 typename EdgeFlow, typename NodeFlow> |
45 class MaxMatching { |
45 class MaxMatching { |
46 // : public MaxFlow<stGraphWrapper<Graph>, |
|
47 // stGraphWrapper<Graph>:: EdgeMapWrapper<EdgeCan, NodeCap>, stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > { |
|
48 // typedef MaxFlow<stGraphWrapper<Graph>, |
|
49 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCan, NodeCap>, |
|
50 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > |
|
51 // Parent; |
|
52 protected: |
46 protected: |
53 // EdgeCap* edge_cap; |
47 // EdgeCap* edge_cap; |
54 // NodeCap* node_cap; |
48 // NodeCap* node_cap; |
55 // EdgeFlow* edge_flow; |
49 // EdgeFlow* edge_flow; |
56 // NodeFlow* node_flow; |
50 // NodeFlow* node_flow; |
57 typedef stGraphWrapper<Graph> stGW; |
51 typedef stGraphWrapper<Graph> stGW; |
58 stGW stgw; |
52 stGW stgw; |
59 typedef typename stGW::template EdgeMapWrapper<EdgeCap, NodeCap> CapMap; |
53 typedef typename stGW::template EdgeMapWrapper<EdgeCap, NodeCap> CapMap; |
60 CapMap cap; |
54 CapMap cap; |
|
55 NodeFlow* node_flow; |
61 typedef typename stGW::template EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap; |
56 typedef typename stGW::template EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap; |
62 FlowMap flow; |
57 FlowMap flow; |
63 MaxFlow<stGW, int, CapMap, FlowMap> mf; |
58 MaxFlow<stGW, int, CapMap, FlowMap> mf; |
64 //graph* g; |
59 //graph* g; |
65 //EdgeCap* edge_cap; |
60 //EdgeCap* edge_cap; |
66 //EdgeFlow* edge_flow; |
61 //EdgeFlow* edge_flow; |
67 public: |
62 public: |
68 MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, |
63 MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, |
69 EdgeFlow& _edge_flow, NodeFlow& _node_flow) : |
64 EdgeFlow& _edge_flow, NodeFlow& _node_flow) : |
70 stgw(_g), |
65 stgw(_g), |
71 cap(_edge_cap, _node_cap), flow(_edge_flow, _node_flow), |
66 cap(_edge_cap, _node_cap), |
|
67 node_flow(0), |
|
68 flow(_edge_flow, _node_flow), |
72 mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { } |
69 mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { } |
|
70 MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, |
|
71 EdgeFlow& _edge_flow/*, NodeFlow& _node_flow*/) : |
|
72 stgw(_g), |
|
73 cap(_edge_cap, _node_cap), |
|
74 node_flow(new NodeFlow(_g)), |
|
75 flow(_edge_flow, *node_flow), |
|
76 mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { } |
|
77 ~MaxMatching() { if (node_flow) delete node_flow; } |
73 void run() { mf.run(); } |
78 void run() { mf.run(); } |
74 int matchingValue() { return mf.flowValue(); } |
79 int matchingValue() { return mf.flowValue(); } |
75 }; |
80 }; |
76 |
81 |
77 /** |
82 /** |
128 random_init(); |
133 random_init(); |
129 for(int i=0; i<m; ++i) { |
134 for(int i=0; i<m; ++i) { |
130 g.addEdge(s_nodes[random(a)], t_nodes[random(b)]); |
135 g.addEdge(s_nodes[random(a)], t_nodes[random(b)]); |
131 } |
136 } |
132 |
137 |
133 std::cout << "Edges of the bipartite graph:" << std::endl; |
138 // std::cout << "Edges of the bipartite graph:" << std::endl; |
134 FOR_EACH_LOC(EdgeIt, e, g) std::cout << e << " "; |
139 // FOR_EACH_LOC(EdgeIt, e, g) std::cout << e << " "; |
135 std::cout << std::endl; |
140 // std::cout << std::endl; |
136 |
141 |
137 std::cout << "Nodes:" << std::endl; |
142 // std::cout << "Nodes:" << std::endl; |
138 FOR_EACH_LOC(Graph::NodeIt, v, g) std::cout << v << " "; |
143 // FOR_EACH_LOC(Graph::NodeIt, v, g) std::cout << v << " "; |
139 std::cout << std::endl; |
144 // std::cout << std::endl; |
140 std::cout << "Nodes in T:" << std::endl; |
145 // std::cout << "Nodes in T:" << std::endl; |
141 FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " "; |
146 // FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " "; |
142 std::cout << std::endl; |
147 // std::cout << std::endl; |
143 std::cout << "Nodes in S:" << std::endl; |
148 // std::cout << "Nodes in S:" << std::endl; |
144 FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " "; |
149 // FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " "; |
145 std::cout << std::endl; |
150 // std::cout << std::endl; |
146 |
151 |
147 std::cout << "Erasing the first node..." << std::endl; |
152 // std::cout << "Erasing the first node..." << std::endl; |
148 NodeIt n; |
153 // NodeIt n; |
149 g.first(n); |
154 // g.first(n); |
150 g.erase(n); |
155 // g.erase(n); |
151 std::cout << "Nodes of the bipartite graph:" << std::endl; |
156 // std::cout << "Nodes of the bipartite graph:" << std::endl; |
152 FOR_EACH_GLOB(n, g) std::cout << n << " "; |
157 // FOR_EACH_GLOB(n, g) std::cout << n << " "; |
153 std::cout << std::endl; |
158 // std::cout << std::endl; |
154 |
159 |
155 std::cout << "Nodes in T:" << std::endl; |
160 // std::cout << "Nodes in T:" << std::endl; |
156 FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " "; |
161 // FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " "; |
157 std::cout << std::endl; |
162 // std::cout << std::endl; |
158 std::cout << "Nodes in S:" << std::endl; |
163 // std::cout << "Nodes in S:" << std::endl; |
159 FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " "; |
164 // FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " "; |
160 std::cout << std::endl; |
165 // std::cout << std::endl; |
161 |
166 |
162 typedef stGraphWrapper<Graph> stGW; |
167 typedef stGraphWrapper<Graph> stGW; |
163 stGW stgw(g); |
168 stGW stgw(g); |
164 ConstMap<stGW::Edge, int> const1map(1); |
169 ConstMap<stGW::Edge, int> const1map(1); |
165 |
170 |
175 // while (max_flow_test.augmentOnBlockingFlow2()) { |
180 // while (max_flow_test.augmentOnBlockingFlow2()) { |
176 // std::cout << max_flow_test.flowValue() << std::endl; |
181 // std::cout << max_flow_test.flowValue() << std::endl; |
177 // } |
182 // } |
178 std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl; |
183 std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl; |
179 std::cout << "elapsed time: " << ts << std::endl; |
184 std::cout << "elapsed time: " << ts << std::endl; |
180 FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { |
185 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { |
181 if (flow[e]) std::cout << e << std::endl; |
186 // if (flow[e]) std::cout << e << std::endl; |
182 } |
187 // } |
183 std::cout << std::endl; |
188 std::cout << std::endl; |
184 |
189 |
185 typedef ConstMap<Graph::Edge, int> EdgeCap; |
190 typedef ConstMap<Graph::Edge, int> EdgeCap; |
186 EdgeCap ge1(1); |
191 EdgeCap ge1(1); |
187 typedef ConstMap<Graph::Node, int> NodeCap; |
192 typedef ConstMap<Graph::Node, int> NodeCap; |
227 std::cout << "elapsed time: " << ts << std::endl; |
232 std::cout << "elapsed time: " << ts << std::endl; |
228 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
233 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
229 // if (gef[e]) std::cout << e << std::endl; |
234 // if (gef[e]) std::cout << e << std::endl; |
230 // } |
235 // } |
231 std::cout << std::endl; |
236 std::cout << std::endl; |
|
237 |
|
238 ts.reset(); |
|
239 FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0); |
|
240 //FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0); |
|
241 MaxMatching<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>, |
|
242 Graph::EdgeMap<int>, Graph::NodeMap<int> > |
|
243 matching_test_1(g, ge1, gn1, gef/*, gnf*/); |
|
244 matching_test_1.run(); |
|
245 |
|
246 std::cout << "max flow value: " << matching_test_1.matchingValue() << std::endl; |
|
247 std::cout << "elapsed time: " << ts << std::endl; |
|
248 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
|
249 // if (gef[e]) std::cout << e << std::endl; |
|
250 // } |
|
251 std::cout << std::endl; |
|
252 |
232 return 0; |
253 return 0; |
233 } |
254 } |