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