| changeset 78 | ecc1171307be |
| parent 72 | e560867cbe79 |
| child 83 | efafe79a88d3 |
| 0:1ed0c10bae66 | 1:1fa8019deecd |
|---|---|
27 |
27 |
28 #include <algorithm> |
28 #include <algorithm> |
29 #include <vector> |
29 #include <vector> |
30 #include <stack> |
30 #include <stack> |
31 |
31 |
32 #include <reverse_bfs.hh> |
32 #include <reverse_bfs.h> |
33 |
33 |
34 namespace marci { |
34 namespace marci { |
35 |
35 |
36 template <typename Graph, typename T, typename FlowMap, typename CapacityMap> |
36 template <typename Graph, typename T> |
37 class preflow_push_hl { |
37 class preflow_push_hl { |
38 |
38 |
39 typedef typename Graph::NodeIt NodeIt; |
39 typedef typename Graph::NodeIt NodeIt; |
40 typedef typename Graph::EdgeIt EdgeIt; |
40 typedef typename Graph::EdgeIt EdgeIt; |
41 typedef typename Graph::EachNodeIt EachNodeIt; |
41 typedef typename Graph::EachNodeIt EachNodeIt; |
45 |
45 |
46 |
46 |
47 Graph& G; |
47 Graph& G; |
48 NodeIt s; |
48 NodeIt s; |
49 NodeIt t; |
49 NodeIt t; |
50 Graph::EdgeMap<T> flow; |
50 typename Graph::EdgeMap<T> flow; |
51 Graph::EdgeMap<T> capacity; |
51 typename Graph::EdgeMap<T> capacity; |
52 T value; |
52 T value; |
53 Graph::NodeMap<bool> mincutvector; |
53 typename Graph::NodeMap<bool> mincutvector; |
54 |
54 |
55 |
55 |
56 public: |
56 public: |
57 |
57 |
58 preflow_push_hl(Graph& _G, NodeIt _s, NodeIt _t, |
58 preflow_push_hl(Graph& _G, NodeIt _s, NodeIt _t, |
59 Graph::EdgeMap<T>& _capacity) : |
59 typename Graph::EdgeMap<T>& _capacity) : |
60 G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), mincutvector(_G, true) { } |
60 G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), mincutvector(_G, true) { } |
61 |
61 |
62 |
62 |
63 |
63 |
64 |
64 |
66 The run() function runs the highest label preflow-push, |
66 The run() function runs the highest label preflow-push, |
67 running time: O(n^2\sqrt(m)) |
67 running time: O(n^2\sqrt(m)) |
68 */ |
68 */ |
69 void run() { |
69 void run() { |
70 |
70 |
71 Graph::NodeMap<int> level(G); //level of Node |
71 typename Graph::NodeMap<int> level(G); //level of Node |
72 Graph::NodeMap<T> excess(G); //excess of Node |
72 typename Graph::NodeMap<T> excess(G); //excess of Node |
73 |
73 |
74 int n=G.nodeNum(); //number of Nodes |
74 int n=G.nodeNum(); //number of Nodes |
75 int b=n; |
75 int b=n; |
76 /*b is a bound on the highest level of an active Node. In the beginning it is at most n-2.*/ |
76 /*b is a bound on the highest level of an active Node. In the beginning it is at most n-2.*/ |
77 |
77 |
80 |
80 |
81 |
81 |
82 |
82 |
83 /*Reverse_bfs from t, to find the starting level.*/ |
83 /*Reverse_bfs from t, to find the starting level.*/ |
84 |
84 |
85 reverse_bfs<list_graph> bfs(G, t); |
85 reverse_bfs<Graph> bfs(G, t); |
86 bfs.run(); |
86 bfs.run(); |
87 for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) { |
87 for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) { |
88 level.set(v, bfs.dist(v)); |
88 level.set(v, bfs.dist(v)); |
89 //std::cout << "the level of " << v << " is " << bfs.dist(v); |
89 //std::cout << "the level of " << v << " is " << bfs.dist(v); |
90 } |
90 } |
266 |
266 |
267 /* |
267 /* |
268 Returns the maximum flow x found by the algorithm. |
268 Returns the maximum flow x found by the algorithm. |
269 */ |
269 */ |
270 |
270 |
271 EdgeMap<graph_type, T> allflow() { |
271 typename Graph::EdgeMap<T> allflow() { |
272 return flow; |
272 return flow; |
273 } |
273 } |
274 |
274 |
275 |
275 |
276 |
276 |
277 /* |
277 /* |
278 Returns a minimum cut by using a reverse bfs from t in the residual graph. |
278 Returns a minimum cut by using a reverse bfs from t in the residual graph. |
279 */ |
279 */ |
280 |
280 |
281 NodeMap<graph_type, bool> mincut() { |
281 typename Graph::NodeMap<bool> mincut() { |
282 |
282 |
283 std::queue<NodeIt> queue; |
283 std::queue<NodeIt> queue; |
284 |
284 |
285 mincutvector.set(t,false); |
285 mincutvector.set(t,false); |
286 queue.push(t); |
286 queue.push(t); |
308 } |
308 } |
309 |
309 |
310 return mincutvector; |
310 return mincutvector; |
311 |
311 |
312 } |
312 } |
313 |
|
314 |
|
315 }; |
313 }; |
316 }//namespace marci |
314 }//namespace marci |
317 #endif |
315 #endif |
318 |
316 |
319 |
317 |