COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/max_bipartite_matching.h @ 1031:0b7169db694f

Last change on this file since 1031:0b7169db694f was 921:818510fa3d99, checked in by Alpar Juttner, 20 years ago

hugo -> lemon

File size: 4.8 KB
Line 
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
20namespace 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
Note: See TracBrowser for help on using the repository browser.