1.1 --- a/src/work/marci/leda/bipartite_matching_leda.cc	Thu Apr 29 16:45:40 2004 +0000
     1.2 +++ b/src/work/marci/leda/bipartite_matching_leda.cc	Thu Apr 29 16:59:00 2004 +0000
     1.3 @@ -18,8 +18,7 @@
     1.4  //#include <bfs_iterator.h>
     1.5  #include <graph_wrapper.h>
     1.6  #include <maps.h>
     1.7 -#include <edmonds_karp.h>
     1.8 -#include <preflow.h>
     1.9 +#include <max_flow.h>
    1.10  
    1.11  /**
    1.12   * Inicializalja a veletlenszamgeneratort.
    1.13 @@ -101,10 +100,12 @@
    1.14    ConstMap<stGW::Edge, int> const1map(1);
    1.15  
    1.16    Timer ts;
    1.17 +  stGW::EdgeMap<int> flow(stgw);
    1.18 +  MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
    1.19 +    max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
    1.20 +
    1.21    ts.reset();
    1.22 -  stGW::EdgeMap<int> max_flow(stgw);
    1.23 -  MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
    1.24 -    max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, max_flow);
    1.25 +  FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
    1.26  //  while (max_flow_test.augmentOnShortestPath()) { }
    1.27    typedef ListGraph MutableGraph;
    1.28  //  while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
    1.29 @@ -113,35 +114,17 @@
    1.30    }
    1.31    std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl;
    1.32    std::cout << "elapsed time: " << ts << std::endl;
    1.33 -//   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { 
    1.34 -//     std::cout << e << ": " << max_flow[e] << "\n"; 
    1.35 -//   }
    1.36 -//   std::cout << "\n";
    1.37  
    1.38    ts.reset();
    1.39 -  stGW::EdgeMap<int> pre_flow(stgw);
    1.40 -  Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
    1.41 -    pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow/*, true*/);
    1.42 -  pre_flow_test.run();
    1.43 +  FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
    1.44 +  max_flow_test.run();
    1.45    std::cout << "pre flow value: " << max_flow_test.flowValue() << std::endl;
    1.46    std::cout << "elapsed time: " << ts << std::endl;
    1.47 -//   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { 
    1.48 -//     std::cout << e << ": " << pre_flow[e] << "\n"; 
    1.49 -//   }
    1.50 -//   std::cout << "\n";
    1.51  
    1.52    ts.reset();  
    1.53    leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg);
    1.54 -  //  stGW::EdgeMap<int> pre_flow(stgw);
    1.55 -  //Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
    1.56 -  //  pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow, true);
    1.57 -  //pre_flow_test.run();
    1.58    std::cout << "leda matching value: " << ml.size() << std::endl;
    1.59    std::cout << "elapsed time: " << ts << std::endl;
    1.60 -//   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { 
    1.61 -//     std::cout << e << ": " << pre_flow[e] << "\n"; 
    1.62 -//   }
    1.63 -//   std::cout << "\n";
    1.64  
    1.65    return 0;
    1.66  }

     2.1 --- a/src/work/marci/leda/bipartite_matching_leda_gen.cc	Thu Apr 29 16:45:40 2004 +0000
     2.2 +++ b/src/work/marci/leda/bipartite_matching_leda_gen.cc	Thu Apr 29 16:59:00 2004 +0000
     2.3 @@ -15,11 +15,9 @@
     2.4  //#include <dimacs.h>
     2.5  #include <time_measure.h>
     2.6  #include <for_each_macros.h>
     2.7 -//#include <bfs_iterator.h>
     2.8  #include <graph_wrapper.h>
     2.9  #include <maps.h>
    2.10 -#include <edmonds_karp.h>
    2.11 -#include <preflow.h>
    2.12 +#include <max_flow.h>
    2.13  
    2.14  /**
    2.15   * Inicializalja a veletlenszamgeneratort.
    2.16 @@ -78,82 +76,59 @@
    2.17    std::cout << "A bipartite graph is a random group graph if the color classes \nA and B are partitiones to A_0, A_1, ..., A_{k-1} and B_0, B_1, ..., B_{k-1} \nas equally as possible \nand the edges from A_i goes to A_{i-1 mod k} and A_{i+1 mod k}.\n";
    2.18    std::cout << "number of groups in LEDA random group graph=";
    2.19    std::cin >> k; 
    2.20 -
    2.21 +  std::cout << std::endl;
    2.22 +  
    2.23    leda_list<leda_node> lS;
    2.24    leda_list<leda_node> lT;
    2.25    random_bigraph(lg, a, b, m, lS, lT, k);
    2.26  
    2.27 -//   for (int i=0; i<a; ++i) s_nodes.push_back(g.addNode());
    2.28 -//   for (int i=0; i<b; ++i) t_nodes.push_back(g.addNode());
    2.29 +  Graph::NodeMap<int> ref_map(g, -1);
    2.30 +  IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
    2.31  
    2.32 -//   random_init();
    2.33 -//   for(int i=0; i<m; ++i) {
    2.34 -//     g.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
    2.35 -//   }
    2.36 -
    2.37 -  Graph::NodeMap<int> ref_map(g, -1);
    2.38 -
    2.39 -  IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
    2.40 -//   for (int i=0; i<a; ++i) bipartite_map.insert(s_nodes[i], false);
    2.41 -//   for (int i=0; i<b; ++i) bipartite_map.insert(t_nodes[i], true);
    2.42 +  //generating leda random group graph
    2.43    leda_node ln;
    2.44    forall(ln, lS) bipartite_map.insert(ln, false);
    2.45    forall(ln, lT) bipartite_map.insert(ln, true);
    2.46  
    2.47 +  //making bipartite graph
    2.48    typedef BipartiteGraphWrapper<Graph> BGW;
    2.49    BGW bgw(g, bipartite_map);
    2.50  
    2.51 -  //  BGW::NodeMap<int> dbyj(bgw);
    2.52 -  //  BGW::EdgeMap<int> dbyxcj(bgw);
    2.53  
    2.54 +  //st-wrapper
    2.55    typedef stGraphWrapper<BGW> stGW;
    2.56    stGW stgw(bgw);
    2.57    ConstMap<stGW::Edge, int> const1map(1);
    2.58    stGW::EdgeMap<int> flow(stgw);
    2.59  
    2.60    Timer ts;
    2.61 +
    2.62 +  ts.reset();
    2.63    FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
    2.64 -  ts.reset();
    2.65 -  //  stGW::EdgeMap<int> pre_flow(stgw);
    2.66 -  Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
    2.67 -    pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
    2.68 -  pre_flow_test.run();
    2.69 -  std::cout << "HUGO pre flow value: " << pre_flow_test.flowValue() << std::endl;
    2.70 -  std::cout << "elapsed time: " << ts << std::endl;
    2.71 -//   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { 
    2.72 -//     std::cout << e << ": " << pre_flow[e] << "\n"; 
    2.73 -//   }
    2.74 -  std::cout << "\n";
    2.75 +  MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
    2.76 +    max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
    2.77 +  max_flow_test.run();
    2.78 +  std::cout << "HUGO max matching algorithm based on preflow." << std::endl 
    2.79 +	    << "Size of matching: " 
    2.80 +	    << max_flow_test.flowValue() << std::endl;
    2.81 +  std::cout << "elapsed time: " << ts << std::endl << std::endl;
    2.82  
    2.83    ts.reset();  
    2.84    leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg);
    2.85 -  //  stGW::EdgeMap<int> pre_flow(stgw);
    2.86 -  //Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
    2.87 -  //  pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow, true);
    2.88 -  //pre_flow_test.run();
    2.89 -  std::cout << "LEDA matching value: " << ml.size() << std::endl;
    2.90 +  std::cout << "LEDA max matching algorithm." << std::endl 
    2.91 +	    << "Size of matching: " 
    2.92 +	    << ml.size() << std::endl;
    2.93    std::cout << "elapsed time: " << ts << std::endl;
    2.94 -//   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { 
    2.95 -//     std::cout << e << ": " << pre_flow[e] << "\n"; 
    2.96 -//   }
    2.97    std::cout << "\n";
    2.98  
    2.99 +  ts.reset();
   2.100    FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
   2.101 -  ts.reset();
   2.102 -  MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
   2.103 -    max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
   2.104 -//  while (max_flow_test.augmentOnShortestPath()) { }
   2.105    typedef ListGraph MutableGraph;
   2.106 -//  while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
   2.107 -  while (max_flow_test.augmentOnBlockingFlow2()) {
   2.108 -   std::cout << max_flow_test.flowValue() << std::endl;
   2.109 -  }
   2.110 -  std::cout << "HUGO blocking flow value: " << max_flow_test.flowValue() << std::endl;
   2.111 +  while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { }
   2.112 +  std::cout << "HUGO max matching algorithm based on blocking flow augmentation." 
   2.113 +	    << std::endl << "Matching size: " 
   2.114 +	    << max_flow_test.flowValue() << std::endl;
   2.115    std::cout << "elapsed time: " << ts << std::endl;
   2.116 -//   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { 
   2.117 -//     std::cout << e << ": " << max_flow[e] << "\n"; 
   2.118 -//   }
   2.119 -//   std::cout << "\n";
   2.120  
   2.121    return 0;
   2.122  }

     3.1 --- a/src/work/marci/leda/leda_graph_wrapper.h	Thu Apr 29 16:45:40 2004 +0000
     3.2 +++ b/src/work/marci/leda/leda_graph_wrapper.h	Thu Apr 29 16:59:00 2004 +0000
     3.3 @@ -46,7 +46,7 @@
     3.4    protected:
     3.5      Graph* _graph;
     3.6      LedaGraphWrapper() : _graph(0) { }
     3.7 -    setGraph(Graph& __graph) { _graph=&__graph; }
     3.8 +    void setGraph(Graph& __graph) { _graph=&__graph; }
     3.9    public:
    3.10     
    3.11          //LedaGraphWrapper() { }