Changeset 69:24c2c2989e0f in lemon0.x for src/work/edmonds_karp.hh
 Timestamp:
 02/09/04 14:11:10 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@85
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/edmonds_karp.hh
r64 r69 97 97 int id(NodeIt v) const { return G.id(v); } 98 98 99 template <typename ValueType>99 template <typename S> 100 100 class NodeMap { 101 typename Graph::NodeMap< ValueType> node_map;101 typename Graph::NodeMap<S> node_map; 102 102 public: 103 103 NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { } 104 NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, ValueTypea) : node_map(_G.G, a) { }105 void set(NodeIt nit, ValueTypea) { node_map.set(nit, a); }106 ValueTypeget(NodeIt nit) const { return node_map.get(nit); }104 NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { } 105 void set(NodeIt nit, S a) { node_map.set(nit, a); } 106 S get(NodeIt nit) const { return node_map.get(nit); } 107 107 }; 108 108 … … 141 141 //searching for augmenting path 142 142 while ( !res_bfs.finished() ) { 143 //std::queue<AugOutEdgeIt> bfs_copy(res_bfs.getBfsQueue());144 //while (!bfs_copy.empty()) {145 // AugOutEdgeIt e=bfs_copy.front();146 // bfs_copy.pop();147 // if (e.valid()) {148 // std::cout<<"queue:"<<res_graph.tail(e)<<">"<<res_graph.head(e)<<" ";149 // } else {150 // std::cout<<"queue:"<<res_graph.aNode(e)<<">"<<" ";151 // }152 //}153 //std::cout<<std::endl;154 143 AugOutEdgeIt e=AugOutEdgeIt(res_bfs); 155 //if (e.valid()) {156 // std::cout<<"actual:"<<res_graph.tail(e)<<">"<<res_graph.head(e)<<std::endl;157 //} else {158 // std::cout<<"actual:"<<res_graph.aNode(e)<<">"<<std::endl;159 //}160 144 if (e.valid() && res_bfs.isBNodeNewlyReached()) { 161 145 NodeIt v=res_graph.tail(e); 162 146 NodeIt w=res_graph.head(e); 163 //std::cout<<v<<">"<<w<<std::endl;164 147 pred.set(w, e); 165 148 if (pred.get(v).valid()) { … … 177 160 NodeIt n=t; 178 161 T augment_value=free.get(t); 179 //std::cout<<"augmentation: ";180 162 while (pred.get(n).valid()) { 181 163 AugEdgeIt e=pred.get(n); 182 164 e.augment(augment_value); 183 //std::cout<<"("<<res_graph.tail(e)<< ">"<<res_graph.head(e)<<") ";184 165 n=res_graph.tail(e); 185 166 } 186 //std::cout<<std::endl;187 167 } 188 //std::cout << "actual flow: "<< std::endl;189 //for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {190 //std::cout<<"("<<G.tail(e)<< ""<<flow.get(e)<<">"<<G.head(e)<<") ";191 //}192 //std::cout<<std::endl;193 168 194 169 return _augment; … … 197 172 while (augment()) { } 198 173 } 174 T flowValue() { 175 T a=0; 176 for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) { 177 a+=flow.get(i); 178 } 179 return a; 180 } 199 181 }; 200 182
Note: See TracChangeset
for help on using the changeset viewer.