COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci_max_flow.hh @ 14:99014d576aed

Last change on this file since 14:99014d576aed was 14:99014d576aed, checked in by marci, 17 years ago

reimplemented max_flow algorithm class with bfs_iterator1

File size: 6.6 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 T>
98  struct max_flow_type {
99   
100    typedef typename graph_traits<graph_type>::node_iterator node_iterator;
101    typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
102    typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
103    typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
104    typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
105
106    graph_type& G;
107    node_iterator s;
108    node_iterator t;
109    edge_property_vector<graph_type, T> flow;
110    edge_property_vector<graph_type, T>& capacity;
111
112    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) {
113      for(each_node_iterator i=G.first_node(); i.is_valid(); ++i)
114        for(out_edge_iterator j=G.first_out_edge(i); j.is_valid(); ++j)
115          flow.put(j, 0);
116    }
117    void run() {
118      typedef res_graph_type<graph_type, T> aug_graph_type;
119      aug_graph_type res_graph(G, flow, capacity);
120
121      bool augment;
122      do {
123        augment=false;
124
125        typedef std::queue<graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type;
126        bfs_queue_type bfs_queue;
127        bfs_queue.push(res_graph.first_out_edge(s));
128
129        typedef node_property_vector<aug_graph_type, bool> reached_type;
130        //reached_type reached(res_graph);
131        //for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) { reached.put(i, false); }
132        reached_type reached(res_graph, false);
133        reached.put(s, true);
134       
135        bfs_iterator1< aug_graph_type, reached_type >
136        res_bfs(res_graph, bfs_queue, reached);
137
138        typedef node_property_vector<aug_graph_type, graph_traits<aug_graph_type>::edge_iterator> pred_type;
139        pred_type pred(res_graph);
140        pred.put(s, res_graph.invalid_edge());
141
142        typedef node_property_vector<aug_graph_type, int> free_type;
143        free_type free(res_graph);
144       
145        //searching for augmenting path
146        while ( res_bfs.is_valid() ) {
147          //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl;
148          if (res_bfs.is_newly_reached()) {
149            graph_traits<aug_graph_type>::edge_iterator e;
150            e=res_bfs;
151            node_iterator v=res_graph.tail(e);
152            node_iterator w=res_graph.head(e);
153            //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
154            pred.put(w, e);
155            if (pred.get(v).is_valid()) {
156              free.put(w, std::min(free.get(v), e.free()));
157              //std::cout <<" nem elso csucs: ";
158              //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
159            } else {
160              free.put(w, e.free());
161              //std::cout <<" elso csucs: ";
162              //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
163            }
164            //std::cout<<std::endl;
165          }
166       
167          if (res_graph.head(res_bfs)==t) break;
168          ++res_bfs;
169        }
170        if (reached.get(t)) {
171          augment=true;
172          node_iterator n=t;
173          T augment_value=free.get(t);
174          std::cout<<"augmentation: ";
175          while (pred.get(n).is_valid()) {
176            graph_traits<aug_graph_type>::edge_iterator e=pred.get(n);
177            e.augment(augment_value);
178            std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
179            n=res_graph.tail(e);
180          }
181          std::cout<<std::endl;
182        }
183
184        std::cout << "actual flow: "<< std::endl;
185        for(graph_traits<graph_type>::each_edge_iterator e=G.first_edge(); e.is_valid(); ++e) {
186          std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
187        }
188        std::cout<<std::endl;
189
190      } while (augment);
191    }
192  };
193
194} // namespace marci
195
196#endif //MARCI_MAX_FLOW_HH
Note: See TracBrowser for help on using the repository browser.