11 #include <bfs_iterator.h> |
11 #include <bfs_iterator.h> |
12 #include <bipartite_graph_wrapper.h> |
12 #include <bipartite_graph_wrapper.h> |
13 #include <hugo/maps.h> |
13 #include <hugo/maps.h> |
14 #include <max_flow.h> |
14 #include <max_flow.h> |
15 #include <graph_gen.h> |
15 #include <graph_gen.h> |
|
16 #include <max_bipartite_matching.h> |
16 |
17 |
17 using namespace hugo; |
18 using namespace hugo; |
18 |
|
19 // template <typename Graph, typename EdgeCap, typename NodeCap, |
|
20 // typename EdgeFlow, typename NodeFlow> |
|
21 // class MaxMatching : public MaxFlow<stGraphWrapper<Graph>, |
|
22 // stGraphWrapper<Graph>:: EdgeMapWrapper<EdgeCan, NodeCap>, stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > { |
|
23 // typedef MaxFlow<stGraphWrapper<Graph>, |
|
24 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCan, NodeCap>, |
|
25 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > |
|
26 // Parent; |
|
27 // protected: |
|
28 // stGraphWrapper<Graph> gw; |
|
29 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCap, NodeCap> cap; |
|
30 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> flow; |
|
31 // //graph* g; |
|
32 // //EdgeCap* edge_cap; |
|
33 // //EdgeFlow* edge_flow; |
|
34 // public: |
|
35 // MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, |
|
36 // EdgeFlow& _edge_flow, NodeFlow& _node_flow) : |
|
37 // MaxFlow(), gw(_g), |
|
38 // cap(_edge_cap, _node_cap), flow(_edge_flow, _node_flow) { |
|
39 // Parent::set(gw, cap, flow); |
|
40 // } |
|
41 // }; |
|
42 |
|
43 template <typename Graph, typename EdgeCap, typename NodeCap, |
|
44 typename EdgeFlow, typename NodeFlow> |
|
45 class MaxMatching { |
|
46 protected: |
|
47 // EdgeCap* edge_cap; |
|
48 // NodeCap* node_cap; |
|
49 // EdgeFlow* edge_flow; |
|
50 // NodeFlow* node_flow; |
|
51 typedef stGraphWrapper<Graph> stGW; |
|
52 stGW stgw; |
|
53 typedef typename stGW::template EdgeMapWrapper<EdgeCap, NodeCap> CapMap; |
|
54 CapMap cap; |
|
55 NodeFlow* node_flow; |
|
56 typedef typename stGW::template EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap; |
|
57 FlowMap flow; |
|
58 MaxFlow<stGW, int, CapMap, FlowMap> mf; |
|
59 //graph* g; |
|
60 //EdgeCap* edge_cap; |
|
61 //EdgeFlow* edge_flow; |
|
62 public: |
|
63 MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, |
|
64 EdgeFlow& _edge_flow, NodeFlow& _node_flow) : |
|
65 stgw(_g), |
|
66 cap(_edge_cap, _node_cap), |
|
67 node_flow(0), |
|
68 flow(_edge_flow, _node_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; } |
|
78 void run() { mf.run(); } |
|
79 int matchingValue() { return mf.flowValue(); } |
|
80 }; |
|
81 |
|
82 |
19 |
83 int main() { |
20 int main() { |
84 //typedef UndirListGraph Graph; |
21 //typedef UndirListGraph Graph; |
85 typedef BipartiteGraph<ListGraph> Graph; |
22 typedef BipartiteGraph<ListGraph> Graph; |
86 |
23 |