Changeset 19:3151a1026db9 in lemon0.x for src/work/marci_max_flow.hh
 Timestamp:
 01/20/04 18:39:13 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@32
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci_max_flow.hh
r17 r19 4 4 #include <algorithm> 5 5 6 #include <marci_graph_traits.hh>7 6 #include <marci_property_vector.hh> 8 7 #include <marci_bfs.hh> … … 12 11 template<typename graph_type, typename T> 13 12 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 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; 19 16 graph_type& G; 20 17 edge_property_vector<graph_type, T>& flow; … … 23 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) { } 24 21 25 class res_edge_it{22 class edge_iterator { 26 23 friend class res_graph_type<graph_type, T>; 27 24 protected: 28 25 res_graph_type<graph_type, T>* resG; 29 sym_edge_iterator sym;26 old_sym_edge_iterator sym; 30 27 public: 31 res_edge_it() { }28 edge_iterator() { } 32 29 //bool is_free() { 33 30 //if (resG>G.a_node(sym)==resG>G.tail(sym)) { … … 44 41 } 45 42 } 46 bool is_valid() { return sym.is_valid(); }43 bool valid() { return sym.valid(); } 47 44 void make_invalid() { sym.make_invalid(); } 48 45 void augment(T a) { … … 55 52 }; 56 53 57 class res_out_edge_it : public res_edge_it{54 class out_edge_iterator : public edge_iterator { 58 55 public: 59 res_out_edge_it() { }60 res_out_edge_it(res_graph_type<graph_type, T>& _resG, const node_iterator& v) {56 out_edge_iterator() { } 57 out_edge_iterator(res_graph_type<graph_type, T>& _resG, const node_iterator& v) { 61 58 resG=&_resG; 62 59 sym=resG>G.first_sym_edge(v); 63 while( sym. is_valid() && !(free()>0) ) { ++sym; }60 while( sym.valid() && !(free()>0) ) { ++sym; } 64 61 } 65 res_out_edge_it& operator++() {62 out_edge_iterator& operator++() { 66 63 ++sym; 67 while( sym. is_valid() && !(free()>0) ) { ++sym; }64 while( sym.valid() && !(free()>0) ) { ++sym; } 68 65 return *this; 69 66 } 70 67 }; 71 68 72 res_out_edge_itfirst_out_edge(const node_iterator& v) {73 return res_out_edge_it(*this, v);69 out_edge_iterator first_out_edge(const node_iterator& v) { 70 return out_edge_iterator(*this, v); 74 71 } 75 72 … … 78 75 } 79 76 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); }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); } 82 79 83 80 int id(const node_iterator& v) { return G.id(v); } 84 81 85 82 //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; 83 //res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; } 96 84 }; 97 85 98 86 template <typename graph_type, typename T> 99 87 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 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; 107 93 graph_type& G; 108 94 node_iterator s; … … 112 98 113 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) { 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)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) 116 102 flow.put(j, 0); 117 103 } … … 124 110 augment=false; 125 111 126 typedef std::queue< graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type;112 typedef std::queue<aug_graph_type::out_edge_iterator> bfs_queue_type; 127 113 bfs_queue_type bfs_queue; 128 114 bfs_queue.push(res_graph.first_out_edge(s)); … … 135 121 res_bfs(res_graph, bfs_queue, reached); 136 122 137 typedef node_property_vector<aug_graph_type, graph_traits<aug_graph_type>::edge_iterator> pred_type;123 typedef node_property_vector<aug_graph_type, aug_graph_type::edge_iterator> pred_type; 138 124 pred_type pred(res_graph); 139 graph_traits<aug_graph_type>::edge_iterator a;125 aug_graph_type::edge_iterator a; 140 126 a.make_invalid(); 141 127 pred.put(s, a); … … 145 131 146 132 //searching for augmenting path 147 while ( res_bfs. is_valid() ) {133 while ( res_bfs.valid() ) { 148 134 //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;135 if (res_bfs.newly_reached()) { 136 aug_graph_type::edge_iterator e; 151 137 e=res_bfs; 152 138 node_iterator v=res_graph.tail(e); … … 154 140 //std::cout<<G.id(v)<<">"<<G.id(w)<<", "<<G.id(w)<<" is newly reached"; 155 141 pred.put(w, e); 156 if (pred.get(v). is_valid()) {142 if (pred.get(v).valid()) { 157 143 free.put(w, std::min(free.get(v), e.free())); 158 144 //std::cout <<" nem elso csucs: "; … … 174 160 T augment_value=free.get(t); 175 161 std::cout<<"augmentation: "; 176 while (pred.get(n). is_valid()) {177 graph_traits<aug_graph_type>::edge_iterator e=pred.get(n);162 while (pred.get(n).valid()) { 163 aug_graph_type::edge_iterator e=pred.get(n); 178 164 e.augment(augment_value); 179 165 std::cout<<"("<<res_graph.tail(e)<< ">"<<res_graph.head(e)<<") "; … … 184 170 185 171 std::cout << "actual flow: "<< std::endl; 186 for( graph_traits<graph_type>::each_edge_iterator e=G.first_edge(); e.is_valid(); ++e) {172 for(typename graph_type::each_edge_iterator e=G.first_edge(); e.valid(); ++e) { 187 173 std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") "; 188 174 }
Note: See TracChangeset
for help on using the changeset viewer.