Changeset 409:7ab7f083760a in lemon0.x for src/work/marci/bipartite_graph_wrapper_test.cc
 Timestamp:
 04/26/04 11:54:24 (19 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@542
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci/bipartite_graph_wrapper_test.cc
r393 r409 25 25 26 26 Graph g; 27 //Node s, t; 28 //Graph::EdgeMap<int> cap(g); 29 //readDimacsMaxFlow(std::cin, g, s, t, cap); 30 std::vector<Graph::Node> s_nodes; 31 std::vector<Graph::Node> t_nodes; 32 for (int i=0; i<3; ++i) s_nodes.push_back(g.addNode()); 33 for (int i=0; i<3; ++i) t_nodes.push_back(g.addNode()); 34 g.addEdge(s_nodes[0], t_nodes[2]); 35 g.addEdge(t_nodes[1], s_nodes[2]); 27 // std::vector<Graph::Node> s_nodes; 28 // std::vector<Graph::Node> t_nodes; 29 // for (int i=0; i<3; ++i) s_nodes.push_back(g.addNode()); 30 // for (int i=0; i<3; ++i) t_nodes.push_back(g.addNode()); 31 // g.addEdge(s_nodes[0], t_nodes[2]); 32 // g.addEdge(t_nodes[1], s_nodes[2]); 33 // g.addEdge(s_nodes[0], t_nodes[1]); 34 35 // Graph::NodeMap<int> ref_map(g, 1); 36 // IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map); 37 // for (int i=0; i<3; ++i) bipartite_map.insert(s_nodes[i], false); 38 // for (int i=0; i<3; ++i) bipartite_map.insert(t_nodes[i], true); 39 40 std::vector<Graph::Node> nodes; 41 for (int i=0; i<3; ++i) nodes.push_back(g.addNode()); 42 for (int i=3; i<6; ++i) nodes.push_back(g.addNode()); 43 g.addEdge(nodes[0], nodes[3+2]); 44 g.addEdge(nodes[3+1], nodes[2]); 45 g.addEdge(nodes[0], nodes[3+1]); 36 46 37 47 Graph::NodeMap<int> ref_map(g, 1); 38 48 IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map); 39 for (int i=0; i<3; ++i) bipartite_map.insert(s_nodes[i], false); 40 for (int i=0; i<3; ++i) bipartite_map.insert(t_nodes[i], true); 49 for (int i=0; i<3; ++i) bipartite_map.insert(nodes[i], false); 50 for (int i=3; i<6; ++i) bipartite_map.insert(nodes[i], true); 51 52 Graph::Node u; 53 std::cout << "These nodes will be in S:\n"; 54 //FIXME azert kellene ++, es invalid vizsgalat ubol, hogy ezt le lehessen 55 //irni 1etlen FOR_EACHcsel. 56 for (bipartite_map.first(u, false); g.valid(u); bipartite_map.next(u)) 57 std::cout << u << " "; 58 std::cout << "\n"; 59 std::cout << "These nodes will be in T:\n"; 60 for (bipartite_map.first(u, true); g.valid(u); bipartite_map.next(u)) 61 std::cout << u << " "; 62 std::cout << "\n"; 63 41 64 typedef BipartiteGraphWrapper<Graph> BGW; 42 65 BGW bgw(g, bipartite_map); 66 67 std::cout << "Nodes by NodeIt:\n"; 68 FOR_EACH_LOC(BGW::NodeIt, n, bgw) { 69 std::cout << n << " "; 70 } 71 std::cout << "\n"; 72 std::cout << "Nodes in S by ClassNodeIt:\n"; 73 FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.S_CLASS) { 74 std::cout << n << " "; 75 } 76 std::cout << "\n"; 77 std::cout << "Nodes in T by ClassNodeIt:\n"; 78 FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.T_CLASS) { 79 std::cout << n << " "; 80 } 81 std::cout << "\n"; 82 std::cout << "Edges of the bipartite graph:\n"; 43 83 FOR_EACH_LOC(BGW::EdgeIt, e, bgw) { 44 84 std::cout << bgw.tail(e) << ">" << bgw.head(e) << std::endl; … … 59 99 s=g.first(si); 60 100 bfs.pushAndSetReached(BGW::Node(s)); 61 while (!bfs.finished()) ++bfs;101 while (!bfs.finished()) { ++bfs; } 62 102 63 BGW::EdgeMap<bool> cap(bgw); 64 BGW::EdgeMap<bool> flow1(bgw); 103 FOR_EACH_LOC(stGW::NodeIt, n, stgw) { 104 std::cout << "outedges of " << n << ":\n"; 105 FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) { 106 std::cout << " " << e << "\n"; 107 std::cout << " aNode: " << stgw.aNode(e) << "\n"; 108 std::cout << " bNode: " << stgw.bNode(e) << "\n"; 109 } 110 std::cout << "inedges of " << n << ":\n"; 111 FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) { 112 std::cout << " " << e << "\n"; 113 std::cout << " aNode: " << stgw.aNode(e) << "\n"; 114 std::cout << " bNode: " << stgw.bNode(e) << "\n"; 115 } 116 } 117 std::cout << "Edges of the stGraphWrapper:\n"; 118 FOR_EACH_LOC(stGW::EdgeIt, n, stgw) { 119 std::cout << " " << n << "\n"; 120 } 65 121 66 typedef ResGraphWrapper< BGW, int, BGW::EdgeMap<bool>, BGW::EdgeMap<bool> > 67 RBGW; 68 RBGW rbgw(bgw, cap, flow1); 69 RBGW::NodeMap<int> u(rbgw); 122 stGW::NodeMap<bool> b(stgw); 123 FOR_EACH_LOC(stGW::NodeIt, n, stgw) { 124 std::cout << n << ": " << b[n] <<"\n"; 125 } 126 127 std::cout << "Bfs from s: \n"; 128 BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw); 129 bfs_stgw.pushAndSetReached(stgw.S_NODE); 130 while (!bfs_stgw.finished()) { 131 std::cout << " " << stGW::OutEdgeIt(bfs_stgw) << "\n"; 132 ++bfs_stgw; 133 } 70 134 71 72 135 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 73 136 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow); 74 max_flow_test.augmentOnShortestPath(); 75 max_flow_test.augmentOnShortestPath(); 137 while (max_flow_test.augmentOnShortestPath()) { } 76 138 77 139 std::cout << max_flow_test.flowValue() << std::endl;
Note: See TracChangeset
for help on using the changeset viewer.