1.1 --- a/src/work/marci/leda/bipartite_matching_leda_gen.cc	Thu Apr 29 16:45:40 2004 +0000
     1.2 +++ b/src/work/marci/leda/bipartite_matching_leda_gen.cc	Thu Apr 29 16:59:00 2004 +0000
     1.3 @@ -15,11 +15,9 @@
     1.4  //#include <dimacs.h>
     1.5  #include <time_measure.h>
     1.6  #include <for_each_macros.h>
     1.7 -//#include <bfs_iterator.h>
     1.8  #include <graph_wrapper.h>
     1.9  #include <maps.h>
    1.10 -#include <edmonds_karp.h>
    1.11 -#include <preflow.h>
    1.12 +#include <max_flow.h>
    1.13  
    1.14  /**
    1.15   * Inicializalja a veletlenszamgeneratort.
    1.16 @@ -78,82 +76,59 @@
    1.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";
    1.18    std::cout << "number of groups in LEDA random group graph=";
    1.19    std::cin >> k; 
    1.20 -
    1.21 +  std::cout << std::endl;
    1.22 +  
    1.23    leda_list<leda_node> lS;
    1.24    leda_list<leda_node> lT;
    1.25    random_bigraph(lg, a, b, m, lS, lT, k);
    1.26  
    1.27 -//   for (int i=0; i<a; ++i) s_nodes.push_back(g.addNode());
    1.28 -//   for (int i=0; i<b; ++i) t_nodes.push_back(g.addNode());
    1.29 +  Graph::NodeMap<int> ref_map(g, -1);
    1.30 +  IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
    1.31  
    1.32 -//   random_init();
    1.33 -//   for(int i=0; i<m; ++i) {
    1.34 -//     g.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
    1.35 -//   }
    1.36 -
    1.37 -  Graph::NodeMap<int> ref_map(g, -1);
    1.38 -
    1.39 -  IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
    1.40 -//   for (int i=0; i<a; ++i) bipartite_map.insert(s_nodes[i], false);
    1.41 -//   for (int i=0; i<b; ++i) bipartite_map.insert(t_nodes[i], true);
    1.42 +  //generating leda random group graph
    1.43    leda_node ln;
    1.44    forall(ln, lS) bipartite_map.insert(ln, false);
    1.45    forall(ln, lT) bipartite_map.insert(ln, true);
    1.46  
    1.47 +  //making bipartite graph
    1.48    typedef BipartiteGraphWrapper<Graph> BGW;
    1.49    BGW bgw(g, bipartite_map);
    1.50  
    1.51 -  //  BGW::NodeMap<int> dbyj(bgw);
    1.52 -  //  BGW::EdgeMap<int> dbyxcj(bgw);
    1.53  
    1.54 +  //st-wrapper
    1.55    typedef stGraphWrapper<BGW> stGW;
    1.56    stGW stgw(bgw);
    1.57    ConstMap<stGW::Edge, int> const1map(1);
    1.58    stGW::EdgeMap<int> flow(stgw);
    1.59  
    1.60    Timer ts;
    1.61 +
    1.62 +  ts.reset();
    1.63    FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
    1.64 -  ts.reset();
    1.65 -  //  stGW::EdgeMap<int> pre_flow(stgw);
    1.66 -  Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
    1.67 -    pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
    1.68 -  pre_flow_test.run();
    1.69 -  std::cout << "HUGO pre flow value: " << pre_flow_test.flowValue() << std::endl;
    1.70 -  std::cout << "elapsed time: " << ts << std::endl;
    1.71 -//   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { 
    1.72 -//     std::cout << e << ": " << pre_flow[e] << "\n"; 
    1.73 -//   }
    1.74 -  std::cout << "\n";
    1.75 +  MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
    1.76 +    max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
    1.77 +  max_flow_test.run();
    1.78 +  std::cout << "HUGO max matching algorithm based on preflow." << std::endl 
    1.79 +	    << "Size of matching: " 
    1.80 +	    << max_flow_test.flowValue() << std::endl;
    1.81 +  std::cout << "elapsed time: " << ts << std::endl << std::endl;
    1.82  
    1.83    ts.reset();  
    1.84    leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg);
    1.85 -  //  stGW::EdgeMap<int> pre_flow(stgw);
    1.86 -  //Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
    1.87 -  //  pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow, true);
    1.88 -  //pre_flow_test.run();
    1.89 -  std::cout << "LEDA matching value: " << ml.size() << std::endl;
    1.90 +  std::cout << "LEDA max matching algorithm." << std::endl 
    1.91 +	    << "Size of matching: " 
    1.92 +	    << ml.size() << std::endl;
    1.93    std::cout << "elapsed time: " << ts << std::endl;
    1.94 -//   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { 
    1.95 -//     std::cout << e << ": " << pre_flow[e] << "\n"; 
    1.96 -//   }
    1.97    std::cout << "\n";
    1.98  
    1.99 +  ts.reset();
   1.100    FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
   1.101 -  ts.reset();
   1.102 -  MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
   1.103 -    max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
   1.104 -//  while (max_flow_test.augmentOnShortestPath()) { }
   1.105    typedef ListGraph MutableGraph;
   1.106 -//  while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
   1.107 -  while (max_flow_test.augmentOnBlockingFlow2()) {
   1.108 -   std::cout << max_flow_test.flowValue() << std::endl;
   1.109 -  }
   1.110 -  std::cout << "HUGO blocking flow value: " << max_flow_test.flowValue() << std::endl;
   1.111 +  while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { }
   1.112 +  std::cout << "HUGO max matching algorithm based on blocking flow augmentation." 
   1.113 +	    << std::endl << "Matching size: " 
   1.114 +	    << max_flow_test.flowValue() << std::endl;
   1.115    std::cout << "elapsed time: " << ts << std::endl;
   1.116 -//   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { 
   1.117 -//     std::cout << e << ": " << max_flow[e] << "\n"; 
   1.118 -//   }
   1.119 -//   std::cout << "\n";
   1.120  
   1.121    return 0;
   1.122  }