marci@368: // -*- c++ -*- marci@368: #include marci@368: #include marci@368: #include marci@368: marci@368: #include marci@389: //#include marci@368: //#include marci@555: #include marci@368: #include marci@368: #include marci@557: #include marci@496: #include marci@555: #include marci@480: #include marci@368: marci@368: using namespace hugo; marci@368: marci@368: int main() { marci@368: typedef UndirListGraph Graph; marci@368: typedef Graph::Node Node; marci@368: typedef Graph::NodeIt NodeIt; marci@368: typedef Graph::Edge Edge; marci@368: typedef Graph::EdgeIt EdgeIt; marci@368: typedef Graph::OutEdgeIt OutEdgeIt; marci@368: marci@368: Graph g; marci@409: // std::vector s_nodes; marci@409: // std::vector t_nodes; marci@409: // for (int i=0; i<3; ++i) s_nodes.push_back(g.addNode()); marci@409: // for (int i=0; i<3; ++i) t_nodes.push_back(g.addNode()); marci@409: // g.addEdge(s_nodes[0], t_nodes[2]); marci@409: // g.addEdge(t_nodes[1], s_nodes[2]); marci@409: // g.addEdge(s_nodes[0], t_nodes[1]); marci@409: marci@409: // Graph::NodeMap ref_map(g, -1); marci@409: // IterableBoolMap< Graph::NodeMap > bipartite_map(ref_map); marci@409: // for (int i=0; i<3; ++i) bipartite_map.insert(s_nodes[i], false); marci@409: // for (int i=0; i<3; ++i) bipartite_map.insert(t_nodes[i], true); marci@409: marci@409: std::vector nodes; marci@409: for (int i=0; i<3; ++i) nodes.push_back(g.addNode()); marci@409: for (int i=3; i<6; ++i) nodes.push_back(g.addNode()); marci@409: g.addEdge(nodes[0], nodes[3+2]); marci@409: g.addEdge(nodes[3+1], nodes[2]); marci@409: g.addEdge(nodes[0], nodes[3+1]); marci@368: marci@368: Graph::NodeMap ref_map(g, -1); marci@368: IterableBoolMap< Graph::NodeMap > bipartite_map(ref_map); marci@409: for (int i=0; i<3; ++i) bipartite_map.insert(nodes[i], false); marci@409: for (int i=3; i<6; ++i) bipartite_map.insert(nodes[i], true); marci@409: marci@409: Graph::Node u; marci@409: std::cout << "These nodes will be in S:\n"; marci@409: //FIXME azert kellene ++, es invalid vizsgalat u-bol, hogy ezt le lehessen marci@409: //irni 1etlen FOR_EACH-csel. marci@409: for (bipartite_map.first(u, false); g.valid(u); bipartite_map.next(u)) marci@409: std::cout << u << " "; marci@409: std::cout << "\n"; marci@409: std::cout << "These nodes will be in T:\n"; marci@409: for (bipartite_map.first(u, true); g.valid(u); bipartite_map.next(u)) marci@409: std::cout << u << " "; marci@409: std::cout << "\n"; marci@409: marci@368: typedef BipartiteGraphWrapper BGW; marci@368: BGW bgw(g, bipartite_map); marci@409: marci@409: std::cout << "Nodes by NodeIt:\n"; marci@409: FOR_EACH_LOC(BGW::NodeIt, n, bgw) { marci@409: std::cout << n << " "; marci@409: } marci@409: std::cout << "\n"; marci@409: std::cout << "Nodes in S by ClassNodeIt:\n"; marci@409: FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.S_CLASS) { marci@409: std::cout << n << " "; marci@409: } marci@409: std::cout << "\n"; marci@409: std::cout << "Nodes in T by ClassNodeIt:\n"; marci@409: FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.T_CLASS) { marci@409: std::cout << n << " "; marci@409: } marci@409: std::cout << "\n"; marci@409: std::cout << "Edges of the bipartite graph:\n"; marci@368: FOR_EACH_LOC(BGW::EdgeIt, e, bgw) { marci@368: std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl; marci@368: } marci@368: marci@379: BGW::NodeMap dbyj(bgw); marci@379: BGW::EdgeMap dbyxcj(bgw); marci@368: marci@379: typedef stGraphWrapper stGW; marci@379: stGW stgw(bgw); marci@379: ConstMap const1map(1); marci@379: stGW::NodeMap ize(stgw); marci@379: stGW::EdgeMap flow(stgw); marci@379: marci@379: BfsIterator< BGW, BGW::NodeMap > bfs(bgw); marci@379: Graph::NodeIt si; marci@379: Graph::Node s; marci@379: s=g.first(si); marci@379: bfs.pushAndSetReached(BGW::Node(s)); marci@409: while (!bfs.finished()) { ++bfs; } marci@379: marci@409: FOR_EACH_LOC(stGW::NodeIt, n, stgw) { marci@409: std::cout << "out-edges of " << n << ":\n"; marci@409: FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) { marci@409: std::cout << " " << e << "\n"; marci@409: std::cout << " aNode: " << stgw.aNode(e) << "\n"; marci@409: std::cout << " bNode: " << stgw.bNode(e) << "\n"; marci@409: } marci@409: std::cout << "in-edges of " << n << ":\n"; marci@409: FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) { marci@409: std::cout << " " << e << "\n"; marci@409: std::cout << " aNode: " << stgw.aNode(e) << "\n"; marci@409: std::cout << " bNode: " << stgw.bNode(e) << "\n"; marci@409: } marci@409: } marci@409: std::cout << "Edges of the stGraphWrapper:\n"; marci@409: FOR_EACH_LOC(stGW::EdgeIt, n, stgw) { marci@409: std::cout << " " << n << "\n"; marci@409: } marci@379: marci@409: stGW::NodeMap b(stgw); marci@409: FOR_EACH_LOC(stGW::NodeIt, n, stgw) { marci@409: std::cout << n << ": " << b[n] <<"\n"; marci@409: } marci@409: marci@409: std::cout << "Bfs from s: \n"; marci@409: BfsIterator< stGW, stGW::NodeMap > bfs_stgw(stgw); marci@409: bfs_stgw.pushAndSetReached(stgw.S_NODE); marci@409: while (!bfs_stgw.finished()) { marci@409: std::cout << " " << stGW::OutEdgeIt(bfs_stgw) << "\n"; marci@409: ++bfs_stgw; marci@409: } marci@379: marci@379: MaxFlow, stGW::EdgeMap > marci@379: max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow); marci@409: while (max_flow_test.augmentOnShortestPath()) { } marci@393: marci@393: std::cout << max_flow_test.flowValue() << std::endl; marci@368: marci@368: return 0; marci@368: }