COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/edmonds_karp.hh @ 69:24c2c2989e0f

Last change on this file since 69:24c2c2989e0f was 69:24c2c2989e0f, checked in by marci, 17 years ago

.

File size: 5.1 KB
Line 
1#ifndef EDMONDS_KARP_HH
2#define EDMONDS_KARP_HH
3
4#include <algorithm>
5
6#include <bfs_iterator.hh>
7
8namespace marci {
9
10  template<typename Graph, typename T, typename FlowMap, typename CapacityMap>
11  class ResGraph {
12    typedef typename Graph::NodeIt NodeIt;
13    typedef typename Graph::EachNodeIt EachNodeIt;
14    typedef typename Graph::SymEdgeIt OldSymEdgeIt;
15    const Graph& G;
16    FlowMap& flow;
17    const CapacityMap& capacity;
18  public:
19    ResGraph(const Graph& _G, FlowMap& _flow,
20             const CapacityMap& _capacity) :
21      G(_G), flow(_flow), capacity(_capacity) { }
22
23    class EdgeIt;
24    class OutEdgeIt;
25    friend class EdgeIt;
26    friend class OutEdgeIt;
27
28    class EdgeIt {
29      friend class ResGraph<Graph, T, FlowMap, CapacityMap>;
30    protected:
31      const ResGraph<Graph, T, FlowMap, CapacityMap>* resG;
32      OldSymEdgeIt sym;
33    public:
34      EdgeIt() { }
35      //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { }
36      T free() const {
37        if (resG->G.aNode(sym)==resG->G.tail(sym)) {
38          return (resG->capacity.get(sym)-resG->flow.get(sym));
39        } else {
40          return (resG->flow.get(sym));
41        }
42      }
43      bool valid() const { return sym.valid(); }
44      void augment(T a) const {
45        if (resG->G.aNode(sym)==resG->G.tail(sym)) {
46          resG->flow.set(sym, resG->flow.get(sym)+a);
47        } else {
48          resG->flow.set(sym, resG->flow.get(sym)-a);
49        }
50      }
51    };
52
53    class OutEdgeIt : public EdgeIt {
54      friend class ResGraph<Graph, T, FlowMap, CapacityMap>;
55    public:
56      OutEdgeIt() { }
57      //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
58    private:
59      OutEdgeIt(const ResGraph<Graph, T, FlowMap, CapacityMap>& _resG, NodeIt v) {
60        resG=&_resG;
61        sym=resG->G.template first<OldSymEdgeIt>(v);
62        while( sym.valid() && !(free()>0) ) { ++sym; }
63      }
64    public:
65      OutEdgeIt& operator++() {
66        ++sym;
67        while( sym.valid() && !(free()>0) ) { ++sym; }
68        return *this;
69      }
70    };
71
72    void getFirst(OutEdgeIt& e, NodeIt v) const {
73      e=OutEdgeIt(*this, v);
74    }
75    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
76   
77    template< typename It >
78    It first() const {
79      It e;
80      getFirst(e);
81      return e;
82    }
83
84    template< typename It >
85    It first(NodeIt v) const {
86      It e;
87      getFirst(e, v);
88      return e;
89    }
90
91    NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }
92    NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }
93
94    NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
95    NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
96
97    int id(NodeIt v) const { return G.id(v); }
98
99    template <typename S>
100    class NodeMap {
101      typename Graph::NodeMap<S> node_map;
102    public:
103      NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
104      NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
105      void set(NodeIt nit, S a) { node_map.set(nit, a); }
106      S get(NodeIt nit) const { return node_map.get(nit); }
107    };
108
109  };
110
111  template <typename Graph, typename T, typename FlowMap, typename CapacityMap>
112  class MaxFlow {
113    typedef typename Graph::NodeIt NodeIt;
114    typedef typename Graph::EdgeIt EdgeIt;
115    typedef typename Graph::EachEdgeIt EachEdgeIt;
116    typedef typename Graph::OutEdgeIt OutEdgeIt;
117    typedef typename Graph::InEdgeIt InEdgeIt;
118    const Graph& G;
119    NodeIt s;
120    NodeIt t;
121    FlowMap& flow;
122    const CapacityMap& capacity;
123    typedef ResGraph<Graph, T, FlowMap, CapacityMap > AugGraph;
124    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
125    typedef typename AugGraph::EdgeIt AugEdgeIt;
126  public:
127    MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) { }
128    bool augment() {
129      AugGraph res_graph(G, flow, capacity);
130      bool _augment=false;
131     
132      typedef typename AugGraph::NodeMap<bool> ReachedMap;
133      BfsIterator2< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
134      res_bfs.pushAndSetReached(s);
135       
136      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
137      //filled with invalid iterators
138     
139      typename AugGraph::NodeMap<int> free(res_graph);
140       
141      //searching for augmenting path
142      while ( !res_bfs.finished() ) {
143        AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
144        if (e.valid() && res_bfs.isBNodeNewlyReached()) {
145          NodeIt v=res_graph.tail(e);
146          NodeIt w=res_graph.head(e);
147          pred.set(w, e);
148          if (pred.get(v).valid()) {
149            free.set(w, std::min(free.get(v), e.free()));
150          } else {
151            free.set(w, e.free());
152          }
153          if (res_graph.head(e)==t) { _augment=true; break; }
154        }
155       
156        ++res_bfs;
157      } //end of searching augmenting path
158
159      if (_augment) {
160        NodeIt n=t;
161        T augment_value=free.get(t);
162        while (pred.get(n).valid()) {
163          AugEdgeIt e=pred.get(n);
164          e.augment(augment_value);
165          n=res_graph.tail(e);
166        }
167      }
168
169      return _augment;
170    }
171    void run() {
172      while (augment()) { }
173    }
174    T flowValue() {
175      T a=0;
176      for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) {
177        a+=flow.get(i);
178      }
179      return a;
180    }
181  };
182
183} // namespace marci
184
185#endif //EDMONDS_KARP_HH
Note: See TracBrowser for help on using the repository browser.