COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

source: lemon-0.x/src/work/marci_max_flow.hh @ 43:8ff5dc7d18eb

Last change on this file since 43:8ff5dc7d18eb was 19:3151a1026db9, checked in by marci, 21 years ago

* empty log message *
File size: 5.8 KB
RevLine 
[9]1#ifndef MARCI_MAX_FLOW_HH
2#define MARCI_MAX_FLOW_HH
3
4#include <algorithm>
5
6#include <marci_property_vector.hh>
7#include <marci_bfs.hh>
8
9namespace marci {
10
11  template<typename graph_type, typename T>
12  class res_graph_type {
[19]13    typedef typename graph_type::node_iterator node_iterator;
14    typedef typename graph_type::each_node_iterator each_node_iterator;
15    typedef typename graph_type::sym_edge_iterator old_sym_edge_iterator;
[9]16    graph_type& G;
17    edge_property_vector<graph_type, T>& flow;
18    edge_property_vector<graph_type, T>& capacity;
19  public:
20    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) { }
21
[19]22    class edge_iterator {
[9]23      friend class res_graph_type<graph_type, T>;
24    protected:
25      res_graph_type<graph_type, T>* resG;
[19]26      old_sym_edge_iterator sym;
[9]27    public:
[19]28      edge_iterator() { }
[9]29      //bool is_free() { 
30      //if (resG->G.a_node(sym)==resG->G.tail(sym)) {
31      //  return (resG->flow.get(sym)<resG->capacity.get(sym));
32      //} else {
33      //  return (resG->flow.get(sym)>0);
34      //}
35      //}
36      T free() {
37        if (resG->G.a_node(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      }
[19]43      bool valid() { return sym.valid(); }
[17]44      void make_invalid() { sym.make_invalid(); }
[9]45      void augment(T a) {
46        if (resG->G.a_node(sym)==resG->G.tail(sym)) {
47          resG->flow.put(sym, resG->flow.get(sym)+a);
48        } else {
49          resG->flow.put(sym, resG->flow.get(sym)-a);
50        }
51      }
52    };
53
[19]54    class out_edge_iterator : public edge_iterator {
[9]55    public:
[19]56      out_edge_iterator() { }
57      out_edge_iterator(res_graph_type<graph_type, T>& _resG, const node_iterator& v) {
[9]58        resG=&_resG;
59        sym=resG->G.first_sym_edge(v);
[19]60        while( sym.valid() && !(free()>0) ) { ++sym; }
[9]61      }
[19]62      out_edge_iterator& operator++() {
[9]63        ++sym;
[19]64        while( sym.valid() && !(free()>0) ) { ++sym; }
[9]65        return *this;
66      }
67    };
68
[19]69    out_edge_iterator first_out_edge(const node_iterator& v) {
70      return out_edge_iterator(*this, v);
[9]71    }
72
73    each_node_iterator first_node() {
74      return G.first_node();
75    }
76
[19]77    node_iterator tail(const edge_iterator& e) { return G.a_node(e.sym); }
78    node_iterator head(const edge_iterator& e) { return G.b_node(e.sym); }
[9]79
80    int id(const node_iterator& v) { return G.id(v); }
81
[17]82    //node_iterator invalid_node() { return G.invalid_node(); }
[19]83    //res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; }
[9]84  };
85
86  template <typename graph_type, typename T>
87  struct max_flow_type {
[19]88    typedef typename graph_type::node_iterator node_iterator;
89    typedef typename graph_type::edge_iterator edge_iterator;
90    typedef typename graph_type::each_node_iterator each_node_iterator;
91    typedef typename graph_type::out_edge_iterator out_edge_iterator;
92    typedef typename graph_type::in_edge_iterator in_edge_iterator;
[9]93    graph_type& G;
94    node_iterator s;
95    node_iterator t;
96    edge_property_vector<graph_type, T> flow;
97    edge_property_vector<graph_type, T>& capacity;
98
99    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) {
[19]100      for(each_node_iterator i=G.first_node(); i.valid(); ++i)
101        for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j)
[9]102          flow.put(j, 0);
103    }
104    void run() {
105      typedef res_graph_type<graph_type, T> aug_graph_type;
106      aug_graph_type res_graph(G, flow, capacity);
107
108      bool augment;
109      do {
110        augment=false;
[14]111
[19]112        typedef std::queue<aug_graph_type::out_edge_iterator> bfs_queue_type;
[14]113        bfs_queue_type bfs_queue;
[9]114        bfs_queue.push(res_graph.first_out_edge(s));
[14]115
116        typedef node_property_vector<aug_graph_type, bool> reached_type;
117        reached_type reached(res_graph, false);
[9]118        reached.put(s, true);
119       
[14]120        bfs_iterator1< aug_graph_type, reached_type >
121        res_bfs(res_graph, bfs_queue, reached);
122
[19]123        typedef node_property_vector<aug_graph_type, aug_graph_type::edge_iterator> pred_type;
[14]124        pred_type pred(res_graph);
[19]125        aug_graph_type::edge_iterator a;
[17]126        a.make_invalid();
127        pred.put(s, a);
[14]128
129        typedef node_property_vector<aug_graph_type, int> free_type;
130        free_type free(res_graph);
131       
[9]132        //searching for augmenting path
[19]133        while ( res_bfs.valid() ) {
[14]134          //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl;
[19]135          if (res_bfs.newly_reached()) {
136            aug_graph_type::edge_iterator e;
[14]137            e=res_bfs;
138            node_iterator v=res_graph.tail(e);
139            node_iterator w=res_graph.head(e);
140            //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
141            pred.put(w, e);
[19]142            if (pred.get(v).valid()) {
[14]143              free.put(w, std::min(free.get(v), e.free()));
144              //std::cout <<" nem elso csucs: ";
145              //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
146            } else {
147              free.put(w, e.free());
148              //std::cout <<" elso csucs: ";
149              //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
150            }
151            //std::cout<<std::endl;
152          }
153       
[9]154          if (res_graph.head(res_bfs)==t) break;
155          ++res_bfs;
156        }
157        if (reached.get(t)) {
158          augment=true;
159          node_iterator n=t;
160          T augment_value=free.get(t);
161          std::cout<<"augmentation: ";
[19]162          while (pred.get(n).valid()) {
163            aug_graph_type::edge_iterator e=pred.get(n);
[9]164            e.augment(augment_value);
165            std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
166            n=res_graph.tail(e);
167          }
168          std::cout<<std::endl;
169        }
170
[14]171        std::cout << "actual flow: "<< std::endl;
[19]172        for(typename graph_type::each_edge_iterator e=G.first_edge(); e.valid(); ++e) {
[9]173          std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
174        }
175        std::cout<<std::endl;
176
177      } while (augment);
178    }
179  };
180
181} // namespace marci
182
183#endif //MARCI_MAX_FLOW_HH
Note: See TracBrowser for help on using the repository browser.