marci@410: // -*- c++ -*- marci@410: #include marci@410: #include marci@410: #include marci@410: #include marci@410: marci@410: #include marci@410: //#include marci@410: //#include marci@410: #include marci@410: #include marci@410: #include marci@410: #include marci@410: #include marci@410: #include marci@410: #include marci@410: marci@410: /** marci@410: * Inicializalja a veletlenszamgeneratort. marci@410: * Figyelem, ez nem jo igazi random szamokhoz, marci@410: * erre ne bizzad a titkaidat! marci@410: */ marci@410: void random_init() marci@410: { marci@410: unsigned int seed = getpid(); marci@410: seed |= seed << 15; marci@410: seed ^= time(0); marci@410: marci@410: srand(seed); marci@410: } marci@410: marci@410: /** marci@410: * Egy veletlen int-et ad vissza 0 es m-1 kozott. marci@410: */ marci@410: int random(int m) marci@410: { marci@410: return int( double(m) * rand() / (RAND_MAX + 1.0) ); marci@410: } marci@410: marci@410: using namespace hugo; marci@410: marci@410: int main() { marci@410: typedef UndirListGraph Graph; marci@410: typedef Graph::Node Node; marci@410: typedef Graph::NodeIt NodeIt; marci@410: typedef Graph::Edge Edge; marci@410: typedef Graph::EdgeIt EdgeIt; marci@410: typedef Graph::OutEdgeIt OutEdgeIt; marci@410: marci@410: Graph g; marci@410: marci@410: std::vector s_nodes; marci@410: std::vector t_nodes; marci@410: marci@410: int a; marci@410: std::cout << "number of nodes in the first color class="; marci@410: std::cin >> a; marci@410: int b; marci@410: std::cout << "number of nodes in the second color class="; marci@410: std::cin >> b; marci@410: int m; marci@410: std::cout << "number of edges="; marci@410: std::cin >> m; marci@410: marci@410: marci@410: for (int i=0; i ref_map(g, -1); marci@410: marci@410: IterableBoolMap< Graph::NodeMap > bipartite_map(ref_map); marci@410: for (int i=0; i BGW; marci@410: BGW bgw(g, bipartite_map); marci@410: marci@410: // std::cout << "Nodes by NodeIt:\n"; marci@410: // FOR_EACH_LOC(BGW::NodeIt, n, bgw) { marci@410: // std::cout << n << " "; marci@410: // } marci@410: // std::cout << "\n"; marci@410: // std::cout << "Nodes in S by ClassNodeIt:\n"; marci@410: // FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.S_CLASS) { marci@410: // std::cout << n << " "; marci@410: // } marci@410: // std::cout << "\n"; marci@410: // std::cout << "Nodes in T by ClassNodeIt:\n"; marci@410: // FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.T_CLASS) { marci@410: // std::cout << n << " "; marci@410: // } marci@410: // std::cout << "\n"; marci@410: // std::cout << "Edges of the bipartite graph:\n"; marci@410: // FOR_EACH_LOC(BGW::EdgeIt, e, bgw) { marci@410: // std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl; marci@410: // } marci@410: marci@410: BGW::NodeMap dbyj(bgw); marci@410: BGW::EdgeMap dbyxcj(bgw); marci@410: marci@410: typedef stGraphWrapper stGW; marci@410: stGW stgw(bgw); marci@410: ConstMap const1map(1); marci@410: // stGW::NodeMap ize(stgw); marci@410: marci@410: // BfsIterator< BGW, BGW::NodeMap > bfs(bgw); marci@410: // Graph::NodeIt si; marci@410: // Graph::Node s; marci@410: // s=g.first(si); marci@410: // bfs.pushAndSetReached(BGW::Node(s)); marci@410: // while (!bfs.finished()) { ++bfs; } marci@410: marci@410: // FOR_EACH_LOC(stGW::NodeIt, n, stgw) { marci@410: // std::cout << "out-edges of " << n << ":\n"; marci@410: // FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) { marci@410: // std::cout << " " << e << "\n"; marci@410: // std::cout << " aNode: " << stgw.aNode(e) << "\n"; marci@410: // std::cout << " bNode: " << stgw.bNode(e) << "\n"; marci@410: // } marci@410: // std::cout << "in-edges of " << n << ":\n"; marci@410: // FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) { marci@410: // std::cout << " " << e << "\n"; marci@410: // std::cout << " aNode: " << stgw.aNode(e) << "\n"; marci@410: // std::cout << " bNode: " << stgw.bNode(e) << "\n"; marci@410: // } marci@410: // } marci@410: // std::cout << "Edges of the stGraphWrapper:\n"; marci@410: // FOR_EACH_LOC(stGW::EdgeIt, n, stgw) { marci@410: // std::cout << " " << n << "\n"; marci@410: // } marci@410: marci@410: // stGW::NodeMap b(stgw); marci@410: // FOR_EACH_LOC(stGW::NodeIt, n, stgw) { marci@410: // std::cout << n << ": " << b[n] <<"\n"; marci@410: // } marci@410: marci@410: // std::cout << "Bfs from s: \n"; marci@410: // BfsIterator< stGW, stGW::NodeMap > bfs_stgw(stgw); marci@410: // bfs_stgw.pushAndSetReached(stgw.S_NODE); marci@410: // while (!bfs_stgw.finished()) { marci@410: // std::cout << " " << stGW::OutEdgeIt(bfs_stgw) << "\n"; marci@410: // ++bfs_stgw; marci@410: // } marci@410: marci@410: marci@410: Timer ts; marci@410: ts.reset(); marci@410: stGW::EdgeMap max_flow(stgw); marci@410: MaxFlow, stGW::EdgeMap > marci@410: max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, max_flow); marci@410: // while (max_flow_test.augmentOnShortestPath()) { } marci@410: typedef ListGraph MutableGraph; marci@410: // while (max_flow_test.augmentOnBlockingFlow1()) { marci@410: while (max_flow_test.augmentOnBlockingFlow2()) { marci@410: std::cout << max_flow_test.flowValue() << std::endl; marci@410: } marci@410: std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl; marci@410: std::cout << "elapsed time: " << ts << std::endl; marci@410: // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { marci@410: // std::cout << e << ": " << max_flow[e] << "\n"; marci@410: // } marci@410: // std::cout << "\n"; marci@410: marci@410: ts.reset(); marci@410: stGW::EdgeMap pre_flow(stgw); marci@410: Preflow, stGW::EdgeMap > marci@465: pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow/*, true*/); marci@410: pre_flow_test.run(); marci@410: std::cout << "pre flow value: " << max_flow_test.flowValue() << std::endl; marci@410: std::cout << "elapsed time: " << ts << std::endl; marci@410: // FOR_EACH_LOC(stGW::EdgeIt, e, stgw) { marci@410: // std::cout << e << ": " << pre_flow[e] << "\n"; marci@410: // } marci@410: // std::cout << "\n"; marci@410: marci@410: return 0; marci@410: }