COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/f_ed_ka.h @ 74:82d3dbe912d9

Last change on this file since 74:82d3dbe912d9 was 74:82d3dbe912d9, checked in by Alpar Juttner, 17 years ago

.

File size: 2.9 KB
Line 
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
14namespace 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
Note: See TracBrowser for help on using the repository browser.