1.1 --- a/src/work/athos/minlengthpaths.h Thu Apr 15 08:06:43 2004 +0000
1.2 +++ b/src/work/athos/minlengthpaths.h Thu Apr 15 14:41:20 2004 +0000
1.3 @@ -37,7 +37,7 @@
1.4
1.5 typedef ConstMap<Edge,int> ConstMap;
1.6
1.7 - typedef ResGraphWrapper<const Graph,int,EdgeIntMap,ConstMap> ResGraphType;
1.8 + typedef ResGraphWrapper<const Graph,int,ConstMap,EdgeIntMap> ResGraphType;
1.9
1.10
1.11 class ModLengthMap {
1.12 @@ -92,7 +92,7 @@
1.13 ConstMap const1map(1);
1.14
1.15 //We need a residual graph, in which some of the edges are reversed
1.16 - ResGraphType res_graph(G, reversed, const1map);
1.17 + ResGraphType res_graph(G, const1map, reversed);
1.18
1.19 //Initialize the copy of the Dijkstra potential to zero
1.20 typename ResGraphType::NodeMap<Length> dijkstra_dist(res_graph);
2.1 --- a/src/work/jacint/preflow.h Thu Apr 15 08:06:43 2004 +0000
2.2 +++ b/src/work/jacint/preflow.h Thu Apr 15 14:41:20 2004 +0000
2.3 @@ -43,8 +43,8 @@
2.4 namespace hugo {
2.5
2.6 template <typename Graph, typename T,
2.7 - typename FlowMap=typename Graph::EdgeMap<T>,
2.8 - typename CapMap=typename Graph::EdgeMap<T> >
2.9 + typename CapMap=typename Graph::EdgeMap<T>,
2.10 + typename FlowMap=typename Graph::EdgeMap<T> >
2.11 class Preflow {
2.12
2.13 typedef typename Graph::Node Node;
2.14 @@ -56,15 +56,14 @@
2.15 const Graph& G;
2.16 Node s;
2.17 Node t;
2.18 + const CapMap& capacity;
2.19 FlowMap& flow;
2.20 - const CapMap& capacity;
2.21 T value;
2.22
2.23 public:
2.24 Preflow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
2.25 FlowMap& _flow ) :
2.26 - G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) {}
2.27 -
2.28 + G(_G), s(_s), t(_t), capacity(_capacity), flow(_flow) {}
2.29
2.30 void run() {
2.31
3.1 --- a/src/work/marci/edmonds_karp.h Thu Apr 15 08:06:43 2004 +0000
3.2 +++ b/src/work/marci/edmonds_karp.h Thu Apr 15 14:41:20 2004 +0000
3.3 @@ -13,243 +13,243 @@
3.4
3.5 namespace hugo {
3.6
3.7 - template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
3.8 - class ResGraph {
3.9 - public:
3.10 - typedef typename Graph::Node Node;
3.11 - typedef typename Graph::NodeIt NodeIt;
3.12 - private:
3.13 - typedef typename Graph::SymEdgeIt OldSymEdgeIt;
3.14 - const Graph& G;
3.15 - FlowMap& flow;
3.16 - const CapacityMap& capacity;
3.17 - public:
3.18 - ResGraph(const Graph& _G, FlowMap& _flow,
3.19 - const CapacityMap& _capacity) :
3.20 - G(_G), flow(_flow), capacity(_capacity) { }
3.21 +// template<typename Graph, typename Number, typename CapacityMap, typename FlowMap>
3.22 +// class ResGraph {
3.23 +// public:
3.24 +// typedef typename Graph::Node Node;
3.25 +// typedef typename Graph::NodeIt NodeIt;
3.26 +// private:
3.27 +// typedef typename Graph::SymEdgeIt OldSymEdgeIt;
3.28 +// const Graph& G;
3.29 +// const CapacityMap& capacity;
3.30 +// FlowMap& flow;
3.31 +// public:
3.32 +// ResGraph(const Graph& _G, const CapacityMap& _capacity, FlowMap& _flow) :
3.33 +// G(_G), capacity(_capacity), flow(_flow) { }
3.34
3.35 - class Edge;
3.36 - class OutEdgeIt;
3.37 - friend class Edge;
3.38 - friend class OutEdgeIt;
3.39 +// class Edge;
3.40 +// class OutEdgeIt;
3.41 +// friend class Edge;
3.42 +// friend class OutEdgeIt;
3.43
3.44 - class Edge {
3.45 - friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
3.46 - protected:
3.47 - const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
3.48 - OldSymEdgeIt sym;
3.49 - public:
3.50 - Edge() { }
3.51 - //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }
3.52 - Number free() const {
3.53 - if (resG->G.aNode(sym)==resG->G.tail(sym)) {
3.54 - return (resG->capacity.get(sym)-resG->flow.get(sym));
3.55 - } else {
3.56 - return (resG->flow.get(sym));
3.57 - }
3.58 - }
3.59 - bool valid() const { return sym.valid(); }
3.60 - void augment(Number a) const {
3.61 - if (resG->G.aNode(sym)==resG->G.tail(sym)) {
3.62 - resG->flow.set(sym, resG->flow.get(sym)+a);
3.63 - //resG->flow[sym]+=a;
3.64 - } else {
3.65 - resG->flow.set(sym, resG->flow.get(sym)-a);
3.66 - //resG->flow[sym]-=a;
3.67 - }
3.68 - }
3.69 - };
3.70 +// class Edge {
3.71 +// friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
3.72 +// protected:
3.73 +// const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
3.74 +// OldSymEdgeIt sym;
3.75 +// public:
3.76 +// Edge() { }
3.77 +// //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }
3.78 +// Number free() const {
3.79 +// if (resG->G.aNode(sym)==resG->G.tail(sym)) {
3.80 +// return (resG->capacity.get(sym)-resG->flow.get(sym));
3.81 +// } else {
3.82 +// return (resG->flow.get(sym));
3.83 +// }
3.84 +// }
3.85 +// bool valid() const { return sym.valid(); }
3.86 +// void augment(Number a) const {
3.87 +// if (resG->G.aNode(sym)==resG->G.tail(sym)) {
3.88 +// resG->flow.set(sym, resG->flow.get(sym)+a);
3.89 +// //resG->flow[sym]+=a;
3.90 +// } else {
3.91 +// resG->flow.set(sym, resG->flow.get(sym)-a);
3.92 +// //resG->flow[sym]-=a;
3.93 +// }
3.94 +// }
3.95 +// };
3.96
3.97 - class OutEdgeIt : public Edge {
3.98 - friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
3.99 - public:
3.100 - OutEdgeIt() { }
3.101 - //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
3.102 - private:
3.103 - OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
3.104 - resG=&_resG;
3.105 - sym=resG->G.template first<OldSymEdgeIt>(v);
3.106 - while( sym.valid() && !(free()>0) ) { ++sym; }
3.107 - }
3.108 - public:
3.109 - OutEdgeIt& operator++() {
3.110 - ++sym;
3.111 - while( sym.valid() && !(free()>0) ) { ++sym; }
3.112 - return *this;
3.113 - }
3.114 - };
3.115 +// class OutEdgeIt : public Edge {
3.116 +// friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
3.117 +// public:
3.118 +// OutEdgeIt() { }
3.119 +// //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
3.120 +// private:
3.121 +// OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
3.122 +// resG=&_resG;
3.123 +// sym=resG->G.template first<OldSymEdgeIt>(v);
3.124 +// while( sym.valid() && !(free()>0) ) { ++sym; }
3.125 +// }
3.126 +// public:
3.127 +// OutEdgeIt& operator++() {
3.128 +// ++sym;
3.129 +// while( sym.valid() && !(free()>0) ) { ++sym; }
3.130 +// return *this;
3.131 +// }
3.132 +// };
3.133
3.134 - void /*getF*/first(OutEdgeIt& e, Node v) const {
3.135 - e=OutEdgeIt(*this, v);
3.136 - }
3.137 - void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
3.138 +// void /*getF*/first(OutEdgeIt& e, Node v) const {
3.139 +// e=OutEdgeIt(*this, v);
3.140 +// }
3.141 +// void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
3.142
3.143 - template< typename It >
3.144 - It first() const {
3.145 - It e;
3.146 - /*getF*/first(e);
3.147 - return e;
3.148 - }
3.149 +// template< typename It >
3.150 +// It first() const {
3.151 +// It e;
3.152 +// /*getF*/first(e);
3.153 +// return e;
3.154 +// }
3.155
3.156 - template< typename It >
3.157 - It first(Node v) const {
3.158 - It e;
3.159 - /*getF*/first(e, v);
3.160 - return e;
3.161 - }
3.162 +// template< typename It >
3.163 +// It first(Node v) const {
3.164 +// It e;
3.165 +// /*getF*/first(e, v);
3.166 +// return e;
3.167 +// }
3.168
3.169 - Node tail(Edge e) const { return G.aNode(e.sym); }
3.170 - Node head(Edge e) const { return G.bNode(e.sym); }
3.171 +// Node tail(Edge e) const { return G.aNode(e.sym); }
3.172 +// Node head(Edge e) const { return G.bNode(e.sym); }
3.173
3.174 - Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
3.175 - Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
3.176 +// Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
3.177 +// Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
3.178
3.179 - int id(Node v) const { return G.id(v); }
3.180 +// int id(Node v) const { return G.id(v); }
3.181
3.182 - template <typename S>
3.183 - class NodeMap {
3.184 - typename Graph::NodeMap<S> node_map;
3.185 - public:
3.186 - NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
3.187 - NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
3.188 - void set(Node nit, S a) { node_map.set(nit, a); }
3.189 - S get(Node nit) const { return node_map.get(nit); }
3.190 - S& operator[](Node nit) { return node_map[nit]; }
3.191 - const S& operator[](Node nit) const { return node_map[nit]; }
3.192 - };
3.193 +// template <typename S>
3.194 +// class NodeMap {
3.195 +// typename Graph::NodeMap<S> node_map;
3.196 +// public:
3.197 +// NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
3.198 +// NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
3.199 +// void set(Node nit, S a) { node_map.set(nit, a); }
3.200 +// S get(Node nit) const { return node_map.get(nit); }
3.201 +// S& operator[](Node nit) { return node_map[nit]; }
3.202 +// const S& operator[](Node nit) const { return node_map[nit]; }
3.203 +// };
3.204
3.205 - };
3.206 +// };
3.207
3.208
3.209 - template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
3.210 - class ResGraph2 {
3.211 - public:
3.212 - typedef typename Graph::Node Node;
3.213 - typedef typename Graph::NodeIt NodeIt;
3.214 - private:
3.215 - //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
3.216 - typedef typename Graph::OutEdgeIt OldOutEdgeIt;
3.217 - typedef typename Graph::InEdgeIt OldInEdgeIt;
3.218 +// template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
3.219 +// class ResGraph2 {
3.220 +// public:
3.221 +// typedef typename Graph::Node Node;
3.222 +// typedef typename Graph::NodeIt NodeIt;
3.223 +// private:
3.224 +// //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
3.225 +// typedef typename Graph::OutEdgeIt OldOutEdgeIt;
3.226 +// typedef typename Graph::InEdgeIt OldInEdgeIt;
3.227
3.228 - const Graph& G;
3.229 - FlowMap& flow;
3.230 - const CapacityMap& capacity;
3.231 - public:
3.232 - ResGraph2(const Graph& _G, FlowMap& _flow,
3.233 - const CapacityMap& _capacity) :
3.234 - G(_G), flow(_flow), capacity(_capacity) { }
3.235 +// const Graph& G;
3.236 +// FlowMap& flow;
3.237 +// const CapacityMap& capacity;
3.238 +// public:
3.239 +// ResGraph2(const Graph& _G, FlowMap& _flow,
3.240 +// const CapacityMap& _capacity) :
3.241 +// G(_G), flow(_flow), capacity(_capacity) { }
3.242
3.243 - class Edge;
3.244 - class OutEdgeIt;
3.245 - friend class Edge;
3.246 - friend class OutEdgeIt;
3.247 +// class Edge;
3.248 +// class OutEdgeIt;
3.249 +// friend class Edge;
3.250 +// friend class OutEdgeIt;
3.251
3.252 - class Edge {
3.253 - friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
3.254 - protected:
3.255 - const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
3.256 - //OldSymEdgeIt sym;
3.257 - OldOutEdgeIt out;
3.258 - OldInEdgeIt in;
3.259 - bool out_or_in; //true, iff out
3.260 - public:
3.261 - Edge() : out_or_in(true) { }
3.262 - Number free() const {
3.263 - if (out_or_in) {
3.264 - return (resG->capacity.get(out)-resG->flow.get(out));
3.265 - } else {
3.266 - return (resG->flow.get(in));
3.267 - }
3.268 - }
3.269 - bool valid() const {
3.270 - return out_or_in && out.valid() || in.valid(); }
3.271 - void augment(Number a) const {
3.272 - if (out_or_in) {
3.273 - resG->flow.set(out, resG->flow.get(out)+a);
3.274 - } else {
3.275 - resG->flow.set(in, resG->flow.get(in)-a);
3.276 - }
3.277 - }
3.278 - };
3.279 +// class Edge {
3.280 +// friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
3.281 +// protected:
3.282 +// const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
3.283 +// //OldSymEdgeIt sym;
3.284 +// OldOutEdgeIt out;
3.285 +// OldInEdgeIt in;
3.286 +// bool out_or_in; //true, iff out
3.287 +// public:
3.288 +// Edge() : out_or_in(true) { }
3.289 +// Number free() const {
3.290 +// if (out_or_in) {
3.291 +// return (resG->capacity.get(out)-resG->flow.get(out));
3.292 +// } else {
3.293 +// return (resG->flow.get(in));
3.294 +// }
3.295 +// }
3.296 +// bool valid() const {
3.297 +// return out_or_in && out.valid() || in.valid(); }
3.298 +// void augment(Number a) const {
3.299 +// if (out_or_in) {
3.300 +// resG->flow.set(out, resG->flow.get(out)+a);
3.301 +// } else {
3.302 +// resG->flow.set(in, resG->flow.get(in)-a);
3.303 +// }
3.304 +// }
3.305 +// };
3.306
3.307 - class OutEdgeIt : public Edge {
3.308 - friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
3.309 - public:
3.310 - OutEdgeIt() { }
3.311 - private:
3.312 - OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
3.313 - resG=&_resG;
3.314 - out=resG->G.template first<OldOutEdgeIt>(v);
3.315 - while( out.valid() && !(free()>0) ) { ++out; }
3.316 - if (!out.valid()) {
3.317 - out_or_in=0;
3.318 - in=resG->G.template first<OldInEdgeIt>(v);
3.319 - while( in.valid() && !(free()>0) ) { ++in; }
3.320 - }
3.321 - }
3.322 - public:
3.323 - OutEdgeIt& operator++() {
3.324 - if (out_or_in) {
3.325 - Node v=resG->G.aNode(out);
3.326 - ++out;
3.327 - while( out.valid() && !(free()>0) ) { ++out; }
3.328 - if (!out.valid()) {
3.329 - out_or_in=0;
3.330 - in=resG->G.template first<OldInEdgeIt>(v);
3.331 - while( in.valid() && !(free()>0) ) { ++in; }
3.332 - }
3.333 - } else {
3.334 - ++in;
3.335 - while( in.valid() && !(free()>0) ) { ++in; }
3.336 - }
3.337 - return *this;
3.338 - }
3.339 - };
3.340 +// class OutEdgeIt : public Edge {
3.341 +// friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
3.342 +// public:
3.343 +// OutEdgeIt() { }
3.344 +// private:
3.345 +// OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
3.346 +// resG=&_resG;
3.347 +// out=resG->G.template first<OldOutEdgeIt>(v);
3.348 +// while( out.valid() && !(free()>0) ) { ++out; }
3.349 +// if (!out.valid()) {
3.350 +// out_or_in=0;
3.351 +// in=resG->G.template first<OldInEdgeIt>(v);
3.352 +// while( in.valid() && !(free()>0) ) { ++in; }
3.353 +// }
3.354 +// }
3.355 +// public:
3.356 +// OutEdgeIt& operator++() {
3.357 +// if (out_or_in) {
3.358 +// Node v=resG->G.aNode(out);
3.359 +// ++out;
3.360 +// while( out.valid() && !(free()>0) ) { ++out; }
3.361 +// if (!out.valid()) {
3.362 +// out_or_in=0;
3.363 +// in=resG->G.template first<OldInEdgeIt>(v);
3.364 +// while( in.valid() && !(free()>0) ) { ++in; }
3.365 +// }
3.366 +// } else {
3.367 +// ++in;
3.368 +// while( in.valid() && !(free()>0) ) { ++in; }
3.369 +// }
3.370 +// return *this;
3.371 +// }
3.372 +// };
3.373
3.374 - void /*getF*/first(OutEdgeIt& e, Node v) const {
3.375 - e=OutEdgeIt(*this, v);
3.376 - }
3.377 - void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
3.378 +// void /*getF*/first(OutEdgeIt& e, Node v) const {
3.379 +// e=OutEdgeIt(*this, v);
3.380 +// }
3.381 +// void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
3.382
3.383 - template< typename It >
3.384 - It first() const {
3.385 - It e;
3.386 - /*getF*/first(e);
3.387 - return e;
3.388 - }
3.389 +// template< typename It >
3.390 +// It first() const {
3.391 +// It e;
3.392 +// /*getF*/first(e);
3.393 +// return e;
3.394 +// }
3.395
3.396 - template< typename It >
3.397 - It first(Node v) const {
3.398 - It e;
3.399 - /*getF*/first(e, v);
3.400 - return e;
3.401 - }
3.402 +// template< typename It >
3.403 +// It first(Node v) const {
3.404 +// It e;
3.405 +// /*getF*/first(e, v);
3.406 +// return e;
3.407 +// }
3.408
3.409 - Node tail(Edge e) const {
3.410 - return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
3.411 - Node head(Edge e) const {
3.412 - return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
3.413 +// Node tail(Edge e) const {
3.414 +// return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
3.415 +// Node head(Edge e) const {
3.416 +// return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
3.417
3.418 - Node aNode(OutEdgeIt e) const {
3.419 - return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
3.420 - Node bNode(OutEdgeIt e) const {
3.421 - return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
3.422 +// Node aNode(OutEdgeIt e) const {
3.423 +// return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
3.424 +// Node bNode(OutEdgeIt e) const {
3.425 +// return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
3.426
3.427 - int id(Node v) const { return G.id(v); }
3.428 +// int id(Node v) const { return G.id(v); }
3.429
3.430 - template <typename S>
3.431 - class NodeMap {
3.432 - typename Graph::NodeMap<S> node_map;
3.433 - public:
3.434 - NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
3.435 - NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
3.436 - void set(Node nit, S a) { node_map.set(nit, a); }
3.437 - S get(Node nit) const { return node_map.get(nit); }
3.438 - };
3.439 - };
3.440 +// template <typename S>
3.441 +// class NodeMap {
3.442 +// typename Graph::NodeMap<S> node_map;
3.443 +// public:
3.444 +// NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
3.445 +// NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
3.446 +// void set(Node nit, S a) { node_map.set(nit, a); }
3.447 +// S get(Node nit) const { return node_map.get(nit); }
3.448 +// };
3.449 +// };
3.450
3.451
3.452 - template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
3.453 + template <typename Graph, typename Number,
3.454 + typename CapacityMap, typename FlowMap>
3.455 class MaxFlow {
3.456 protected:
3.457 typedef typename Graph::Node Node;
3.458 @@ -260,18 +260,19 @@
3.459 const Graph* g;
3.460 Node s;
3.461 Node t;
3.462 + const CapacityMap* capacity;
3.463 FlowMap* flow;
3.464 - const CapacityMap* capacity;
3.465 - typedef ResGraphWrapper<const Graph, Number, FlowMap, CapacityMap > ResGW;
3.466 + typedef ResGraphWrapper<const Graph, Number, CapacityMap, FlowMap> ResGW;
3.467 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
3.468 typedef typename ResGW::Edge ResGWEdge;
3.469 public:
3.470
3.471 - MaxFlow(const Graph& _g, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
3.472 - g(&_g), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
3.473 + MaxFlow(const Graph& _g, Node _s, Node _t, const CapacityMap& _capacity,
3.474 + FlowMap& _flow) :
3.475 + g(&_g), s(_s), t(_t), capacity(&_capacity), flow(&_flow) { }
3.476
3.477 bool augmentOnShortestPath() {
3.478 - ResGW res_graph(*g, *flow, *capacity);
3.479 + ResGW res_graph(*g, *capacity, *flow);
3.480 bool _augment=false;
3.481
3.482 BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
3.483 @@ -336,7 +337,7 @@
3.484 typedef MutableGraph MG;
3.485 bool _augment=false;
3.486
3.487 - ResGW res_graph(*g, *flow, *capacity);
3.488 + ResGW res_graph(*g, *capacity, *flow);
3.489
3.490 BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
3.491
3.492 @@ -445,7 +446,7 @@
3.493 typedef MutableGraph MG;
3.494 bool _augment=false;
3.495
3.496 - ResGW res_graph(*g, *flow, *capacity);
3.497 + ResGW res_graph(*g, *capacity, *flow);
3.498
3.499 //bfs for distances on the residual graph
3.500 BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
3.501 @@ -550,7 +551,7 @@
3.502 bool augmentOnBlockingFlow2() {
3.503 bool _augment=false;
3.504
3.505 - ResGW res_graph(*g, *flow, *capacity);
3.506 + ResGW res_graph(*g, *capacity, *flow);
3.507
3.508 BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
3.509
4.1 --- a/src/work/marci/edmonds_karp_demo.cc Thu Apr 15 08:06:43 2004 +0000
4.2 +++ b/src/work/marci/edmonds_karp_demo.cc Thu Apr 15 14:41:20 2004 +0000
4.3 @@ -104,7 +104,7 @@
4.4 ts.reset();
4.5
4.6 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
4.7 - max_flow_test(G, s, t, flow, cap);
4.8 + max_flow_test(G, s, t, cap, flow);
4.9 int i=0;
4.10 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) {
4.11 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
4.12 @@ -132,7 +132,7 @@
4.13 ts.reset();
4.14
4.15 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
4.16 - max_flow_test(G, s, t, flow, cap);
4.17 + max_flow_test(G, s, t, cap, flow);
4.18 int i=0;
4.19 while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
4.20 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
4.21 @@ -160,7 +160,7 @@
4.22 ts.reset();
4.23
4.24 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
4.25 - max_flow_test(G, s, t, flow, cap);
4.26 + max_flow_test(G, s, t, cap, flow);
4.27 int i=0;
4.28 while (max_flow_test.augmentOnBlockingFlow2()) {
4.29 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
4.30 @@ -188,7 +188,7 @@
4.31 ts.reset();
4.32
4.33 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
4.34 - max_flow_test(G, s, t, flow, cap);
4.35 + max_flow_test(G, s, t, cap, flow);
4.36 int i=0;
4.37 while (max_flow_test.augmentOnShortestPath()) {
4.38 // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/src/work/marci/for_each_macros.h Thu Apr 15 14:41:20 2004 +0000
5.3 @@ -0,0 +1,85 @@
5.4 +// -*- c++ -*-
5.5 +#ifndef FOR_EACH_MACROS_H
5.6 +#define FOR_EACH_MACROS_H
5.7 +
5.8 +namespace hugo {
5.9 +
5.10 +#define FOR_EACH(e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))
5.11 +#define FOR_EACH_INC(e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e)))
5.12 +
5.13 +#define FOR_EACH_EDGE(e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))
5.14 +#define FOR_EACH_NODE(e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))
5.15 +#define FOR_EACH_INEDGE(e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e)))
5.16 +#define FOR_EACH_OUTEDGE(e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e)))
5.17 +
5.18 +// template<typename It, typename Graph>
5.19 +// It loopFirst(const Graph& g) const {
5.20 +// It e; g.first(e); return e;
5.21 +// }
5.22 +
5.23 +// template<typename It, typename Graph>
5.24 +// It loopFirst(const Graph& g, const Node& v) const {
5.25 +// It e; g.first(e, v); return e;
5.26 +// }
5.27 +
5.28 +// template<typename Graph>
5.29 +// typename Graph::NodeIt loopFirstNode(const Graph& g) const {
5.30 +// typename Graph::NodeIt e; g.first(e); return e;
5.31 +// }
5.32 +// template<typename Graph>
5.33 +// typename Graph::EdgeIt loopFirstEdge(const Graph& g) const {
5.34 +// typename Graph::EdgeIt e; g.first(e); return e;
5.35 +// }
5.36 +// template<typename Graph>
5.37 +// typename Graph::OutEdgeIt
5.38 +// loopFirstOutEdge(const Graph& g, const Node& n) const {
5.39 +// typename Graph::OutEdgeIt e; g.first(e, n); return e;
5.40 +// }
5.41 +// template<typename Graph>
5.42 +// typename Graph::InEdgeIt
5.43 +// loopFirstIn Edge(const Graph& g, const Node& n) const {
5.44 +// typename Graph::InEdgeIt e; g.first(e, n); return e;
5.45 +// }
5.46 +
5.47 +//FIXME ezt hogy a gorcsbe birja levezetni. Csak ugy leveszi a const-ot??
5.48 + template<typename It, typename Graph>
5.49 + It loopFirst(const It& i, const Graph& g) {
5.50 + It e=i; g.first(e); return e;
5.51 + }
5.52 +
5.53 + template<typename It, typename Graph, typename Node>
5.54 + It loopFirst(const It& i, const Graph& g, const Node& v) {
5.55 + It e=i; g.first(e, v); return e;
5.56 + }
5.57 +
5.58 +// template<typename Graph>
5.59 +// typename Graph::NodeIt loopFirstNode(const Graph& g) const {
5.60 +// typename Graph::NodeIt e; g.first(e); return e;
5.61 +// }
5.62 +// template<typename Graph>
5.63 +// typename Graph::EdgeIt loopFirstEdge(const Graph& g) const {
5.64 +// typename Graph::EdgeIt e; g.first(e); return e;
5.65 +// }
5.66 +// template<typename Graph>
5.67 +// typename Graph::OutEdgeIt
5.68 +// loopFirstOutEdge(const Graph& g, const Node& n) const {
5.69 +// typename Graph::OutEdgeIt e; g.first(e, n); return e;
5.70 +// }
5.71 +// template<typename Graph>
5.72 +// typename Graph::InEdgeIt
5.73 +// loopFirstIn Edge(const Graph& g, const Node& n) const {
5.74 +// typename Graph::InEdgeIt e; g.first(e, n); return e;
5.75 +// }
5.76 +
5.77 +#define FOR_EACH_LOC(Ittype, e, g) for(Ittype (e)=loopFirst(Ittype(), (g)); (g).valid((e)); (g).next((e)))
5.78 +#define FOR_EACH_INC_LOC(Ittype, e, g, v) for(Ittype (e)=loopFirst(Ittype(), (g), (v)); (g).valid((e)); (g).next((e)))
5.79 +
5.80 +// #define FOR_EACH_EDGE_LOC(e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))
5.81 +// #define FOR_EACH_NODE_LOC(e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))
5.82 +// #define FOR_EACH_INEDGE_LOC(e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e)))
5.83 +// #define FOR_EACH_OUTEDGE_LOC(e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e)))
5.84 +
5.85 +
5.86 +} //namespace hugo
5.87 +
5.88 +#endif //FOR_EACH_MACROS_H
6.1 --- a/src/work/marci/graph_wrapper.h Thu Apr 15 08:06:43 2004 +0000
6.2 +++ b/src/work/marci/graph_wrapper.h Thu Apr 15 14:41:20 2004 +0000
6.3 @@ -896,19 +896,20 @@
6.4
6.5
6.6
6.7 - template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
6.8 + template<typename Graph, typename Number,
6.9 + typename CapacityMap, typename FlowMap>
6.10 class ResGraphWrapper : public GraphWrapper<Graph> {
6.11 protected:
6.12 // typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
6.13 // typedef typename Graph::InEdgeIt GraphInEdgeIt;
6.14 // typedef typename Graph::Edge GraphEdge;
6.15 + const CapacityMap* capacity;
6.16 FlowMap* flow;
6.17 - const CapacityMap* capacity;
6.18 public:
6.19
6.20 - ResGraphWrapper(Graph& _graph, FlowMap& _flow,
6.21 - const CapacityMap& _capacity) :
6.22 - GraphWrapper<Graph>(_graph), flow(&_flow), capacity(&_capacity) { }
6.23 + ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
6.24 + FlowMap& _flow) :
6.25 + GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
6.26
6.27 class Edge;
6.28 class OutEdgeIt;
6.29 @@ -918,7 +919,7 @@
6.30 typedef typename GraphWrapper<Graph>::Node Node;
6.31 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
6.32 class Edge : public Graph::Edge {
6.33 - friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
6.34 + friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
6.35 protected:
6.36 bool forward; //true, iff forward
6.37 // typename Graph::Edge e;
6.38 @@ -940,7 +941,7 @@
6.39 }
6.40 };
6.41 // class Edge {
6.42 -// friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
6.43 +// friend class ResGraphWrapper<Graph, Number,lksd FlowMap, CapacityMap>;
6.44 // protected:
6.45 // bool out_or_in; //true, iff out
6.46 // GraphOutEdgeIt out;
6.47 @@ -967,7 +968,7 @@
6.48 // }
6.49 // };
6.50 class OutEdgeIt {
6.51 - friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
6.52 + friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
6.53 protected:
6.54 typename Graph::OutEdgeIt out;
6.55 typename Graph::InEdgeIt in;
6.56 @@ -978,7 +979,7 @@
6.57 // OutEdgeIt(const Edge& e) : Edge(e) { }
6.58 OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
6.59 //the unique invalid iterator
6.60 - OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) {
6.61 + OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
6.62 forward=true;
6.63 resG.graph->first(out, v);
6.64 while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
6.65 @@ -1000,13 +1001,13 @@
6.66 }
6.67 };
6.68 // class OutEdgeIt : public Edge {
6.69 -// friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
6.70 +// friend class ResGraphWrapper<Graph, Number, FkklowMap, CapacityMap>;
6.71 // public:
6.72 // OutEdgeIt() { }
6.73 // //FIXME
6.74 // OutEdgeIt(const Edge& e) : Edge(e) { }
6.75 // OutEdgeIt(const Invalid& i) : Edge(i) { }
6.76 -// OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
6.77 +// OutEdgeIt(const ResGraphWrapper<Graph, Number, FdfvlowMap, CapacityMap>& resG, Node v) : Edge() {
6.78 // resG.graph->first(out, v);
6.79 // while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
6.80 // if (!resG.graph->valid(out)) {
6.81 @@ -1038,7 +1039,7 @@
6.82 // class InEdgeIt : public Edge { };
6.83
6.84 class InEdgeIt {
6.85 - friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
6.86 + friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
6.87 protected:
6.88 typename Graph::OutEdgeIt out;
6.89 typename Graph::InEdgeIt in;
6.90 @@ -1049,7 +1050,7 @@
6.91 // OutEdgeIt(const Edge& e) : Edge(e) { }
6.92 InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
6.93 //the unique invalid iterator
6.94 - InEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) {
6.95 + InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
6.96 forward=true;
6.97 resG.graph->first(in, v);
6.98 while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
6.99 @@ -1072,14 +1073,14 @@
6.100 };
6.101
6.102 class EdgeIt {
6.103 - friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
6.104 + friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
6.105 protected:
6.106 typename Graph::EdgeIt e;
6.107 bool forward;
6.108 public:
6.109 EdgeIt() { }
6.110 EdgeIt(const Invalid& i) : e(i), forward(false) { }
6.111 - EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) {
6.112 + EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) {
6.113 forward=true;
6.114 resG.graph->first(e);
6.115 while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
6.116 @@ -1094,13 +1095,13 @@
6.117 }
6.118 };
6.119 // class EdgeIt : public Edge {
6.120 -// friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
6.121 +// friend class ResGraphWrapper<Graph, Number, FflowMap, CapacityMap>;
6.122 // NodeIt v;
6.123 // public:
6.124 // EdgeIt() { }
6.125 // //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
6.126 // EdgeIt(const Invalid& i) : Edge(i) { }
6.127 -// EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
6.128 +// EdgeIt(const ResGraphWrapper<Graph, Number, FlfowMap, CapacityMap>& resG) : Edge() {
6.129 // resG.graph->first(v);
6.130 // if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
6.131 // while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
6.132 @@ -1317,9 +1318,9 @@
6.133
6.134 // template<typename T> class NodeMap : public Graph::NodeMap<T> {
6.135 // public:
6.136 -// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
6.137 +// NodeMap(const ResGraphWrapper<Graph, Number, FlovwMap, CapacityMap>& _G)
6.138 // : Graph::NodeMap<T>(_G.gw) { }
6.139 -// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
6.140 +// NodeMap(const ResGraphWrapper<Graph, Number, FlowvMap, CapacityMap>& _G,
6.141 // T a) : Graph::NodeMap<T>(_G.gw, a) { }
6.142 // };
6.143
6.144 @@ -1337,8 +1338,8 @@
6.145 class EdgeMap {
6.146 typename Graph::EdgeMap<T> forward_map, backward_map;
6.147 public:
6.148 - EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
6.149 - EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
6.150 + EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
6.151 + EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
6.152 void set(Edge e, T a) {
6.153 if (e.forward)
6.154 forward_map.set(e.out, a);
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/src/work/marci/macro_test.cc Thu Apr 15 14:41:20 2004 +0000
7.3 @@ -0,0 +1,28 @@
7.4 +// -*- c++ -*-
7.5 +#include <iostream>
7.6 +#include <fstream>
7.7 +
7.8 +#include <list_graph.h>
7.9 +#include <for_each_macros.h>
7.10 +
7.11 +using namespace hugo;
7.12 +
7.13 +int main()
7.14 +{
7.15 + typedef ListGraph Graph;
7.16 + Graph g;
7.17 + Graph::Node n1=g.addNode();
7.18 + Graph::Node n2=g.addNode();
7.19 + Graph::NodeIt n;
7.20 + FOR_EACH(n, g) {
7.21 + std::cout << g.id(n) << " ";
7.22 + }
7.23 + std::cout << std::endl;
7.24 + FOR_EACH_LOC(Graph::NodeIt, m, g) {
7.25 + std::cout << g.id(m) << " ";
7.26 + }
7.27 + std::cout << std::endl;
7.28 +
7.29 +
7.30 + return 0;
7.31 +}
8.1 --- a/src/work/marci/makefile Thu Apr 15 08:06:43 2004 +0000
8.2 +++ b/src/work/marci/makefile Thu Apr 15 14:41:20 2004 +0000
8.3 @@ -12,7 +12,7 @@
8.4 CXXFLAGS = -g -O -W -Wall $(INCLUDEDIRS) -ansi -pedantic -ftemplate-depth-30
8.5
8.6 LEDABINARIES = lg_vs_sg leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
8.7 -BINARIES = edmonds_karp_demo iterator_bfs_demo
8.8 +BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test
8.9 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
8.10
8.11 all: $(BINARIES)