Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/marci/max_bipartite_matching_demo.cc
changeset 197 fff43d9c7110
parent 196 8a9b9360463e
child 198 5cec393baade
equal deleted inserted replaced
3:20b06c9d07eb 4:7fab5b6d1870 
     2 #include <iostream>
 
     2 #include <iostream>
 
     3 #include <fstream>
 
     3 #include <fstream>
 
     4 #include <vector>
 
     4 #include <vector>
 
     5 #include <cstdlib>
 
     5 #include <cstdlib>
 
     6 
     6 
     7 //#include <LEDA/graph.h>
 
     7 #include <LEDA/graph.h>
 
     8 //#include <leda_graph_wrapper.h>
 
     8 #include <LEDA/mcb_matching.h>
 
       
     9 #include <LEDA/list.h>
 
       
    10 
       
    11 #include <leda_graph_wrapper.h>
 
     9 #include <list_graph.h>
 
    12 #include <list_graph.h>
 
    10 #include <dimacs.h>
 
    13 #include <dimacs.h>
 
    11 #include <time_measure.h>
 
    14 #include <time_measure.h>
 
    12 #include <edmonds_karp.h>
 
    15 #include <edmonds_karp.h>
 
    13 
    16 
    34 }
 
    37 }
 
    35 
    38 
    36 using namespace hugo;
 
    39 using namespace hugo;
 
    37 
    40 
    38 using std::cout; 
    41 using std::cout; 
       
    42 using std::cin; 
    39 using std::endl;
 
    43 using std::endl;
 
    40 
    44 
    41 int main() {
 
    45 int main() {
 
    42 //   leda::graph g;
 
    46    leda::graph g;
 
    43 //   typedef LedaGraphWrapper<leda::graph> Graph;
 
    47    typedef LedaGraphWrapper<leda::graph> Graph;
 
    44 //   Graph G(g);
 
    48    Graph G(g);
 
    45   typedef ListGraph Graph;
 
    49 //  typedef ListGraph Graph;
 
    46   Graph G;
 
    50 //  Graph G;
 
    47 
    51 
    48   typedef Graph::Node Node;
 
    52   typedef Graph::Node Node;
 
    49   typedef Graph::NodeIt NodeIt;  
    53   typedef Graph::NodeIt NodeIt;  
    50   typedef Graph::Edge Edge;
 
    54   typedef Graph::Edge Edge;
 
    51   typedef Graph::EdgeIt EdgeIt;
 
    55   typedef Graph::EdgeIt EdgeIt;
 
    56   //Graph::EdgeMap<int> cap(G);
 
    60   //Graph::EdgeMap<int> cap(G);
 
    57   //readDimacsMaxFlow(std::cin, G, s, t, cap);
 
    61   //readDimacsMaxFlow(std::cin, G, s, t, cap);
 
    58   std::vector<Node> s_nodes;
 
    62   std::vector<Node> s_nodes;
 
    59   std::vector<Node> t_nodes;
 
    63   std::vector<Node> t_nodes;
 
    60 
    64 
    61   for(int i=0; i<4; ++i) {
 
    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 
       
    76   for(int i=0; i<a; ++i) {
 
    62     s_nodes.push_back(G.addNode());
 
    77     s_nodes.push_back(G.addNode());
 
    63   }
 
    78   }
 
    64   for(int i=0; i<4; ++i) {
 
    79   for(int i=0; i<a; ++i) {
 
    65     t_nodes.push_back(G.addNode());
 
    80     t_nodes.push_back(G.addNode());
 
    66   }
 
    81   }
 
    67   random_init();
 
    82   random_init();
 
    68   for(int i=0; i<6; ++i) {
 
    83   for(int i=0; i<m; ++i) {
 
    69     G.addEdge(s_nodes[random(4)], t_nodes[random(4)]);
 
    84     G.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
 
    70   }
 
    85   }
 
    71   
    86   
       
    87 //   G.addEdge(s_nodes[1], t_nodes[5-4]);
 
       
    88 //   G.addEdge(s_nodes[1], t_nodes[5-4]);
 
       
    89 //   G.addEdge(s_nodes[1], t_nodes[4-4]);
 
       
    90 //   G.addEdge(s_nodes[1], t_nodes[4-4]);
 
    72 //   G.addEdge(s_nodes[2], t_nodes[4-4]);
 
    91 //   G.addEdge(s_nodes[2], t_nodes[4-4]);
 
    73 //   G.addEdge(s_nodes[2], t_nodes[7-4]);
 
    92 //   G.addEdge(s_nodes[3], t_nodes[4-4]);
 
    74 //   G.addEdge(s_nodes[2], t_nodes[4-4]);
 
       
    75 //   G.addEdge(s_nodes[3], t_nodes[6-4]);
 
       
    76 //   G.addEdge(s_nodes[3], t_nodes[5-4]);
 
       
    77 //   G.addEdge(s_nodes[3], t_nodes[5-4]);
 
       
    78 
    93 
    79 
    94 
    80   Graph::NodeMap<bool> s_map(G); //false
 
    95   Graph::NodeMap<bool> s_map(G); //false
 
    81   Graph::NodeMap<bool> t_map(G); //false
 
    96   Graph::NodeMap<bool> t_map(G); //false
 
    82   
    97   
    83   for(int i=0; i<4; ++i) {
 
    98   for(int i=0; i<a; ++i) s_map.set(s_nodes[i], true);
 
    84     s_map.set(s_nodes[i], true);
 
    99   for(int i=0; i<b; ++i) t_map.set(t_nodes[i], true);
 
    85     t_map.set(t_nodes[i], true);
 
   100 
    86   }
 
   101 //   cout << "bfs and dfs iterator demo on the directed graph" << endl;
 
    87 
   102 //   for(NodeIt n=G.first<NodeIt>(); G.valid(n); G.next(n)) { 
    88   cout << "bfs and dfs iterator demo on the directed graph" << endl;
 
   103 //     cout << G.id(n) << ": ";
 
    89   for(NodeIt n=G.first<NodeIt>(); G.valid(n); G.next(n)) { 
   104 //     cout << "out edges: ";
 
    90     cout << G.id(n) << ": ";
 
   105 //     for(OutEdgeIt e=G.first<OutEdgeIt>(n); G.valid(e); G.next(e)) 
    91     cout << "out edges: ";
 
   106 //       cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
 
    92     for(OutEdgeIt e=G.first<OutEdgeIt>(n); G.valid(e); G.next(e)) 
   107 //     cout << "in edges: ";
 
    93       cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
 
   108 //     for(InEdgeIt e=G.first<InEdgeIt>(n); G.valid(e); G.next(e)) 
    94     cout << "in edges: ";
 
   109 //       cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
 
    95     for(InEdgeIt e=G.first<InEdgeIt>(n); G.valid(e); G.next(e)) 
   110 //     cout << endl;
 
    96       cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
 
   111 //   }
 
    97     cout << endl;
 
       
    98   }
 
       
    99 
   112 
   100 
   113 
   101   {
 
   114   {
 
   102     std::cout << "on-the-fly max bipartite matching demo on wrapped leda graph..." << std::endl;
 
   115     std::cout << "on-the-fly max bipartite matching demo on wrapped leda graph..." << std::endl;
 
   103     Graph::EdgeMap<int> flow(G); //0 flow
 
   116     Graph::EdgeMap<int> flow(G); //0 flow
 
   105 
   118 
   106     Timer ts;
 
   119     Timer ts;
 
   107     ts.reset();
 
   120     ts.reset();
 
   108 
   121 
   109     MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
 
   122     MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
 
   110     //max_flow_test.augmentWithBlockingFlow<Graph>();
 
       
   111     int i=0;
 
   123     int i=0;
 
   112     while (max_flow_test.augmentOnShortestPath()) { 
   124     while (max_flow_test.augmentOnShortestPath()) { 
   113 //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
   125 //       for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
   114 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 
   126 // 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
 
   115 //     }
 
   127 //       std::cout<<std::endl;
 
   116 //     std::cout<<std::endl;
 
       
   117       ++i; 
   128       ++i; 
   118     }
 
   129     }
 
   119 
   130 
   120     std::cout << "maximum matching: "<< std::endl;
 
   131 //     std::cout << "maximum matching: "<< std::endl;
 
   121     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
   132 //     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
   122       if (flow.get(e))
 
   133 //       if (flow.get(e))
 
   123 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
 
   134 // 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
 
   124     std::cout<<std::endl;
 
   135 //     std::cout<<std::endl;
 
   125     std::cout << "edges which are not in this maximum matching: "<< std::endl;
 
   136 //     std::cout << "edges which are not in this maximum matching: "<< std::endl;
 
   126     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
   137 //     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
   127       if (!flow.get(e))
 
   138 //       if (!flow.get(e))
 
   128 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
 
   139 // 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
 
   129     std::cout<<std::endl;
 
   140 //     std::cout<<std::endl;
 
   130     
   141     
   131     std::cout << "elapsed time: " << ts << std::endl;
 
   142     std::cout << "elapsed time: " << ts << std::endl;
 
   132     std::cout << "number of augmentation phases: " << i << std::endl; 
   143     std::cout << "number of augmentation phases: " << i << std::endl; 
   133     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   144     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   134   }
 
   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     Timer ts;
 
       
   186     ts.reset();
 
       
   187 
       
   188     //MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
 
       
   189     //int i=0;
 
       
   190     //while (max_flow_test.augmentOnShortestPath()) { ++i; }
 
       
   191 
       
   192     leda_list<leda_edge> l=MAX_CARD_BIPARTITE_MATCHING(g);    
       
   193     
       
   194 
       
   195 //     std::cout << "maximum matching: "<< std::endl;
 
       
   196 //     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
       
   197 //       if (flow.get(e))
 
       
   198 // 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
 
       
   199 //     std::cout<<std::endl;
 
       
   200 //     std::cout << "edges which are not in this maximum matching: "<< std::endl;
 
       
   201 //     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
       
   202 //       if (!flow.get(e))
 
       
   203 // 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
 
       
   204 //     std::cout<<std::endl;
 
       
   205     
       
   206     
       
   207     std::cout << "elapsed time: " << ts << std::endl;
 
       
   208     //std::cout << "number of augmentation phases: " << i << std::endl; 
       
   209     std::cout << "flow value: "<< l.size() << std::endl;
 
       
   210   }
 
       
   211   
   135   
   212   
   136 
   213 
   137   return 0;
 
   214   return 0;
 
   138 }
 
   215 }
lemon-0.x