marci@510: // -*- c++ -*- marci@510: #include <iostream> marci@510: #include <fstream> marci@510: #include <vector> marci@510: marci@510: #include <list_graph.h> marci@510: //#include <smart_graph.h> marci@510: //#include <dimacs.h> marci@555: #include <hugo/time_measure.h> marci@510: #include <for_each_macros.h> marci@602: #include <bfs_dfs.h> marci@510: #include <bipartite_graph_wrapper.h> marci@555: #include <hugo/maps.h> marci@510: #include <max_flow.h> marci@558: #include <graph_gen.h> marci@559: #include <max_bipartite_matching.h> marci@510: marci@510: using namespace hugo; marci@510: marci@510: int main() { marci@510: //typedef UndirListGraph Graph; marci@510: typedef BipartiteGraph<ListGraph> 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<Graph> stGW; marci@510: stGW stgw(g); marci@510: ConstMap<stGW::Edge, int> const1map(1); marci@510: marci@510: Timer ts; marci@510: ts.reset(); marci@510: stGW::EdgeMap<int> flow(stgw); marci@510: MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 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<MutableGraph>()) { 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<Graph::Edge, int> EdgeCap; marci@510: EdgeCap ge1(1); marci@510: typedef ConstMap<Graph::Node, int> NodeCap; marci@510: NodeCap gn1(1); marci@510: typedef Graph::EdgeMap<int> EdgeFlow; marci@510: EdgeFlow gef(g); //0 marci@510: typedef Graph::NodeMap<int> NodeFlow; marci@510: NodeFlow gnf(g); //0 marci@510: marci@510: typedef stGraphWrapper<Graph>::EdgeMapWrapper<EdgeCap, NodeCap> CapMap; marci@510: typedef stGraphWrapper<Graph>::EdgeMapWrapper<EdgeFlow, NodeFlow> 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<int> flow(stgw); marci@510: MaxFlow<stGW, int, CapMap, FlowMap> 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<MutableGraph>()) { 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<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>, marci@510: Graph::EdgeMap<int>, Graph::NodeMap<int> > 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<Graph, ConstMap<Graph::Edge, int>, ConstMap<Graph::Node, int>, marci@512: Graph::EdgeMap<int>, Graph::NodeMap<int> > 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: }