1.1 --- a/src/work/jacint/preflow.h Thu Apr 29 09:08:14 2004 +0000
1.2 +++ b/src/work/jacint/preflow.h Thu Apr 29 10:16:46 2004 +0000
1.3 @@ -59,7 +59,7 @@
1.4 typedef typename Graph::template NodeMap<Node> NNMap;
1.5 typedef typename std::vector<Node> VecNode;
1.6
1.7 - const Graph& G;
1.8 + const Graph* g;
1.9 Node s;
1.10 Node t;
1.11 const CapMap* capacity;
1.12 @@ -79,7 +79,7 @@
1.13
1.14 Preflow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
1.15 FlowMap& _flow) :
1.16 - G(_G), s(_s), t(_t), capacity(&_capacity),
1.17 + g(&_G), s(_s), t(_t), capacity(&_capacity),
1.18 flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {}
1.19
1.20 void run() {
1.21 @@ -109,13 +109,13 @@
1.22
1.23 VecStack active(n);
1.24
1.25 - NNMap left(G,INVALID);
1.26 - NNMap right(G,INVALID);
1.27 + NNMap left(*g, INVALID);
1.28 + NNMap right(*g, INVALID);
1.29 VecNode level_list(n,INVALID);
1.30 //List of the nodes in level i<n, set to n.
1.31
1.32 NodeIt v;
1.33 - for(G.first(v); G.valid(v); G.next(v)) level.set(v,n);
1.34 + for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
1.35 //setting each node to level n
1.36
1.37 switch ( fe ) {
1.38 @@ -123,13 +123,13 @@
1.39 {
1.40 //counting the excess
1.41 NodeIt v;
1.42 - for(G.first(v); G.valid(v); G.next(v)) {
1.43 + for(g->first(v); g->valid(v); g->next(v)) {
1.44 T exc=0;
1.45
1.46 InEdgeIt e;
1.47 - for(G.first(e,v); G.valid(e); G.next(e)) exc+=(*flow)[e];
1.48 + for(g->first(e,v); g->valid(e); g->next(e)) exc+=(*flow)[e];
1.49 OutEdgeIt f;
1.50 - for(G.first(f,v); G.valid(f); G.next(f)) exc-=(*flow)[f];
1.51 + for(g->first(f,v); g->valid(f); g->next(f)) exc-=(*flow)[f];
1.52
1.53 excess.set(v,exc);
1.54
1.55 @@ -145,9 +145,9 @@
1.56 T exc=0;
1.57
1.58 InEdgeIt e;
1.59 - for(G.first(e,t); G.valid(e); G.next(e)) exc+=(*flow)[e];
1.60 + for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
1.61 OutEdgeIt f;
1.62 - for(G.first(f,t); G.valid(f); G.next(f)) exc-=(*flow)[f];
1.63 + for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
1.64
1.65 excess.set(t,exc);
1.66
1.67 @@ -216,9 +216,9 @@
1.68 int l=level[v]+1;
1.69
1.70 InEdgeIt e;
1.71 - for(G.first(e,v); G.valid(e); G.next(e)) {
1.72 + for(g->first(e,v); g->valid(e); g->next(e)) {
1.73 if ( (*capacity)[e] == (*flow)[e] ) continue;
1.74 - Node u=G.tail(e);
1.75 + Node u=g->tail(e);
1.76 if ( level[u] >= n ) {
1.77 bfs_queue.push(u);
1.78 level.set(u, l);
1.79 @@ -227,9 +227,9 @@
1.80 }
1.81
1.82 OutEdgeIt f;
1.83 - for(G.first(f,v); G.valid(f); G.next(f)) {
1.84 + for(g->first(f,v); g->valid(f); g->next(f)) {
1.85 if ( 0 == (*flow)[f] ) continue;
1.86 - Node u=G.head(f);
1.87 + Node u=g->head(f);
1.88 if ( level[u] >= n ) {
1.89 bfs_queue.push(u);
1.90 level.set(u, l);
1.91 @@ -269,9 +269,12 @@
1.92 template<typename _CutMap>
1.93 void actMinCut(_CutMap& M) {
1.94 NodeIt v;
1.95 - for(G.first(v); G.valid(v); G.next(v))
1.96 - if ( level[v] < n ) M.set(v,false);
1.97 - else M.set(v,true);
1.98 + for(g->first(v); g->valid(v); g->next(v))
1.99 + if ( level[v] < n ) {
1.100 + M.set(v,false);
1.101 + } else {
1.102 + M.set(v,true);
1.103 + }
1.104 }
1.105
1.106
1.107 @@ -292,8 +295,8 @@
1.108 queue.pop();
1.109
1.110 OutEdgeIt e;
1.111 - for(G.first(e,w) ; G.valid(e); G.next(e)) {
1.112 - Node v=G.head(e);
1.113 + for(g->first(e,w) ; g->valid(e); g->next(e)) {
1.114 + Node v=g->head(e);
1.115 if (!M[v] && (*flow)[e] < (*capacity)[e] ) {
1.116 queue.push(v);
1.117 M.set(v, true);
1.118 @@ -301,8 +304,8 @@
1.119 }
1.120
1.121 InEdgeIt f;
1.122 - for(G.first(f,w) ; G.valid(f); G.next(f)) {
1.123 - Node v=G.tail(f);
1.124 + for(g->first(f,w) ; g->valid(f); g->next(f)) {
1.125 + Node v=g->tail(f);
1.126 if (!M[v] && (*flow)[f] > 0 ) {
1.127 queue.push(v);
1.128 M.set(v, true);
1.129 @@ -322,7 +325,7 @@
1.130 void maxMinCut(_CutMap& M) {
1.131
1.132 NodeIt v;
1.133 - for(G.first(v) ; G.valid(v); G.next(v)) {
1.134 + for(g->first(v) ; g->valid(v); g->next(v)) {
1.135 M.set(v, true);
1.136 }
1.137
1.138 @@ -337,8 +340,8 @@
1.139
1.140
1.141 InEdgeIt e;
1.142 - for(G.first(e,w) ; G.valid(e); G.next(e)) {
1.143 - Node v=G.tail(e);
1.144 + for(g->first(e,w) ; g->valid(e); g->next(e)) {
1.145 + Node v=g->tail(e);
1.146 if (M[v] && (*flow)[e] < (*capacity)[e] ) {
1.147 queue.push(v);
1.148 M.set(v, false);
1.149 @@ -346,8 +349,8 @@
1.150 }
1.151
1.152 OutEdgeIt f;
1.153 - for(G.first(f,w) ; G.valid(f); G.next(f)) {
1.154 - Node v=G.head(f);
1.155 + for(g->first(f,w) ; g->valid(f); g->next(f)) {
1.156 + Node v=g->head(f);
1.157 if (M[v] && (*flow)[f] > 0 ) {
1.158 queue.push(v);
1.159 M.set(v, false);
1.160 @@ -385,10 +388,10 @@
1.161 int newlevel=n; //bound on the next level of w
1.162
1.163 OutEdgeIt e;
1.164 - for(G.first(e,w); G.valid(e); G.next(e)) {
1.165 + for(g->first(e,w); g->valid(e); g->next(e)) {
1.166
1.167 if ( (*flow)[e] == (*capacity)[e] ) continue;
1.168 - Node v=G.head(e);
1.169 + Node v=g->head(e);
1.170
1.171 if( lev > level[v] ) { //Push is allowed now
1.172
1.173 @@ -418,10 +421,10 @@
1.174
1.175 if ( exc > 0 ) {
1.176 InEdgeIt e;
1.177 - for(G.first(e,w); G.valid(e); G.next(e)) {
1.178 + for(g->first(e,w); g->valid(e); g->next(e)) {
1.179
1.180 if( (*flow)[e] == 0 ) continue;
1.181 - Node v=G.tail(e);
1.182 + Node v=g->tail(e);
1.183
1.184 if( lev > level[v] ) { //Push is allowed now
1.185
1.186 @@ -474,12 +477,12 @@
1.187 int l=level[v]+1;
1.188
1.189 InEdgeIt e;
1.190 - for(G.first(e,v); G.valid(e); G.next(e)) {
1.191 - Node w=G.tail(e);
1.192 + for(g->first(e,v); g->valid(e); g->next(e)) {
1.193 + Node w=g->tail(e);
1.194 if ( level[w] == n && w != s ) {
1.195 bfs_queue.push(w);
1.196 Node first=level_list[l];
1.197 - if ( G.valid(first) ) left.set(first,w);
1.198 + if ( g->valid(first) ) left.set(first,w);
1.199 right.set(w,first);
1.200 level_list[l]=w;
1.201 level.set(w, l);
1.202 @@ -489,11 +492,11 @@
1.203
1.204 //the starting flow
1.205 OutEdgeIt e;
1.206 - for(G.first(e,s); G.valid(e); G.next(e))
1.207 + for(g->first(e,s); g->valid(e); g->next(e))
1.208 {
1.209 T c=(*capacity)[e];
1.210 if ( c == 0 ) continue;
1.211 - Node w=G.head(e);
1.212 + Node w=g->head(e);
1.213 if ( level[w] < n ) {
1.214 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
1.215 flow->set(e, c);
1.216 @@ -518,13 +521,13 @@
1.217 int l=level[v]+1;
1.218
1.219 InEdgeIt e;
1.220 - for(G.first(e,v); G.valid(e); G.next(e)) {
1.221 + for(g->first(e,v); g->valid(e); g->next(e)) {
1.222 if ( (*capacity)[e] == (*flow)[e] ) continue;
1.223 - Node w=G.tail(e);
1.224 + Node w=g->tail(e);
1.225 if ( level[w] == n && w != s ) {
1.226 bfs_queue.push(w);
1.227 Node first=level_list[l];
1.228 - if ( G.valid(first) ) left.set(first,w);
1.229 + if ( g->valid(first) ) left.set(first,w);
1.230 right.set(w,first);
1.231 level_list[l]=w;
1.232 level.set(w, l);
1.233 @@ -532,13 +535,13 @@
1.234 }
1.235
1.236 OutEdgeIt f;
1.237 - for(G.first(f,v); G.valid(f); G.next(f)) {
1.238 + for(g->first(f,v); g->valid(f); g->next(f)) {
1.239 if ( 0 == (*flow)[f] ) continue;
1.240 - Node w=G.head(f);
1.241 + Node w=g->head(f);
1.242 if ( level[w] == n && w != s ) {
1.243 bfs_queue.push(w);
1.244 Node first=level_list[l];
1.245 - if ( G.valid(first) ) left.set(first,w);
1.246 + if ( g->valid(first) ) left.set(first,w);
1.247 right.set(w,first);
1.248 level_list[l]=w;
1.249 level.set(w, l);
1.250 @@ -549,11 +552,11 @@
1.251
1.252 //the starting flow
1.253 OutEdgeIt e;
1.254 - for(G.first(e,s); G.valid(e); G.next(e))
1.255 + for(g->first(e,s); g->valid(e); g->next(e))
1.256 {
1.257 T rem=(*capacity)[e]-(*flow)[e];
1.258 if ( rem == 0 ) continue;
1.259 - Node w=G.head(e);
1.260 + Node w=g->head(e);
1.261 if ( level[w] < n ) {
1.262 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
1.263 flow->set(e, (*capacity)[e]);
1.264 @@ -562,10 +565,10 @@
1.265 }
1.266
1.267 InEdgeIt f;
1.268 - for(G.first(f,s); G.valid(f); G.next(f))
1.269 + for(g->first(f,s); g->valid(f); g->next(f))
1.270 {
1.271 if ( (*flow)[f] == 0 ) continue;
1.272 - Node w=G.tail(f);
1.273 + Node w=g->tail(f);
1.274 if ( level[w] < n ) {
1.275 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
1.276 excess.set(w, excess[w]+(*flow)[f]);
1.277 @@ -589,8 +592,8 @@
1.278 Node left_n=left[w];
1.279
1.280 //unlacing starts
1.281 - if ( G.valid(right_n) ) {
1.282 - if ( G.valid(left_n) ) {
1.283 + if ( g->valid(right_n) ) {
1.284 + if ( g->valid(left_n) ) {
1.285 right.set(left_n, right_n);
1.286 left.set(right_n, left_n);
1.287 } else {
1.288 @@ -598,7 +601,7 @@
1.289 left.set(right_n, INVALID);
1.290 }
1.291 } else {
1.292 - if ( G.valid(left_n) ) {
1.293 + if ( g->valid(left_n) ) {
1.294 right.set(left_n, INVALID);
1.295 } else {
1.296 level_list[lev]=INVALID;
1.297 @@ -606,12 +609,12 @@
1.298 }
1.299 //unlacing ends
1.300
1.301 - if ( !G.valid(level_list[lev]) ) {
1.302 + if ( !g->valid(level_list[lev]) ) {
1.303
1.304 //gapping starts
1.305 for (int i=lev; i!=k ; ) {
1.306 Node v=level_list[++i];
1.307 - while ( G.valid(v) ) {
1.308 + while ( g->valid(v) ) {
1.309 level.set(v,n);
1.310 v=right[v];
1.311 }
1.312 @@ -637,7 +640,7 @@
1.313 if ( what_heur ) b=newlevel;
1.314 if ( k < newlevel ) ++k; //now k=newlevel
1.315 Node first=level_list[newlevel];
1.316 - if ( G.valid(first) ) left.set(first,w);
1.317 + if ( g->valid(first) ) left.set(first,w);
1.318 right.set(w,first);
1.319 left.set(w,INVALID);
1.320 level_list[newlevel]=w;
2.1 --- a/src/work/marci/edmonds_karp.h Thu Apr 29 09:08:14 2004 +0000
2.2 +++ b/src/work/marci/edmonds_karp.h Thu Apr 29 10:16:46 2004 +0000
2.3 @@ -10,244 +10,10 @@
2.4 #include <invalid.h>
2.5 #include <graph_wrapper.h>
2.6 #include <maps.h>
2.7 +#include <for_each_macros.h>
2.8
2.9 namespace hugo {
2.10
2.11 -// template<typename Graph, typename Number, typename CapacityMap, typename FlowMap>
2.12 -// class ResGraph {
2.13 -// public:
2.14 -// typedef typename Graph::Node Node;
2.15 -// typedef typename Graph::NodeIt NodeIt;
2.16 -// private:
2.17 -// typedef typename Graph::SymEdgeIt OldSymEdgeIt;
2.18 -// const Graph& G;
2.19 -// const CapacityMap& capacity;
2.20 -// FlowMap& flow;
2.21 -// public:
2.22 -// ResGraph(const Graph& _G, const CapacityMap& _capacity, FlowMap& _flow) :
2.23 -// G(_G), capacity(_capacity), flow(_flow) { }
2.24 -
2.25 -// class Edge;
2.26 -// class OutEdgeIt;
2.27 -// friend class Edge;
2.28 -// friend class OutEdgeIt;
2.29 -
2.30 -// class Edge {
2.31 -// friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
2.32 -// protected:
2.33 -// const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
2.34 -// OldSymEdgeIt sym;
2.35 -// public:
2.36 -// Edge() { }
2.37 -// //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }
2.38 -// Number free() const {
2.39 -// if (resG->G.aNode(sym)==resG->G.tail(sym)) {
2.40 -// return (resG->capacity.get(sym)-resG->flow.get(sym));
2.41 -// } else {
2.42 -// return (resG->flow.get(sym));
2.43 -// }
2.44 -// }
2.45 -// bool valid() const { return sym.valid(); }
2.46 -// void augment(Number a) const {
2.47 -// if (resG->G.aNode(sym)==resG->G.tail(sym)) {
2.48 -// resG->flow.set(sym, resG->flow.get(sym)+a);
2.49 -// //resG->flow[sym]+=a;
2.50 -// } else {
2.51 -// resG->flow.set(sym, resG->flow.get(sym)-a);
2.52 -// //resG->flow[sym]-=a;
2.53 -// }
2.54 -// }
2.55 -// };
2.56 -
2.57 -// class OutEdgeIt : public Edge {
2.58 -// friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
2.59 -// public:
2.60 -// OutEdgeIt() { }
2.61 -// //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
2.62 -// private:
2.63 -// OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
2.64 -// resG=&_resG;
2.65 -// sym=resG->G.template first<OldSymEdgeIt>(v);
2.66 -// while( sym.valid() && !(free()>0) ) { ++sym; }
2.67 -// }
2.68 -// public:
2.69 -// OutEdgeIt& operator++() {
2.70 -// ++sym;
2.71 -// while( sym.valid() && !(free()>0) ) { ++sym; }
2.72 -// return *this;
2.73 -// }
2.74 -// };
2.75 -
2.76 -// void /*getF*/first(OutEdgeIt& e, Node v) const {
2.77 -// e=OutEdgeIt(*this, v);
2.78 -// }
2.79 -// void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
2.80 -
2.81 -// template< typename It >
2.82 -// It first() const {
2.83 -// It e;
2.84 -// /*getF*/first(e);
2.85 -// return e;
2.86 -// }
2.87 -
2.88 -// template< typename It >
2.89 -// It first(Node v) const {
2.90 -// It e;
2.91 -// /*getF*/first(e, v);
2.92 -// return e;
2.93 -// }
2.94 -
2.95 -// Node tail(Edge e) const { return G.aNode(e.sym); }
2.96 -// Node head(Edge e) const { return G.bNode(e.sym); }
2.97 -
2.98 -// Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
2.99 -// Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
2.100 -
2.101 -// int id(Node v) const { return G.id(v); }
2.102 -
2.103 -// template <typename S>
2.104 -// class NodeMap {
2.105 -// typename Graph::NodeMap<S> node_map;
2.106 -// public:
2.107 -// NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
2.108 -// NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
2.109 -// void set(Node nit, S a) { node_map.set(nit, a); }
2.110 -// S get(Node nit) const { return node_map.get(nit); }
2.111 -// S& operator[](Node nit) { return node_map[nit]; }
2.112 -// const S& operator[](Node nit) const { return node_map[nit]; }
2.113 -// };
2.114 -
2.115 -// };
2.116 -
2.117 -
2.118 -// template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
2.119 -// class ResGraph2 {
2.120 -// public:
2.121 -// typedef typename Graph::Node Node;
2.122 -// typedef typename Graph::NodeIt NodeIt;
2.123 -// private:
2.124 -// //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
2.125 -// typedef typename Graph::OutEdgeIt OldOutEdgeIt;
2.126 -// typedef typename Graph::InEdgeIt OldInEdgeIt;
2.127 -
2.128 -// const Graph& G;
2.129 -// FlowMap& flow;
2.130 -// const CapacityMap& capacity;
2.131 -// public:
2.132 -// ResGraph2(const Graph& _G, FlowMap& _flow,
2.133 -// const CapacityMap& _capacity) :
2.134 -// G(_G), flow(_flow), capacity(_capacity) { }
2.135 -
2.136 -// class Edge;
2.137 -// class OutEdgeIt;
2.138 -// friend class Edge;
2.139 -// friend class OutEdgeIt;
2.140 -
2.141 -// class Edge {
2.142 -// friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
2.143 -// protected:
2.144 -// const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
2.145 -// //OldSymEdgeIt sym;
2.146 -// OldOutEdgeIt out;
2.147 -// OldInEdgeIt in;
2.148 -// bool out_or_in; //true, iff out
2.149 -// public:
2.150 -// Edge() : out_or_in(true) { }
2.151 -// Number free() const {
2.152 -// if (out_or_in) {
2.153 -// return (resG->capacity.get(out)-resG->flow.get(out));
2.154 -// } else {
2.155 -// return (resG->flow.get(in));
2.156 -// }
2.157 -// }
2.158 -// bool valid() const {
2.159 -// return out_or_in && out.valid() || in.valid(); }
2.160 -// void augment(Number a) const {
2.161 -// if (out_or_in) {
2.162 -// resG->flow.set(out, resG->flow.get(out)+a);
2.163 -// } else {
2.164 -// resG->flow.set(in, resG->flow.get(in)-a);
2.165 -// }
2.166 -// }
2.167 -// };
2.168 -
2.169 -// class OutEdgeIt : public Edge {
2.170 -// friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
2.171 -// public:
2.172 -// OutEdgeIt() { }
2.173 -// private:
2.174 -// OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
2.175 -// resG=&_resG;
2.176 -// out=resG->G.template first<OldOutEdgeIt>(v);
2.177 -// while( out.valid() && !(free()>0) ) { ++out; }
2.178 -// if (!out.valid()) {
2.179 -// out_or_in=0;
2.180 -// in=resG->G.template first<OldInEdgeIt>(v);
2.181 -// while( in.valid() && !(free()>0) ) { ++in; }
2.182 -// }
2.183 -// }
2.184 -// public:
2.185 -// OutEdgeIt& operator++() {
2.186 -// if (out_or_in) {
2.187 -// Node v=resG->G.aNode(out);
2.188 -// ++out;
2.189 -// while( out.valid() && !(free()>0) ) { ++out; }
2.190 -// if (!out.valid()) {
2.191 -// out_or_in=0;
2.192 -// in=resG->G.template first<OldInEdgeIt>(v);
2.193 -// while( in.valid() && !(free()>0) ) { ++in; }
2.194 -// }
2.195 -// } else {
2.196 -// ++in;
2.197 -// while( in.valid() && !(free()>0) ) { ++in; }
2.198 -// }
2.199 -// return *this;
2.200 -// }
2.201 -// };
2.202 -
2.203 -// void /*getF*/first(OutEdgeIt& e, Node v) const {
2.204 -// e=OutEdgeIt(*this, v);
2.205 -// }
2.206 -// void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
2.207 -
2.208 -// template< typename It >
2.209 -// It first() const {
2.210 -// It e;
2.211 -// /*getF*/first(e);
2.212 -// return e;
2.213 -// }
2.214 -
2.215 -// template< typename It >
2.216 -// It first(Node v) const {
2.217 -// It e;
2.218 -// /*getF*/first(e, v);
2.219 -// return e;
2.220 -// }
2.221 -
2.222 -// Node tail(Edge e) const {
2.223 -// return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
2.224 -// Node head(Edge e) const {
2.225 -// return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
2.226 -
2.227 -// Node aNode(OutEdgeIt e) const {
2.228 -// return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
2.229 -// Node bNode(OutEdgeIt e) const {
2.230 -// return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
2.231 -
2.232 -// int id(Node v) const { return G.id(v); }
2.233 -
2.234 -// template <typename S>
2.235 -// class NodeMap {
2.236 -// typename Graph::NodeMap<S> node_map;
2.237 -// public:
2.238 -// NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
2.239 -// NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
2.240 -// void set(Node nit, S a) { node_map.set(nit, a); }
2.241 -// S get(Node nit) const { return node_map.get(nit); }
2.242 -// };
2.243 -// };
2.244 -
2.245 -
2.246 template <typename Graph, typename Number,
2.247 typename CapacityMap, typename FlowMap>
2.248 class MaxFlow {
2.249 @@ -265,18 +31,23 @@
2.250 typedef ResGraphWrapper<const Graph, Number, CapacityMap, FlowMap> ResGW;
2.251 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
2.252 typedef typename ResGW::Edge ResGWEdge;
2.253 + //typedef typename ResGW::template NodeMap<bool> ReachedMap;
2.254 + typedef typename Graph::template NodeMap<bool> ReachedMap;
2.255 + ReachedMap level;
2.256 + //reached is called level because of compatibility with preflow
2.257 public:
2.258
2.259 MaxFlow(const Graph& _g, Node _s, Node _t, const CapacityMap& _capacity,
2.260 FlowMap& _flow) :
2.261 - g(&_g), s(_s), t(_t), capacity(&_capacity), flow(&_flow) { }
2.262 + g(&_g), s(_s), t(_t), capacity(&_capacity), flow(&_flow), level(_g) { }
2.263
2.264 bool augmentOnShortestPath() {
2.265 ResGW res_graph(*g, *capacity, *flow);
2.266 bool _augment=false;
2.267
2.268 - BfsIterator< ResGW, typename ResGW::template NodeMap<bool> >
2.269 - bfs(res_graph);
2.270 + //ReachedMap level(res_graph);
2.271 + FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
2.272 + BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
2.273 bfs.pushAndSetReached(s);
2.274
2.275 typename ResGW::template NodeMap<ResGWEdge> pred(res_graph);
2.276 @@ -342,8 +113,9 @@
2.277
2.278 ResGW res_graph(*g, *capacity, *flow);
2.279
2.280 - BfsIterator< ResGW, typename ResGW::template NodeMap<bool> >
2.281 - bfs(res_graph);
2.282 + //ReachedMap level(res_graph);
2.283 + FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
2.284 + BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
2.285
2.286 bfs.pushAndSetReached(s);
2.287 //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's
2.288 @@ -454,8 +226,9 @@
2.289 ResGW res_graph(*g, *capacity, *flow);
2.290
2.291 //bfs for distances on the residual graph
2.292 - BfsIterator< ResGW, typename ResGW::template NodeMap<bool> >
2.293 - bfs(res_graph);
2.294 + //ReachedMap level(res_graph);
2.295 + FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
2.296 + BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
2.297 bfs.pushAndSetReached(s);
2.298 typename ResGW::template NodeMap<int>
2.299 dist(res_graph); //filled up with 0's
2.300 @@ -560,9 +333,10 @@
2.301 bool _augment=false;
2.302
2.303 ResGW res_graph(*g, *capacity, *flow);
2.304 -
2.305 - BfsIterator< ResGW, typename ResGW::template NodeMap<bool> >
2.306 - bfs(res_graph);
2.307 +
2.308 + //ReachedMap level(res_graph);
2.309 + FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
2.310 + BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
2.311
2.312 bfs.pushAndSetReached(s);
2.313 DistanceMap<ResGW> dist(res_graph);