1.1 --- a/src/work/marci_max_flow.hh Sat Apr 03 14:22:33 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,183 +0,0 @@
1.4 -#ifndef MARCI_MAX_FLOW_HH
1.5 -#define MARCI_MAX_FLOW_HH
1.6 -
1.7 -#include <algorithm>
1.8 -
1.9 -#include <marci_property_vector.hh>
1.10 -#include <marci_bfs.hh>
1.11 -
1.12 -namespace hugo {
1.13 -
1.14 - template<typename graph_type, typename T>
1.15 - class res_graph_type {
1.16 - typedef typename graph_type::node_iterator node_iterator;
1.17 - typedef typename graph_type::each_node_iterator each_node_iterator;
1.18 - typedef typename graph_type::sym_edge_iterator old_sym_edge_iterator;
1.19 - graph_type& G;
1.20 - edge_property_vector<graph_type, T>& flow;
1.21 - edge_property_vector<graph_type, T>& capacity;
1.22 - public:
1.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) { }
1.24 -
1.25 - class edge_iterator {
1.26 - friend class res_graph_type<graph_type, T>;
1.27 - protected:
1.28 - res_graph_type<graph_type, T>* resG;
1.29 - old_sym_edge_iterator sym;
1.30 - public:
1.31 - edge_iterator() { }
1.32 - //bool is_free() {
1.33 - //if (resG->G.a_node(sym)==resG->G.tail(sym)) {
1.34 - // return (resG->flow.get(sym)<resG->capacity.get(sym));
1.35 - //} else {
1.36 - // return (resG->flow.get(sym)>0);
1.37 - //}
1.38 - //}
1.39 - T free() {
1.40 - if (resG->G.a_node(sym)==resG->G.tail(sym)) {
1.41 - return (resG->capacity.get(sym)-resG->flow.get(sym));
1.42 - } else {
1.43 - return (resG->flow.get(sym));
1.44 - }
1.45 - }
1.46 - bool valid() { return sym.valid(); }
1.47 - void make_invalid() { sym.make_invalid(); }
1.48 - void augment(T a) {
1.49 - if (resG->G.a_node(sym)==resG->G.tail(sym)) {
1.50 - resG->flow.put(sym, resG->flow.get(sym)+a);
1.51 - } else {
1.52 - resG->flow.put(sym, resG->flow.get(sym)-a);
1.53 - }
1.54 - }
1.55 - };
1.56 -
1.57 - class out_edge_iterator : public edge_iterator {
1.58 - public:
1.59 - out_edge_iterator() { }
1.60 - out_edge_iterator(res_graph_type<graph_type, T>& _resG, const node_iterator& v) {
1.61 - resG=&_resG;
1.62 - sym=resG->G.first_sym_edge(v);
1.63 - while( sym.valid() && !(free()>0) ) { ++sym; }
1.64 - }
1.65 - out_edge_iterator& operator++() {
1.66 - ++sym;
1.67 - while( sym.valid() && !(free()>0) ) { ++sym; }
1.68 - return *this;
1.69 - }
1.70 - };
1.71 -
1.72 - out_edge_iterator first_out_edge(const node_iterator& v) {
1.73 - return out_edge_iterator(*this, v);
1.74 - }
1.75 -
1.76 - each_node_iterator first_node() {
1.77 - return G.first_node();
1.78 - }
1.79 -
1.80 - node_iterator tail(const edge_iterator& e) { return G.a_node(e.sym); }
1.81 - node_iterator head(const edge_iterator& e) { return G.b_node(e.sym); }
1.82 -
1.83 - int id(const node_iterator& v) { return G.id(v); }
1.84 -
1.85 - //node_iterator invalid_node() { return G.invalid_node(); }
1.86 - //res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; }
1.87 - };
1.88 -
1.89 - template <typename graph_type, typename T>
1.90 - struct max_flow_type {
1.91 - typedef typename graph_type::node_iterator node_iterator;
1.92 - typedef typename graph_type::edge_iterator edge_iterator;
1.93 - typedef typename graph_type::each_node_iterator each_node_iterator;
1.94 - typedef typename graph_type::out_edge_iterator out_edge_iterator;
1.95 - typedef typename graph_type::in_edge_iterator in_edge_iterator;
1.96 - graph_type& G;
1.97 - node_iterator s;
1.98 - node_iterator t;
1.99 - edge_property_vector<graph_type, T> flow;
1.100 - edge_property_vector<graph_type, T>& capacity;
1.101 -
1.102 - 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) {
1.103 - for(each_node_iterator i=G.first_node(); i.valid(); ++i)
1.104 - for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j)
1.105 - flow.put(j, 0);
1.106 - }
1.107 - void run() {
1.108 - typedef res_graph_type<graph_type, T> aug_graph_type;
1.109 - aug_graph_type res_graph(G, flow, capacity);
1.110 -
1.111 - bool augment;
1.112 - do {
1.113 - augment=false;
1.114 -
1.115 - typedef std::queue<aug_graph_type::out_edge_iterator> bfs_queue_type;
1.116 - bfs_queue_type bfs_queue;
1.117 - bfs_queue.push(res_graph.first_out_edge(s));
1.118 -
1.119 - typedef node_property_vector<aug_graph_type, bool> reached_type;
1.120 - reached_type reached(res_graph, false);
1.121 - reached.put(s, true);
1.122 -
1.123 - bfs_iterator1< aug_graph_type, reached_type >
1.124 - res_bfs(res_graph, bfs_queue, reached);
1.125 -
1.126 - typedef node_property_vector<aug_graph_type, aug_graph_type::edge_iterator> pred_type;
1.127 - pred_type pred(res_graph);
1.128 - aug_graph_type::edge_iterator a;
1.129 - a.make_invalid();
1.130 - pred.put(s, a);
1.131 -
1.132 - typedef node_property_vector<aug_graph_type, int> free_type;
1.133 - free_type free(res_graph);
1.134 -
1.135 - //searching for augmenting path
1.136 - while ( res_bfs.valid() ) {
1.137 - //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl;
1.138 - if (res_bfs.newly_reached()) {
1.139 - aug_graph_type::edge_iterator e;
1.140 - e=res_bfs;
1.141 - node_iterator v=res_graph.tail(e);
1.142 - node_iterator w=res_graph.head(e);
1.143 - //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
1.144 - pred.put(w, e);
1.145 - if (pred.get(v).valid()) {
1.146 - free.put(w, std::min(free.get(v), e.free()));
1.147 - //std::cout <<" nem elso csucs: ";
1.148 - //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
1.149 - } else {
1.150 - free.put(w, e.free());
1.151 - //std::cout <<" elso csucs: ";
1.152 - //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
1.153 - }
1.154 - //std::cout<<std::endl;
1.155 - }
1.156 -
1.157 - if (res_graph.head(res_bfs)==t) break;
1.158 - ++res_bfs;
1.159 - }
1.160 - if (reached.get(t)) {
1.161 - augment=true;
1.162 - node_iterator n=t;
1.163 - T augment_value=free.get(t);
1.164 - std::cout<<"augmentation: ";
1.165 - while (pred.get(n).valid()) {
1.166 - aug_graph_type::edge_iterator e=pred.get(n);
1.167 - e.augment(augment_value);
1.168 - std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
1.169 - n=res_graph.tail(e);
1.170 - }
1.171 - std::cout<<std::endl;
1.172 - }
1.173 -
1.174 - std::cout << "actual flow: "<< std::endl;
1.175 - for(typename graph_type::each_edge_iterator e=G.first_edge(); e.valid(); ++e) {
1.176 - std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
1.177 - }
1.178 - std::cout<<std::endl;
1.179 -
1.180 - } while (augment);
1.181 - }
1.182 - };
1.183 -
1.184 -} // namespace hugo
1.185 -
1.186 -#endif //MARCI_MAX_FLOW_HH