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