|
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 marci { |
|
15 template <typename Graph, typename FlowMap, typename CapacityMap> |
|
16 typename FlowMap::ValueType 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::EdgeIt EdgeIt; |
|
24 typedef typename Graph::EachEdgeIt EachEdgeIt; |
|
25 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
26 typedef typename Graph::InEdgeIt InEdgeIt; |
|
27 typedef typename FlowMap::ValueType T; |
|
28 |
|
29 T flow_val = 0; |
|
30 T aug_val; |
|
31 |
|
32 for(EachEdgeIt e(G);G.valid(e);G.next(e)) |
|
33 f.set(e,0); |
|
34 |
|
35 std::queue<NodeIt> bfs_queue; |
|
36 typename Graph::NodeMap<int> visited(G); //0: unvisited, |
|
37 //1: reached by a forward edge |
|
38 //2: reached by a backward edge |
|
39 //3: it is node s |
|
40 typename Graph::NodeMap<EdgeIt> tree(G); |
|
41 |
|
42 NodeIt gn; //FIXME: it might be too global for some people... |
|
43 |
|
44 augment: |
|
45 |
|
46 for(NodeIt n(G);G.valid(n);G.next(n)) |
|
47 visited.set(n,0); |
|
48 |
|
49 visited.set(s,3); |
|
50 |
|
51 //There must be a better way to do this: |
|
52 while(!bfs_queue.empty()) bfs_queue.pop(); |
|
53 |
|
54 bfs_queue.push(s); |
|
55 |
|
56 while(!bfs_queue.empty() && !visited.get(t)) |
|
57 { |
|
58 NodeIt n(bfs_queue.front()); |
|
59 for(OutEdgeIt e(G,n);G.valid(e);G.next(e)) |
|
60 if(f.get(e)<c.get(e) && //FIXME: < |
|
61 !visited.get(G.bNode(e))) |
|
62 { |
|
63 tree.set(G.bNode(e),e); |
|
64 visited.set(G.bNode(e),1); |
|
65 } |
|
66 for(InEdgeIt e(G,n);G.valid(e);G.next(e)) |
|
67 if(f.get(e)>0 && //FIXME: > |
|
68 !visited.get(G.bNode(e))) |
|
69 { |
|
70 tree.set(G.bNode(e),e); |
|
71 visited.set(G.bNode(e),2); |
|
72 } |
|
73 } |
|
74 |
|
75 if(!visited.get(t)) return flow_val; |
|
76 |
|
77 // Augmenting value computation |
|
78 aug_val = visited.get(t)==2 ? |
|
79 c.get(tree.get(t))-f.get(tree.get(t)) : f.get(tree.get(t)); |
|
80 //FIXME: I would need 'G.opposite(e,n)' |
|
81 gn = visited.get(t)==2 ? G.from(tree.get(t)) : G.to(tree.get(t)); |
|
82 while(gn!=s) if(visited.get(gn)==2) |
|
83 { |
|
84 //FIXME: nonstandars. gcc extension! |
|
85 aug_val <?= c.get(tree.get(gn))-f.get(tree.get(gn)); |
|
86 gn=G.from(tree.get(gn)); |
|
87 } |
|
88 else { |
|
89 //FIXME: nonstandars. gcc extension! |
|
90 aug_val <?= f.get(tree.get(gn)); |
|
91 gn=G.from(tree.get(gn)); |
|
92 } |
|
93 |
|
94 // The augmentation itself |
|
95 gn = t; |
|
96 while(gn!=s) if(visited.get(gn)==2) |
|
97 { |
|
98 f.set(tree.get(gn),f.get(tree.get(gn))+aug_val); |
|
99 gn=G.from(tree.get(gn)); |
|
100 } |
|
101 else { |
|
102 f.set(tree.get(gn),f.get(tree.get(gn))-aug_val); |
|
103 gn=G.from(tree.get(gn)); |
|
104 } |
|
105 |
|
106 flow_val+=aug_val; |
|
107 |
|
108 goto augment; // Vivat goto forever! |
|
109 } |
|
110 |
|
111 } // namespace marci |
|
112 |
|
113 #endif //EDMONDS_KARP_HH |