COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/f_ed_ka.h @ 476:cfe550761745

Last change on this file since 476:cfe550761745 was 108:0351b00fd283, checked in by Alpar Juttner, 20 years ago

Dynamic Maps added.

File size: 3.1 KB
RevLine 
[74]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
[108]14namespace hugo {
[74]15  template <typename Graph, typename FlowMap, typename CapacityMap>
16  typename FlowMap::ValueType maxFlow(Graph &G,
17                                      FlowMap &f,
18                                      CapacityMap &c,
[95]19                                      typename Graph::NodeIt s,
20                                      typename Graph::NodeIt t)
[74]21  {
[93]22    typedef typename Graph::NodeIt NodeIt;
[91]23    typedef typename Graph::EachNodeIt EachNodeIt;
[74]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::ValueType T;
29   
30    T flow_val = 0;
31    T aug_val;
32
[93]33    for(EachEdgeIt e(G);G.valid(e);G.goNext(e))
[74]34      f.set(e,0);
35   
[93]36    std::queue<NodeIt> bfs_queue;
[74]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   
[94]43    NodeIt gn;  //FIXME: it might be too global for some people...
[74]44   
45  augment:
46   
[93]47    for(EachNodeIt n(G);G.valid(n);G.goNext(n))
[74]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      {
[93]59        NodeIt n(bfs_queue.front());
60        bfs_queue.pop();
61        for(OutEdgeIt e(G,n);G.valid(e);G.goNext(e))
[74]62          if(f.get(e)<c.get(e) &&   //FIXME: <
63             !visited.get(G.bNode(e)))
64            {
[93]65              NodeIt nn(G.bNode(e)); //It improves nothing
66              tree.set(nn,e);
67              visited.set(nn,1);
68              bfs_queue.push(nn);
[74]69            }
[93]70        for(InEdgeIt e(G,n);G.valid(e);G.goNext(e))
[74]71          if(f.get(e)>0 &&   //FIXME: >
72             !visited.get(G.bNode(e)))
73            {
[93]74              NodeIt nn(G.bNode(e));
75              tree.set(nn,e);
76              visited.set(nn,2);
77              bfs_queue.push(nn);
[74]78            }
79      }
80   
81    if(!visited.get(t)) return flow_val;
82
83    // Augmenting value computation
[80]84    aug_val = visited.get(t)==1 ?
[74]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)'
[80]87    gn = visited.get(t)==1 ? G.tail(tree.get(t)) : G.head(tree.get(t));
88    while(gn!=s) if(visited.get(gn)==1)
[74]89      {
[93]90        //FIXME: nonstandard gcc extension!
[74]91        aug_val <?= c.get(tree.get(gn))-f.get(tree.get(gn));
[80]92        gn=G.tail(tree.get(gn));
[74]93      }
94    else {
[93]95      //FIXME: nonstandard gcc extension!
[74]96      aug_val <?= f.get(tree.get(gn));
[80]97      gn=G.head(tree.get(gn));
[74]98    }
99       
100    // The augmentation itself
101    gn = t;
[80]102    while(gn!=s) if(visited.get(gn)==1)
[74]103      {
104        f.set(tree.get(gn),f.get(tree.get(gn))+aug_val);
[80]105        gn=G.tail(tree.get(gn));
[74]106      }
107    else {
108      f.set(tree.get(gn),f.get(tree.get(gn))-aug_val);
[80]109      gn=G.head(tree.get(gn));
[74]110    }
111
112    flow_val+=aug_val;
113
114    goto augment;   // Vivat goto forever!
115  }
116 
[108]117} // namespace hugo
[74]118
119#endif //EDMONDS_KARP_HH
Note: See TracBrowser for help on using the repository browser.