COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/edmonds_karp.hh @ 64:72bd463289a9

Last change on this file since 64:72bd463289a9 was 64:72bd463289a9, checked in by marci, 17 years ago

.

File size: 5.9 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 ValueType>
100    class NodeMap {
101      typename Graph::NodeMap<ValueType> 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, ValueType a) : node_map(_G.G, a) { }
105      void set(NodeIt nit, ValueType a) { node_map.set(nit, a); }
106      ValueType 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        //std::queue<AugOutEdgeIt> bfs_copy(res_bfs.getBfsQueue());
144        //while (!bfs_copy.empty()) {
145        //  AugOutEdgeIt e=bfs_copy.front();
146        //  bfs_copy.pop();
147        //  if (e.valid()) {
148        //    std::cout<<"queue:"<<res_graph.tail(e)<<"->"<<res_graph.head(e)<<" ";
149        //  } else {
150        //    std::cout<<"queue:"<<res_graph.aNode(e)<<"->"<<" ";
151        //  }
152        //}
153        //std::cout<<std::endl;
154        AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
155        //if (e.valid()) {
156        //  std::cout<<"actual:"<<res_graph.tail(e)<<"->"<<res_graph.head(e)<<std::endl;
157        //} else {
158        //  std::cout<<"actual:"<<res_graph.aNode(e)<<"->"<<std::endl;
159        //}
160        if (e.valid() && res_bfs.isBNodeNewlyReached()) {
161          NodeIt v=res_graph.tail(e);
162          NodeIt w=res_graph.head(e);
163          //std::cout<<v<<"->"<<w<<std::endl;
164          pred.set(w, e);
165          if (pred.get(v).valid()) {
166            free.set(w, std::min(free.get(v), e.free()));
167          } else {
168            free.set(w, e.free());
169          }
170          if (res_graph.head(e)==t) { _augment=true; break; }
171        }
172       
173        ++res_bfs;
174      } //end of searching augmenting path
175
176      if (_augment) {
177        NodeIt n=t;
178        T augment_value=free.get(t);
179        //std::cout<<"augmentation: ";
180        while (pred.get(n).valid()) {
181          AugEdgeIt e=pred.get(n);
182          e.augment(augment_value);
183          //std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
184          n=res_graph.tail(e);
185        }
186        //std::cout<<std::endl;
187      }
188      //std::cout << "actual flow: "<< std::endl;
189      //for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
190      //std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
191      //}
192      //std::cout<<std::endl;
193
194      return _augment;
195    }
196    void run() {
197      while (augment()) { }
198    }
199  };
200
201} // namespace marci
202
203#endif //EDMONDS_KARP_HH
Note: See TracBrowser for help on using the repository browser.