COIN-OR::LEMON - Graph Library

Ignore:
Timestamp:
05/06/04 19:45:12 (16 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.

File:
1 edited

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() {
Note: See TracChangeset for help on using the changeset viewer.