39 typedef BipartiteGraphWrapper<Graph> BGW; |
41 typedef BipartiteGraphWrapper<Graph> BGW; |
40 BGW bgw(g, bipartite_map); |
42 BGW bgw(g, bipartite_map); |
41 FOR_EACH_LOC(BGW::EdgeIt, e, bgw) { |
43 FOR_EACH_LOC(BGW::EdgeIt, e, bgw) { |
42 std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl; |
44 std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl; |
43 } |
45 } |
44 // Graph::NodeMap<OutEdgeIt> pred(G); |
|
45 // Timer ts; |
|
46 // { |
|
47 // ts.reset(); |
|
48 // Graph::NodeMap<bool> reached(G); |
|
49 // reached.set(s, true); |
|
50 // pred.set(s, INVALID); |
|
51 // std::queue<Node> bfs_queue; |
|
52 // bfs_queue.push(t); |
|
53 // while (!bfs_queue.empty()) { |
|
54 // Node v=bfs_queue.front(); |
|
55 // bfs_queue.pop(); |
|
56 // OutEdgeIt e; |
|
57 // for(G.first(e,v); G.valid(e); G.next(e)) { |
|
58 // Node w=G.head(e); |
|
59 // if (!reached[w]) { |
|
60 // bfs_queue.push(w); |
|
61 // reached.set(w, true); |
|
62 // pred.set(w, e); |
|
63 // } |
|
64 // } |
|
65 // } |
|
66 |
46 |
67 // std::cout << ts << std::endl; |
47 BGW::NodeMap<int> dbyj(bgw); |
68 // } |
48 BGW::EdgeMap<int> dbyxcj(bgw); |
69 |
49 |
70 // { |
50 typedef stGraphWrapper<BGW> stGW; |
71 // ts.reset(); |
51 stGW stgw(bgw); |
72 // BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G); |
52 ConstMap<stGW::Edge, int> const1map(1); |
73 // bfs.pushAndSetReached(s); |
53 stGW::NodeMap<int> ize(stgw); |
74 // pred.set(s, INVALID); |
54 stGW::EdgeMap<int> flow(stgw); |
75 // while (!bfs.finished()) { |
55 |
76 // ++bfs; |
56 BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw); |
77 // if (G.valid(bfs) && bfs.isBNodeNewlyReached()) |
57 Graph::NodeIt si; |
78 // pred.set(bfs.bNode(), bfs); |
58 Graph::Node s; |
79 // } |
59 s=g.first(si); |
80 // std::cout << ts << std::endl; |
60 bfs.pushAndSetReached(BGW::Node(s)); |
81 // } |
61 while (!bfs.finished()) ++bfs; |
|
62 |
|
63 BGW::EdgeMap<bool> cap(bgw); |
|
64 BGW::EdgeMap<bool> flow1(bgw); |
|
65 |
|
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); |
|
70 |
|
71 |
|
72 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > |
|
73 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow); |
|
74 max_flow_test.augmentOnShortestPath(); |
82 |
75 |
83 return 0; |
76 return 0; |
84 } |
77 } |