marci@510: // -*- c++ -*- marci@510: #include marci@510: #include marci@510: #include marci@510: marci@642: #include marci@510: //#include marci@510: //#include marci@555: #include marci@640: #include marci@602: #include marci@510: #include marci@555: #include marci@510: #include marci@558: #include marci@559: #include marci@510: marci@510: using namespace hugo; marci@510: marci@510: int main() { marci@510: //typedef UndirListGraph Graph; marci@642: typedef BipartiteGraph Graph; marci@510: marci@510: typedef Graph::Node Node; marci@510: typedef Graph::NodeIt NodeIt; marci@510: typedef Graph::Edge Edge; marci@510: typedef Graph::EdgeIt EdgeIt; marci@510: typedef Graph::OutEdgeIt OutEdgeIt; marci@510: marci@510: Graph g; marci@510: marci@510: int a; marci@510: std::cout << "number of nodes in the first color class="; marci@510: std::cin >> a; marci@510: int b; marci@510: std::cout << "number of nodes in the second color class="; marci@510: std::cin >> b; marci@510: int m; marci@510: std::cout << "number of edges="; marci@510: std::cin >> m; marci@510: marci@510: std::cout << "Generatig a random bipartite graph..." << std::endl; marci@510: random_init(); marci@558: randomBipartiteGraph(g, a, b, m); marci@510: marci@512: // std::cout << "Edges of the bipartite graph:" << std::endl; marci@512: // FOR_EACH_LOC(EdgeIt, e, g) std::cout << e << " "; marci@512: // std::cout << std::endl; marci@510: marci@512: // std::cout << "Nodes:" << std::endl; marci@512: // FOR_EACH_LOC(Graph::NodeIt, v, g) std::cout << v << " "; marci@512: // std::cout << std::endl; marci@512: // std::cout << "Nodes in T:" << std::endl; marci@512: // FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " "; marci@512: // std::cout << std::endl; marci@512: // std::cout << "Nodes in S:" << std::endl; marci@512: // FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " "; marci@512: // std::cout << std::endl; marci@510: marci@512: // std::cout << "Erasing the first node..." << std::endl; marci@512: // NodeIt n; marci@512: // g.first(n); marci@512: // g.erase(n); marci@512: // std::cout << "Nodes of the bipartite graph:" << std::endl; marci@512: // FOR_EACH_GLOB(n, g) std::cout << n << " "; marci@512: // std::cout << std::endl; marci@510: marci@512: // std::cout << "Nodes in T:" << std::endl; marci@512: // FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " "; marci@512: // std::cout << std::endl; marci@512: // std::cout << "Nodes in S:" << std::endl; marci@512: // FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " "; marci@512: // std::cout << std::endl; marci@510: marci@510: typedef stGraphWrapper stGW; marci@510: stGW stgw(g); marci@510: ConstMap const1map(1); marci@510: marci@510: Timer ts; marci@510: ts.reset(); marci@510: stGW::EdgeMap flow(stgw); marci@510: MaxFlow, stGW::EdgeMap > marci@510: max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow); marci@510: max_flow_test.run(); marci@510: // while (max_flow_test.augmentOnShortestPath()) { } marci@510: // typedef ListGraph MutableGraph; marci@510: // while (max_flow_test.augmentOnBlockingFlow1()) { marci@510: // while (max_flow_test.augmentOnBlockingFlow2()) { marci@510: // std::cout << max_flow_test.flowValue() << std::endl; marci@510: // } marci@510: std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl; marci@510: std::cout << "elapsed time: " << ts << std::endl; marci@512: // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { marci@512: // if (flow[e]) std::cout << e << std::endl; marci@512: // } marci@510: std::cout << std::endl; marci@510: marci@510: typedef ConstMap EdgeCap; marci@510: EdgeCap ge1(1); marci@510: typedef ConstMap NodeCap; marci@510: NodeCap gn1(1); marci@510: typedef Graph::EdgeMap EdgeFlow; marci@510: EdgeFlow gef(g); //0 marci@510: typedef Graph::NodeMap NodeFlow; marci@510: NodeFlow gnf(g); //0 marci@510: marci@510: typedef stGraphWrapper::EdgeMapWrapper CapMap; marci@510: typedef stGraphWrapper::EdgeMapWrapper FlowMap; marci@510: CapMap cm(ge1, gn1); marci@510: FlowMap fm(gef, gnf); marci@510: marci@510: //Timer ts; marci@510: ts.reset(); marci@510: //stGW::EdgeMap flow(stgw); marci@510: MaxFlow marci@510: max_flow_test1(stgw, stgw.S_NODE, stgw.T_NODE, cm, fm); marci@510: max_flow_test1.run(); marci@510: // while (max_flow_test.augmentOnShortestPath()) { } marci@510: // typedef ListGraph MutableGraph; marci@510: // while (max_flow_test.augmentOnBlockingFlow1()) { marci@510: // while (max_flow_test.augmentOnBlockingFlow2()) { marci@510: // std::cout << max_flow_test.flowValue() << std::endl; marci@510: // } marci@510: std::cout << "max flow value: " << max_flow_test1.flowValue() << std::endl; marci@510: std::cout << "elapsed time: " << ts << std::endl; marci@510: // FOR_EACH_LOC(Graph::EdgeIt, e, g) { marci@510: // if (gef[e]) std::cout << e << std::endl; marci@510: // } marci@510: std::cout << std::endl; marci@510: marci@510: ts.reset(); marci@510: FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0); marci@510: FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0); marci@613: MaxBipartiteMatching, ConstMap, marci@510: Graph::EdgeMap, Graph::NodeMap > marci@510: matching_test(g, ge1, gn1, gef, gnf); marci@510: matching_test.run(); marci@510: marci@510: std::cout << "max flow value: " << matching_test.matchingValue() << std::endl; marci@510: std::cout << "elapsed time: " << ts << std::endl; marci@510: // FOR_EACH_LOC(Graph::EdgeIt, e, g) { marci@510: // if (gef[e]) std::cout << e << std::endl; marci@510: // } marci@510: std::cout << std::endl; marci@512: marci@512: ts.reset(); marci@512: FOR_EACH_LOC(Graph::EdgeIt, e, g) gef.set(e, 0); marci@512: //FOR_EACH_LOC(Graph::NodeIt, n, g) gnf.set(n, 0); marci@613: MaxBipartiteMatching, ConstMap, marci@512: Graph::EdgeMap, Graph::NodeMap > marci@512: matching_test_1(g, ge1, gn1, gef/*, gnf*/); marci@512: matching_test_1.run(); marci@512: marci@512: std::cout << "max flow value: " << matching_test_1.matchingValue() << std::endl; marci@512: std::cout << "elapsed time: " << ts << std::endl; marci@512: // FOR_EACH_LOC(Graph::EdgeIt, e, g) { marci@512: // if (gef[e]) std::cout << e << std::endl; marci@512: // } marci@512: std::cout << std::endl; marci@512: marci@510: return 0; marci@510: }