src/work/marci/leda/bipartite_matching_leda.cc
author jacint
Mon, 26 Apr 2004 17:05:22 +0000
changeset 422 ede61a3d229b
parent 413 9cb93f692e92
child 446 77ef5c7a57d9
permissions -rw-r--r--
macro erase
     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 
    11 #include <leda_graph_wrapper.h>
    12 #include <list_graph.h>
    13 //#include <smart_graph.h>
    14 //#include <dimacs.h>
    15 #include <time_measure.h>
    16 #include <for_each_macros.h>
    17 //#include <bfs_iterator.h>
    18 #include <graph_wrapper.h>
    19 #include <maps.h>
    20 #include <edmonds_karp.h>
    21 #include <preflow.h>
    22 
    23 /**
    24  * Inicializalja a veletlenszamgeneratort.
    25  * Figyelem, ez nem jo igazi random szamokhoz,
    26  * erre ne bizzad a titkaidat!
    27  */
    28 void random_init()
    29 {
    30 	unsigned int seed = getpid();
    31 	seed |= seed << 15;
    32 	seed ^= time(0);
    33 
    34 	srand(seed);
    35 }
    36 
    37 /**
    38  * Egy veletlen int-et ad vissza 0 es m-1 kozott.
    39  */
    40 int random(int m)
    41 {
    42   return int( double(m) * rand() / (RAND_MAX + 1.0) );
    43 }
    44 
    45 using namespace hugo;
    46 
    47 int main() {
    48   //for leda graph
    49   leda::graph lg;
    50   //lg.make_undirected();
    51   typedef LedaGraphWrapper<leda::graph> Graph;
    52   Graph g(lg);
    53 
    54   //for UndirListGraph
    55   //typedef UndirListGraph Graph; 
    56   //Graph g;
    57 
    58   typedef Graph::Node Node;
    59   typedef Graph::NodeIt NodeIt;
    60   typedef Graph::Edge Edge;
    61   typedef Graph::EdgeIt EdgeIt;
    62   typedef Graph::OutEdgeIt OutEdgeIt;
    63 
    64   std::vector<Graph::Node> s_nodes;
    65   std::vector<Graph::Node> t_nodes;
    66 
    67   int a;
    68   std::cout << "number of nodes in the first color class=";
    69   std::cin >> a; 
    70   int b;
    71   std::cout << "number of nodes in the second color class=";
    72   std::cin >> b; 
    73   int m;
    74   std::cout << "number of edges=";
    75   std::cin >> m; 
    76   
    77 
    78   for (int i=0; i<a; ++i) s_nodes.push_back(g.addNode());
    79   for (int i=0; i<b; ++i) t_nodes.push_back(g.addNode());
    80 
    81   random_init();
    82   for(int i=0; i<m; ++i) {
    83     g.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
    84   }
    85 
    86   Graph::NodeMap<int> ref_map(g, -1);
    87 
    88   IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
    89   for (int i=0; i<a; ++i) bipartite_map.insert(s_nodes[i], false);
    90   for (int i=0; i<b; ++i) bipartite_map.insert(t_nodes[i], true);
    91 
    92 //   Graph::Node u;
    93 //   std::cout << "These nodes will be in S:\n";
    94 //   //FIXME azert kellene ++, es invalid vizsgalat u-bol, hogy ezt le lehessen 
    95 //   //irni 1etlen FOR_EACH-csel.
    96 //   for (bipartite_map.first(u, false); g.valid(u); bipartite_map.next(u)) 
    97 //     std::cout << u << " ";
    98 //   std::cout << "\n";
    99 //   std::cout << "These nodes will be in T:\n";
   100 //   for (bipartite_map.first(u, true); g.valid(u); bipartite_map.next(u)) 
   101 //     std::cout << u << " ";
   102 //   std::cout << "\n";
   103 
   104   typedef BipartiteGraphWrapper<Graph> BGW;
   105   BGW bgw(g, bipartite_map);
   106 
   107 //   std::cout << "Nodes by NodeIt:\n";
   108 //   FOR_EACH_LOC(BGW::NodeIt, n, bgw) {
   109 //     std::cout << n << " ";
   110 //   }
   111 //   std::cout << "\n";
   112 //   std::cout << "Nodes in S by ClassNodeIt:\n";
   113 //   FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.S_CLASS) {
   114 //     std::cout << n << " ";
   115 //   }
   116 //   std::cout << "\n";
   117 //   std::cout << "Nodes in T by ClassNodeIt:\n";
   118 //   FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.T_CLASS) {
   119 //     std::cout << n << " ";
   120 //   }
   121 //   std::cout << "\n";
   122 //   std::cout << "Edges of the bipartite graph:\n";
   123 //   FOR_EACH_LOC(BGW::EdgeIt, e, bgw) {
   124 //     std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl;
   125 //   }
   126 
   127   BGW::NodeMap<int> dbyj(bgw);
   128   BGW::EdgeMap<int> dbyxcj(bgw);
   129 
   130   typedef stGraphWrapper<BGW> stGW;
   131   stGW stgw(bgw);
   132   ConstMap<stGW::Edge, int> const1map(1);
   133 //  stGW::NodeMap<int> ize(stgw);
   134 
   135 //   BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);
   136 //   Graph::NodeIt si;
   137 //   Graph::Node s; 
   138 //   s=g.first(si);
   139 //   bfs.pushAndSetReached(BGW::Node(s));
   140 //   while (!bfs.finished()) { ++bfs; }
   141 
   142 //   FOR_EACH_LOC(stGW::NodeIt, n, stgw) { 
   143 //     std::cout << "out-edges of " << n << ":\n"; 
   144 //     FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) { 
   145 //       std::cout << " " << e << "\n";
   146 //       std::cout << " aNode: " << stgw.aNode(e) << "\n";
   147 //       std::cout << " bNode: " << stgw.bNode(e) << "\n";      
   148 //     }
   149 //     std::cout << "in-edges of " << n << ":\n"; 
   150 //     FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) { 
   151 //       std::cout << " " << e << "\n";
   152 //       std::cout << " aNode: " << stgw.aNode(e) << "\n";
   153 //       std::cout << " bNode: " << stgw.bNode(e) << "\n";     
   154 //     }
   155 //   }
   156 //   std::cout << "Edges of the stGraphWrapper:\n"; 
   157 //   FOR_EACH_LOC(stGW::EdgeIt, n, stgw) { 
   158 //     std::cout << " " << n << "\n";
   159 //   }
   160 
   161 //   stGW::NodeMap<bool> b(stgw);
   162 //   FOR_EACH_LOC(stGW::NodeIt, n, stgw) { 
   163 //     std::cout << n << ": " << b[n] <<"\n";
   164 //   }
   165 
   166 //   std::cout << "Bfs from s: \n";
   167 //   BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw);
   168 //   bfs_stgw.pushAndSetReached(stgw.S_NODE);
   169 //   while (!bfs_stgw.finished()) { 
   170 //     std::cout << " " << stGW::OutEdgeIt(bfs_stgw) << "\n";
   171 //     ++bfs_stgw; 
   172 //   }
   173 
   174 
   175   Timer ts;
   176   ts.reset();
   177   stGW::EdgeMap<int> max_flow(stgw);
   178   MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
   179     max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, max_flow);
   180 //  while (max_flow_test.augmentOnShortestPath()) { }
   181   typedef ListGraph MutableGraph;
   182 //  while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
   183   while (max_flow_test.augmentOnBlockingFlow2()) {
   184    std::cout << max_flow_test.flowValue() << std::endl;
   185   }
   186   std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl;
   187   std::cout << "elapsed time: " << ts << std::endl;
   188 //   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { 
   189 //     std::cout << e << ": " << max_flow[e] << "\n"; 
   190 //   }
   191 //   std::cout << "\n";
   192 
   193   ts.reset();
   194   stGW::EdgeMap<int> pre_flow(stgw);
   195   Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
   196     pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow, true);
   197   pre_flow_test.run();
   198   std::cout << "pre flow value: " << max_flow_test.flowValue() << std::endl;
   199   std::cout << "elapsed time: " << ts << std::endl;
   200 //   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { 
   201 //     std::cout << e << ": " << pre_flow[e] << "\n"; 
   202 //   }
   203 //   std::cout << "\n";
   204 
   205   ts.reset();  
   206   leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg);
   207   //  stGW::EdgeMap<int> pre_flow(stgw);
   208   //Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
   209   //  pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow, true);
   210   //pre_flow_test.run();
   211   std::cout << "leda matching value: " << ml.size() << std::endl;
   212   std::cout << "elapsed time: " << ts << std::endl;
   213 //   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { 
   214 //     std::cout << e << ": " << pre_flow[e] << "\n"; 
   215 //   }
   216 //   std::cout << "\n";
   217 
   218   return 0;
   219 }