Changeset 902:309d81806228 in lemon-0.x for src/work/marci/bipartite_graph_wrapper_test.cc
- Timestamp:
- 09/22/04 14:25:50 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1210
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/marci/bipartite_graph_wrapper_test.cc
r768 r902 4 4 #include <vector> 5 5 6 #include <sage_graph.h>7 //#include <smart_graph.h>6 //#include <sage_graph.h> 7 #include <hugo/smart_graph.h> 8 8 //#include <dimacs.h> 9 9 #include <hugo/time_measure.h> 10 #include <for_each_macros.h>10 //#include <for_each_macros.h> 11 11 #include <bfs_dfs.h> 12 12 #include <hugo/graph_wrapper.h> 13 13 #include <bipartite_graph_wrapper.h> 14 14 #include <hugo/maps.h> 15 #include <hugo/ max_flow.h>15 #include <hugo/preflow.h> 16 16 #include <augmenting_flow.h> 17 18 using std::cout; 19 using std::endl; 17 20 18 21 using namespace hugo; 19 22 20 23 int main() { 21 typedef UndirSageGraph Graph; 24 //typedef UndirSageGraph Graph; 25 typedef SmartGraph Graph; 22 26 typedef Graph::Node Node; 23 27 typedef Graph::NodeIt NodeIt; … … 53 57 54 58 Graph::Node u; 55 std::cout << "These nodes will be in S:\n";59 cout << "These nodes will be in S:" << endl; 56 60 //FIXME azert kellene ++, es invalid vizsgalat u-bol, hogy ezt le lehessen 57 61 //irni 1etlen FOR_EACH-csel. 58 for (bipartite_map.first(u, false); g.valid(u); bipartite_map.next(u))59 std::cout << u<< " ";60 std::cout << "\n";61 std::cout << "These nodes will be in T:\n";62 for (bipartite_map.first(u, true); g.valid(u); bipartite_map.next(u))63 std::cout << u<< " ";64 std::cout << "\n";62 for (bipartite_map.first(u, false); u!=INVALID; bipartite_map.next(u)) 63 cout << g.id(u) << " "; 64 cout << endl; 65 cout << "These nodes will be in T:" << endl; 66 for (bipartite_map.first(u, true); u!=INVALID; bipartite_map.next(u)) 67 cout << g.id(u) << " "; 68 cout << endl; 65 69 66 70 typedef BipartiteGraphWrapper<Graph> BGW; 67 71 BGW bgw(g, bipartite_map); 68 72 69 std::cout << "Nodes by NodeIt:\n"; 70 FOR_EACH_LOC(BGW::NodeIt, n, bgw) { 71 std::cout << n << " "; 72 } 73 std::cout << "\n"; 74 std::cout << "Nodes in S by ClassNodeIt:\n"; 75 FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.S_CLASS) { 76 std::cout << n << " "; 77 } 78 std::cout << "\n"; 79 std::cout << "Nodes in T by ClassNodeIt:\n"; 80 FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.T_CLASS) { 81 std::cout << n << " "; 82 } 83 std::cout << "\n"; 84 std::cout << "Edges of the bipartite graph:\n"; 85 FOR_EACH_LOC(BGW::EdgeIt, e, bgw) { 86 std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl; 87 } 73 cout << "Nodes by NodeIt:" << endl; 74 for (BGW::NodeIt n(bgw); n!=INVALID; ++n) 75 cout << g.id(n) << " "; 76 cout << endl; 77 78 cout << "Nodes in S by ClassNodeIt:" << endl; 79 for (BGW::ClassNodeIt n(bgw, bgw.S_CLASS); n!=INVALID; ++n) 80 cout << g.id(n) << " "; 81 cout << endl; 82 83 cout << "Nodes in T by ClassNodeIt:" << endl; 84 for (BGW::ClassNodeIt n(bgw, bgw.T_CLASS); n!=INVALID; ++n) 85 cout << g.id(n) << " "; 86 cout << endl; 87 88 cout << "Edges of the bipartite graph:" << endl; 89 for (BGW::EdgeIt e(bgw); e!=INVALID; ++e) 90 cout << g.id(bgw.tail(e)) << "->" << g.id(bgw.head(e)) << endl; 88 91 89 92 BGW::NodeMap<int> dbyj(bgw); 90 93 BGW::EdgeMap<int> dbyxcj(bgw); 91 94 92 typedef stBipartiteGraphWrapper<BGW> stGW;93 stGW stgw(bgw);94 ConstMap<stGW::Edge, int> const1map(1);95 stGW::NodeMap<int> ize(stgw);96 stGW::EdgeMap<int> flow(stgw);95 // typedef stBipartiteGraphWrapper<BGW> stGW; 96 // stGW stgw(bgw); 97 // ConstMap<stGW::Edge, int> const1map(1); 98 // stGW::NodeMap<int> ize(stgw); 99 // stGW::EdgeMap<int> flow(stgw); 97 100 98 BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);99 Graph::NodeIt si;100 Graph::Node s;101 s=g.first(si);102 bfs.pushAndSetReached(BGW::Node(s));103 while (!bfs.finished()) { ++bfs; }101 // BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw); 102 // Graph::NodeIt si; 103 // Graph::Node s; 104 // s=g.first(si); 105 // bfs.pushAndSetReached(BGW::Node(s)); 106 // while (!bfs.finished()) { ++bfs; } 104 107 105 FOR_EACH_LOC(stGW::NodeIt, n, stgw) {106 std::cout << "out-edges of " << n << ":\n";107 FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) {108 std::cout << " " << e << "\n";109 std::cout << " aNode: " << stgw.aNode(e) << "\n";110 std::cout << " bNode: " << stgw.bNode(e) << "\n";111 }112 std::cout << "in-edges of " << n << ":\n";113 FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) {114 std::cout << " " << e << "\n";115 std::cout << " aNode: " << stgw.aNode(e) << "\n";116 std::cout << " bNode: " << stgw.bNode(e) << "\n";117 }118 }119 std::cout << "Edges of the stGraphWrapper:\n";120 FOR_EACH_LOC(stGW::EdgeIt, n, stgw) {121 std::cout << " " << n << "\n";122 }108 // FOR_EACH_LOC(stGW::NodeIt, n, stgw) { 109 // cout << "out-edges of " << n << ":" << endl; 110 // FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) { 111 // cout << " " << e << endl; 112 // cout << " aNode: " << stgw.aNode(e) << endl; 113 // cout << " bNode: " << stgw.bNode(e) << endl; 114 // } 115 // cout << "in-edges of " << n << ":" << endl; 116 // FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) { 117 // cout << " " << e << endl; 118 // cout << " aNode: " << stgw.aNode(e) << endl; 119 // cout << " bNode: " << stgw.bNode(e) << endl; 120 // } 121 // } 122 // cout << "Edges of the stGraphWrapper:" << endl; 123 // FOR_EACH_LOC(stGW::EdgeIt, n, stgw) { 124 // cout << " " << n << endl; 125 // } 123 126 124 stGW::NodeMap<bool> b(stgw);125 FOR_EACH_LOC(stGW::NodeIt, n, stgw) {126 std::cout << n << ": " << b[n] <<"\n";127 }127 // stGW::NodeMap<bool> b(stgw); 128 // FOR_EACH_LOC(stGW::NodeIt, n, stgw) { 129 // cout << n << ": " << b[n] << endl; 130 // } 128 131 129 std::cout << "Bfs from s: \n";130 BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw);131 bfs_stgw.pushAndSetReached(stgw.S_NODE);132 while (!bfs_stgw.finished()) {133 std::cout << " " << stGW::OutEdgeIt(bfs_stgw) << "\n";134 ++bfs_stgw;135 }132 // cout << "Bfs from s:" << endl; 133 // BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw); 134 // bfs_stgw.pushAndSetReached(stgw.S_NODE); 135 // while (!bfs_stgw.finished()) { 136 // cout << " " << stGW::OutEdgeIt(bfs_stgw) << endl; 137 // ++bfs_stgw; 138 // } 136 139 137 AugmentingFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >138 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);139 while (max_flow_test.augmentOnShortestPath()) { }140 // AugmentingFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 141 // max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow); 142 // while (max_flow_test.augmentOnShortestPath()) { } 140 143 141 std::cout << max_flow_test.flowValue() << std::endl;144 // cout << max_flow_test.flowValue() << std::endl; 142 145 143 146 return 0;
Note: See TracChangeset
for help on using the changeset viewer.