1.1 --- a/src/work/marci/edmonds_karp.h Thu Apr 29 09:08:14 2004 +0000
1.2 +++ b/src/work/marci/edmonds_karp.h Thu Apr 29 10:16:46 2004 +0000
1.3 @@ -10,244 +10,10 @@
1.4 #include <invalid.h>
1.5 #include <graph_wrapper.h>
1.6 #include <maps.h>
1.7 +#include <for_each_macros.h>
1.8
1.9 namespace hugo {
1.10
1.11 -// template<typename Graph, typename Number, typename CapacityMap, typename FlowMap>
1.12 -// class ResGraph {
1.13 -// public:
1.14 -// typedef typename Graph::Node Node;
1.15 -// typedef typename Graph::NodeIt NodeIt;
1.16 -// private:
1.17 -// typedef typename Graph::SymEdgeIt OldSymEdgeIt;
1.18 -// const Graph& G;
1.19 -// const CapacityMap& capacity;
1.20 -// FlowMap& flow;
1.21 -// public:
1.22 -// ResGraph(const Graph& _G, const CapacityMap& _capacity, FlowMap& _flow) :
1.23 -// G(_G), capacity(_capacity), flow(_flow) { }
1.24 -
1.25 -// class Edge;
1.26 -// class OutEdgeIt;
1.27 -// friend class Edge;
1.28 -// friend class OutEdgeIt;
1.29 -
1.30 -// class Edge {
1.31 -// friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
1.32 -// protected:
1.33 -// const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
1.34 -// OldSymEdgeIt sym;
1.35 -// public:
1.36 -// Edge() { }
1.37 -// //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }
1.38 -// Number free() const {
1.39 -// if (resG->G.aNode(sym)==resG->G.tail(sym)) {
1.40 -// return (resG->capacity.get(sym)-resG->flow.get(sym));
1.41 -// } else {
1.42 -// return (resG->flow.get(sym));
1.43 -// }
1.44 -// }
1.45 -// bool valid() const { return sym.valid(); }
1.46 -// void augment(Number a) const {
1.47 -// if (resG->G.aNode(sym)==resG->G.tail(sym)) {
1.48 -// resG->flow.set(sym, resG->flow.get(sym)+a);
1.49 -// //resG->flow[sym]+=a;
1.50 -// } else {
1.51 -// resG->flow.set(sym, resG->flow.get(sym)-a);
1.52 -// //resG->flow[sym]-=a;
1.53 -// }
1.54 -// }
1.55 -// };
1.56 -
1.57 -// class OutEdgeIt : public Edge {
1.58 -// friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
1.59 -// public:
1.60 -// OutEdgeIt() { }
1.61 -// //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
1.62 -// private:
1.63 -// OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
1.64 -// resG=&_resG;
1.65 -// sym=resG->G.template first<OldSymEdgeIt>(v);
1.66 -// while( sym.valid() && !(free()>0) ) { ++sym; }
1.67 -// }
1.68 -// public:
1.69 -// OutEdgeIt& operator++() {
1.70 -// ++sym;
1.71 -// while( sym.valid() && !(free()>0) ) { ++sym; }
1.72 -// return *this;
1.73 -// }
1.74 -// };
1.75 -
1.76 -// void /*getF*/first(OutEdgeIt& e, Node v) const {
1.77 -// e=OutEdgeIt(*this, v);
1.78 -// }
1.79 -// void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
1.80 -
1.81 -// template< typename It >
1.82 -// It first() const {
1.83 -// It e;
1.84 -// /*getF*/first(e);
1.85 -// return e;
1.86 -// }
1.87 -
1.88 -// template< typename It >
1.89 -// It first(Node v) const {
1.90 -// It e;
1.91 -// /*getF*/first(e, v);
1.92 -// return e;
1.93 -// }
1.94 -
1.95 -// Node tail(Edge e) const { return G.aNode(e.sym); }
1.96 -// Node head(Edge e) const { return G.bNode(e.sym); }
1.97 -
1.98 -// Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
1.99 -// Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
1.100 -
1.101 -// int id(Node v) const { return G.id(v); }
1.102 -
1.103 -// template <typename S>
1.104 -// class NodeMap {
1.105 -// typename Graph::NodeMap<S> node_map;
1.106 -// public:
1.107 -// NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
1.108 -// NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
1.109 -// void set(Node nit, S a) { node_map.set(nit, a); }
1.110 -// S get(Node nit) const { return node_map.get(nit); }
1.111 -// S& operator[](Node nit) { return node_map[nit]; }
1.112 -// const S& operator[](Node nit) const { return node_map[nit]; }
1.113 -// };
1.114 -
1.115 -// };
1.116 -
1.117 -
1.118 -// template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.119 -// class ResGraph2 {
1.120 -// public:
1.121 -// typedef typename Graph::Node Node;
1.122 -// typedef typename Graph::NodeIt NodeIt;
1.123 -// private:
1.124 -// //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
1.125 -// typedef typename Graph::OutEdgeIt OldOutEdgeIt;
1.126 -// typedef typename Graph::InEdgeIt OldInEdgeIt;
1.127 -
1.128 -// const Graph& G;
1.129 -// FlowMap& flow;
1.130 -// const CapacityMap& capacity;
1.131 -// public:
1.132 -// ResGraph2(const Graph& _G, FlowMap& _flow,
1.133 -// const CapacityMap& _capacity) :
1.134 -// G(_G), flow(_flow), capacity(_capacity) { }
1.135 -
1.136 -// class Edge;
1.137 -// class OutEdgeIt;
1.138 -// friend class Edge;
1.139 -// friend class OutEdgeIt;
1.140 -
1.141 -// class Edge {
1.142 -// friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
1.143 -// protected:
1.144 -// const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
1.145 -// //OldSymEdgeIt sym;
1.146 -// OldOutEdgeIt out;
1.147 -// OldInEdgeIt in;
1.148 -// bool out_or_in; //true, iff out
1.149 -// public:
1.150 -// Edge() : out_or_in(true) { }
1.151 -// Number free() const {
1.152 -// if (out_or_in) {
1.153 -// return (resG->capacity.get(out)-resG->flow.get(out));
1.154 -// } else {
1.155 -// return (resG->flow.get(in));
1.156 -// }
1.157 -// }
1.158 -// bool valid() const {
1.159 -// return out_or_in && out.valid() || in.valid(); }
1.160 -// void augment(Number a) const {
1.161 -// if (out_or_in) {
1.162 -// resG->flow.set(out, resG->flow.get(out)+a);
1.163 -// } else {
1.164 -// resG->flow.set(in, resG->flow.get(in)-a);
1.165 -// }
1.166 -// }
1.167 -// };
1.168 -
1.169 -// class OutEdgeIt : public Edge {
1.170 -// friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
1.171 -// public:
1.172 -// OutEdgeIt() { }
1.173 -// private:
1.174 -// OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
1.175 -// resG=&_resG;
1.176 -// out=resG->G.template first<OldOutEdgeIt>(v);
1.177 -// while( out.valid() && !(free()>0) ) { ++out; }
1.178 -// if (!out.valid()) {
1.179 -// out_or_in=0;
1.180 -// in=resG->G.template first<OldInEdgeIt>(v);
1.181 -// while( in.valid() && !(free()>0) ) { ++in; }
1.182 -// }
1.183 -// }
1.184 -// public:
1.185 -// OutEdgeIt& operator++() {
1.186 -// if (out_or_in) {
1.187 -// Node v=resG->G.aNode(out);
1.188 -// ++out;
1.189 -// while( out.valid() && !(free()>0) ) { ++out; }
1.190 -// if (!out.valid()) {
1.191 -// out_or_in=0;
1.192 -// in=resG->G.template first<OldInEdgeIt>(v);
1.193 -// while( in.valid() && !(free()>0) ) { ++in; }
1.194 -// }
1.195 -// } else {
1.196 -// ++in;
1.197 -// while( in.valid() && !(free()>0) ) { ++in; }
1.198 -// }
1.199 -// return *this;
1.200 -// }
1.201 -// };
1.202 -
1.203 -// void /*getF*/first(OutEdgeIt& e, Node v) const {
1.204 -// e=OutEdgeIt(*this, v);
1.205 -// }
1.206 -// void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
1.207 -
1.208 -// template< typename It >
1.209 -// It first() const {
1.210 -// It e;
1.211 -// /*getF*/first(e);
1.212 -// return e;
1.213 -// }
1.214 -
1.215 -// template< typename It >
1.216 -// It first(Node v) const {
1.217 -// It e;
1.218 -// /*getF*/first(e, v);
1.219 -// return e;
1.220 -// }
1.221 -
1.222 -// Node tail(Edge e) const {
1.223 -// return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
1.224 -// Node head(Edge e) const {
1.225 -// return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
1.226 -
1.227 -// Node aNode(OutEdgeIt e) const {
1.228 -// return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
1.229 -// Node bNode(OutEdgeIt e) const {
1.230 -// return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
1.231 -
1.232 -// int id(Node v) const { return G.id(v); }
1.233 -
1.234 -// template <typename S>
1.235 -// class NodeMap {
1.236 -// typename Graph::NodeMap<S> node_map;
1.237 -// public:
1.238 -// NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
1.239 -// NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
1.240 -// void set(Node nit, S a) { node_map.set(nit, a); }
1.241 -// S get(Node nit) const { return node_map.get(nit); }
1.242 -// };
1.243 -// };
1.244 -
1.245 -
1.246 template <typename Graph, typename Number,
1.247 typename CapacityMap, typename FlowMap>
1.248 class MaxFlow {
1.249 @@ -265,18 +31,23 @@
1.250 typedef ResGraphWrapper<const Graph, Number, CapacityMap, FlowMap> ResGW;
1.251 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
1.252 typedef typename ResGW::Edge ResGWEdge;
1.253 + //typedef typename ResGW::template NodeMap<bool> ReachedMap;
1.254 + typedef typename Graph::template NodeMap<bool> ReachedMap;
1.255 + ReachedMap level;
1.256 + //reached is called level because of compatibility with preflow
1.257 public:
1.258
1.259 MaxFlow(const Graph& _g, Node _s, Node _t, const CapacityMap& _capacity,
1.260 FlowMap& _flow) :
1.261 - g(&_g), s(_s), t(_t), capacity(&_capacity), flow(&_flow) { }
1.262 + g(&_g), s(_s), t(_t), capacity(&_capacity), flow(&_flow), level(_g) { }
1.263
1.264 bool augmentOnShortestPath() {
1.265 ResGW res_graph(*g, *capacity, *flow);
1.266 bool _augment=false;
1.267
1.268 - BfsIterator< ResGW, typename ResGW::template NodeMap<bool> >
1.269 - bfs(res_graph);
1.270 + //ReachedMap level(res_graph);
1.271 + FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
1.272 + BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
1.273 bfs.pushAndSetReached(s);
1.274
1.275 typename ResGW::template NodeMap<ResGWEdge> pred(res_graph);
1.276 @@ -342,8 +113,9 @@
1.277
1.278 ResGW res_graph(*g, *capacity, *flow);
1.279
1.280 - BfsIterator< ResGW, typename ResGW::template NodeMap<bool> >
1.281 - bfs(res_graph);
1.282 + //ReachedMap level(res_graph);
1.283 + FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
1.284 + BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
1.285
1.286 bfs.pushAndSetReached(s);
1.287 //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's
1.288 @@ -454,8 +226,9 @@
1.289 ResGW res_graph(*g, *capacity, *flow);
1.290
1.291 //bfs for distances on the residual graph
1.292 - BfsIterator< ResGW, typename ResGW::template NodeMap<bool> >
1.293 - bfs(res_graph);
1.294 + //ReachedMap level(res_graph);
1.295 + FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
1.296 + BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
1.297 bfs.pushAndSetReached(s);
1.298 typename ResGW::template NodeMap<int>
1.299 dist(res_graph); //filled up with 0's
1.300 @@ -560,9 +333,10 @@
1.301 bool _augment=false;
1.302
1.303 ResGW res_graph(*g, *capacity, *flow);
1.304 -
1.305 - BfsIterator< ResGW, typename ResGW::template NodeMap<bool> >
1.306 - bfs(res_graph);
1.307 +
1.308 + //ReachedMap level(res_graph);
1.309 + FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
1.310 + BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
1.311
1.312 bfs.pushAndSetReached(s);
1.313 DistanceMap<ResGW> dist(res_graph);