equal
deleted
inserted
replaced
14 namespace marci { |
14 namespace marci { |
15 template <typename Graph, typename FlowMap, typename CapacityMap> |
15 template <typename Graph, typename FlowMap, typename CapacityMap> |
16 typename FlowMap::ValueType maxFlow(Graph &G, |
16 typename FlowMap::ValueType maxFlow(Graph &G, |
17 FlowMap &f, |
17 FlowMap &f, |
18 CapacityMap &c, |
18 CapacityMap &c, |
19 typename Graph::NodeIt s, |
19 typename Graph::EachNodeIt s, |
20 typename Graph::NodeIt t) |
20 typename Graph::EachNodeIt t) |
21 { |
21 { |
22 typedef typename Graph::NodeIt NodeIt; |
22 typedef typename Graph::EachNodeIt EachNodeIt; |
23 typedef typename Graph::EdgeIt EdgeIt; |
23 typedef typename Graph::EdgeIt EdgeIt; |
24 typedef typename Graph::EachEdgeIt EachEdgeIt; |
24 typedef typename Graph::EachEdgeIt EachEdgeIt; |
25 typedef typename Graph::OutEdgeIt OutEdgeIt; |
25 typedef typename Graph::OutEdgeIt OutEdgeIt; |
26 typedef typename Graph::InEdgeIt InEdgeIt; |
26 typedef typename Graph::InEdgeIt InEdgeIt; |
27 typedef typename FlowMap::ValueType T; |
27 typedef typename FlowMap::ValueType T; |
30 T aug_val; |
30 T aug_val; |
31 |
31 |
32 for(EachEdgeIt e(G);G.valid(e);G.next(e)) |
32 for(EachEdgeIt e(G);G.valid(e);G.next(e)) |
33 f.set(e,0); |
33 f.set(e,0); |
34 |
34 |
35 std::queue<NodeIt> bfs_queue; |
35 std::queue<EachNodeIt> bfs_queue; |
36 typename Graph::NodeMap<int> visited(G); //0: unvisited, |
36 typename Graph::NodeMap<int> visited(G); //0: unvisited, |
37 //1: reached by a forward edge |
37 //1: reached by a forward edge |
38 //2: reached by a backward edge |
38 //2: reached by a backward edge |
39 //3: it is node s |
39 //3: it is node s |
40 typename Graph::NodeMap<EdgeIt> tree(G); |
40 typename Graph::NodeMap<EdgeIt> tree(G); |
41 |
41 |
42 NodeIt gn; //FIXME: it might be too global for some people... |
42 EachNodeIt gn; //FIXME: it might be too global for some people... |
43 |
43 |
44 augment: |
44 augment: |
45 |
45 |
46 for(NodeIt n(G);G.valid(n);G.next(n)) |
46 for(EachNodeIt n(G);G.valid(n);G.next(n)) |
47 visited.set(n,0); |
47 visited.set(n,0); |
48 |
48 |
49 visited.set(s,3); |
49 visited.set(s,3); |
50 |
50 |
51 //There must be a better way to do this: |
51 //There must be a better way to do this: |
53 |
53 |
54 bfs_queue.push(s); |
54 bfs_queue.push(s); |
55 |
55 |
56 while(!bfs_queue.empty() && !visited.get(t)) |
56 while(!bfs_queue.empty() && !visited.get(t)) |
57 { |
57 { |
58 NodeIt n(bfs_queue.front()); |
58 EachNodeIt n(bfs_queue.front()); |
59 for(OutEdgeIt e(G,n);G.valid(e);G.next(e)) |
59 for(OutEdgeIt e(G,n);G.valid(e);G.next(e)) |
60 if(f.get(e)<c.get(e) && //FIXME: < |
60 if(f.get(e)<c.get(e) && //FIXME: < |
61 !visited.get(G.bNode(e))) |
61 !visited.get(G.bNode(e))) |
62 { |
62 { |
63 tree.set(G.bNode(e),e); |
63 tree.set(G.bNode(e),e); |