1 // -*- mode:c++ -*- |
|
2 |
|
3 #ifndef EDMONDS_KARP_HH |
|
4 #define EDMONDS_KARP_HH |
|
5 |
|
6 #include <queue> |
|
7 |
|
8 //#include <marci_property_vector.hh> |
|
9 |
|
10 #include <algorithm> |
|
11 |
|
12 //#include <bfs_iterator.hh> |
|
13 |
|
14 namespace lemon { |
|
15 template <typename Graph, typename FlowMap, typename CapacityMap> |
|
16 typename FlowMap::Value maxFlow(Graph &G, |
|
17 FlowMap &f, |
|
18 CapacityMap &c, |
|
19 typename Graph::NodeIt s, |
|
20 typename Graph::NodeIt t) |
|
21 { |
|
22 typedef typename Graph::NodeIt NodeIt; |
|
23 typedef typename Graph::EachNodeIt EachNodeIt; |
|
24 typedef typename Graph::EdgeIt EdgeIt; |
|
25 typedef typename Graph::EachEdgeIt EachEdgeIt; |
|
26 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
27 typedef typename Graph::InEdgeIt InEdgeIt; |
|
28 typedef typename FlowMap::Value T; |
|
29 |
|
30 T flow_val = 0; |
|
31 T aug_val; |
|
32 |
|
33 for(EachEdgeIt e(G);G.valid(e);G.goNext(e)) |
|
34 f.set(e,0); |
|
35 |
|
36 std::queue<NodeIt> bfs_queue; |
|
37 typename Graph::NodeMap<int> visited(G); //0: unvisited, |
|
38 //1: reached by a forward edge |
|
39 //2: reached by a backward edge |
|
40 //3: it is node s |
|
41 typename Graph::NodeMap<EdgeIt> tree(G); |
|
42 |
|
43 NodeIt gn; //FIXME: it might be too global for some people... |
|
44 |
|
45 augment: |
|
46 |
|
47 for(EachNodeIt n(G);G.valid(n);G.goNext(n)) |
|
48 visited.set(n,0); |
|
49 |
|
50 visited.set(s,3); |
|
51 |
|
52 //There must be a better way to do this: |
|
53 while(!bfs_queue.empty()) bfs_queue.pop(); |
|
54 |
|
55 bfs_queue.push(s); |
|
56 |
|
57 while(!bfs_queue.empty() && !visited.get(t)) |
|
58 { |
|
59 NodeIt n(bfs_queue.front()); |
|
60 bfs_queue.pop(); |
|
61 for(OutEdgeIt e(G,n);G.valid(e);G.goNext(e)) |
|
62 if(f.get(e)<c.get(e) && //FIXME: < |
|
63 !visited.get(G.bNode(e))) |
|
64 { |
|
65 NodeIt nn(G.bNode(e)); //It improves nothing |
|
66 tree.set(nn,e); |
|
67 visited.set(nn,1); |
|
68 bfs_queue.push(nn); |
|
69 } |
|
70 for(InEdgeIt e(G,n);G.valid(e);G.goNext(e)) |
|
71 if(f.get(e)>0 && //FIXME: > |
|
72 !visited.get(G.bNode(e))) |
|
73 { |
|
74 NodeIt nn(G.bNode(e)); |
|
75 tree.set(nn,e); |
|
76 visited.set(nn,2); |
|
77 bfs_queue.push(nn); |
|
78 } |
|
79 } |
|
80 |
|
81 if(!visited.get(t)) return flow_val; |
|
82 |
|
83 // Augmenting value computation |
|
84 aug_val = visited.get(t)==1 ? |
|
85 c.get(tree.get(t))-f.get(tree.get(t)) : f.get(tree.get(t)); |
|
86 //FIXME: I would need 'G.opposite(e,n)' |
|
87 gn = visited.get(t)==1 ? G.source(tree.get(t)) : G.target(tree.get(t)); |
|
88 while(gn!=s) if(visited.get(gn)==1) |
|
89 { |
|
90 //FIXME: nonstandard gcc extension! |
|
91 aug_val <?= c.get(tree.get(gn))-f.get(tree.get(gn)); |
|
92 gn=G.source(tree.get(gn)); |
|
93 } |
|
94 else { |
|
95 //FIXME: nonstandard gcc extension! |
|
96 aug_val <?= f.get(tree.get(gn)); |
|
97 gn=G.target(tree.get(gn)); |
|
98 } |
|
99 |
|
100 // The augmentation itself |
|
101 gn = t; |
|
102 while(gn!=s) if(visited.get(gn)==1) |
|
103 { |
|
104 f.set(tree.get(gn),f.get(tree.get(gn))+aug_val); |
|
105 gn=G.source(tree.get(gn)); |
|
106 } |
|
107 else { |
|
108 f.set(tree.get(gn),f.get(tree.get(gn))-aug_val); |
|
109 gn=G.target(tree.get(gn)); |
|
110 } |
|
111 |
|
112 flow_val+=aug_val; |
|
113 |
|
114 goto augment; // Vivat goto forever! |
|
115 } |
|
116 |
|
117 } // namespace lemon |
|
118 |
|
119 #endif //EDMONDS_KARP_HH |
|