src/work/marci/leda/bipartite_matching_leda_gen.cc
author deba
Mon, 04 Oct 2004 17:13:21 +0000
changeset 937 d4e911acef3d
parent 769 eb61fbc64c16
permissions -rw-r--r--
Revert backport changes -r1230.
     1 // -*- c++ -*-
     2 #include <iostream>
     3 #include <fstream>
     4 #include <vector>
     5 #include <cstdlib>
     6 
     7 #include <LEDA/graph.h>
     8 #include <LEDA/mcb_matching.h>
     9 #include <LEDA/list.h>
    10 #include <LEDA/graph_gen.h>
    11 
    12 #include <leda_graph_wrapper.h>
    13 #include <sage_graph.h>
    14 //#include <smart_graph.h>
    15 //#include <dimacs.h>
    16 #include <lemon/time_measure.h>
    17 #include <for_each_macros.h>
    18 #include <lemon/graph_wrapper.h>
    19 #include <bipartite_graph_wrapper.h>
    20 #include <lemon/maps.h>
    21 #include <lemon/max_flow.h>
    22 #include <augmenting_flow.h>
    23 
    24 /**
    25  * Inicializalja a veletlenszamgeneratort.
    26  * Figyelem, ez nem jo igazi random szamokhoz,
    27  * erre ne bizzad a titkaidat!
    28  */
    29 void random_init()
    30 {
    31 	unsigned int seed = getpid();
    32 	seed |= seed << 15;
    33 	seed ^= time(0);
    34 
    35 	srand(seed);
    36 }
    37 
    38 /**
    39  * Egy veletlen int-et ad vissza 0 es m-1 kozott.
    40  */
    41 int random(int m)
    42 {
    43   return int( double(m) * rand() / (RAND_MAX + 1.0) );
    44 }
    45 
    46 using namespace lemon;
    47 
    48 int main() {
    49   //for leda graph
    50   leda::graph lg;
    51   //lg.make_undirected();
    52   typedef LedaGraphWrapper<leda::graph> Graph;
    53   Graph g(lg);
    54 
    55   //for UndirSageGraph
    56   //typedef UndirSageGraph Graph; 
    57   //Graph g;
    58 
    59   typedef Graph::Node Node;
    60   typedef Graph::NodeIt NodeIt;
    61   typedef Graph::Edge Edge;
    62   typedef Graph::EdgeIt EdgeIt;
    63   typedef Graph::OutEdgeIt OutEdgeIt;
    64 
    65   std::vector<Graph::Node> s_nodes;
    66   std::vector<Graph::Node> t_nodes;
    67 
    68   int a;
    69   std::cout << "number of nodes in the first color class=";
    70   std::cin >> a; 
    71   int b;
    72   std::cout << "number of nodes in the second color class=";
    73   std::cin >> b; 
    74   int m;
    75   std::cout << "number of edges=";
    76   std::cin >> m; 
    77   int k;
    78   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";
    79   std::cout << "number of groups in LEDA random group graph=";
    80   std::cin >> k; 
    81   std::cout << std::endl;
    82   
    83   leda_list<leda_node> lS;
    84   leda_list<leda_node> lT;
    85   random_bigraph(lg, a, b, m, lS, lT, k);
    86 
    87   Graph::NodeMap<int> ref_map(g, -1);
    88   IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
    89 
    90   //generating leda random group graph
    91   leda_node ln;
    92   forall(ln, lS) bipartite_map.insert(ln, false);
    93   forall(ln, lT) bipartite_map.insert(ln, true);
    94 
    95   //making bipartite graph
    96   typedef BipartiteGraphWrapper<Graph> BGW;
    97   BGW bgw(g, bipartite_map);
    98 
    99 
   100   //st-wrapper
   101   typedef stBipartiteGraphWrapper<BGW> stGW;
   102   stGW stgw(bgw);
   103   ConstMap<stGW::Edge, int> const1map(1);
   104   stGW::EdgeMap<int> flow(stgw);
   105 
   106   Timer ts;
   107 
   108   ts.reset();
   109   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
   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*/);
   112   max_flow_test.run();
   113   std::cout << "LEMON max matching algorithm based on preflow." << std::endl 
   114 	    << "Size of matching: " 
   115 	    << max_flow_test.flowValue() << std::endl;
   116   std::cout << "elapsed time: " << ts << std::endl << std::endl;
   117 
   118   ts.reset();  
   119   leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg);
   120   std::cout << "LEDA max matching algorithm." << std::endl 
   121 	    << "Size of matching: " 
   122 	    << ml.size() << std::endl;
   123   std::cout << "elapsed time: " << ts << std::endl;
   124   std::cout << "\n";
   125 
   126   ts.reset();
   127   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
   128   typedef SageGraph MutableGraph;
   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*/);
   131   while (max_flow_test_1.augmentOnBlockingFlow<MutableGraph>()) { }
   132   std::cout << "LEMON max matching algorithm based on blocking flow augmentation." 
   133 	    << std::endl << "Matching size: " 
   134 	    << max_flow_test_1.flowValue() << std::endl;
   135   std::cout << "elapsed time: " << ts << std::endl;
   136 
   137   return 0;
   138 }