[510] | 1 | // -*- c++ -*- |
---|
[559] | 2 | #ifndef HUGO_MAX_BIPARTITE_MATCHING_H |
---|
| 3 | #define HUGO_MAX_BIPARTITE_MATCHING_H |
---|
[510] | 4 | |
---|
[615] | 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 | |
---|
[559] | 15 | //#include <for_each_macros.h> |
---|
[510] | 16 | #include <bipartite_graph_wrapper.h> |
---|
[559] | 17 | //#include <hugo/maps.h> |
---|
[762] | 18 | #include <hugo/max_flow.h> |
---|
[510] | 19 | |
---|
[559] | 20 | namespace hugo { |
---|
[510] | 21 | |
---|
[559] | 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 | // }; |
---|
[510] | 45 | |
---|
[613] | 46 | /// \brief A bipartite matching class. |
---|
| 47 | /// |
---|
[559] | 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. |
---|
[613] | 53 | /// \ingroup galgs |
---|
[559] | 54 | template <typename Graph, typename EdgeCap, typename NodeCap, |
---|
| 55 | typename EdgeFlow, typename NodeFlow> |
---|
[613] | 56 | class MaxBipartiteMatching { |
---|
[559] | 57 | protected: |
---|
| 58 | // EdgeCap* edge_cap; |
---|
| 59 | // NodeCap* node_cap; |
---|
| 60 | // EdgeFlow* edge_flow; |
---|
| 61 | // NodeFlow* node_flow; |
---|
[768] | 62 | typedef stBipartiteGraphWrapper<Graph> stGW; |
---|
[559] | 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; |
---|
[768] | 69 | typedef MaxFlow<stGW, int, CapMap, FlowMap> MaxFlow; |
---|
| 70 | MaxFlow mf; |
---|
[559] | 71 | //graph* g; |
---|
| 72 | //EdgeCap* edge_cap; |
---|
| 73 | //EdgeFlow* edge_flow; |
---|
| 74 | public: |
---|
[768] | 75 | enum MatchingEnum{ |
---|
| 76 | ZERO_MATCHING, |
---|
| 77 | GEN_MATCHING, |
---|
| 78 | GEN_MATCHING_WITH_GOOD_NODE_FLOW, |
---|
| 79 | NO_MATCHING |
---|
| 80 | }; |
---|
[559] | 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. |
---|
[613] | 87 | MaxBipartiteMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, |
---|
[559] | 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. |
---|
[613] | 98 | MaxBipartiteMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap, |
---|
[559] | 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. |
---|
[613] | 106 | ~MaxBipartiteMatching() { if (node_flow) delete node_flow; } |
---|
[559] | 107 | /// run computes the max matching. |
---|
[768] | 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 | } |
---|
[559] | 134 | /// The matching value after running \c run. |
---|
[768] | 135 | int matchingValue() const { return mf.flowValue(); } |
---|
[559] | 136 | }; |
---|
[510] | 137 | |
---|
[559] | 138 | } //namespace hugo |
---|
[510] | 139 | |
---|
[559] | 140 | #endif //HUGO_MAX_BIPARTITE_MATCHING_H |
---|