Changeset 69:24c2c2989e0f in lemon-0.x for src/work/edmonds_karp.hh
- Timestamp:
- 02/09/04 14:11:10 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/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.