COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 559:82a8f2bc5758 in lemon-0.x for src/work/marci


Ignore:
Timestamp:
05/06/04 19:45:12 (21 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@732
Message:

A max bipartite matching class in src/work/marci/max_bipartite_matching.h
which can be used for computing maximum cardinality ordinary matching, b-matching and capacitated b-matching.

Location:
src/work/marci
Files:
1 edited
1 copied

Legend:

Unmodified
Added
Removed

  • src/work/marci/bipartite_matching_try_3.cc

    r558 r559  
    1414#include <max_flow.h>
    1515#include <graph_gen.h>
     16#include <max_bipartite_matching.h>
    1617
    1718using 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 
    8219
    8320int main() {

  • src/work/marci/max_bipartite_matching.h

    r558 r559  
    11// -*- c++ -*-
    2 #include <iostream>
    3 #include <fstream>
    4 #include <vector>
     2#ifndef HUGO_MAX_BIPARTITE_MATCHING_H
     3#define HUGO_MAX_BIPARTITE_MATCHING_H
    54
    6 #include <list_graph.h>
    7 //#include <smart_graph.h>
    8 //#include <dimacs.h>
    9 #include <hugo/time_measure.h>
    10 #include <for_each_macros.h>
    11 #include <bfs_iterator.h>
     5//#include <for_each_macros.h>
    126#include <bipartite_graph_wrapper.h>
    13 #include <hugo/maps.h>
     7//#include <hugo/maps.h>
    148#include <max_flow.h>
    15 #include <graph_gen.h>
    169
    17 using namespace hugo;
     10namespace hugo {
    1811
    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 // };
     12  // template <typename Graph, typename EdgeCap, typename NodeCap,
     13  //      typename EdgeFlow, typename NodeFlow>
     14  // class MaxMatching : public MaxFlow<stGraphWrapper<Graph>,
     15  //                               stGraphWrapper<Graph>:: EdgeMapWrapper<EdgeCan, NodeCap>, stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > {
     16  //   typedef MaxFlow<stGraphWrapper<Graph>,
     17  //              stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCan, NodeCap>,
     18  //              stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> >
     19  //   Parent;
     20  // protected:
     21  //   stGraphWrapper<Graph> gw;
     22  //   stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCap, NodeCap> cap;
     23  //   stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> flow;
     24  //   //graph* g;
     25  //   //EdgeCap* edge_cap;
     26  //   //EdgeFlow* edge_flow;
     27  // public:
     28  //   MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
     29  //          EdgeFlow& _edge_flow, NodeFlow& _node_flow) :
     30  //     MaxFlow(), gw(_g),
     31  //     cap(_edge_cap, _node_cap), flow(_edge_flow, _node_flow) {
     32  //     Parent::set(gw, cap, flow);
     33  //   }
     34  // };
    4235
    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 };
     36  /// A bipartite matching class.
     37  /// This class reduces the matching problem to a flow problem and
     38  /// a preflow is used on a wrapper. Such a generic approach means that
     39  /// matchings, b-matchings an capacitated b-matchings can be handled in
     40  /// a similar way. Due to the efficiency of the preflow algorithm, an
     41  /// efficient matching framework is obtained.
     42  template <typename Graph, typename EdgeCap, typename NodeCap,
     43            typename EdgeFlow, typename NodeFlow>
     44  class MaxMatching {
     45  protected:
     46    //   EdgeCap* edge_cap;
     47    //   NodeCap* node_cap;
     48    //   EdgeFlow* edge_flow;
     49    //   NodeFlow* node_flow;
     50    typedef  stGraphWrapper<Graph> stGW;
     51    stGW stgw;
     52    typedef typename stGW::template EdgeMapWrapper<EdgeCap, NodeCap> CapMap;
     53    CapMap cap;
     54    NodeFlow* node_flow;
     55    typedef typename stGW::template EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap;
     56    FlowMap flow;
     57    MaxFlow<stGW, int, CapMap, FlowMap> mf;
     58    //graph* g;
     59    //EdgeCap* edge_cap;
     60    //EdgeFlow* edge_flow;
     61  public:
     62    /// For capacitated b-matchings, edge-caoacities and node-capacities
     63    /// have to be given. After running \c run the matching is is given
     64    /// back in the edge-map \c _edge_flow and \c _node_map can be used
     65    /// to obtain saturation information about nodes.
     66    ///\bug Note that the values in _edge_flow and _node_flow have
     67    /// to form a flow.
     68    MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
     69                EdgeFlow& _edge_flow, NodeFlow& _node_flow) :
     70      stgw(_g),
     71      cap(_edge_cap, _node_cap),
     72      node_flow(0),
     73      flow(_edge_flow, _node_flow),
     74      mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { }
     75    /// If the saturation information of nodes is not needed that the use of
     76    /// this constructor is more comfortable.
     77    ///\bug Note that the values in _edge_flow and _node_flow have
     78    /// to form a flow.
     79    MaxMatching(Graph& _g, EdgeCap& _edge_cap, NodeCap& _node_cap,
     80                EdgeFlow& _edge_flow/*, NodeFlow& _node_flow*/) :
     81      stgw(_g),
     82      cap(_edge_cap, _node_cap),
     83      node_flow(new NodeFlow(_g)),
     84      flow(_edge_flow, *node_flow),
     85      mf(stgw, stgw.S_NODE, stgw.T_NODE, cap, flow) { }
     86    /// The class have a nontrivial destructor.
     87    ~MaxMatching() { if (node_flow) delete node_flow; }
     88    /// run computes the max matching.
     89    void run() { mf.run(); }
     90    /// The matching value after running \c run.
     91    int matchingValue() { return mf.flowValue(); }
     92  };
    8193
     94} //namespace hugo
    8295
    83 int main() {
    84   //typedef UndirListGraph Graph;
    85   typedef BipartiteGraph<ListGraph> Graph;
    86  
    87   typedef Graph::Node Node;
    88   typedef Graph::NodeIt NodeIt;
    89   typedef Graph::Edge Edge;
    90   typedef Graph::EdgeIt EdgeIt;
    91   typedef Graph::OutEdgeIt OutEdgeIt;
    92 
    93   Graph g;
    94 
    95   int a;
    96   std::cout << "number of nodes in the first color class=";
    97   std::cin >> a;
    98   int b;
    99   std::cout << "number of nodes in the second color class=";
    100   std::cin >> b;
    101   int m;
    102   std::cout << "number of edges=";
    103   std::cin >> m;
    104  
    105   std::cout << "Generatig a random bipartite graph..." << std::endl;
    106   random_init();
    107   randomBipartiteGraph(g, a, b, m);
    108 
    109 //   std::cout << "Edges of the bipartite graph:" << std::endl;
    110 //   FOR_EACH_LOC(EdgeIt, e, g) std::cout << e << " ";
    111 //   std::cout << std::endl;
    112 
    113 //   std::cout << "Nodes:" << std::endl;
    114 //   FOR_EACH_LOC(Graph::NodeIt, v, g) std::cout << v << " ";
    115 //   std::cout << std::endl;
    116 //   std::cout << "Nodes in T:" << std::endl;
    117 //   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
    118 //   std::cout << std::endl;
    119 //   std::cout << "Nodes in S:" << std::endl;
    120 //   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
    121 //   std::cout << std::endl;
    122 
    123 //   std::cout << "Erasing the first node..." << std::endl;
    124 //   NodeIt n;
    125 //   g.first(n);
    126 //   g.erase(n);
    127 //   std::cout << "Nodes of the bipartite graph:" << std::endl;
    128 //   FOR_EACH_GLOB(n, g) std::cout << n << " ";
    129 //   std::cout << std::endl;
    130 
    131 //   std::cout << "Nodes in T:" << std::endl;
    132 //   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
    133 //   std::cout << std::endl;
    134 //   std::cout << "Nodes in S:" << std::endl;
    135 //   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
    136 //   std::cout << std::endl;
    137 
    138   typedef stGraphWrapper<Graph> stGW;
    139   stGW stgw(g);
    140   ConstMap<stGW::Edge, int> const1map(1);
    141 
    142   Timer ts;
    143   ts.reset();
    144   stGW::EdgeMap<int> flow(stgw);
    145   MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
    146     max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
    147   max_flow_test.run();
    148 //  while (max_flow_test.augmentOnShortestPath()) { }
    149 //  typedef ListGraph MutableGraph;
    150 //  while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
    151 //  while (max_flow_test.augmentOnBlockingFlow2()) {
    152 //   std::cout << max_flow_test.flowValue() << std::endl;
    153 //  }
    154   std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl;
    155   std::cout << "elapsed time: " << ts << std::endl;
    156 //   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
    157 //     if (flow[e]) std::cout << e << std::endl;
    158 //   }
    159   std::cout << std::endl;
    160 
    161   typedef ConstMap<Graph::Edge, int> EdgeCap;
    162   EdgeCap ge1(1);
    163   typedef ConstMap<Graph::Node, int> NodeCap;
    164   NodeCap gn1(1);
    165   typedef Graph::EdgeMap<int> EdgeFlow;
    166   EdgeFlow gef(g); //0
    167   typedef Graph::NodeMap<int> NodeFlow;
    168   NodeFlow gnf(g); //0
    169 
    170   typedef stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCap, NodeCap> CapMap;
    171   typedef stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap;
    172   CapMap cm(ge1, gn1);
    173   FlowMap fm(gef, gnf);
    174 
    175   //Timer ts;
    176   ts.reset();
    177   //stGW::EdgeMap<int> flow(stgw);
    178   MaxFlow<stGW, int, CapMap, FlowMap>
    179     max_flow_test1(stgw, stgw.S_NODE, stgw.T_NODE, cm, fm);
    180   max_flow_test1.run();
    181 //  while (max_flow_test.augmentOnShortestPath()) { }
    182 //  typedef ListGraph MutableGraph;
    183 //  while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
    184 //  while (max_flow_test.augmentOnBlockingFlow2()) {
    185 //   std::cout << max_flow_test.flowValue() << std::endl;
    186 //  }
    187   std::cout << "max flow value: " << max_flow_test1.flowValue() << std::endl;
    188   std::cout << "elapsed time: " << ts << std::endl;
    189 //   FOR_EACH_LOC(Graph::EdgeIt, e, g) {
    190 //     if (gef[e]) std::cout << e << std::endl;
    191 //   }
    192   std::cout << std::endl;
    193 
    194   ts.reset();
    195   FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0);
    196   FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0);
    197   MaxMatching<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>,
    198     Graph::EdgeMap<int>, Graph::NodeMap<int> >
    199     matching_test(g, ge1, gn1, gef, gnf);
    200   matching_test.run();
    201 
    202   std::cout << "max flow value: " << matching_test.matchingValue() << std::endl;
    203   std::cout << "elapsed time: " << ts << std::endl;
    204 //   FOR_EACH_LOC(Graph::EdgeIt, e, g) {
    205 //     if (gef[e]) std::cout << e << std::endl;
    206 //   }
    207   std::cout << std::endl;
    208 
    209   ts.reset();
    210   FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0);
    211   //FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0);
    212   MaxMatching<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>,
    213     Graph::EdgeMap<int>, Graph::NodeMap<int> >
    214     matching_test_1(g, ge1, gn1, gef/*, gnf*/);
    215   matching_test_1.run();
    216 
    217   std::cout << "max flow value: " << matching_test_1.matchingValue() << std::endl;
    218   std::cout << "elapsed time: " << ts << std::endl;
    219 //   FOR_EACH_LOC(Graph::EdgeIt, e, g) {
    220 //     if (gef[e]) std::cout << e << std::endl;
    221 //   }
    222   std::cout << std::endl;
    223 
    224   return 0;
    225 }
     96#endif //HUGO_MAX_BIPARTITE_MATCHING_H
Note: See TracChangeset for help on using the changeset viewer.