COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci_max_flow.hh @ 9:a9ed3f1c2c63

Last change on this file since 9:a9ed3f1c2c63 was 9:a9ed3f1c2c63, checked in by marci, 17 years ago

marci

File size: 8.1 KB
Line 
1#ifndef MARCI_MAX_FLOW_HH
2#define MARCI_MAX_FLOW_HH
3
4#include <algorithm>
5
6#include <marci_graph_traits.hh>
7#include <marci_property_vector.hh>
8#include <marci_bfs.hh>
9
10namespace marci {
11
12  template<typename graph_type, typename T>
13  class res_graph_type {
14    typedef typename graph_traits<graph_type>::node_iterator node_iterator;
15    typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
16    typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
17    typedef typename graph_traits<graph_type>::sym_edge_iterator sym_edge_iterator;
18
19    graph_type& G;
20    edge_property_vector<graph_type, T>& flow;
21    edge_property_vector<graph_type, T>& capacity;
22  public:
23    res_graph_type(graph_type& _G, edge_property_vector<graph_type, T>& _flow, edge_property_vector<graph_type, T>& _capacity) : G(_G), flow(_flow), capacity(_capacity) { }
24
25    class res_edge_it {
26      friend class res_graph_type<graph_type, T>;
27    protected:
28      res_graph_type<graph_type, T>* resG;
29      sym_edge_iterator sym;
30    public:
31      res_edge_it() { }
32      //bool is_free() { 
33      //if (resG->G.a_node(sym)==resG->G.tail(sym)) {
34      //  return (resG->flow.get(sym)<resG->capacity.get(sym));
35      //} else {
36      //  return (resG->flow.get(sym)>0);
37      //}
38      //}
39      T free() {
40        if (resG->G.a_node(sym)==resG->G.tail(sym)) {
41          return (resG->capacity.get(sym)-resG->flow.get(sym));
42        } else {
43          return (resG->flow.get(sym));
44        }
45      }
46      bool is_valid() { return sym.is_valid(); }
47      void augment(T a) {
48        if (resG->G.a_node(sym)==resG->G.tail(sym)) {
49          resG->flow.put(sym, resG->flow.get(sym)+a);
50        } else {
51          resG->flow.put(sym, resG->flow.get(sym)-a);
52        }
53      }
54    };
55
56    class res_out_edge_it : public res_edge_it {
57    public:
58      res_out_edge_it() { }
59      res_out_edge_it(res_graph_type<graph_type, T>& _resG, const node_iterator& v) {
60        resG=&_resG;
61        sym=resG->G.first_sym_edge(v);
62        while( sym.is_valid() && !(free()>0) ) { ++sym; }
63      }
64      res_out_edge_it& operator++() {
65        ++sym;
66        while( sym.is_valid() && !(free()>0) ) { ++sym; }
67        return *this;
68      }
69    };
70
71    res_out_edge_it first_out_edge(const node_iterator& v) {
72      return res_out_edge_it(*this, v);
73    }
74
75    each_node_iterator first_node() {
76      return G.first_node();
77    }
78
79    node_iterator tail(const res_edge_it& e) { return G.a_node(e.sym); }
80    node_iterator head(const res_edge_it& e) { return G.b_node(e.sym); }
81
82    int id(const node_iterator& v) { return G.id(v); }
83
84    node_iterator invalid_node() { return G.invalid_node(); }
85    res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; }
86   
87  };
88
89  template <typename graph_type, typename T>
90  struct graph_traits< res_graph_type<graph_type, T> > {
91    typedef typename graph_traits<graph_type>::node_iterator node_iterator;
92    typedef typename res_graph_type<graph_type, T>::res_edge_it edge_iterator;
93    typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
94    typedef typename res_graph_type<graph_type, T>::res_out_edge_it out_edge_iterator;
95  };
96
97  template <typename graph_type, typename pred_type, typename free_type>
98  struct flow_visitor {
99    typedef typename graph_traits<graph_type>::node_iterator node_iterator;
100    typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
101    typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
102    typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
103    graph_type& G;
104    pred_type& pred;
105    free_type& free;
106    flow_visitor(graph_type& _G, pred_type& _pred, free_type& _free) : G(_G), pred(_pred), free(_free) { }
107    void at_previously_reached(out_edge_iterator& e) {
108      //node_iterator v=G.tail(e);
109      //node_iterator w=G.head(e);
110      //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is already reached";
111      //std::cout<<std::endl;
112   }
113    void at_newly_reached(out_edge_iterator& e) {
114      node_iterator v=G.tail(e);
115      node_iterator w=G.head(e);
116      //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
117      pred.put(w, e);
118      if (pred.get(v).is_valid()) {
119        free.put(w, std::min(free.get(v), e.free()));
120        //std::cout <<" nem elso csucs: ";
121        //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
122      } else {
123        free.put(w, e.free());
124        //std::cout <<" elso csucs: ";
125        //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
126      }
127      //std::cout<<std::endl;
128    }
129  };
130
131  template <typename graph_type, typename T>
132  struct max_flow_type {
133   
134    typedef typename graph_traits<graph_type>::node_iterator node_iterator;
135    typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
136    typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
137    typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
138    typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
139
140    graph_type& G;
141    node_iterator s;
142    node_iterator t;
143    edge_property_vector<graph_type, T> flow;
144    edge_property_vector<graph_type, T>& capacity;
145
146    max_flow_type(graph_type& _G, node_iterator _s, node_iterator _t, edge_property_vector<graph_type, T>& _capacity) : G(_G), s(_s), t(_t), flow(_G), capacity(_capacity) {
147      for(each_node_iterator i=G.first_node(); i.is_valid(); ++i)
148        for(out_edge_iterator j=G.first_out_edge(i); j.is_valid(); ++j)
149          flow.put(j, 0);
150    }
151    void run() {
152      typedef res_graph_type<graph_type, T> aug_graph_type;
153      aug_graph_type res_graph(G, flow, capacity);
154
155      typedef std::queue<graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type;
156      bfs_queue_type bfs_queue;
157      //bfs_queue.push(res_graph.first_out_edge(s));
158
159      typedef node_property_vector<aug_graph_type, bool> reached_type;
160      //reached_type reached(res_graph, false);
161      reached_type reached(res_graph);
162      //reached.put(s, true);
163
164      typedef node_property_vector<aug_graph_type, graph_traits<aug_graph_type>::edge_iterator> pred_type;
165      pred_type pred(res_graph);
166      pred.put(s, res_graph.invalid_edge());
167     
168      typedef node_property_vector<aug_graph_type, int> free_type;
169      free_type free(res_graph);
170
171      typedef flow_visitor<aug_graph_type, pred_type, free_type> visitor_type;
172      visitor_type vis(res_graph, pred, free);
173     
174      bfs_iterator< aug_graph_type, reached_type, visitor_type >
175        res_bfs(res_graph, bfs_queue, reached, vis);
176
177      //for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) {
178      //for(graph_traits<aug_graph_type>::out_edge_iterator j=res_graph.first_out_edge(i); j.is_valid(); ++j) {
179      //  std::cout<<"("<<res_graph.tail(j)<< "->"<<res_graph.head(j)<<") ";
180      //}
181      //}
182      //std::cout<<std::endl;
183
184      //char c;
185      bool augment;
186      do {
187        augment=false;
188       
189        while (!bfs_queue.empty()) { bfs_queue.pop(); }
190        bfs_queue.push(res_graph.first_out_edge(s));
191       
192        for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) { reached.put(i, false); }
193        reached.put(s, true);
194       
195        //searching for augmenting path
196        while ( /*std::cin>>c &&*/ res_bfs.is_valid() ) {
197          res_bfs.process();
198          //if (res_graph.head(graph_traits<aug_graph_type>::out_edge_iterator(res_bfs))==t) break;
199          if (res_graph.head(res_bfs)==t) break;
200          //res_bfs.next();
201          ++res_bfs;
202        }
203        //for (; std::cin>>c && !res_bfs.finished() && res_graph.head(res_bfs.current())!=t; res_bfs.next()) { res_bfs.process(); }
204        if (reached.get(t)) {
205          augment=true;
206          node_iterator n=t;
207          T augment_value=free.get(t);
208          std::cout<<"augmentation: ";
209          while (pred.get(n).is_valid()) {
210            graph_traits<aug_graph_type>::edge_iterator e=pred.get(n);
211            e.augment(augment_value);
212            std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
213            n=res_graph.tail(e);
214          }
215          std::cout<<std::endl;
216        }
217
218        std::cout << "max flow:"<< std::endl;
219        for(graph_traits<graph_type>::each_edge_iterator e=G.first_edge(); e.is_valid(); ++e) {
220          std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
221        }
222        std::cout<<std::endl;
223
224      } while (augment);
225    }
226  };
227
228} // namespace marci
229
230#endif //MARCI_MAX_FLOW_HH
Note: See TracBrowser for help on using the repository browser.