Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/marci/leda/max_bipartite_matching_demo.cc
changeset 997 665ffade9aca
parent 921 818510fa3d99
equal deleted inserted replaced
1:7a1e94c7d388 2:bc5d94d96bda 
   101 //   cout << "bfs and dfs iterator demo on the directed graph" << endl;
 
   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)) { 
   102 //   for(NodeIt n=G.first<NodeIt>(); G.valid(n); G.next(n)) { 
   103 //     cout << G.id(n) << ": ";
 
   103 //     cout << G.id(n) << ": ";
 
   104 //     cout << "out edges: ";
 
   104 //     cout << "out edges: ";
 
   105 //     for(OutEdgeIt e=G.first<OutEdgeIt>(n); G.valid(e); G.next(e)) 
   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)) << " ";
 
   106 //       cout << G.id(G.source(e)) << "->" << G.id(G.target(e)) << " ";
 
   107 //     cout << "in edges: ";
 
   107 //     cout << "in edges: ";
 
   108 //     for(InEdgeIt e=G.first<InEdgeIt>(n); G.valid(e); G.next(e)) 
   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)) << " ";
 
   109 //       cout << G.id(G.source(e)) << "->" << G.id(G.target(e)) << " ";
 
   110 //     cout << endl;
 
   110 //     cout << endl;
 
   111 //   }
 
   111 //   }
 
   112 
   112 
   113 
   113 
   114   {
 
   114   {
 
   121 
   121 
   122     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);
 
   123     int i=0;
 
   123     int i=0;
 
   124     while (max_flow_test.augmentOnShortestPath()) { 
   124     while (max_flow_test.augmentOnShortestPath()) { 
   125 //       for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
   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)) << " ";
 
   126 // 	std::cout << G.id(G.source(e)) << "-" << flow.get(e) << "->" << G.id(G.target(e)) << " ";
 
   127 //       std::cout<<std::endl;
 
   127 //       std::cout<<std::endl;
 
   128       ++i; 
   128       ++i; 
   129     }
 
   129     }
 
   130 
   130 
   131 //     std::cout << "maximum matching: "<< std::endl;
 
   131 //     std::cout << "maximum matching: "<< std::endl;
 
   132 //     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))  
   133 //       if (flow.get(e))
 
   133 //       if (flow.get(e))
 
   134 // 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
 
   134 // 	std::cout << G.id(G.source(e)) << "-" << flow.get(e) << "->" << G.id(G.target(e)) << " ";
 
   135 //     std::cout<<std::endl;
 
   135 //     std::cout<<std::endl;
 
   136 //     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;
 
   137 //     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))  
   138 //       if (!flow.get(e))
 
   138 //       if (!flow.get(e))
 
   139 // 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
 
   139 // 	std::cout << G.id(G.source(e)) << "-" << flow.get(e) << "->" << G.id(G.target(e)) << " ";
 
   140 //     std::cout<<std::endl;
 
   140 //     std::cout<<std::endl;
 
   141     
   141     
   142     std::cout << "elapsed time: " << ts << std::endl;
 
   142     std::cout << "elapsed time: " << ts << std::endl;
 
   143     std::cout << "number of augmentation phases: " << i << std::endl; 
   143     std::cout << "number of augmentation phases: " << i << std::endl; 
   144     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   144     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   154 
   154 
   155 //     MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
 
   155 //     MaxMatching<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s_map, t_map, flow, cap);
 
   156 //     int i=0;
 
   156 //     int i=0;
 
   157 //     while (max_flow_test.augmentOnBlockingFlow2()) { 
   157 //     while (max_flow_test.augmentOnBlockingFlow2()) { 
   158 // //       for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
   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)) << " ";
 
   159 // // 	std::cout << G.id(G.source(e)) << "-" << flow.get(e) << "->" << G.id(G.target(e)) << " ";
 
   160 // //       std::cout<<std::endl;
 
   160 // //       std::cout<<std::endl;
 
   161 //       ++i; 
   161 //       ++i; 
   162 //     }
 
   162 //     }
 
   163 
   163 
   164 // //     std::cout << "maximum matching: "<< std::endl;
 
   164 // //     std::cout << "maximum matching: "<< std::endl;
 
   165 // //     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
   165 // //     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
   166 // //       if (flow.get(e))
 
   166 // //       if (flow.get(e))
 
   167 // // 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
 
   167 // // 	std::cout << G.id(G.source(e)) << "-" << flow.get(e) << "->" << G.id(G.target(e)) << " ";
 
   168 // //     std::cout<<std::endl;
 
   168 // //     std::cout<<std::endl;
 
   169 // //     std::cout << "edges which are not in this maximum matching: "<< 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))  
   170 // //     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
   171 // //       if (!flow.get(e))
 
   171 // //       if (!flow.get(e))
 
   172 // // 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
 
   172 // // 	std::cout << G.id(G.source(e)) << "-" << flow.get(e) << "->" << G.id(G.target(e)) << " ";
 
   173 // //     std::cout<<std::endl;
 
   173 // //     std::cout<<std::endl;
 
   174     
   174     
   175 //     std::cout << "elapsed time: " << ts << std::endl;
 
   175 //     std::cout << "elapsed time: " << ts << std::endl;
 
   176 //     std::cout << "number of augmentation phases: " << i << std::endl; 
   176 //     std::cout << "number of augmentation phases: " << i << std::endl; 
   177 //     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   177 //     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   196     
   196     
   197 
   197 
   198 //     std::cout << "maximum matching: "<< std::endl;
 
   198 //     std::cout << "maximum matching: "<< std::endl;
 
   199 //     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
   199 //     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
   200 //       if (flow.get(e))
 
   200 //       if (flow.get(e))
 
   201 // 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
 
   201 // 	std::cout << G.id(G.source(e)) << "-" << flow.get(e) << "->" << G.id(G.target(e)) << " ";
 
   202 //     std::cout<<std::endl;
 
   202 //     std::cout<<std::endl;
 
   203 //     std::cout << "edges which are not in this maximum matching: "<< 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))  
   204 //     for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
   205 //       if (!flow.get(e))
 
   205 //       if (!flow.get(e))
 
   206 // 	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
 
   206 // 	std::cout << G.id(G.source(e)) << "-" << flow.get(e) << "->" << G.id(G.target(e)) << " ";
 
   207 //     std::cout<<std::endl;
 
   207 //     std::cout<<std::endl;
 
   208     
   208     
   209     
   209     
   210     std::cout << "elapsed time: " << ts << std::endl;
 
   210     std::cout << "elapsed time: " << ts << std::endl;
 
   211     //std::cout << "number of augmentation phases: " << i << std::endl; 
   211     //std::cout << "number of augmentation phases: " << i << std::endl;
lemon-0.x