1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/marci_max_flow.hh Tue Dec 30 13:59:08 2003 +0000
1.3 @@ -0,0 +1,230 @@
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_graph_traits.hh>
1.10 +#include <marci_property_vector.hh>
1.11 +#include <marci_bfs.hh>
1.12 +
1.13 +namespace marci {
1.14 +
1.15 + template<typename graph_type, typename T>
1.16 + class res_graph_type {
1.17 + typedef typename graph_traits<graph_type>::node_iterator node_iterator;
1.18 + typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
1.19 + typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
1.20 + typedef typename graph_traits<graph_type>::sym_edge_iterator sym_edge_iterator;
1.21 +
1.22 + graph_type& G;
1.23 + edge_property_vector<graph_type, T>& flow;
1.24 + edge_property_vector<graph_type, T>& capacity;
1.25 + public:
1.26 + 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.27 +
1.28 + class res_edge_it {
1.29 + friend class res_graph_type<graph_type, T>;
1.30 + protected:
1.31 + res_graph_type<graph_type, T>* resG;
1.32 + sym_edge_iterator sym;
1.33 + public:
1.34 + res_edge_it() { }
1.35 + //bool is_free() {
1.36 + //if (resG->G.a_node(sym)==resG->G.tail(sym)) {
1.37 + // return (resG->flow.get(sym)<resG->capacity.get(sym));
1.38 + //} else {
1.39 + // return (resG->flow.get(sym)>0);
1.40 + //}
1.41 + //}
1.42 + T free() {
1.43 + if (resG->G.a_node(sym)==resG->G.tail(sym)) {
1.44 + return (resG->capacity.get(sym)-resG->flow.get(sym));
1.45 + } else {
1.46 + return (resG->flow.get(sym));
1.47 + }
1.48 + }
1.49 + bool is_valid() { return sym.is_valid(); }
1.50 + void augment(T a) {
1.51 + if (resG->G.a_node(sym)==resG->G.tail(sym)) {
1.52 + resG->flow.put(sym, resG->flow.get(sym)+a);
1.53 + } else {
1.54 + resG->flow.put(sym, resG->flow.get(sym)-a);
1.55 + }
1.56 + }
1.57 + };
1.58 +
1.59 + class res_out_edge_it : public res_edge_it {
1.60 + public:
1.61 + res_out_edge_it() { }
1.62 + res_out_edge_it(res_graph_type<graph_type, T>& _resG, const node_iterator& v) {
1.63 + resG=&_resG;
1.64 + sym=resG->G.first_sym_edge(v);
1.65 + while( sym.is_valid() && !(free()>0) ) { ++sym; }
1.66 + }
1.67 + res_out_edge_it& operator++() {
1.68 + ++sym;
1.69 + while( sym.is_valid() && !(free()>0) ) { ++sym; }
1.70 + return *this;
1.71 + }
1.72 + };
1.73 +
1.74 + res_out_edge_it first_out_edge(const node_iterator& v) {
1.75 + return res_out_edge_it(*this, v);
1.76 + }
1.77 +
1.78 + each_node_iterator first_node() {
1.79 + return G.first_node();
1.80 + }
1.81 +
1.82 + node_iterator tail(const res_edge_it& e) { return G.a_node(e.sym); }
1.83 + node_iterator head(const res_edge_it& e) { return G.b_node(e.sym); }
1.84 +
1.85 + int id(const node_iterator& v) { return G.id(v); }
1.86 +
1.87 + node_iterator invalid_node() { return G.invalid_node(); }
1.88 + res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; }
1.89 +
1.90 + };
1.91 +
1.92 + template <typename graph_type, typename T>
1.93 + struct graph_traits< res_graph_type<graph_type, T> > {
1.94 + typedef typename graph_traits<graph_type>::node_iterator node_iterator;
1.95 + typedef typename res_graph_type<graph_type, T>::res_edge_it edge_iterator;
1.96 + typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
1.97 + typedef typename res_graph_type<graph_type, T>::res_out_edge_it out_edge_iterator;
1.98 + };
1.99 +
1.100 + template <typename graph_type, typename pred_type, typename free_type>
1.101 + struct flow_visitor {
1.102 + typedef typename graph_traits<graph_type>::node_iterator node_iterator;
1.103 + typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
1.104 + typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
1.105 + typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
1.106 + graph_type& G;
1.107 + pred_type& pred;
1.108 + free_type& free;
1.109 + flow_visitor(graph_type& _G, pred_type& _pred, free_type& _free) : G(_G), pred(_pred), free(_free) { }
1.110 + void at_previously_reached(out_edge_iterator& e) {
1.111 + //node_iterator v=G.tail(e);
1.112 + //node_iterator w=G.head(e);
1.113 + //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is already reached";
1.114 + //std::cout<<std::endl;
1.115 + }
1.116 + void at_newly_reached(out_edge_iterator& e) {
1.117 + node_iterator v=G.tail(e);
1.118 + node_iterator w=G.head(e);
1.119 + //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
1.120 + pred.put(w, e);
1.121 + if (pred.get(v).is_valid()) {
1.122 + free.put(w, std::min(free.get(v), e.free()));
1.123 + //std::cout <<" nem elso csucs: ";
1.124 + //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
1.125 + } else {
1.126 + free.put(w, e.free());
1.127 + //std::cout <<" elso csucs: ";
1.128 + //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
1.129 + }
1.130 + //std::cout<<std::endl;
1.131 + }
1.132 + };
1.133 +
1.134 + template <typename graph_type, typename T>
1.135 + struct max_flow_type {
1.136 +
1.137 + typedef typename graph_traits<graph_type>::node_iterator node_iterator;
1.138 + typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
1.139 + typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
1.140 + typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
1.141 + typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
1.142 +
1.143 + graph_type& G;
1.144 + node_iterator s;
1.145 + node_iterator t;
1.146 + edge_property_vector<graph_type, T> flow;
1.147 + edge_property_vector<graph_type, T>& capacity;
1.148 +
1.149 + 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.150 + for(each_node_iterator i=G.first_node(); i.is_valid(); ++i)
1.151 + for(out_edge_iterator j=G.first_out_edge(i); j.is_valid(); ++j)
1.152 + flow.put(j, 0);
1.153 + }
1.154 + void run() {
1.155 + typedef res_graph_type<graph_type, T> aug_graph_type;
1.156 + aug_graph_type res_graph(G, flow, capacity);
1.157 +
1.158 + typedef std::queue<graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type;
1.159 + bfs_queue_type bfs_queue;
1.160 + //bfs_queue.push(res_graph.first_out_edge(s));
1.161 +
1.162 + typedef node_property_vector<aug_graph_type, bool> reached_type;
1.163 + //reached_type reached(res_graph, false);
1.164 + reached_type reached(res_graph);
1.165 + //reached.put(s, true);
1.166 +
1.167 + typedef node_property_vector<aug_graph_type, graph_traits<aug_graph_type>::edge_iterator> pred_type;
1.168 + pred_type pred(res_graph);
1.169 + pred.put(s, res_graph.invalid_edge());
1.170 +
1.171 + typedef node_property_vector<aug_graph_type, int> free_type;
1.172 + free_type free(res_graph);
1.173 +
1.174 + typedef flow_visitor<aug_graph_type, pred_type, free_type> visitor_type;
1.175 + visitor_type vis(res_graph, pred, free);
1.176 +
1.177 + bfs_iterator< aug_graph_type, reached_type, visitor_type >
1.178 + res_bfs(res_graph, bfs_queue, reached, vis);
1.179 +
1.180 + //for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) {
1.181 + //for(graph_traits<aug_graph_type>::out_edge_iterator j=res_graph.first_out_edge(i); j.is_valid(); ++j) {
1.182 + // std::cout<<"("<<res_graph.tail(j)<< "->"<<res_graph.head(j)<<") ";
1.183 + //}
1.184 + //}
1.185 + //std::cout<<std::endl;
1.186 +
1.187 + //char c;
1.188 + bool augment;
1.189 + do {
1.190 + augment=false;
1.191 +
1.192 + while (!bfs_queue.empty()) { bfs_queue.pop(); }
1.193 + bfs_queue.push(res_graph.first_out_edge(s));
1.194 +
1.195 + for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) { reached.put(i, false); }
1.196 + reached.put(s, true);
1.197 +
1.198 + //searching for augmenting path
1.199 + while ( /*std::cin>>c &&*/ res_bfs.is_valid() ) {
1.200 + res_bfs.process();
1.201 + //if (res_graph.head(graph_traits<aug_graph_type>::out_edge_iterator(res_bfs))==t) break;
1.202 + if (res_graph.head(res_bfs)==t) break;
1.203 + //res_bfs.next();
1.204 + ++res_bfs;
1.205 + }
1.206 + //for (; std::cin>>c && !res_bfs.finished() && res_graph.head(res_bfs.current())!=t; res_bfs.next()) { res_bfs.process(); }
1.207 + if (reached.get(t)) {
1.208 + augment=true;
1.209 + node_iterator n=t;
1.210 + T augment_value=free.get(t);
1.211 + std::cout<<"augmentation: ";
1.212 + while (pred.get(n).is_valid()) {
1.213 + graph_traits<aug_graph_type>::edge_iterator e=pred.get(n);
1.214 + e.augment(augment_value);
1.215 + std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
1.216 + n=res_graph.tail(e);
1.217 + }
1.218 + std::cout<<std::endl;
1.219 + }
1.220 +
1.221 + std::cout << "max flow:"<< std::endl;
1.222 + for(graph_traits<graph_type>::each_edge_iterator e=G.first_edge(); e.is_valid(); ++e) {
1.223 + std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
1.224 + }
1.225 + std::cout<<std::endl;
1.226 +
1.227 + } while (augment);
1.228 + }
1.229 + };
1.230 +
1.231 +} // namespace marci
1.232 +
1.233 +#endif //MARCI_MAX_FLOW_HH