COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci_max_flow.hh @ 17:8b29d935f1a6

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

make_invalid()

File size: 6.5 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 make_invalid() { sym.make_invalid(); }
48      void augment(T a) {
49        if (resG->G.a_node(sym)==resG->G.tail(sym)) {
50          resG->flow.put(sym, resG->flow.get(sym)+a);
51        } else {
52          resG->flow.put(sym, resG->flow.get(sym)-a);
53        }
54      }
55    };
56
57    class res_out_edge_it : public res_edge_it {
58    public:
59      res_out_edge_it() { }
60      res_out_edge_it(res_graph_type<graph_type, T>& _resG, const node_iterator& v) {
61        resG=&_resG;
62        sym=resG->G.first_sym_edge(v);
63        while( sym.is_valid() && !(free()>0) ) { ++sym; }
64      }
65      res_out_edge_it& operator++() {
66        ++sym;
67        while( sym.is_valid() && !(free()>0) ) { ++sym; }
68        return *this;
69      }
70    };
71
72    res_out_edge_it first_out_edge(const node_iterator& v) {
73      return res_out_edge_it(*this, v);
74    }
75
76    each_node_iterator first_node() {
77      return G.first_node();
78    }
79
80    node_iterator tail(const res_edge_it& e) { return G.a_node(e.sym); }
81    node_iterator head(const res_edge_it& e) { return G.b_node(e.sym); }
82
83    int id(const node_iterator& v) { return G.id(v); }
84
85    //node_iterator invalid_node() { return G.invalid_node(); }
86    //res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; }
87   
88  };
89
90  template <typename graph_type, typename T>
91  struct graph_traits< res_graph_type<graph_type, T> > {
92    typedef typename graph_traits<graph_type>::node_iterator node_iterator;
93    typedef typename res_graph_type<graph_type, T>::res_edge_it edge_iterator;
94    typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
95    typedef typename res_graph_type<graph_type, T>::res_out_edge_it out_edge_iterator;
96  };
97
98  template <typename graph_type, typename T>
99  struct max_flow_type {
100   
101    typedef typename graph_traits<graph_type>::node_iterator node_iterator;
102    typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
103    typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
104    typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
105    typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
106
107    graph_type& G;
108    node_iterator s;
109    node_iterator t;
110    edge_property_vector<graph_type, T> flow;
111    edge_property_vector<graph_type, T>& capacity;
112
113    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) {
114      for(each_node_iterator i=G.first_node(); i.is_valid(); ++i)
115        for(out_edge_iterator j=G.first_out_edge(i); j.is_valid(); ++j)
116          flow.put(j, 0);
117    }
118    void run() {
119      typedef res_graph_type<graph_type, T> aug_graph_type;
120      aug_graph_type res_graph(G, flow, capacity);
121
122      bool augment;
123      do {
124        augment=false;
125
126        typedef std::queue<graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type;
127        bfs_queue_type bfs_queue;
128        bfs_queue.push(res_graph.first_out_edge(s));
129
130        typedef node_property_vector<aug_graph_type, bool> reached_type;
131        reached_type reached(res_graph, false);
132        reached.put(s, true);
133       
134        bfs_iterator1< aug_graph_type, reached_type >
135        res_bfs(res_graph, bfs_queue, reached);
136
137        typedef node_property_vector<aug_graph_type, graph_traits<aug_graph_type>::edge_iterator> pred_type;
138        pred_type pred(res_graph);
139        graph_traits<aug_graph_type>::edge_iterator a;
140        a.make_invalid();
141        pred.put(s, a);
142
143        typedef node_property_vector<aug_graph_type, int> free_type;
144        free_type free(res_graph);
145       
146        //searching for augmenting path
147        while ( res_bfs.is_valid() ) {
148          //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl;
149          if (res_bfs.is_newly_reached()) {
150            graph_traits<aug_graph_type>::edge_iterator e;
151            e=res_bfs;
152            node_iterator v=res_graph.tail(e);
153            node_iterator w=res_graph.head(e);
154            //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
155            pred.put(w, e);
156            if (pred.get(v).is_valid()) {
157              free.put(w, std::min(free.get(v), e.free()));
158              //std::cout <<" nem elso csucs: ";
159              //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
160            } else {
161              free.put(w, e.free());
162              //std::cout <<" elso csucs: ";
163              //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
164            }
165            //std::cout<<std::endl;
166          }
167       
168          if (res_graph.head(res_bfs)==t) break;
169          ++res_bfs;
170        }
171        if (reached.get(t)) {
172          augment=true;
173          node_iterator n=t;
174          T augment_value=free.get(t);
175          std::cout<<"augmentation: ";
176          while (pred.get(n).is_valid()) {
177            graph_traits<aug_graph_type>::edge_iterator e=pred.get(n);
178            e.augment(augment_value);
179            std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
180            n=res_graph.tail(e);
181          }
182          std::cout<<std::endl;
183        }
184
185        std::cout << "actual flow: "<< std::endl;
186        for(graph_traits<graph_type>::each_edge_iterator e=G.first_edge(); e.is_valid(); ++e) {
187          std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
188        }
189        std::cout<<std::endl;
190
191      } while (augment);
192    }
193  };
194
195} // namespace marci
196
197#endif //MARCI_MAX_FLOW_HH
Note: See TracBrowser for help on using the repository browser.