src/work/marci/leda/max_bipartite_matching_demo.cc
changeset 814 d2d747fe1db3
child 921 818510fa3d99
equal deleted inserted replaced
-1:000000000000 0:c2ac918c0937
       
     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 <sage_graph.h>
       
    13 #include <dimacs.h>
       
    14 #include <time_measure.h>
       
    15 #include <edmonds_karp.h>
       
    16 
       
    17 /**
       
    18  * Inicializalja a veletlenszamgeneratort.
       
    19  * Figyelem, ez nem jo igazi random szamokhoz,
       
    20  * erre ne bizzad a titkaidat!
       
    21  */
       
    22 void random_init()
       
    23 {
       
    24 	unsigned int seed = getpid();
       
    25 	seed |= seed << 15;
       
    26 	seed ^= time(0);
       
    27 
       
    28 	srand(seed);
       
    29 }
       
    30 
       
    31 /**
       
    32  * Egy veletlen int-et ad vissza 0 es m-1 kozott.
       
    33  */
       
    34 int random(int m)
       
    35 {
       
    36 	return int( double(m) * rand() / (RAND_MAX + 1.0) );
       
    37 }
       
    38 
       
    39 using namespace hugo;
       
    40 
       
    41 using std::cout; 
       
    42 using std::cin; 
       
    43 using std::endl;
       
    44 
       
    45 int main() {
       
    46    leda::graph g;
       
    47    typedef LedaGraphWrapper<leda::graph> Graph;
       
    48    Graph G(g);
       
    49 //  typedef ListGraph Graph;
       
    50 //  Graph G;
       
    51 
       
    52   typedef Graph::Node Node;
       
    53   typedef Graph::NodeIt NodeIt;  
       
    54   typedef Graph::Edge Edge;
       
    55   typedef Graph::EdgeIt EdgeIt;
       
    56   typedef Graph::OutEdgeIt OutEdgeIt;
       
    57   typedef Graph::InEdgeIt InEdgeIt;
       
    58 
       
    59   //Node s, t;
       
    60   //Graph::EdgeMap<int> cap(G);
       
    61   //readDimacsMaxFlow(std::cin, G, s, t, cap);
       
    62   std::vector<Node> s_nodes;
       
    63   std::vector<Node> t_nodes;
       
    64 
       
    65   int a;
       
    66   cout << "number of nodes in the first color class=";
       
    67   cin >> a; 
       
    68   int b;
       
    69   cout << "number of nodes in the second color class=";
       
    70   cin >> b; 
       
    71   int m;
       
    72   cout << "number of edges=";
       
    73   cin >> m;   
       
    74 
       
    75   for(int i=0; i<a; ++i) {
       
    76     s_nodes.push_back(G.addNode());
       
    77   }
       
    78   for(int i=0; i<a; ++i) {
       
    79     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 //   G.addEdge(s_nodes[1], t_nodes[5-4]);
       
    87 //   G.addEdge(s_nodes[1], t_nodes[5-4]);
       
    88 //   G.addEdge(s_nodes[1], t_nodes[4-4]);
       
    89 //   G.addEdge(s_nodes[1], t_nodes[4-4]);
       
    90 //   G.addEdge(s_nodes[2], t_nodes[4-4]);
       
    91 //   G.addEdge(s_nodes[3], t_nodes[4-4]);
       
    92 
       
    93   leda_list<leda_node> A;
       
    94   leda_list<leda_node> B;
       
    95   Graph::NodeMap<bool> s_map(G); //false
       
    96   Graph::NodeMap<bool> t_map(G); //false
       
    97   
       
    98   for(int i=0; i<a; ++i) { s_map.set(s_nodes[i], true); A+=s_nodes[i]; }
       
    99   for(int i=0; i<b; ++i) { t_map.set(t_nodes[i], true); B+=t_nodes[i]; }
       
   100 
       
   101 //   cout << "bfs and dfs iterator demo on the directed graph" << endl;
       
   102 //   for(NodeIt n=G.first<NodeIt>(); G.valid(n); G.next(n)) { 
       
   103 //     cout << G.id(n) << ": ";
       
   104 //     cout << "out edges: ";
       
   105 //     for(OutEdgeIt e=G.first<OutEdgeIt>(n); G.valid(e); G.next(e)) 
       
   106 //       cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
       
   107 //     cout << "in edges: ";
       
   108 //     for(InEdgeIt e=G.first<InEdgeIt>(n); G.valid(e); G.next(e)) 
       
   109 //       cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
       
   110 //     cout << endl;
       
   111 //   }
       
   112 
       
   113 
       
   114   {
       
   115     std::cout << "on-the-fly max bipartite matching (Edmonds-Karp) demo on wrapped leda graph..." << std::endl;
       
   116     Graph::EdgeMap<int> flow(G); //0 flow
       
   117     Graph::EdgeMap<int> cap(G, 1);
       
   118 
       
   119     Timer ts;
       
   120     ts.reset();
       
   121 
       
   122     MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
       
   123     int i=0;
       
   124     while (max_flow_test.augmentOnShortestPath()) { 
       
   125 //       for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
       
   126 // 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
       
   127 //       std::cout<<std::endl;
       
   128       ++i; 
       
   129     }
       
   130 
       
   131 //     std::cout << "maximum matching: "<< std::endl;
       
   132 //     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
       
   133 //       if (flow.get(e))
       
   134 // 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
       
   135 //     std::cout<<std::endl;
       
   136 //     std::cout << "edges which are not in this maximum matching: "<< std::endl;
       
   137 //     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
       
   138 //       if (!flow.get(e))
       
   139 // 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
       
   140 //     std::cout<<std::endl;
       
   141     
       
   142     std::cout << "elapsed time: " << ts << std::endl;
       
   143     std::cout << "number of augmentation phases: " << i << std::endl; 
       
   144     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
       
   145   }
       
   146 
       
   147 //   {
       
   148 //     std::cout << "on-the-fly max bipartite matching demo (Hopcroft-Karp) on wrapped leda graph..." << std::endl;
       
   149 //     Graph::EdgeMap<int> flow(G); //0 flow
       
   150 //     Graph::EdgeMap<int> cap(G, 1);
       
   151 
       
   152 //     Timer ts;
       
   153 //     ts.reset();
       
   154 
       
   155 //     MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
       
   156 //     int i=0;
       
   157 //     while (max_flow_test.augmentOnBlockingFlow2()) { 
       
   158 // //       for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
       
   159 // // 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
       
   160 // //       std::cout<<std::endl;
       
   161 //       ++i; 
       
   162 //     }
       
   163 
       
   164 // //     std::cout << "maximum matching: "<< std::endl;
       
   165 // //     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
       
   166 // //       if (flow.get(e))
       
   167 // // 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
       
   168 // //     std::cout<<std::endl;
       
   169 // //     std::cout << "edges which are not in this maximum matching: "<< std::endl;
       
   170 // //     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
       
   171 // //       if (!flow.get(e))
       
   172 // // 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
       
   173 // //     std::cout<<std::endl;
       
   174     
       
   175 //     std::cout << "elapsed time: " << ts << std::endl;
       
   176 //     std::cout << "number of augmentation phases: " << i << std::endl; 
       
   177 //     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
       
   178 //   }
       
   179 
       
   180   {
       
   181     std::cout << "max bipartite matching (LEDA)..." << std::endl;
       
   182     //Graph::EdgeMap<int> flow(G); //0 flow
       
   183     //Graph::EdgeMap<int> cap(G, 1);
       
   184 
       
   185     leda_node_array<bool> NC(g);
       
   186 
       
   187     Timer ts;
       
   188     ts.reset();
       
   189 
       
   190     //MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
       
   191     //int i=0;
       
   192     //while (max_flow_test.augmentOnShortestPath()) { ++i; }
       
   193     
       
   194     //leda_list<leda_edge> l=MAX_CARD_BIPARTITE_MATCHING_HK(g, A, B, NC, false);
       
   195     leda_list<leda_edge> l=MAX_CARD_BIPARTITE_MATCHING(g);    
       
   196     
       
   197 
       
   198 //     std::cout << "maximum matching: "<< std::endl;
       
   199 //     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
       
   200 //       if (flow.get(e))
       
   201 // 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
       
   202 //     std::cout<<std::endl;
       
   203 //     std::cout << "edges which are not in this maximum matching: "<< std::endl;
       
   204 //     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
       
   205 //       if (!flow.get(e))
       
   206 // 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
       
   207 //     std::cout<<std::endl;
       
   208     
       
   209     
       
   210     std::cout << "elapsed time: " << ts << std::endl;
       
   211     //std::cout << "number of augmentation phases: " << i << std::endl; 
       
   212     std::cout << "flow value: "<< l.size() << std::endl;
       
   213   }
       
   214   
       
   215   
       
   216 
       
   217   return 0;
       
   218 }