src/work/marci/leda/bipartite_matching_comparison.cc
author alpar
Wed, 29 Sep 2004 15:30:04 +0000
changeset 921 818510fa3d99
parent 771 ad7dff9ee2fd
child 986 e997802b855c
permissions -rw-r--r--
hugo -> lemon
     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 
    23 using std::cin;
    24 using std::cout;
    25 using std::endl;
    26 
    27 using namespace lemon;
    28 
    29 int main() {
    30   //for leda graph
    31   leda::graph lg;
    32   //lg.make_undirected();
    33   typedef LedaGraphWrapper<leda::graph> Graph;
    34   Graph g(lg);
    35 
    36   //for UndirSageGraph
    37   //typedef UndirSageGraph Graph; 
    38   //Graph g;
    39 
    40   typedef Graph::Node Node;
    41   typedef Graph::NodeIt NodeIt;
    42   typedef Graph::Edge Edge;
    43   typedef Graph::EdgeIt EdgeIt;
    44   typedef Graph::OutEdgeIt OutEdgeIt;
    45 
    46   std::vector<Graph::Node> s_nodes;
    47   std::vector<Graph::Node> t_nodes;
    48 
    49   int a;
    50   cout << "number of nodes in the first color class=";
    51   cin >> a; 
    52   int b;
    53   cout << "number of nodes in the second color class=";
    54   cin >> b; 
    55   int m;
    56   cout << "number of edges=";
    57   cin >> m; 
    58   int k;
    59   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";
    60   cout << "number of groups in LEDA random group graph=";
    61   cin >> k; 
    62   cout << endl;
    63   
    64   leda_list<leda_node> lS;
    65   leda_list<leda_node> lT;
    66   random_bigraph(lg, a, b, m, lS, lT, k);
    67 
    68   Graph::NodeMap<int> ref_map(g, -1);
    69   IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
    70 
    71   //generating leda random group graph
    72   leda_node ln;
    73   forall(ln, lS) bipartite_map.insert(ln, false);
    74   forall(ln, lT) bipartite_map.insert(ln, true);
    75 
    76   //making bipartite graph
    77   typedef BipartiteGraphWrapper<Graph> BGW;
    78   BGW bgw(g, bipartite_map);
    79 
    80 
    81   //st-wrapper
    82   typedef stBipartiteGraphWrapper<BGW> stGW;
    83   stGW stgw(bgw);
    84   ConstMap<stGW::Edge, int> const1map(1);
    85   stGW::EdgeMap<int> flow(stgw);
    86 
    87   Timer ts;
    88 
    89   ts.reset();
    90   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
    91   MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
    92     max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
    93   max_flow_test.run();
    94   cout << "LEMON max matching algorithm based on preflow." << endl 
    95 	    << "Size of matching: " 
    96 	    << max_flow_test.flowValue() << endl;
    97   cout << "elapsed time: " << ts << endl << endl;
    98 
    99   ts.reset();  
   100   leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg);
   101   cout << "LEDA max matching algorithm." << endl 
   102 	    << "Size of matching: " 
   103 	    << ml.size() << endl;
   104   cout << "elapsed time: " << ts << endl << endl;
   105 
   106 //   ts.reset();
   107 //   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
   108 //   typedef SageGraph MutableGraph;
   109 //   while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { }
   110 //   cout << "LEMON max matching algorithm based on blocking flow augmentation." 
   111 // 	    << endl << "Matching size: " 
   112 // 	    << max_flow_test.flowValue() << endl;
   113 //   cout << "elapsed time: " << ts << endl << endl;
   114 
   115   {
   116   SageGraph hg;
   117   SageGraph::Node s=hg.addNode();  
   118   SageGraph::Node t=hg.addNode();
   119   BGW::NodeMap<SageGraph::Node> b_s_nodes(bgw);  
   120   BGW::NodeMap<SageGraph::Node> b_t_nodes(bgw);
   121   
   122   FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, BGW::S_CLASS) {
   123     b_s_nodes.set(n, hg.addNode());
   124     hg.addEdge(s, b_s_nodes[n]);
   125   }
   126   FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, BGW::T_CLASS) {
   127     b_t_nodes.set(n, hg.addNode());
   128     hg.addEdge(b_t_nodes[n], t);
   129   }
   130 
   131   FOR_EACH_LOC(BGW::EdgeIt, e, bgw) 
   132     hg.addEdge(b_s_nodes[bgw.tail(e)], b_t_nodes[bgw.head(e)]);
   133 
   134   ConstMap<SageGraph::Edge, int> cm(1);
   135   SageGraph::EdgeMap<int> flow(hg); //0
   136   
   137   Timer ts;
   138 
   139   ts.reset();
   140   MaxFlow<SageGraph, int, ConstMap<SageGraph::Edge, int>, 
   141     SageGraph::EdgeMap<int> > 
   142     max_flow_test(hg, s, t, cm, flow);
   143   max_flow_test.run();
   144   cout << "LEMON max matching algorithm on SageGraph by copying the graph, based on preflow." 
   145 	    << endl 
   146 	    << "Size of matching: " 
   147 	    << max_flow_test.flowValue() << endl;
   148   cout << "elapsed time: " << ts << endl << endl;
   149   }
   150 
   151   return 0;
   152 }