1 // -*- c++ -*- |
1 // -*- c++ -*- |
2 #include <iostream> |
2 #ifndef HUGO_MAX_BIPARTITE_MATCHING_H |
3 #include <fstream> |
3 #define HUGO_MAX_BIPARTITE_MATCHING_H |
4 #include <vector> |
|
5 |
4 |
6 #include <list_graph.h> |
5 //#include <for_each_macros.h> |
7 //#include <smart_graph.h> |
|
8 //#include <dimacs.h> |
|
9 #include <hugo/time_measure.h> |
|
10 #include <for_each_macros.h> |
|
11 #include <bfs_iterator.h> |
|
12 #include <bipartite_graph_wrapper.h> |
6 #include <bipartite_graph_wrapper.h> |
13 #include <hugo/maps.h> |
7 //#include <hugo/maps.h> |
14 #include <max_flow.h> |
8 #include <max_flow.h> |
15 #include <graph_gen.h> |
|
16 |
9 |
17 using namespace hugo; |
10 namespace hugo { |
18 |
11 |
19 // template <typename Graph, typename EdgeCap, typename NodeCap, |
12 // template <typename Graph, typename EdgeCap, typename NodeCap, |
20 // typename EdgeFlow, typename NodeFlow> |
13 // typename EdgeFlow, typename NodeFlow> |
21 // class MaxMatching : public MaxFlow<stGraphWrapper<Graph>, |
14 // class MaxMatching : public MaxFlow<stGraphWrapper<Graph>, |
22 // stGraphWrapper<Graph>:: EdgeMapWrapper<EdgeCan, NodeCap>, stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > { |
15 // stGraphWrapper<Graph>:: EdgeMapWrapper<EdgeCan, NodeCap>, stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > { |
23 // typedef MaxFlow<stGraphWrapper<Graph>, |
16 // typedef MaxFlow<stGraphWrapper<Graph>, |
24 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCan, NodeCap>, |
17 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCan, NodeCap>, |
25 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > |
18 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > |
26 // Parent; |
19 // Parent; |
27 // protected: |
20 // protected: |
28 // stGraphWrapper<Graph> gw; |
21 // stGraphWrapper<Graph> gw; |
29 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCap, NodeCap> cap; |
22 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCap, NodeCap> cap; |
30 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> flow; |
23 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> flow; |
31 // //graph* g; |
24 // //graph* g; |
32 // //EdgeCap* edge_cap; |
25 // //EdgeCap* edge_cap; |
33 // //EdgeFlow* edge_flow; |
26 // //EdgeFlow* edge_flow; |
34 // public: |
27 // public: |
35 // MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, |
28 // MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, |
36 // EdgeFlow& _edge_flow, NodeFlow& _node_flow) : |
29 // EdgeFlow& _edge_flow, NodeFlow& _node_flow) : |
37 // MaxFlow(), gw(_g), |
30 // MaxFlow(), gw(_g), |
38 // cap(_edge_cap, _node_cap), flow(_edge_flow, _node_flow) { |
31 // cap(_edge_cap, _node_cap), flow(_edge_flow, _node_flow) { |
39 // Parent::set(gw, cap, flow); |
32 // Parent::set(gw, cap, flow); |
40 // } |
33 // } |
41 // }; |
34 // }; |
42 |
35 |
43 template <typename Graph, typename EdgeCap, typename NodeCap, |
36 /// A bipartite matching class. |
44 typename EdgeFlow, typename NodeFlow> |
37 /// This class reduces the matching problem to a flow problem and |
45 class MaxMatching { |
38 /// a preflow is used on a wrapper. Such a generic approach means that |
46 protected: |
39 /// matchings, b-matchings an capacitated b-matchings can be handled in |
47 // EdgeCap* edge_cap; |
40 /// a similar way. Due to the efficiency of the preflow algorithm, an |
48 // NodeCap* node_cap; |
41 /// efficient matching framework is obtained. |
49 // EdgeFlow* edge_flow; |
42 template <typename Graph, typename EdgeCap, typename NodeCap, |
50 // NodeFlow* node_flow; |
43 typename EdgeFlow, typename NodeFlow> |
51 typedef stGraphWrapper<Graph> stGW; |
44 class MaxMatching { |
52 stGW stgw; |
45 protected: |
53 typedef typename stGW::template EdgeMapWrapper<EdgeCap, NodeCap> CapMap; |
46 // EdgeCap* edge_cap; |
54 CapMap cap; |
47 // NodeCap* node_cap; |
55 NodeFlow* node_flow; |
48 // EdgeFlow* edge_flow; |
56 typedef typename stGW::template EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap; |
49 // NodeFlow* node_flow; |
57 FlowMap flow; |
50 typedef stGraphWrapper<Graph> stGW; |
58 MaxFlow<stGW, int, CapMap, FlowMap> mf; |
51 stGW stgw; |
59 //graph* g; |
52 typedef typename stGW::template EdgeMapWrapper<EdgeCap, NodeCap> CapMap; |
60 //EdgeCap* edge_cap; |
53 CapMap cap; |
61 //EdgeFlow* edge_flow; |
54 NodeFlow* node_flow; |
62 public: |
55 typedef typename stGW::template EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap; |
63 MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, |
56 FlowMap flow; |
64 EdgeFlow& _edge_flow, NodeFlow& _node_flow) : |
57 MaxFlow<stGW, int, CapMap, FlowMap> mf; |
65 stgw(_g), |
58 //graph* g; |
66 cap(_edge_cap, _node_cap), |
59 //EdgeCap* edge_cap; |
67 node_flow(0), |
60 //EdgeFlow* edge_flow; |
68 flow(_edge_flow, _node_flow), |
61 public: |
69 mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { } |
62 /// For capacitated b-matchings, edge-caoacities and node-capacities |
70 MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, |
63 /// have to be given. After running \c run the matching is is given |
71 EdgeFlow& _edge_flow/*, NodeFlow& _node_flow*/) : |
64 /// back in the edge-map \c _edge_flow and \c _node_map can be used |
72 stgw(_g), |
65 /// to obtain saturation information about nodes. |
73 cap(_edge_cap, _node_cap), |
66 ///\bug Note that the values in _edge_flow and _node_flow have |
74 node_flow(new NodeFlow(_g)), |
67 /// to form a flow. |
75 flow(_edge_flow, *node_flow), |
68 MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, |
76 mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { } |
69 EdgeFlow& _edge_flow, NodeFlow& _node_flow) : |
77 ~MaxMatching() { if (node_flow) delete node_flow; } |
70 stgw(_g), |
78 void run() { mf.run(); } |
71 cap(_edge_cap, _node_cap), |
79 int matchingValue() { return mf.flowValue(); } |
72 node_flow(0), |
80 }; |
73 flow(_edge_flow, _node_flow), |
|
74 mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { } |
|
75 /// If the saturation information of nodes is not needed that the use of |
|
76 /// this constructor is more comfortable. |
|
77 ///\bug Note that the values in _edge_flow and _node_flow have |
|
78 /// to form a flow. |
|
79 MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, |
|
80 EdgeFlow& _edge_flow/*, NodeFlow& _node_flow*/) : |
|
81 stgw(_g), |
|
82 cap(_edge_cap, _node_cap), |
|
83 node_flow(new NodeFlow(_g)), |
|
84 flow(_edge_flow, *node_flow), |
|
85 mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { } |
|
86 /// The class have a nontrivial destructor. |
|
87 ~MaxMatching() { if (node_flow) delete node_flow; } |
|
88 /// run computes the max matching. |
|
89 void run() { mf.run(); } |
|
90 /// The matching value after running \c run. |
|
91 int matchingValue() { return mf.flowValue(); } |
|
92 }; |
81 |
93 |
|
94 } //namespace hugo |
82 |
95 |
83 int main() { |
96 #endif //HUGO_MAX_BIPARTITE_MATCHING_H |
84 //typedef UndirListGraph Graph; |
|
85 typedef BipartiteGraph<ListGraph> Graph; |
|
86 |
|
87 typedef Graph::Node Node; |
|
88 typedef Graph::NodeIt NodeIt; |
|
89 typedef Graph::Edge Edge; |
|
90 typedef Graph::EdgeIt EdgeIt; |
|
91 typedef Graph::OutEdgeIt OutEdgeIt; |
|
92 |
|
93 Graph g; |
|
94 |
|
95 int a; |
|
96 std::cout << "number of nodes in the first color class="; |
|
97 std::cin >> a; |
|
98 int b; |
|
99 std::cout << "number of nodes in the second color class="; |
|
100 std::cin >> b; |
|
101 int m; |
|
102 std::cout << "number of edges="; |
|
103 std::cin >> m; |
|
104 |
|
105 std::cout << "Generatig a random bipartite graph..." << std::endl; |
|
106 random_init(); |
|
107 randomBipartiteGraph(g, a, b, m); |
|
108 |
|
109 // std::cout << "Edges of the bipartite graph:" << std::endl; |
|
110 // FOR_EACH_LOC(EdgeIt, e, g) std::cout << e << " "; |
|
111 // std::cout << std::endl; |
|
112 |
|
113 // std::cout << "Nodes:" << std::endl; |
|
114 // FOR_EACH_LOC(Graph::NodeIt, v, g) std::cout << v << " "; |
|
115 // std::cout << std::endl; |
|
116 // std::cout << "Nodes in T:" << std::endl; |
|
117 // FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " "; |
|
118 // std::cout << std::endl; |
|
119 // std::cout << "Nodes in S:" << std::endl; |
|
120 // FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " "; |
|
121 // std::cout << std::endl; |
|
122 |
|
123 // std::cout << "Erasing the first node..." << std::endl; |
|
124 // NodeIt n; |
|
125 // g.first(n); |
|
126 // g.erase(n); |
|
127 // std::cout << "Nodes of the bipartite graph:" << std::endl; |
|
128 // FOR_EACH_GLOB(n, g) std::cout << n << " "; |
|
129 // std::cout << std::endl; |
|
130 |
|
131 // std::cout << "Nodes in T:" << std::endl; |
|
132 // FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " "; |
|
133 // std::cout << std::endl; |
|
134 // std::cout << "Nodes in S:" << std::endl; |
|
135 // FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " "; |
|
136 // std::cout << std::endl; |
|
137 |
|
138 typedef stGraphWrapper<Graph> stGW; |
|
139 stGW stgw(g); |
|
140 ConstMap<stGW::Edge, int> const1map(1); |
|
141 |
|
142 Timer ts; |
|
143 ts.reset(); |
|
144 stGW::EdgeMap<int> flow(stgw); |
|
145 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > |
|
146 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow); |
|
147 max_flow_test.run(); |
|
148 // while (max_flow_test.augmentOnShortestPath()) { } |
|
149 // typedef ListGraph MutableGraph; |
|
150 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { |
|
151 // while (max_flow_test.augmentOnBlockingFlow2()) { |
|
152 // std::cout << max_flow_test.flowValue() << std::endl; |
|
153 // } |
|
154 std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl; |
|
155 std::cout << "elapsed time: " << ts << std::endl; |
|
156 // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { |
|
157 // if (flow[e]) std::cout << e << std::endl; |
|
158 // } |
|
159 std::cout << std::endl; |
|
160 |
|
161 typedef ConstMap<Graph::Edge, int> EdgeCap; |
|
162 EdgeCap ge1(1); |
|
163 typedef ConstMap<Graph::Node, int> NodeCap; |
|
164 NodeCap gn1(1); |
|
165 typedef Graph::EdgeMap<int> EdgeFlow; |
|
166 EdgeFlow gef(g); //0 |
|
167 typedef Graph::NodeMap<int> NodeFlow; |
|
168 NodeFlow gnf(g); //0 |
|
169 |
|
170 typedef stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCap, NodeCap> CapMap; |
|
171 typedef stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap; |
|
172 CapMap cm(ge1, gn1); |
|
173 FlowMap fm(gef, gnf); |
|
174 |
|
175 //Timer ts; |
|
176 ts.reset(); |
|
177 //stGW::EdgeMap<int> flow(stgw); |
|
178 MaxFlow<stGW, int, CapMap, FlowMap> |
|
179 max_flow_test1(stgw, stgw.S_NODE, stgw.T_NODE, cm, fm); |
|
180 max_flow_test1.run(); |
|
181 // while (max_flow_test.augmentOnShortestPath()) { } |
|
182 // typedef ListGraph MutableGraph; |
|
183 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { |
|
184 // while (max_flow_test.augmentOnBlockingFlow2()) { |
|
185 // std::cout << max_flow_test.flowValue() << std::endl; |
|
186 // } |
|
187 std::cout << "max flow value: " << max_flow_test1.flowValue() << std::endl; |
|
188 std::cout << "elapsed time: " << ts << std::endl; |
|
189 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
|
190 // if (gef[e]) std::cout << e << std::endl; |
|
191 // } |
|
192 std::cout << std::endl; |
|
193 |
|
194 ts.reset(); |
|
195 FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0); |
|
196 FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0); |
|
197 MaxMatching<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>, |
|
198 Graph::EdgeMap<int>, Graph::NodeMap<int> > |
|
199 matching_test(g, ge1, gn1, gef, gnf); |
|
200 matching_test.run(); |
|
201 |
|
202 std::cout << "max flow value: " << matching_test.matchingValue() << std::endl; |
|
203 std::cout << "elapsed time: " << ts << std::endl; |
|
204 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
|
205 // if (gef[e]) std::cout << e << std::endl; |
|
206 // } |
|
207 std::cout << std::endl; |
|
208 |
|
209 ts.reset(); |
|
210 FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0); |
|
211 //FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0); |
|
212 MaxMatching<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>, |
|
213 Graph::EdgeMap<int>, Graph::NodeMap<int> > |
|
214 matching_test_1(g, ge1, gn1, gef/*, gnf*/); |
|
215 matching_test_1.run(); |
|
216 |
|
217 std::cout << "max flow value: " << matching_test_1.matchingValue() << std::endl; |
|
218 std::cout << "elapsed time: " << ts << std::endl; |
|
219 // FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
|
220 // if (gef[e]) std::cout << e << std::endl; |
|
221 // } |
|
222 std::cout << std::endl; |
|
223 |
|
224 return 0; |
|
225 } |
|