COIN-OR::LEMON - Graph Library

Changeset 512:d5fe2f3f95fc in lemon-0.x for src/work


Ignore:
Timestamp:
05/03/04 13:43:27 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@672
Message:

bip matching...

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci/bipartite_matching_try_3.cc

    r510 r512  
    4444          typename EdgeFlow, typename NodeFlow>
    4545class MaxMatching {
    46 // : public MaxFlow<stGraphWrapper<Graph>,
    47 //                                 stGraphWrapper<Graph>:: EdgeMapWrapper<EdgeCan, NodeCap>, stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> > {
    48 //   typedef MaxFlow<stGraphWrapper<Graph>,
    49 //                stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCan, NodeCap>,
    50 //                stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> >
    51 //   Parent;
    5246protected:
    5347//   EdgeCap* edge_cap;
     
    5953  typedef typename stGW::template EdgeMapWrapper<EdgeCap, NodeCap> CapMap;
    6054  CapMap cap;
     55  NodeFlow* node_flow;
    6156  typedef typename stGW::template EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap;
    6257  FlowMap flow;
     
    6964              EdgeFlow& _edge_flow, NodeFlow& _node_flow) :
    7065    stgw(_g),
    71     cap(_edge_cap, _node_cap), flow(_edge_flow, _node_flow),
     66    cap(_edge_cap, _node_cap),
     67    node_flow(0),
     68    flow(_edge_flow, _node_flow),
    7269    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; }
    7378  void run() { mf.run(); }
    7479  int matchingValue() { return mf.flowValue(); }
     
    131136  }
    132137
    133   std::cout << "Edges of the bipartite graph:" << std::endl;
    134   FOR_EACH_LOC(EdgeIt, e, g) std::cout << e << " ";
    135   std::cout << std::endl;
    136 
    137   std::cout << "Nodes:" << std::endl;
    138   FOR_EACH_LOC(Graph::NodeIt, v, g) std::cout << v << " ";
    139   std::cout << std::endl;
    140   std::cout << "Nodes in T:" << std::endl;
    141   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
    142   std::cout << std::endl;
    143   std::cout << "Nodes in S:" << std::endl;
    144   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
    145   std::cout << std::endl;
    146 
    147   std::cout << "Erasing the first node..." << std::endl;
    148   NodeIt n;
    149   g.first(n);
    150   g.erase(n);
    151   std::cout << "Nodes of the bipartite graph:" << std::endl;
    152   FOR_EACH_GLOB(n, g) std::cout << n << " ";
    153   std::cout << std::endl;
    154 
    155   std::cout << "Nodes in T:" << std::endl;
    156   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
    157   std::cout << std::endl;
    158   std::cout << "Nodes in S:" << std::endl;
    159   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
    160   std::cout << std::endl;
     138//   std::cout << "Edges of the bipartite graph:" << std::endl;
     139//   FOR_EACH_LOC(EdgeIt, e, g) std::cout << e << " ";
     140//   std::cout << std::endl;
     141
     142//   std::cout << "Nodes:" << std::endl;
     143//   FOR_EACH_LOC(Graph::NodeIt, v, g) std::cout << v << " ";
     144//   std::cout << std::endl;
     145//   std::cout << "Nodes in T:" << std::endl;
     146//   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
     147//   std::cout << std::endl;
     148//   std::cout << "Nodes in S:" << std::endl;
     149//   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
     150//   std::cout << std::endl;
     151
     152//   std::cout << "Erasing the first node..." << std::endl;
     153//   NodeIt n;
     154//   g.first(n);
     155//   g.erase(n);
     156//   std::cout << "Nodes of the bipartite graph:" << std::endl;
     157//   FOR_EACH_GLOB(n, g) std::cout << n << " ";
     158//   std::cout << std::endl;
     159
     160//   std::cout << "Nodes in T:" << std::endl;
     161//   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
     162//   std::cout << std::endl;
     163//   std::cout << "Nodes in S:" << std::endl;
     164//   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
     165//   std::cout << std::endl;
    161166
    162167  typedef stGraphWrapper<Graph> stGW;
     
    178183  std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl;
    179184  std::cout << "elapsed time: " << ts << std::endl;
    180   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
    181     if (flow[e]) std::cout << e << std::endl;
    182   }
     185//   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
     186//     if (flow[e]) std::cout << e << std::endl;
     187//   }
    183188  std::cout << std::endl;
    184189
     
    230235//   }
    231236  std::cout << std::endl;
     237
     238  ts.reset();
     239  FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0);
     240  //FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0);
     241  MaxMatching<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>,
     242    Graph::EdgeMap<int>, Graph::NodeMap<int> >
     243    matching_test_1(g, ge1, gn1, gef/*, gnf*/);
     244  matching_test_1.run();
     245
     246  std::cout << "max flow value: " << matching_test_1.matchingValue() << std::endl;
     247  std::cout << "elapsed time: " << ts << std::endl;
     248//   FOR_EACH_LOC(Graph::EdgeIt, e, g) {
     249//     if (gef[e]) std::cout << e << std::endl;
     250//   }
     251  std::cout << std::endl;
     252
    232253  return 0;
    233254}
Note: See TracChangeset for help on using the changeset viewer.