1.1 --- a/src/work/marci/graph_wrapper.h Thu Mar 11 12:55:50 2004 +0000
1.2 +++ b/src/work/marci/graph_wrapper.h Thu Mar 11 14:15:07 2004 +0000
1.3 @@ -19,6 +19,12 @@
1.4 typedef typename Graph::InEdgeIt InEdgeIt;
1.5 //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.6 typedef typename Graph::EachEdgeIt EachEdgeIt;
1.7 +
1.8 + //TrivGraphWrapper() : graph(0) { }
1.9 + TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.10 +
1.11 + void setGraph(Graph& _graph) { graph = &_graph; }
1.12 + Graph& getGraph() const { return (*graph); }
1.13
1.14 template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
1.15 template<typename I, typename P> I& getFirst(I& i, const P& p) const {
1.16 @@ -66,6 +72,7 @@
1.17 NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :
1.18 Graph::NodeMap<T>(_G.getGraph(), a) { }
1.19 };
1.20 +
1.21 template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
1.22 public:
1.23 EdgeMap(const TrivGraphWrapper<Graph>& _G) :
1.24 @@ -73,12 +80,6 @@
1.25 EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :
1.26 Graph::EdgeMap<T>(_G.getGraph(), a) { }
1.27 };
1.28 -
1.29 - void setGraph(Graph& _graph) { graph = &_graph; }
1.30 - Graph& getGraph() const { return (*graph); }
1.31 -
1.32 - //TrivGraphWrapper() : graph(0) { }
1.33 - TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.34 };
1.35
1.36 template<typename Graph>
1.37 @@ -97,6 +98,12 @@
1.38 typedef typename Graph::InEdgeIt OutEdgeIt;
1.39 //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.40 typedef typename Graph::EachEdgeIt EachEdgeIt;
1.41 +
1.42 + //RevGraphWrapper() : graph(0) { }
1.43 + RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.44 +
1.45 + void setGraph(Graph& _graph) { graph = &_graph; }
1.46 + Graph& getGraph() const { return (*graph); }
1.47
1.48 template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
1.49 template<typename I, typename P> I& getFirst(I& i, const P& p) const {
1.50 @@ -144,6 +151,7 @@
1.51 NodeMap(const RevGraphWrapper<Graph>& _G, T a) :
1.52 Graph::NodeMap<T>(_G.getGraph(), a) { }
1.53 };
1.54 +
1.55 template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
1.56 public:
1.57 EdgeMap(const RevGraphWrapper<Graph>& _G) :
1.58 @@ -151,12 +159,6 @@
1.59 EdgeMap(const RevGraphWrapper<Graph>& _G, T a) :
1.60 Graph::EdgeMap<T>(_G.getGraph(), a) { }
1.61 };
1.62 -
1.63 - void setGraph(Graph& _graph) { graph = &_graph; }
1.64 - Graph& getGraph() const { return (*graph); }
1.65 -
1.66 - //RevGraphWrapper() : graph(0) { }
1.67 - RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.68 };
1.69
1.70
1.71 @@ -182,6 +184,12 @@
1.72 typedef typename Graph::InEdgeIt GraphInEdgeIt;
1.73 //public:
1.74
1.75 + //UndirGraphWrapper() : graph(0) { }
1.76 + UndirGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.77 +
1.78 + void setGraph(Graph& _graph) { graph = &_graph; }
1.79 + Graph& getGraph() const { return (*graph); }
1.80 +
1.81 class EdgeIt {
1.82 friend class UndirGraphWrapper<Graph>;
1.83 bool out_or_in; //true iff out
1.84 @@ -196,9 +204,6 @@
1.85
1.86 class OutEdgeIt : public EdgeIt {
1.87 friend class UndirGraphWrapper<Graph>;
1.88 - //bool out_or_in; //true iff out
1.89 - //GraphOutEdgeIt out;
1.90 - //GraphInEdgeIt in;
1.91 public:
1.92 OutEdgeIt() : EdgeIt() { }
1.93 OutEdgeIt(const UndirGraphWrapper& _G, const NodeIt& n) : EdgeIt() {
1.94 @@ -287,6 +292,7 @@
1.95 NodeMap(const UndirGraphWrapper<Graph>& _G, T a) :
1.96 Graph::NodeMap<T>(_G.getGraph(), a) { }
1.97 };
1.98 +
1.99 template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
1.100 public:
1.101 EdgeMap(const UndirGraphWrapper<Graph>& _G) :
1.102 @@ -294,12 +300,6 @@
1.103 EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) :
1.104 Graph::EdgeMap<T>(_G.getGraph(), a) { }
1.105 };
1.106 -
1.107 - void setGraph(Graph& _graph) { graph = &_graph; }
1.108 - Graph& getGraph() const { return (*graph); }
1.109 -
1.110 - //TrivGraphWrapper() : graph(0) { }
1.111 - UndirGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.112 };
1.113
1.114
1.115 @@ -386,13 +386,16 @@
1.116 FlowMap* flow;
1.117 const CapacityMap* capacity;
1.118 public:
1.119 +
1.120 ResGraphWrapper(const Graph& _G, FlowMap& _flow,
1.121 const CapacityMap& _capacity) :
1.122 G(&_G), flow(&_flow), capacity(&_capacity) { }
1.123 // ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) :
1.124 // G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { }
1.125 - void setGraph(Graph& _graph) { graph = &_graph; }
1.126 - Graph& getGraph() const { return (*graph); }
1.127 +
1.128 + void setGraph(const Graph& _graph) { graph = &_graph; }
1.129 + const Graph& getGraph() const { return (*G); }
1.130 +
1.131 class EdgeIt;
1.132 class OutEdgeIt;
1.133 friend class EdgeIt;
1.134 @@ -401,94 +404,49 @@
1.135 class EdgeIt {
1.136 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.137 protected:
1.138 - //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
1.139 - const Graph* G;
1.140 - FlowMap* flow;
1.141 - const CapacityMap* capacity;
1.142 - //OldSymEdgeIt sym;
1.143 + bool out_or_in; //true, iff out
1.144 OldOutEdgeIt out;
1.145 OldInEdgeIt in;
1.146 - bool out_or_in; //true, iff out
1.147 public:
1.148 EdgeIt() : out_or_in(true) { }
1.149 - EdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) :
1.150 - G(&_G), flow(&_flow), capacity(&_capacity), out_or_in(true) { }
1.151 - //EdgeIt(const EdgeIt& e) : G(e.G), flow(e.flow), capacity(e.capacity), out(e.out), in(e.in), out_or_in(e.out_or_in) { }
1.152 - Number free() const {
1.153 - if (out_or_in) {
1.154 - return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
1.155 - } else {
1.156 - return (/*resG->*/flow->get(in));
1.157 - }
1.158 - }
1.159 - bool valid() const {
1.160 - return out_or_in && out.valid() || in.valid(); }
1.161 - void augment(Number a) const {
1.162 - if (out_or_in) {
1.163 - /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);
1.164 - } else {
1.165 - /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);
1.166 - }
1.167 - }
1.168 - void print() {
1.169 - if (out_or_in) {
1.170 - std::cout << "out ";
1.171 - if (out.valid())
1.172 - std::cout << G->id(G->tail(out)) << "--"<< G->id(out) <<"->"<< G->id(G->head(out));
1.173 - else
1.174 - std::cout << "invalid";
1.175 - }
1.176 - else {
1.177 - std::cout << "in ";
1.178 - if (in.valid())
1.179 - std::cout << G->id(G->head(in)) << "<-"<< G->id(in) <<"--"<< G->id(G->tail(in));
1.180 - else
1.181 - std::cout << "invalid";
1.182 - }
1.183 - std::cout << std::endl;
1.184 - }
1.185 +// bool valid() const {
1.186 +// return out_or_in && out.valid() || in.valid(); }
1.187 };
1.188
1.189 - Number free(OldOutEdgeIt out) const {
1.190 - return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
1.191 - }
1.192 - Number free(OldInEdgeIt in) const {
1.193 - return (/*resG->*/flow->get(in));
1.194 - }
1.195
1.196 class OutEdgeIt : public EdgeIt {
1.197 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
1.198 public:
1.199 OutEdgeIt() { }
1.200 + //FIXME
1.201 + OutEdgeIt(const EdgeIt& e) : EdgeIt(e) { }
1.202 private:
1.203 - OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
1.204 - //out=/*resG->*/G->template first<OldOutEdgeIt>(v);
1.205 - G->getFirst(out, v);
1.206 - while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.207 + OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, NodeIt v) : EdgeIt() {
1.208 + resG.G->getFirst(out, v);
1.209 + while( out.valid() && !(resG.free(out)>0) ) { ++out; }
1.210 if (!out.valid()) {
1.211 out_or_in=0;
1.212 - //in=/*resG->*/G->template first<OldInEdgeIt>(v);
1.213 - G->getFirst(in, v);
1.214 - while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.215 + resG.G->getFirst(in, v);
1.216 + while( in.valid() && !(resG.free(in)>0) ) { ++in; }
1.217 }
1.218 }
1.219 - public:
1.220 - OutEdgeIt& operator++() {
1.221 - if (out_or_in) {
1.222 - NodeIt v=/*resG->*/G->aNode(out);
1.223 - ++out;
1.224 - while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.225 - if (!out.valid()) {
1.226 - out_or_in=0;
1.227 - G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
1.228 - while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.229 - }
1.230 - } else {
1.231 - ++in;
1.232 - while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.233 - }
1.234 - return *this;
1.235 - }
1.236 +// public:
1.237 +// OutEdgeIt& operator++() {
1.238 +// if (out_or_in) {
1.239 +// NodeIt v=/*resG->*/G->aNode(out);
1.240 +// ++out;
1.241 +// while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.242 +// if (!out.valid()) {
1.243 +// out_or_in=0;
1.244 +// G->getFirst(in, v);
1.245 +// while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.246 +// }
1.247 +// } else {
1.248 +// ++in;
1.249 +// while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.250 +// }
1.251 +// return *this;
1.252 +// }
1.253 };
1.254
1.255 class EachEdgeIt : public EdgeIt {
1.256 @@ -497,67 +455,66 @@
1.257 public:
1.258 EachEdgeIt() { }
1.259 //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
1.260 - EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
1.261 - out_or_in=true;
1.262 - G->getFirst(v);
1.263 - if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
1.264 - while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.265 + EachEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : EdgeIt() {
1.266 + resG.G->getFirst(v);
1.267 + if (v.valid()) resG.G->getFirst(out, v); else out=OldOutEdgeIt();
1.268 + while (out.valid() && !(resG.free(out)>0) ) { ++out; }
1.269 while (v.valid() && !out.valid()) {
1.270 ++v;
1.271 - if (v.valid()) G->getFirst(out, v);
1.272 - while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.273 + if (v.valid()) resG.G->getFirst(out, v);
1.274 + while (out.valid() && !(resG.free(out)>0) ) { ++out; }
1.275 }
1.276 if (!out.valid()) {
1.277 out_or_in=0;
1.278 - G->getFirst(v);
1.279 - if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
1.280 - while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.281 + resG.G->getFirst(v);
1.282 + if (v.valid()) resG.G->getFirst(in, v); else in=OldInEdgeIt();
1.283 + while (in.valid() && !(resG.free(in)>0) ) { ++in; }
1.284 while (v.valid() && !in.valid()) {
1.285 ++v;
1.286 - if (v.valid()) G->getFirst(in, v);
1.287 - while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.288 + if (v.valid()) resG.G->getFirst(in, v);
1.289 + while (in.valid() && !(resG.free(in)>0) ) { ++in; }
1.290 }
1.291 }
1.292 }
1.293 - EachEdgeIt& operator++() {
1.294 - if (out_or_in) {
1.295 - ++out;
1.296 - while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.297 - while (v.valid() && !out.valid()) {
1.298 - ++v;
1.299 - if (v.valid()) G->getFirst(out, v);
1.300 - while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.301 - }
1.302 - if (!out.valid()) {
1.303 - out_or_in=0;
1.304 - G->getFirst(v);
1.305 - if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
1.306 - while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.307 - while (v.valid() && !in.valid()) {
1.308 - ++v;
1.309 - if (v.valid()) G->getFirst(in, v);
1.310 - while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.311 - }
1.312 - }
1.313 - } else {
1.314 - ++in;
1.315 - while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.316 - while (v.valid() && !in.valid()) {
1.317 - ++v;
1.318 - if (v.valid()) G->getFirst(in, v);
1.319 - while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.320 - }
1.321 - }
1.322 - return *this;
1.323 - }
1.324 +// EachEdgeIt& operator++() {
1.325 +// if (out_or_in) {
1.326 +// ++out;
1.327 +// while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.328 +// while (v.valid() && !out.valid()) {
1.329 +// ++v;
1.330 +// if (v.valid()) G->getFirst(out, v);
1.331 +// while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
1.332 +// }
1.333 +// if (!out.valid()) {
1.334 +// out_or_in=0;
1.335 +// G->getFirst(v);
1.336 +// if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
1.337 +// while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.338 +// while (v.valid() && !in.valid()) {
1.339 +// ++v;
1.340 +// if (v.valid()) G->getFirst(in, v);
1.341 +// while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.342 +// }
1.343 +// }
1.344 +// } else {
1.345 +// ++in;
1.346 +// while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.347 +// while (v.valid() && !in.valid()) {
1.348 +// ++v;
1.349 +// if (v.valid()) G->getFirst(in, v);
1.350 +// while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
1.351 +// }
1.352 +// }
1.353 +// return *this;
1.354 +// }
1.355 };
1.356
1.357 - void getFirst(EachNodeIt& v) const { G->getFirst(v); }
1.358 - void getFirst(OutEdgeIt& e, NodeIt v) const {
1.359 - e=OutEdgeIt(*G, v, *flow, *capacity);
1.360 + EachNodeIt& getFirst(EachNodeIt& v) const { G->getFirst(v); }
1.361 + OutEdgeIt& getFirst(OutEdgeIt& e, NodeIt v) const {
1.362 + e=OutEdgeIt(*this, v);
1.363 }
1.364 - void getFirst(EachEdgeIt& e) const {
1.365 - e=EachEdgeIt(*G, *flow, *capacity);
1.366 + EachEdgeIt& getFirst(EachEdgeIt& e) const {
1.367 + e=EachEdgeIt(*this);
1.368 }
1.369
1.370 EachNodeIt& next(EachNodeIt& n) const { return G->next(n); }
1.371 @@ -566,15 +523,15 @@
1.372 if (e.out_or_in) {
1.373 NodeIt v=G->aNode(e.out);
1.374 ++(e.out);
1.375 - while( G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
1.376 + while( G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
1.377 if (!G->valid(e.out)) {
1.378 e.out_or_in=0;
1.379 - G->getFirst(e.in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
1.380 - while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
1.381 + G->getFirst(e.in, v);
1.382 + while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
1.383 }
1.384 } else {
1.385 ++(e.in);
1.386 - while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
1.387 + while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
1.388 }
1.389 return e;
1.390 }
1.391 @@ -582,30 +539,30 @@
1.392 EachEdgeIt& next(EachEdgeIt& e) const {
1.393 if (e.out_or_in) {
1.394 ++(e.out);
1.395 - while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
1.396 + while (G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
1.397 while (G->valid(e.v) && !G->valid(e.out)) {
1.398 ++(e.v);
1.399 if (G->valid(e.v)) G->getFirst(e.out, e.v);
1.400 - while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
1.401 + while (G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
1.402 }
1.403 if (!G->valid(e.out)) {
1.404 e.out_or_in=0;
1.405 G->getFirst(e.v);
1.406 if (G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt();
1.407 - while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
1.408 + while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
1.409 while (G->valid(e.v) && !G->valid(e.in)) {
1.410 ++(e.v);
1.411 if (G->valid(e.v)) G->getFirst(e.in, e.v);
1.412 - while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
1.413 + while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
1.414 }
1.415 }
1.416 } else {
1.417 ++(e.in);
1.418 - while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
1.419 + while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
1.420 while (G->valid(e.v) && !G->valid(e.in)) {
1.421 ++(e.v);
1.422 if (G->valid(e.v)) G->getFirst(e.in, e.v);
1.423 - while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
1.424 + while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
1.425 }
1.426 }
1.427 return e;
1.428 @@ -642,6 +599,28 @@
1.429 bool valid(EdgeIt e) const {
1.430 return e.out_or_in ? G->valid(e.out) : G->valid(e.in); }
1.431
1.432 + void augment(const EdgeIt& e, Number a) const {
1.433 + if (e.out_or_in)
1.434 + flow->set(e.out, flow->get(e.out)+a);
1.435 + else
1.436 + flow->set(e.in, flow->get(e.in)-a);
1.437 + }
1.438 +
1.439 + Number free(const EdgeIt& e) const {
1.440 + if (e.out_or_in)
1.441 + return (capacity->get(e.out)-flow->get(e.out));
1.442 + else
1.443 + return (flow->get(e.in));
1.444 + }
1.445 +
1.446 + Number free(OldOutEdgeIt out) const {
1.447 + return (capacity->get(out)-flow->get(out));
1.448 + }
1.449 +
1.450 + Number free(OldInEdgeIt in) const {
1.451 + return (flow->get(in));
1.452 + }
1.453 +
1.454 template<typename T> class NodeMap : public Graph::NodeMap<T> {
1.455 public:
1.456 NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
1.457 @@ -679,6 +658,243 @@
1.458 return backward_map.get(e.in);
1.459 }
1.460 };
1.461 + };
1.462 +
1.463 + template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.464 + class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
1.465 + protected:
1.466 + ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
1.467 + //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
1.468 + public:
1.469 + ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow,
1.470 + const CapacityMap& _capacity) :
1.471 + ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),
1.472 + first_out_edges(*this) /*, dist(*this)*/ {
1.473 + for(EachNodeIt n=this->template first<EachNodeIt>(); this->valid(n); this->next(n)) {
1.474 + OutEdgeIt e;
1.475 + ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(e, n);
1.476 + first_out_edges.set(n, e);
1.477 + }
1.478 + }
1.479 +
1.480 + //void setGraph(Graph& _graph) { graph = &_graph; }
1.481 + //Graph& getGraph() const { return (*graph); }
1.482 +
1.483 + //TrivGraphWrapper() : graph(0) { }
1.484 + //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.485 +
1.486 + //typedef Graph BaseGraph;
1.487 +
1.488 + //typedef typename Graph::NodeIt NodeIt;
1.489 + //typedef typename Graph::EachNodeIt EachNodeIt;
1.490 +
1.491 + //typedef typename Graph::EdgeIt EdgeIt;
1.492 + //typedef typename Graph::OutEdgeIt OutEdgeIt;
1.493 + //typedef typename Graph::InEdgeIt InEdgeIt;
1.494 + //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.495 + //typedef typename Graph::EachEdgeIt EachEdgeIt;
1.496 +
1.497 + typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
1.498 + typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachNodeIt EachNodeIt;
1.499 +
1.500 + typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
1.501 + typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
1.502 + //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
1.503 + //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.504 + //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachEdgeIt EachEdgeIt;
1.505 +
1.506 + EachNodeIt& getFirst(EachNodeIt& n) const {
1.507 + return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(n);
1.508 + }
1.509 +
1.510 + OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {
1.511 + e=first_out_edges.get(n);
1.512 + return e;
1.513 + }
1.514 +
1.515 + //ROSSZ template<typename I> I& getFirst(I& i) const { return getFirst(i); }
1.516 + //ROSSZ template<typename I, typename P> I& getFirst(I& i, const P& p) const {
1.517 + // return getFirst(i, p); }
1.518 +
1.519 + //template<typename I> I getNext(const I& i) const {
1.520 + // return graph->getNext(i); }
1.521 + //template<typename I> I& next(I &i) const { return graph->next(i); }
1.522 +
1.523 + template< typename It > It first() const {
1.524 + It e; getFirst(e); return e; }
1.525 +
1.526 + template< typename It > It first(const NodeIt& v) const {
1.527 + It e; getFirst(e, v); return e; }
1.528 +
1.529 + //NodeIt head(const EdgeIt& e) const { return graph->head(e); }
1.530 + //NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
1.531 +
1.532 + //template<typename I> bool valid(const I& i) const
1.533 + // { return graph->valid(i); }
1.534 +
1.535 + //int nodeNum() const { return graph->nodeNum(); }
1.536 + //int edgeNum() const { return graph->edgeNum(); }
1.537 +
1.538 + //template<typename I> NodeIt aNode(const I& e) const {
1.539 + // return graph->aNode(e); }
1.540 + //template<typename I> NodeIt bNode(const I& e) const {
1.541 + // return graph->bNode(e); }
1.542 +
1.543 + //NodeIt addNode() const { return graph->addNode(); }
1.544 + //EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
1.545 + // return graph->addEdge(tail, head); }
1.546 +
1.547 + //void erase(const OutEdgeIt& e) {
1.548 + // first_out_edge(this->tail(e))=e;
1.549 + //}
1.550 + void erase(const EdgeIt& e) {
1.551 + OutEdgeIt f(e);
1.552 + next(f);
1.553 + first_out_edges.set(this->tail(e), f);
1.554 + }
1.555 + //template<typename I> void erase(const I& i) const { graph->erase(i); }
1.556 +
1.557 + //void clear() const { graph->clear(); }
1.558 +
1.559 + template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
1.560 + public:
1.561 + NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
1.562 + ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
1.563 + NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
1.564 + ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
1.565 + };
1.566 +
1.567 + template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
1.568 + public:
1.569 + EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
1.570 + ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
1.571 + EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
1.572 + ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
1.573 + };
1.574 + };
1.575 +
1.576 + template<typename GraphWrapper>
1.577 + class FilterGraphWrapper {
1.578 + };
1.579 +
1.580 + template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.581 + class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
1.582 +
1.583 + //Graph* graph;
1.584 +
1.585 + public:
1.586 + //typedef Graph BaseGraph;
1.587 +
1.588 + typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
1.589 + typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachNodeIt EachNodeIt;
1.590 +
1.591 + typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
1.592 + typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
1.593 + //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
1.594 + //typedef typename Graph::SymEdgeIt SymEdgeIt;
1.595 + typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachEdgeIt EachEdgeIt;
1.596 +
1.597 + //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
1.598 +
1.599 + public:
1.600 + FilterGraphWrapper(const Graph& _G, FlowMap& _flow,
1.601 + const CapacityMap& _capacity) :
1.602 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this) {
1.603 + }
1.604 +
1.605 + OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {
1.606 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(e, n);
1.607 + while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e))))
1.608 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1.609 + return e;
1.610 + }
1.611 +
1.612 + EachNodeIt& next(EachNodeIt& e) const {
1.613 + return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1.614 + }
1.615 +
1.616 + OutEdgeIt& next(OutEdgeIt& e) const {
1.617 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1.618 + while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e))))
1.619 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
1.620 + return e;
1.621 + }
1.622 +
1.623 + EachNodeIt& getFirst(EachNodeIt& n) const {
1.624 + return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(n);
1.625 + }
1.626 +
1.627 + void erase(const EdgeIt& e) {
1.628 + OutEdgeIt f(e);
1.629 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
1.630 + while (valid(f) && (dist.get(tail(f))+1!=dist.get(head(f))))
1.631 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
1.632 + first_out_edges.set(this->tail(e), f);
1.633 + }
1.634 +
1.635 + //TrivGraphWrapper() : graph(0) { }
1.636 + //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
1.637 +
1.638 + //void setGraph(Graph& _graph) { graph = &_graph; }
1.639 + //Graph& getGraph() const { return (*graph); }
1.640 +
1.641 + //template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
1.642 + //template<typename I, typename P> I& getFirst(I& i, const P& p) const {
1.643 + // return graph->getFirst(i, p); }
1.644 +
1.645 + //template<typename I> I getNext(const I& i) const {
1.646 + // return graph->getNext(i); }
1.647 + //template<typename I> I& next(I &i) const { return graph->next(i); }
1.648 +
1.649 + template< typename It > It first() const {
1.650 + It e; getFirst(e); return e; }
1.651 +
1.652 + template< typename It > It first(const NodeIt& v) const {
1.653 + It e; getFirst(e, v); return e; }
1.654 +
1.655 + //NodeIt head(const EdgeIt& e) const { return graph->head(e); }
1.656 + //NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
1.657 +
1.658 + //template<typename I> bool valid(const I& i) const
1.659 + // { return graph->valid(i); }
1.660 +
1.661 + //template<typename I> void setInvalid(const I &i);
1.662 + //{ return graph->setInvalid(i); }
1.663 +
1.664 + //int nodeNum() const { return graph->nodeNum(); }
1.665 + //int edgeNum() const { return graph->edgeNum(); }
1.666 +
1.667 + //template<typename I> NodeIt aNode(const I& e) const {
1.668 + // return graph->aNode(e); }
1.669 + //template<typename I> NodeIt bNode(const I& e) const {
1.670 + // return graph->bNode(e); }
1.671 +
1.672 + //NodeIt addNode() const { return graph->addNode(); }
1.673 + //EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
1.674 + // return graph->addEdge(tail, head); }
1.675 +
1.676 + //template<typename I> void erase(const I& i) const { graph->erase(i); }
1.677 +
1.678 + //void clear() const { graph->clear(); }
1.679 +
1.680 + template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
1.681 + public:
1.682 + NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
1.683 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
1.684 + NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
1.685 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
1.686 + };
1.687 +
1.688 + template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
1.689 + public:
1.690 + EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
1.691 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
1.692 + EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
1.693 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
1.694 + };
1.695 +
1.696 + public:
1.697 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
1.698
1.699 };
1.700