1 // -*- c++ -*- |
|
2 #ifndef LEMON_MAX_BIPARTITE_MATCHING_H |
|
3 #define LEMON_MAX_BIPARTITE_MATCHING_H |
|
4 |
|
5 /// \ingroup galgs |
|
6 /// \file |
|
7 /// \brief Maximum bipartite matchings, b-matchings and |
|
8 /// capacitated b-matchings. |
|
9 /// |
|
10 /// This file contains a class for bipartite maximum matching, b-matchings |
|
11 /// and capacitated b-matching computations. |
|
12 /// |
|
13 // /// \author Marton Makai |
|
14 |
|
15 //#include <for_each_macros.h> |
|
16 #include <bipartite_graph_wrapper.h> |
|
17 //#include <lemon/maps.h> |
|
18 #include <lemon/max_flow.h> |
|
19 |
|
20 namespace lemon { |
|
21 |
|
22 // template <typename Graph, typename EdgeCap, typename NodeCap, |
|
23 // typename EdgeFlow, typename NodeFlow> |
|
24 // class MaxMatching : public MaxFlow<stGraphWrapper<Graph>, |
|
25 // stGraphWrapper<Graph>:: EdgeMapWrapper<EdgeCan, NodeCap>, stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > { |
|
26 // typedef MaxFlow<stGraphWrapper<Graph>, |
|
27 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCan, NodeCap>, |
|
28 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > |
|
29 // Parent; |
|
30 // protected: |
|
31 // stGraphWrapper<Graph> gw; |
|
32 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCap, NodeCap> cap; |
|
33 // stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> flow; |
|
34 // //graph* g; |
|
35 // //EdgeCap* edge_cap; |
|
36 // //EdgeFlow* edge_flow; |
|
37 // public: |
|
38 // MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, |
|
39 // EdgeFlow& _edge_flow, NodeFlow& _node_flow) : |
|
40 // MaxFlow(), gw(_g), |
|
41 // cap(_edge_cap, _node_cap), flow(_edge_flow, _node_flow) { |
|
42 // Parent::set(gw, cap, flow); |
|
43 // } |
|
44 // }; |
|
45 |
|
46 /// \brief A bipartite matching class. |
|
47 /// |
|
48 /// This class reduces the matching problem to a flow problem and |
|
49 /// a preflow is used on a wrapper. Such a generic approach means that |
|
50 /// matchings, b-matchings an capacitated b-matchings can be handled in |
|
51 /// a similar way. Due to the efficiency of the preflow algorithm, an |
|
52 /// efficient matching framework is obtained. |
|
53 /// \ingroup galgs |
|
54 template <typename Graph, typename EdgeCap, typename NodeCap, |
|
55 typename EdgeFlow, typename NodeFlow> |
|
56 class MaxBipartiteMatching { |
|
57 protected: |
|
58 // EdgeCap* edge_cap; |
|
59 // NodeCap* node_cap; |
|
60 // EdgeFlow* edge_flow; |
|
61 // NodeFlow* node_flow; |
|
62 typedef stBipartiteGraphWrapper<Graph> stGW; |
|
63 stGW stgw; |
|
64 typedef typename stGW::template EdgeMapWrapper<EdgeCap, NodeCap> CapMap; |
|
65 CapMap cap; |
|
66 NodeFlow* node_flow; |
|
67 typedef typename stGW::template EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap; |
|
68 FlowMap flow; |
|
69 typedef MaxFlow<stGW, int, CapMap, FlowMap> MaxFlow; |
|
70 MaxFlow mf; |
|
71 //graph* g; |
|
72 //EdgeCap* edge_cap; |
|
73 //EdgeFlow* edge_flow; |
|
74 public: |
|
75 enum MatchingEnum{ |
|
76 ZERO_MATCHING, |
|
77 GEN_MATCHING, |
|
78 GEN_MATCHING_WITH_GOOD_NODE_FLOW, |
|
79 NO_MATCHING |
|
80 }; |
|
81 /// For capacitated b-matchings, edge-caoacities and node-capacities |
|
82 /// have to be given. After running \c run the matching is is given |
|
83 /// back in the edge-map \c _edge_flow and \c _node_map can be used |
|
84 /// to obtain saturation information about nodes. |
|
85 ///\bug Note that the values in _edge_flow and _node_flow have |
|
86 /// to form a flow. |
|
87 MaxBipartiteMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, |
|
88 EdgeFlow& _edge_flow, NodeFlow& _node_flow) : |
|
89 stgw(_g), |
|
90 cap(_edge_cap, _node_cap), |
|
91 node_flow(0), |
|
92 flow(_edge_flow, _node_flow), |
|
93 mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { } |
|
94 /// If the saturation information of nodes is not needed that the use of |
|
95 /// this constructor is more comfortable. |
|
96 ///\bug Note that the values in _edge_flow and _node_flow have |
|
97 /// to form a flow. |
|
98 MaxBipartiteMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, |
|
99 EdgeFlow& _edge_flow/*, NodeFlow& _node_flow*/) : |
|
100 stgw(_g), |
|
101 cap(_edge_cap, _node_cap), |
|
102 node_flow(new NodeFlow(_g)), |
|
103 flow(_edge_flow, *node_flow), |
|
104 mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { } |
|
105 /// The class have a nontrivial destructor. |
|
106 ~MaxBipartiteMatching() { if (node_flow) delete node_flow; } |
|
107 /// run computes the max matching. |
|
108 void run(MatchingEnum me=ZERO_MATCHING) { |
|
109 switch (me) { |
|
110 case ZERO_MATCHING: |
|
111 mf.run(MaxFlow::ZERO_FLOW); |
|
112 break; |
|
113 case GEN_MATCHING: |
|
114 { |
|
115 typename stGW::OutEdgeIt e; |
|
116 for (stgw.first(e, stgw.S_NODE); stgw.valid(e); stgw.next(e)) |
|
117 flow.set(e, cap[e]); |
|
118 } |
|
119 { |
|
120 typename stGW::InEdgeIt e; |
|
121 for (stgw.first(e, stgw.T_NODE); stgw.valid(e); stgw.next(e)) |
|
122 flow.set(e, 0); |
|
123 } |
|
124 mf.run(MaxFlow::PRE_FLOW); |
|
125 break; |
|
126 case GEN_MATCHING_WITH_GOOD_NODE_FLOW: |
|
127 mf.run(MaxFlow::GEN_FLOW); |
|
128 break; |
|
129 case NO_MATCHING: |
|
130 mf.run(MaxFlow::NO_FLOW); |
|
131 break; |
|
132 } |
|
133 } |
|
134 /// The matching value after running \c run. |
|
135 int matchingValue() const { return mf.flowValue(); } |
|
136 }; |
|
137 |
|
138 } //namespace lemon |
|
139 |
|
140 #endif //LEMON_MAX_BIPARTITE_MATCHING_H |
|