COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/max_bipartite_matching.h @ 615:b6b31b75b522

Last change on this file since 615:b6b31b75b522 was 615:b6b31b75b522, checked in by marci, 20 years ago

docs, max_flow improvments

File size: 4.1 KB
Line 
1// -*- c++ -*-
2#ifndef HUGO_MAX_BIPARTITE_MATCHING_H
3#define HUGO_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 <hugo/maps.h>
18#include <max_flow.h>
19
20namespace hugo {
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  stGraphWrapper<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    MaxFlow<stGW, int, CapMap, FlowMap> mf;
70    //graph* g;
71    //EdgeCap* edge_cap;
72    //EdgeFlow* edge_flow;
73  public:
74    /// For capacitated b-matchings, edge-caoacities and node-capacities
75    /// have to be given. After running \c run the matching is is given
76    /// back in the edge-map \c _edge_flow and \c _node_map can be used
77    /// to obtain saturation information about nodes.
78    ///\bug Note that the values in _edge_flow and _node_flow have
79    /// to form a flow.
80    MaxBipartiteMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
81                EdgeFlow& _edge_flow, NodeFlow& _node_flow) :
82      stgw(_g),
83      cap(_edge_cap, _node_cap),
84      node_flow(0),
85      flow(_edge_flow, _node_flow),
86      mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { }
87    /// If the saturation information of nodes is not needed that the use of
88    /// this constructor is more comfortable.
89    ///\bug Note that the values in _edge_flow and _node_flow have
90    /// to form a flow.
91    MaxBipartiteMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
92                EdgeFlow& _edge_flow/*, NodeFlow& _node_flow*/) :
93      stgw(_g),
94      cap(_edge_cap, _node_cap),
95      node_flow(new NodeFlow(_g)),
96      flow(_edge_flow, *node_flow),
97      mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { }
98    /// The class have a nontrivial destructor.
99    ~MaxBipartiteMatching() { if (node_flow) delete node_flow; }
100    /// run computes the max matching.
101    void run() { mf.run(); }
102    /// The matching value after running \c run.
103    int matchingValue() { return mf.flowValue(); }
104  };
105
106} //namespace hugo
107
108#endif //HUGO_MAX_BIPARTITE_MATCHING_H
Note: See TracBrowser for help on using the repository browser.