COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/edmonds_karp.hh @ 48:55fa34646895

Last change on this file since 48:55fa34646895 was 43:8ff5dc7d18eb, checked in by marci, 18 years ago

marci_max_flow.hh in the new concept

File size: 5.9 KB
Line 
1#ifndef MARCI_MAX_FLOW_HH
2#define MARCI_MAX_FLOW_HH
3
4#include <algorithm>
5
6#include <bfs_iterator.hh>
7
8namespace marci {
9
10  template<typename Graph, typename T>
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    typename Graph::EdgeMap<T>& flow;
17    const typename Graph::EdgeMap<T>& capacity;
18  public:
19    ResGraph(const Graph& _G, typename Graph::EdgeMap<T>& _flow,
20             const typename Graph::EdgeMap<T>& _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>;
30    protected:
31      const ResGraph<Graph, T>* 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(const 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>;
55    public:
56      OutEdgeIt() { }
57      //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
58    private:
59      OutEdgeIt(const ResGraph<Graph, T>& _resG, const 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, const 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(const NodeIt v) const {
86      It e;
87      getFirst(e, v);
88      return e;
89    }
90
91    NodeIt tail(const EdgeIt e) const { return G.aNode(e.sym); }
92    NodeIt head(const EdgeIt e) const { return G.bNode(e.sym); }
93
94    NodeIt aNode(const OutEdgeIt e) const { return G.aNode(e.sym); }
95    NodeIt bNode(const OutEdgeIt e) const { return G.bNode(e.sym); }
96
97    int id(const NodeIt v) const { return G.id(v); }
98
99    template <typename ValueType>
100    class NodeMap {
101      //const ResGraph<Graph, T>& G;
102      typename Graph::NodeMap<ValueType> node_map;
103    public:
104      NodeMap(const ResGraph<Graph, T>& _G) : node_map(_G.G)/*: G(_G)*/ { }
105      NodeMap(const ResGraph<Graph, T>& _G, const ValueType a) : node_map(_G.G, a) /*: G(_G)*/ { }
106      void set(const NodeIt nit, const ValueType a) { node_map.set(nit, a); }
107      ValueType get(const NodeIt nit) const { return node_map.get(nit); }
108    };
109
110  };
111
112  template <typename Graph, typename T>
113  struct max_flow_type {
114    typedef typename Graph::NodeIt NodeIt;
115    typedef typename Graph::EdgeIt EdgeIt;
116    typedef typename Graph::EachEdgeIt EachEdgeIt;
117    typedef typename Graph::OutEdgeIt OutEdgeIt;
118    typedef typename Graph::InEdgeIt InEdgeIt;
119    const Graph& G;
120    NodeIt s;
121    NodeIt t;
122    typename Graph::EdgeMap<T> flow;
123    const typename Graph::EdgeMap<T>& capacity;
124
125    max_flow_type(const Graph& _G, NodeIt _s, NodeIt _t, const typename Graph::EdgeMap<T>& _capacity) : G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { }
126    void run() {
127      typedef ResGraph<Graph, T> AugGraph;
128      AugGraph res_graph(G, flow, capacity);
129
130      bool augment;
131      do {
132        augment=false;
133
134        typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
135        typedef typename AugGraph::EdgeIt AugEdgeIt;
136        typedef std::queue<AugOutEdgeIt> BfsQueue;
137        BfsQueue bfs_queue;
138        bfs_queue.push(res_graph.template first<AugOutEdgeIt>(s));
139
140        typedef typename AugGraph::NodeMap<bool> ReachedMap;
141        ReachedMap reached(res_graph, false);
142        reached.set(s, true);
143       
144        bfs_iterator1< AugGraph, ReachedMap >
145        res_bfs(res_graph, bfs_queue, reached);
146
147        typedef typename AugGraph::NodeMap<AugEdgeIt> PredMap;
148        PredMap pred(res_graph);
149        //typename AugGraph::EdgeIt a; //invalid
150        //a.makeInvalid();
151        //pred.set(s, a);
152
153        typedef typename AugGraph::NodeMap<int> FreeMap;
154        FreeMap free(res_graph);
155       
156        //searching for augmenting path
157        while ( res_bfs.valid() ) {
158          //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl;
159          if (res_bfs.newly_reached()) {
160            AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
161            NodeIt v=res_graph.tail(e);
162            NodeIt w=res_graph.head(e);
163            //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
164            pred.set(w, e);
165            if (pred.get(v).valid()) {
166              free.set(w, std::min(free.get(v), e.free()));
167              //std::cout <<" nem elso csucs: ";
168              //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
169            } else {
170              free.set(w, e.free());
171              //std::cout <<" elso csucs: ";
172              //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
173            }
174            //std::cout<<std::endl;
175          }
176       
177          if (res_graph.head(res_bfs)==t) break;
178          ++res_bfs;
179        } //end searching augmenting path
180        if (reached.get(t)) {
181          augment=true;
182          NodeIt n=t;
183          T augment_value=free.get(t);
184          std::cout<<"augmentation: ";
185          while (pred.get(n).valid()) {
186            AugEdgeIt e=pred.get(n);
187            e.augment(augment_value);
188            std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
189            n=res_graph.tail(e);
190          }
191          std::cout<<std::endl;
192        }
193
194        std::cout << "actual flow: "<< std::endl;
195        for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
196          std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
197        }
198        std::cout<<std::endl;
199
200      } while (augment);
201    }
202  };
203
204} // namespace marci
205
206#endif //MARCI_MAX_FLOW_HH
Note: See TracBrowser for help on using the repository browser.