Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/marci/leda/bipartite_matching_leda_gen.cc
changeset 1246 925002e098e7
parent 769 eb61fbc64c16
equal deleted inserted replaced
8:0e972419424c 9:e2c287f29891 
    11 
    11 
    12 #include <leda_graph_wrapper.h>
 
    12 #include <leda_graph_wrapper.h>
 
    13 #include <sage_graph.h>
 
    13 #include <sage_graph.h>
 
    14 //#include <smart_graph.h>
 
    14 //#include <smart_graph.h>
 
    15 //#include <dimacs.h>
 
    15 //#include <dimacs.h>
 
    16 #include <hugo/time_measure.h>
 
    16 #include <lemon/time_measure.h>
 
    17 #include <for_each_macros.h>
 
    17 #include <for_each_macros.h>
 
    18 #include <hugo/graph_wrapper.h>
 
    18 #include <lemon/graph_wrapper.h>
 
    19 #include <bipartite_graph_wrapper.h>
 
    19 #include <bipartite_graph_wrapper.h>
 
    20 #include <hugo/maps.h>
 
    20 #include <lemon/maps.h>
 
    21 #include <hugo/max_flow.h>
 
    21 #include <lemon/max_flow.h>
 
    22 #include <augmenting_flow.h>
 
    22 #include <augmenting_flow.h>
 
    23 
    23 
    24 /**
 
    24 /**
 
    25  * Inicializalja a veletlenszamgeneratort.
 
    25  * Inicializalja a veletlenszamgeneratort.
 
    26  * Figyelem, ez nem jo igazi random szamokhoz,
 
    26  * Figyelem, ez nem jo igazi random szamokhoz,
 
    41 int random(int m)
 
    41 int random(int m)
 
    42 {
 
    42 {
 
    43   return int( double(m) * rand() / (RAND_MAX + 1.0) );
 
    43   return int( double(m) * rand() / (RAND_MAX + 1.0) );
 
    44 }
 
    44 }
 
    45 
    45 
    46 using namespace hugo;
 
    46 using namespace lemon;
 
    47 
    47 
    48 int main() {
 
    48 int main() {
 
    49   //for leda graph
 
    49   //for leda graph
 
    50   leda::graph lg;
 
    50   leda::graph lg;
 
    51   //lg.make_undirected();
 
    51   //lg.make_undirected();
 
   108   ts.reset();
 
   108   ts.reset();
 
   109   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
 
   109   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
 
   110   MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
   110   MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
   111     max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
 
   111     max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
 
   112   max_flow_test.run();
 
   112   max_flow_test.run();
 
   113   std::cout << "HUGO max matching algorithm based on preflow." << std::endl 
   113   std::cout << "LEMON max matching algorithm based on preflow." << std::endl 
   114 	    << "Size of matching: " 
   114 	    << "Size of matching: " 
   115 	    << max_flow_test.flowValue() << std::endl;
 
   115 	    << max_flow_test.flowValue() << std::endl;
 
   116   std::cout << "elapsed time: " << ts << std::endl << std::endl;
 
   116   std::cout << "elapsed time: " << ts << std::endl << std::endl;
 
   117 
   117 
   118   ts.reset();  
   118   ts.reset();  
   127   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
 
   127   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
 
   128   typedef SageGraph MutableGraph;
 
   128   typedef SageGraph MutableGraph;
 
   129   AugmentingFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
   129   AugmentingFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
   130     max_flow_test_1(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
 
   130     max_flow_test_1(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
 
   131   while (max_flow_test_1.augmentOnBlockingFlow<MutableGraph>()) { }
 
   131   while (max_flow_test_1.augmentOnBlockingFlow<MutableGraph>()) { }
 
   132   std::cout << "HUGO max matching algorithm based on blocking flow augmentation." 
   132   std::cout << "LEMON max matching algorithm based on blocking flow augmentation." 
   133 	    << std::endl << "Matching size: " 
   133 	    << std::endl << "Matching size: " 
   134 	    << max_flow_test_1.flowValue() << std::endl;
 
   134 	    << max_flow_test_1.flowValue() << std::endl;
 
   135   std::cout << "elapsed time: " << ts << std::endl;
 
   135   std::cout << "elapsed time: " << ts << std::endl;
 
   136 
   136 
   137   return 0;
 
   137   return 0;
lemon-0.x