COIN-OR::LEMON - Graph Library

Changeset 482:dce64ce044d6 in lemon-0.x


Ignore:
Timestamp:
04/29/04 18:59:00 (16 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@639
Message:

corrections for leda matching files

Location:
src/work/marci/leda
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci/leda/bipartite_matching_leda.cc

    r459 r482  
    1919#include <graph_wrapper.h>
    2020#include <maps.h>
    21 #include <edmonds_karp.h>
    22 #include <preflow.h>
     21#include <max_flow.h>
    2322
    2423/**
     
    102101
    103102  Timer ts;
     103  stGW::EdgeMap<int> flow(stgw);
     104  MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
     105    max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
     106
    104107  ts.reset();
    105   stGW::EdgeMap<int> max_flow(stgw);
    106   MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
    107     max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, max_flow);
     108  FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
    108109//  while (max_flow_test.augmentOnShortestPath()) { }
    109110  typedef ListGraph MutableGraph;
     
    114115  std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl;
    115116  std::cout << "elapsed time: " << ts << std::endl;
    116 //   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
    117 //     std::cout << e << ": " << max_flow[e] << "\n";
    118 //   }
    119 //   std::cout << "\n";
    120117
    121118  ts.reset();
    122   stGW::EdgeMap<int> pre_flow(stgw);
    123   Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
    124     pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow/*, true*/);
    125   pre_flow_test.run();
     119  FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
     120  max_flow_test.run();
    126121  std::cout << "pre flow value: " << max_flow_test.flowValue() << std::endl;
    127122  std::cout << "elapsed time: " << ts << std::endl;
    128 //   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
    129 //     std::cout << e << ": " << pre_flow[e] << "\n";
    130 //   }
    131 //   std::cout << "\n";
    132123
    133124  ts.reset(); 
    134125  leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg);
    135   //  stGW::EdgeMap<int> pre_flow(stgw);
    136   //Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
    137   //  pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow, true);
    138   //pre_flow_test.run();
    139126  std::cout << "leda matching value: " << ml.size() << std::endl;
    140127  std::cout << "elapsed time: " << ts << std::endl;
    141 //   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
    142 //     std::cout << e << ": " << pre_flow[e] << "\n";
    143 //   }
    144 //   std::cout << "\n";
    145128
    146129  return 0;
  • src/work/marci/leda/bipartite_matching_leda_gen.cc

    r459 r482  
    1616#include <time_measure.h>
    1717#include <for_each_macros.h>
    18 //#include <bfs_iterator.h>
    1918#include <graph_wrapper.h>
    2019#include <maps.h>
    21 #include <edmonds_karp.h>
    22 #include <preflow.h>
     20#include <max_flow.h>
    2321
    2422/**
     
    7977  std::cout << "number of groups in LEDA random group graph=";
    8078  std::cin >> k;
    81 
     79  std::cout << std::endl;
     80 
    8281  leda_list<leda_node> lS;
    8382  leda_list<leda_node> lT;
    8483  random_bigraph(lg, a, b, m, lS, lT, k);
    8584
    86 //   for (int i=0; i<a; ++i) s_nodes.push_back(g.addNode());
    87 //   for (int i=0; i<b; ++i) t_nodes.push_back(g.addNode());
     85  Graph::NodeMap<int> ref_map(g, -1);
     86  IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
    8887
    89 //   random_init();
    90 //   for(int i=0; i<m; ++i) {
    91 //     g.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
    92 //   }
    93 
    94   Graph::NodeMap<int> ref_map(g, -1);
    95 
    96   IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
    97 //   for (int i=0; i<a; ++i) bipartite_map.insert(s_nodes[i], false);
    98 //   for (int i=0; i<b; ++i) bipartite_map.insert(t_nodes[i], true);
     88  //generating leda random group graph
    9989  leda_node ln;
    10090  forall(ln, lS) bipartite_map.insert(ln, false);
    10191  forall(ln, lT) bipartite_map.insert(ln, true);
    10292
     93  //making bipartite graph
    10394  typedef BipartiteGraphWrapper<Graph> BGW;
    10495  BGW bgw(g, bipartite_map);
    10596
    106   //  BGW::NodeMap<int> dbyj(bgw);
    107   //  BGW::EdgeMap<int> dbyxcj(bgw);
    10897
     98  //st-wrapper
    10999  typedef stGraphWrapper<BGW> stGW;
    110100  stGW stgw(bgw);
     
    113103
    114104  Timer ts;
     105
     106  ts.reset();
    115107  FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
    116   ts.reset();
    117   //  stGW::EdgeMap<int> pre_flow(stgw);
    118   Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
    119     pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
    120   pre_flow_test.run();
    121   std::cout << "HUGO pre flow value: " << pre_flow_test.flowValue() << std::endl;
    122   std::cout << "elapsed time: " << ts << std::endl;
    123 //   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
    124 //     std::cout << e << ": " << pre_flow[e] << "\n";
    125 //   }
    126   std::cout << "\n";
     108  MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
     109    max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
     110  max_flow_test.run();
     111  std::cout << "HUGO max matching algorithm based on preflow." << std::endl
     112            << "Size of matching: "
     113            << max_flow_test.flowValue() << std::endl;
     114  std::cout << "elapsed time: " << ts << std::endl << std::endl;
    127115
    128116  ts.reset(); 
    129117  leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg);
    130   //  stGW::EdgeMap<int> pre_flow(stgw);
    131   //Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
    132   //  pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow, true);
    133   //pre_flow_test.run();
    134   std::cout << "LEDA matching value: " << ml.size() << std::endl;
     118  std::cout << "LEDA max matching algorithm." << std::endl
     119            << "Size of matching: "
     120            << ml.size() << std::endl;
    135121  std::cout << "elapsed time: " << ts << std::endl;
    136 //   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
    137 //     std::cout << e << ": " << pre_flow[e] << "\n";
    138 //   }
    139122  std::cout << "\n";
    140123
     124  ts.reset();
    141125  FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
    142   ts.reset();
    143   MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
    144     max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
    145 //  while (max_flow_test.augmentOnShortestPath()) { }
    146126  typedef ListGraph MutableGraph;
    147 //  while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
    148   while (max_flow_test.augmentOnBlockingFlow2()) {
    149    std::cout << max_flow_test.flowValue() << std::endl;
    150   }
    151   std::cout << "HUGO blocking flow value: " << max_flow_test.flowValue() << std::endl;
     127  while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { }
     128  std::cout << "HUGO max matching algorithm based on blocking flow augmentation."
     129            << std::endl << "Matching size: "
     130            << max_flow_test.flowValue() << std::endl;
    152131  std::cout << "elapsed time: " << ts << std::endl;
    153 //   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
    154 //     std::cout << e << ": " << max_flow[e] << "\n";
    155 //   }
    156 //   std::cout << "\n";
    157132
    158133  return 0;
  • src/work/marci/leda/leda_graph_wrapper.h

    r473 r482  
    4747    Graph* _graph;
    4848    LedaGraphWrapper() : _graph(0) { }
    49     setGraph(Graph& __graph) { _graph=&__graph; }
     49    void setGraph(Graph& __graph) { _graph=&__graph; }
    5050  public:
    5151   
Note: See TracChangeset for help on using the changeset viewer.