1.1 --- a/src/work/marci/edmonds_karp.h Thu Apr 15 08:06:43 2004 +0000
1.2 +++ b/src/work/marci/edmonds_karp.h Thu Apr 15 14:41:20 2004 +0000
1.3 @@ -13,243 +13,243 @@
1.4
1.5 namespace hugo {
1.6
1.7 - template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.8 - class ResGraph {
1.9 - public:
1.10 - typedef typename Graph::Node Node;
1.11 - typedef typename Graph::NodeIt NodeIt;
1.12 - private:
1.13 - typedef typename Graph::SymEdgeIt OldSymEdgeIt;
1.14 - const Graph& G;
1.15 - FlowMap& flow;
1.16 - const CapacityMap& capacity;
1.17 - public:
1.18 - ResGraph(const Graph& _G, FlowMap& _flow,
1.19 - const CapacityMap& _capacity) :
1.20 - G(_G), flow(_flow), capacity(_capacity) { }
1.21 +// template<typename Graph, typename Number, typename CapacityMap, typename FlowMap>
1.22 +// class ResGraph {
1.23 +// public:
1.24 +// typedef typename Graph::Node Node;
1.25 +// typedef typename Graph::NodeIt NodeIt;
1.26 +// private:
1.27 +// typedef typename Graph::SymEdgeIt OldSymEdgeIt;
1.28 +// const Graph& G;
1.29 +// const CapacityMap& capacity;
1.30 +// FlowMap& flow;
1.31 +// public:
1.32 +// ResGraph(const Graph& _G, const CapacityMap& _capacity, FlowMap& _flow) :
1.33 +// G(_G), capacity(_capacity), flow(_flow) { }
1.34
1.35 - class Edge;
1.36 - class OutEdgeIt;
1.37 - friend class Edge;
1.38 - friend class OutEdgeIt;
1.39 +// class Edge;
1.40 +// class OutEdgeIt;
1.41 +// friend class Edge;
1.42 +// friend class OutEdgeIt;
1.43
1.44 - class Edge {
1.45 - friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
1.46 - protected:
1.47 - const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
1.48 - OldSymEdgeIt sym;
1.49 - public:
1.50 - Edge() { }
1.51 - //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }
1.52 - Number free() const {
1.53 - if (resG->G.aNode(sym)==resG->G.tail(sym)) {
1.54 - return (resG->capacity.get(sym)-resG->flow.get(sym));
1.55 - } else {
1.56 - return (resG->flow.get(sym));
1.57 - }
1.58 - }
1.59 - bool valid() const { return sym.valid(); }
1.60 - void augment(Number a) const {
1.61 - if (resG->G.aNode(sym)==resG->G.tail(sym)) {
1.62 - resG->flow.set(sym, resG->flow.get(sym)+a);
1.63 - //resG->flow[sym]+=a;
1.64 - } else {
1.65 - resG->flow.set(sym, resG->flow.get(sym)-a);
1.66 - //resG->flow[sym]-=a;
1.67 - }
1.68 - }
1.69 - };
1.70 +// class Edge {
1.71 +// friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
1.72 +// protected:
1.73 +// const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
1.74 +// OldSymEdgeIt sym;
1.75 +// public:
1.76 +// Edge() { }
1.77 +// //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }
1.78 +// Number free() const {
1.79 +// if (resG->G.aNode(sym)==resG->G.tail(sym)) {
1.80 +// return (resG->capacity.get(sym)-resG->flow.get(sym));
1.81 +// } else {
1.82 +// return (resG->flow.get(sym));
1.83 +// }
1.84 +// }
1.85 +// bool valid() const { return sym.valid(); }
1.86 +// void augment(Number a) const {
1.87 +// if (resG->G.aNode(sym)==resG->G.tail(sym)) {
1.88 +// resG->flow.set(sym, resG->flow.get(sym)+a);
1.89 +// //resG->flow[sym]+=a;
1.90 +// } else {
1.91 +// resG->flow.set(sym, resG->flow.get(sym)-a);
1.92 +// //resG->flow[sym]-=a;
1.93 +// }
1.94 +// }
1.95 +// };
1.96
1.97 - class OutEdgeIt : public Edge {
1.98 - friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
1.99 - public:
1.100 - OutEdgeIt() { }
1.101 - //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
1.102 - private:
1.103 - OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
1.104 - resG=&_resG;
1.105 - sym=resG->G.template first<OldSymEdgeIt>(v);
1.106 - while( sym.valid() && !(free()>0) ) { ++sym; }
1.107 - }
1.108 - public:
1.109 - OutEdgeIt& operator++() {
1.110 - ++sym;
1.111 - while( sym.valid() && !(free()>0) ) { ++sym; }
1.112 - return *this;
1.113 - }
1.114 - };
1.115 +// class OutEdgeIt : public Edge {
1.116 +// friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
1.117 +// public:
1.118 +// OutEdgeIt() { }
1.119 +// //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
1.120 +// private:
1.121 +// OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
1.122 +// resG=&_resG;
1.123 +// sym=resG->G.template first<OldSymEdgeIt>(v);
1.124 +// while( sym.valid() && !(free()>0) ) { ++sym; }
1.125 +// }
1.126 +// public:
1.127 +// OutEdgeIt& operator++() {
1.128 +// ++sym;
1.129 +// while( sym.valid() && !(free()>0) ) { ++sym; }
1.130 +// return *this;
1.131 +// }
1.132 +// };
1.133
1.134 - void /*getF*/first(OutEdgeIt& e, Node v) const {
1.135 - e=OutEdgeIt(*this, v);
1.136 - }
1.137 - void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
1.138 +// void /*getF*/first(OutEdgeIt& e, Node v) const {
1.139 +// e=OutEdgeIt(*this, v);
1.140 +// }
1.141 +// void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
1.142
1.143 - template< typename It >
1.144 - It first() const {
1.145 - It e;
1.146 - /*getF*/first(e);
1.147 - return e;
1.148 - }
1.149 +// template< typename It >
1.150 +// It first() const {
1.151 +// It e;
1.152 +// /*getF*/first(e);
1.153 +// return e;
1.154 +// }
1.155
1.156 - template< typename It >
1.157 - It first(Node v) const {
1.158 - It e;
1.159 - /*getF*/first(e, v);
1.160 - return e;
1.161 - }
1.162 +// template< typename It >
1.163 +// It first(Node v) const {
1.164 +// It e;
1.165 +// /*getF*/first(e, v);
1.166 +// return e;
1.167 +// }
1.168
1.169 - Node tail(Edge e) const { return G.aNode(e.sym); }
1.170 - Node head(Edge e) const { return G.bNode(e.sym); }
1.171 +// Node tail(Edge e) const { return G.aNode(e.sym); }
1.172 +// Node head(Edge e) const { return G.bNode(e.sym); }
1.173
1.174 - Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
1.175 - Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
1.176 +// Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
1.177 +// Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
1.178
1.179 - int id(Node v) const { return G.id(v); }
1.180 +// int id(Node v) const { return G.id(v); }
1.181
1.182 - template <typename S>
1.183 - class NodeMap {
1.184 - typename Graph::NodeMap<S> node_map;
1.185 - public:
1.186 - NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
1.187 - NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
1.188 - void set(Node nit, S a) { node_map.set(nit, a); }
1.189 - S get(Node nit) const { return node_map.get(nit); }
1.190 - S& operator[](Node nit) { return node_map[nit]; }
1.191 - const S& operator[](Node nit) const { return node_map[nit]; }
1.192 - };
1.193 +// template <typename S>
1.194 +// class NodeMap {
1.195 +// typename Graph::NodeMap<S> node_map;
1.196 +// public:
1.197 +// NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
1.198 +// NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
1.199 +// void set(Node nit, S a) { node_map.set(nit, a); }
1.200 +// S get(Node nit) const { return node_map.get(nit); }
1.201 +// S& operator[](Node nit) { return node_map[nit]; }
1.202 +// const S& operator[](Node nit) const { return node_map[nit]; }
1.203 +// };
1.204
1.205 - };
1.206 +// };
1.207
1.208
1.209 - template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.210 - class ResGraph2 {
1.211 - public:
1.212 - typedef typename Graph::Node Node;
1.213 - typedef typename Graph::NodeIt NodeIt;
1.214 - private:
1.215 - //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
1.216 - typedef typename Graph::OutEdgeIt OldOutEdgeIt;
1.217 - typedef typename Graph::InEdgeIt OldInEdgeIt;
1.218 +// template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.219 +// class ResGraph2 {
1.220 +// public:
1.221 +// typedef typename Graph::Node Node;
1.222 +// typedef typename Graph::NodeIt NodeIt;
1.223 +// private:
1.224 +// //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
1.225 +// typedef typename Graph::OutEdgeIt OldOutEdgeIt;
1.226 +// typedef typename Graph::InEdgeIt OldInEdgeIt;
1.227
1.228 - const Graph& G;
1.229 - FlowMap& flow;
1.230 - const CapacityMap& capacity;
1.231 - public:
1.232 - ResGraph2(const Graph& _G, FlowMap& _flow,
1.233 - const CapacityMap& _capacity) :
1.234 - G(_G), flow(_flow), capacity(_capacity) { }
1.235 +// const Graph& G;
1.236 +// FlowMap& flow;
1.237 +// const CapacityMap& capacity;
1.238 +// public:
1.239 +// ResGraph2(const Graph& _G, FlowMap& _flow,
1.240 +// const CapacityMap& _capacity) :
1.241 +// G(_G), flow(_flow), capacity(_capacity) { }
1.242
1.243 - class Edge;
1.244 - class OutEdgeIt;
1.245 - friend class Edge;
1.246 - friend class OutEdgeIt;
1.247 +// class Edge;
1.248 +// class OutEdgeIt;
1.249 +// friend class Edge;
1.250 +// friend class OutEdgeIt;
1.251
1.252 - class Edge {
1.253 - friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
1.254 - protected:
1.255 - const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
1.256 - //OldSymEdgeIt sym;
1.257 - OldOutEdgeIt out;
1.258 - OldInEdgeIt in;
1.259 - bool out_or_in; //true, iff out
1.260 - public:
1.261 - Edge() : out_or_in(true) { }
1.262 - Number free() const {
1.263 - if (out_or_in) {
1.264 - return (resG->capacity.get(out)-resG->flow.get(out));
1.265 - } else {
1.266 - return (resG->flow.get(in));
1.267 - }
1.268 - }
1.269 - bool valid() const {
1.270 - return out_or_in && out.valid() || in.valid(); }
1.271 - void augment(Number a) const {
1.272 - if (out_or_in) {
1.273 - resG->flow.set(out, resG->flow.get(out)+a);
1.274 - } else {
1.275 - resG->flow.set(in, resG->flow.get(in)-a);
1.276 - }
1.277 - }
1.278 - };
1.279 +// class Edge {
1.280 +// friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
1.281 +// protected:
1.282 +// const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
1.283 +// //OldSymEdgeIt sym;
1.284 +// OldOutEdgeIt out;
1.285 +// OldInEdgeIt in;
1.286 +// bool out_or_in; //true, iff out
1.287 +// public:
1.288 +// Edge() : out_or_in(true) { }
1.289 +// Number free() const {
1.290 +// if (out_or_in) {
1.291 +// return (resG->capacity.get(out)-resG->flow.get(out));
1.292 +// } else {
1.293 +// return (resG->flow.get(in));
1.294 +// }
1.295 +// }
1.296 +// bool valid() const {
1.297 +// return out_or_in && out.valid() || in.valid(); }
1.298 +// void augment(Number a) const {
1.299 +// if (out_or_in) {
1.300 +// resG->flow.set(out, resG->flow.get(out)+a);
1.301 +// } else {
1.302 +// resG->flow.set(in, resG->flow.get(in)-a);
1.303 +// }
1.304 +// }
1.305 +// };
1.306
1.307 - class OutEdgeIt : public Edge {
1.308 - friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
1.309 - public:
1.310 - OutEdgeIt() { }
1.311 - private:
1.312 - OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
1.313 - resG=&_resG;
1.314 - out=resG->G.template first<OldOutEdgeIt>(v);
1.315 - while( out.valid() && !(free()>0) ) { ++out; }
1.316 - if (!out.valid()) {
1.317 - out_or_in=0;
1.318 - in=resG->G.template first<OldInEdgeIt>(v);
1.319 - while( in.valid() && !(free()>0) ) { ++in; }
1.320 - }
1.321 - }
1.322 - public:
1.323 - OutEdgeIt& operator++() {
1.324 - if (out_or_in) {
1.325 - Node v=resG->G.aNode(out);
1.326 - ++out;
1.327 - while( out.valid() && !(free()>0) ) { ++out; }
1.328 - if (!out.valid()) {
1.329 - out_or_in=0;
1.330 - in=resG->G.template first<OldInEdgeIt>(v);
1.331 - while( in.valid() && !(free()>0) ) { ++in; }
1.332 - }
1.333 - } else {
1.334 - ++in;
1.335 - while( in.valid() && !(free()>0) ) { ++in; }
1.336 - }
1.337 - return *this;
1.338 - }
1.339 - };
1.340 +// class OutEdgeIt : public Edge {
1.341 +// friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
1.342 +// public:
1.343 +// OutEdgeIt() { }
1.344 +// private:
1.345 +// OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
1.346 +// resG=&_resG;
1.347 +// out=resG->G.template first<OldOutEdgeIt>(v);
1.348 +// while( out.valid() && !(free()>0) ) { ++out; }
1.349 +// if (!out.valid()) {
1.350 +// out_or_in=0;
1.351 +// in=resG->G.template first<OldInEdgeIt>(v);
1.352 +// while( in.valid() && !(free()>0) ) { ++in; }
1.353 +// }
1.354 +// }
1.355 +// public:
1.356 +// OutEdgeIt& operator++() {
1.357 +// if (out_or_in) {
1.358 +// Node v=resG->G.aNode(out);
1.359 +// ++out;
1.360 +// while( out.valid() && !(free()>0) ) { ++out; }
1.361 +// if (!out.valid()) {
1.362 +// out_or_in=0;
1.363 +// in=resG->G.template first<OldInEdgeIt>(v);
1.364 +// while( in.valid() && !(free()>0) ) { ++in; }
1.365 +// }
1.366 +// } else {
1.367 +// ++in;
1.368 +// while( in.valid() && !(free()>0) ) { ++in; }
1.369 +// }
1.370 +// return *this;
1.371 +// }
1.372 +// };
1.373
1.374 - void /*getF*/first(OutEdgeIt& e, Node v) const {
1.375 - e=OutEdgeIt(*this, v);
1.376 - }
1.377 - void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
1.378 +// void /*getF*/first(OutEdgeIt& e, Node v) const {
1.379 +// e=OutEdgeIt(*this, v);
1.380 +// }
1.381 +// void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
1.382
1.383 - template< typename It >
1.384 - It first() const {
1.385 - It e;
1.386 - /*getF*/first(e);
1.387 - return e;
1.388 - }
1.389 +// template< typename It >
1.390 +// It first() const {
1.391 +// It e;
1.392 +// /*getF*/first(e);
1.393 +// return e;
1.394 +// }
1.395
1.396 - template< typename It >
1.397 - It first(Node v) const {
1.398 - It e;
1.399 - /*getF*/first(e, v);
1.400 - return e;
1.401 - }
1.402 +// template< typename It >
1.403 +// It first(Node v) const {
1.404 +// It e;
1.405 +// /*getF*/first(e, v);
1.406 +// return e;
1.407 +// }
1.408
1.409 - Node tail(Edge e) const {
1.410 - return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
1.411 - Node head(Edge e) const {
1.412 - return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
1.413 +// Node tail(Edge e) const {
1.414 +// return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
1.415 +// Node head(Edge e) const {
1.416 +// return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
1.417
1.418 - Node aNode(OutEdgeIt e) const {
1.419 - return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
1.420 - Node bNode(OutEdgeIt e) const {
1.421 - return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
1.422 +// Node aNode(OutEdgeIt e) const {
1.423 +// return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
1.424 +// Node bNode(OutEdgeIt e) const {
1.425 +// return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
1.426
1.427 - int id(Node v) const { return G.id(v); }
1.428 +// int id(Node v) const { return G.id(v); }
1.429
1.430 - template <typename S>
1.431 - class NodeMap {
1.432 - typename Graph::NodeMap<S> node_map;
1.433 - public:
1.434 - NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
1.435 - NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
1.436 - void set(Node nit, S a) { node_map.set(nit, a); }
1.437 - S get(Node nit) const { return node_map.get(nit); }
1.438 - };
1.439 - };
1.440 +// template <typename S>
1.441 +// class NodeMap {
1.442 +// typename Graph::NodeMap<S> node_map;
1.443 +// public:
1.444 +// NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
1.445 +// NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
1.446 +// void set(Node nit, S a) { node_map.set(nit, a); }
1.447 +// S get(Node nit) const { return node_map.get(nit); }
1.448 +// };
1.449 +// };
1.450
1.451
1.452 - template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.453 + template <typename Graph, typename Number,
1.454 + typename CapacityMap, typename FlowMap>
1.455 class MaxFlow {
1.456 protected:
1.457 typedef typename Graph::Node Node;
1.458 @@ -260,18 +260,19 @@
1.459 const Graph* g;
1.460 Node s;
1.461 Node t;
1.462 + const CapacityMap* capacity;
1.463 FlowMap* flow;
1.464 - const CapacityMap* capacity;
1.465 - typedef ResGraphWrapper<const Graph, Number, FlowMap, CapacityMap > ResGW;
1.466 + typedef ResGraphWrapper<const Graph, Number, CapacityMap, FlowMap> ResGW;
1.467 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
1.468 typedef typename ResGW::Edge ResGWEdge;
1.469 public:
1.470
1.471 - MaxFlow(const Graph& _g, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
1.472 - g(&_g), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
1.473 + MaxFlow(const Graph& _g, Node _s, Node _t, const CapacityMap& _capacity,
1.474 + FlowMap& _flow) :
1.475 + g(&_g), s(_s), t(_t), capacity(&_capacity), flow(&_flow) { }
1.476
1.477 bool augmentOnShortestPath() {
1.478 - ResGW res_graph(*g, *flow, *capacity);
1.479 + ResGW res_graph(*g, *capacity, *flow);
1.480 bool _augment=false;
1.481
1.482 BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
1.483 @@ -336,7 +337,7 @@
1.484 typedef MutableGraph MG;
1.485 bool _augment=false;
1.486
1.487 - ResGW res_graph(*g, *flow, *capacity);
1.488 + ResGW res_graph(*g, *capacity, *flow);
1.489
1.490 BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
1.491
1.492 @@ -445,7 +446,7 @@
1.493 typedef MutableGraph MG;
1.494 bool _augment=false;
1.495
1.496 - ResGW res_graph(*g, *flow, *capacity);
1.497 + ResGW res_graph(*g, *capacity, *flow);
1.498
1.499 //bfs for distances on the residual graph
1.500 BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
1.501 @@ -550,7 +551,7 @@
1.502 bool augmentOnBlockingFlow2() {
1.503 bool _augment=false;
1.504
1.505 - ResGW res_graph(*g, *flow, *capacity);
1.506 + ResGW res_graph(*g, *capacity, *flow);
1.507
1.508 BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
1.509