1.1 --- a/src/hugo/graph_wrapper.h Mon Sep 13 15:30:01 2004 +0000
1.2 +++ b/src/hugo/graph_wrapper.h Mon Sep 13 16:15:12 2004 +0000
1.3 @@ -331,9 +331,12 @@
1.4 /// A graph wrapper for hiding nodes and edges from a graph.
1.5
1.6 /// This wrapper shows a graph with filtered node-set and
1.7 - /// edge-set. The quick brown fox iterator jumps over
1.8 - /// the lazy dog nodes or edges if the values for them are false
1.9 - /// in the bool maps.
1.10 + /// edge-set. Given a bool-valued map on the node-set and one on
1.11 + /// the edge-set of the graphs, the iterators shows only the objects
1.12 + /// having true value.
1.13 + /// The quick brown fox iterators jump over
1.14 + /// the lazy dog nodes or edges if their values for are false in the
1.15 + /// corresponding bool maps.
1.16 ///
1.17 ///\author Marton Makai
1.18 template<typename Graph, typename NodeFilterMap,
1.19 @@ -544,12 +547,13 @@
1.20
1.21
1.22
1.23 - /// \brief A wrapper for forgetting the orientation of a graph.
1.24 - ///
1.25 - /// A wrapper for getting an undirected graph by forgetting
1.26 - /// the orientation of a directed one.
1.27 - ///
1.28 - /// \author Marton Makai
1.29 +// /// \brief A wrapper for forgetting the orientation of a graph.
1.30 +// ///
1.31 +// /// A wrapper for getting an undirected graph by forgetting
1.32 +// /// the orientation of a directed one.
1.33 +// ///
1.34 +// /// \author Marton Makai
1.35 +// /// does not work in the new concept.
1.36 template<typename Graph>
1.37 class UndirGraphWrapper : public GraphWrapper<Graph> {
1.38 public:
1.39 @@ -1118,324 +1122,6 @@
1.40 };
1.41
1.42
1.43 -
1.44 - // this is a direct implementation of the bidirected-graph wrapper.
1.45 - // in early hugo, it was implemented that way.
1.46 - template<typename Graph>
1.47 - class OldBidirGraphWrapper : public GraphWrapper<Graph> {
1.48 - public:
1.49 - typedef GraphWrapper<Graph> Parent;
1.50 - protected:
1.51 - OldBidirGraphWrapper() : GraphWrapper<Graph>() { }
1.52 -
1.53 - public:
1.54 -
1.55 - OldBidirGraphWrapper(Graph& _graph) :
1.56 - GraphWrapper<Graph>(_graph) { }
1.57 -
1.58 - class Edge;
1.59 - class OutEdgeIt;
1.60 - friend class Edge;
1.61 - friend class OutEdgeIt;
1.62 -
1.63 - //template<typename T> class NodeMap;
1.64 - template<typename T> class EdgeMap;
1.65 -
1.66 - typedef typename GraphWrapper<Graph>::Node Node;
1.67 - typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.68 -
1.69 - class Edge : public Graph::Edge {
1.70 - friend class OldBidirGraphWrapper<Graph>;
1.71 - ///\bug ez nem is kell
1.72 - //template<typename T> friend class NodeMap;
1.73 - template<typename T> friend class EdgeMap;
1.74 - protected:
1.75 - bool backward; //true, iff backward
1.76 -// typename Graph::Edge e;
1.77 - public:
1.78 - Edge() { }
1.79 - ///\bug =false kell-e? zsoltnak kell az addEdge miatt
1.80 - Edge(const typename Graph::Edge& _e, bool _backward=false) :
1.81 - Graph::Edge(_e), backward(_backward) { }
1.82 - Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
1.83 -//the unique invalid iterator
1.84 - friend bool operator==(const Edge& u, const Edge& v) {
1.85 - return (v.backward==u.backward &&
1.86 - static_cast<typename Graph::Edge>(u)==
1.87 - static_cast<typename Graph::Edge>(v));
1.88 - }
1.89 - friend bool operator!=(const Edge& u, const Edge& v) {
1.90 - return (v.backward!=u.backward ||
1.91 - static_cast<typename Graph::Edge>(u)!=
1.92 - static_cast<typename Graph::Edge>(v));
1.93 - }
1.94 - };
1.95 -
1.96 - class OutEdgeIt {
1.97 - friend class OldBidirGraphWrapper<Graph>;
1.98 - protected:
1.99 - typename Graph::OutEdgeIt out;
1.100 - typename Graph::InEdgeIt in;
1.101 - bool backward;
1.102 - public:
1.103 - OutEdgeIt() { }
1.104 - //FIXME
1.105 -// OutEdgeIt(const Edge& e) : Edge(e) { }
1.106 - OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1.107 -//the unique invalid iterator
1.108 - OutEdgeIt(const OldBidirGraphWrapper<Graph>& _G, Node v) {
1.109 - backward=false;
1.110 - _G.graph->first(out, v);
1.111 - while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
1.112 - if (!_G.graph->valid(out)) {
1.113 - backward=true;
1.114 - _G.graph->first(in, v);
1.115 - while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
1.116 - }
1.117 - }
1.118 - operator Edge() const {
1.119 -// Edge e;
1.120 -// e.forward=this->forward;
1.121 -// if (this->forward) e=out; else e=in;
1.122 -// return e;
1.123 - if (this->backward)
1.124 - return Edge(in, this->backward);
1.125 - else
1.126 - return Edge(out, this->backward);
1.127 - }
1.128 - };
1.129 -
1.130 - class InEdgeIt {
1.131 - friend class OldBidirGraphWrapper<Graph>;
1.132 - protected:
1.133 - typename Graph::OutEdgeIt out;
1.134 - typename Graph::InEdgeIt in;
1.135 - bool backward;
1.136 - public:
1.137 - InEdgeIt() { }
1.138 - //FIXME
1.139 -// OutEdgeIt(const Edge& e) : Edge(e) { }
1.140 - InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1.141 -//the unique invalid iterator
1.142 - InEdgeIt(const OldBidirGraphWrapper<Graph>& _G, Node v) {
1.143 - backward=false;
1.144 - _G.graph->first(in, v);
1.145 - while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
1.146 - if (!_G.graph->valid(in)) {
1.147 - backward=true;
1.148 - _G.graph->first(out, v);
1.149 - while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
1.150 - }
1.151 - }
1.152 - operator Edge() const {
1.153 -// Edge e;
1.154 -// e.forward=this->forward;
1.155 -// if (this->forward) e=out; else e=in;
1.156 -// return e;
1.157 - if (this->backward)
1.158 - return Edge(out, this->backward);
1.159 - else
1.160 - return Edge(in, this->backward);
1.161 - }
1.162 - };
1.163 -
1.164 - class EdgeIt {
1.165 - friend class OldBidirGraphWrapper<Graph>;
1.166 - protected:
1.167 - typename Graph::EdgeIt e;
1.168 - bool backward;
1.169 - public:
1.170 - EdgeIt() { }
1.171 - EdgeIt(const Invalid& i) : e(i), backward(true) { }
1.172 - EdgeIt(const OldBidirGraphWrapper<Graph>& _G) {
1.173 - backward=false;
1.174 - _G.graph->first(e);
1.175 - while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
1.176 - if (!_G.graph->valid(e)) {
1.177 - backward=true;
1.178 - _G.graph->first(e);
1.179 - while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
1.180 - }
1.181 - }
1.182 - operator Edge() const {
1.183 - return Edge(e, this->backward);
1.184 - }
1.185 - };
1.186 -
1.187 - using GraphWrapper<Graph>::first;
1.188 -// NodeIt& first(NodeIt& i) const {
1.189 -// i=NodeIt(*this); return i;
1.190 -// }
1.191 - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.192 - i=OutEdgeIt(*this, p); return i;
1.193 - }
1.194 -// FIXME not tested
1.195 - InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.196 - i=InEdgeIt(*this, p); return i;
1.197 - }
1.198 - EdgeIt& first(EdgeIt& i) const {
1.199 - i=EdgeIt(*this); return i;
1.200 - }
1.201 -
1.202 - using GraphWrapper<Graph>::next;
1.203 -// NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
1.204 - OutEdgeIt& next(OutEdgeIt& e) const {
1.205 - if (!e.backward) {
1.206 - Node v=this->graph->aNode(e.out);
1.207 - this->graph->next(e.out);
1.208 - while(this->graph->valid(e.out) && !enabled(e)) {
1.209 - this->graph->next(e.out); }
1.210 - if (!this->graph->valid(e.out)) {
1.211 - e.backward=true;
1.212 - this->graph->first(e.in, v);
1.213 - while(this->graph->valid(e.in) && !enabled(e)) {
1.214 - this->graph->next(e.in); }
1.215 - }
1.216 - } else {
1.217 - this->graph->next(e.in);
1.218 - while(this->graph->valid(e.in) && !enabled(e)) {
1.219 - this->graph->next(e.in); }
1.220 - }
1.221 - return e;
1.222 - }
1.223 -// FIXME Not tested
1.224 - InEdgeIt& next(InEdgeIt& e) const {
1.225 - if (!e.backward) {
1.226 - Node v=this->graph->aNode(e.in);
1.227 - this->graph->next(e.in);
1.228 - while(this->graph->valid(e.in) && !enabled(e)) {
1.229 - this->graph->next(e.in); }
1.230 - if (!this->graph->valid(e.in)) {
1.231 - e.backward=true;
1.232 - this->graph->first(e.out, v);
1.233 - while(this->graph->valid(e.out) && !enabled(e)) {
1.234 - this->graph->next(e.out); }
1.235 - }
1.236 - } else {
1.237 - this->graph->next(e.out);
1.238 - while(this->graph->valid(e.out) && !enabled(e)) {
1.239 - this->graph->next(e.out); }
1.240 - }
1.241 - return e;
1.242 - }
1.243 - EdgeIt& next(EdgeIt& e) const {
1.244 - if (!e.backward) {
1.245 - this->graph->next(e.e);
1.246 - while(this->graph->valid(e.e) && !enabled(e)) {
1.247 - this->graph->next(e.e); }
1.248 - if (!this->graph->valid(e.e)) {
1.249 - e.backward=true;
1.250 - this->graph->first(e.e);
1.251 - while(this->graph->valid(e.e) && !enabled(e)) {
1.252 - this->graph->next(e.e); }
1.253 - }
1.254 - } else {
1.255 - this->graph->next(e.e);
1.256 - while(this->graph->valid(e.e) && !enabled(e)) {
1.257 - this->graph->next(e.e); }
1.258 - }
1.259 - return e;
1.260 - }
1.261 -
1.262 - Node tail(Edge e) const {
1.263 - return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
1.264 - Node head(Edge e) const {
1.265 - return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
1.266 -
1.267 - Node aNode(OutEdgeIt e) const {
1.268 - return ((!e.backward) ? this->graph->aNode(e.out) :
1.269 - this->graph->aNode(e.in)); }
1.270 - Node bNode(OutEdgeIt e) const {
1.271 - return ((!e.backward) ? this->graph->bNode(e.out) :
1.272 - this->graph->bNode(e.in)); }
1.273 -
1.274 - Node aNode(InEdgeIt e) const {
1.275 - return ((!e.backward) ? this->graph->aNode(e.in) :
1.276 - this->graph->aNode(e.out)); }
1.277 - Node bNode(InEdgeIt e) const {
1.278 - return ((!e.backward) ? this->graph->bNode(e.in) :
1.279 - this->graph->bNode(e.out)); }
1.280 -
1.281 - /// Gives back the opposite edge.
1.282 - Edge opposite(const Edge& e) const {
1.283 - Edge f=e;
1.284 - f.backward=!f.backward;
1.285 - return f;
1.286 - }
1.287 -
1.288 -// int nodeNum() const { return graph->nodeNum(); }
1.289 - //FIXME
1.290 - void edgeNum() const { }
1.291 - //int edgeNum() const { return graph->edgeNum(); }
1.292 -
1.293 -
1.294 -// int id(Node v) const { return graph->id(v); }
1.295 -
1.296 - bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
1.297 - bool valid(Edge e) const {
1.298 - return this->graph->valid(e);
1.299 - //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
1.300 - }
1.301 -
1.302 - bool forward(const Edge& e) const { return !e.backward; }
1.303 - bool backward(const Edge& e) const { return e.backward; }
1.304 -
1.305 - bool enabled(const Edge& e) const {
1.306 - if (!e.backward)
1.307 -// return (capacity->get(e.out)-flow->get(e.out));
1.308 - //return ((*capacity)[e]-(*flow)[e]);
1.309 - return true;
1.310 - else
1.311 -// return (flow->get(e.in));
1.312 - //return ((*flow)[e]);
1.313 - return true;
1.314 - }
1.315 -
1.316 -// Number enabled(typename Graph::OutEdgeIt out) const {
1.317 -// // return (capacity->get(out)-flow->get(out));
1.318 -// return ((*capacity)[out]-(*flow)[out]);
1.319 -// }
1.320 -
1.321 -// Number enabled(typename Graph::InEdgeIt in) const {
1.322 -// // return (flow->get(in));
1.323 -// return ((*flow)[in]);
1.324 -// }
1.325 -
1.326 - template <typename T>
1.327 - class EdgeMap {
1.328 - typename Graph::template EdgeMap<T> forward_map, backward_map;
1.329 - public:
1.330 - typedef T ValueType;
1.331 - typedef Edge KeyType;
1.332 - EdgeMap(const OldBidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1.333 - EdgeMap(const OldBidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1.334 - void set(Edge e, T a) {
1.335 - if (!e.backward)
1.336 - forward_map.set(e/*.out*/, a);
1.337 - else
1.338 - backward_map.set(e/*.in*/, a);
1.339 - }
1.340 - T operator[](Edge e) const {
1.341 - if (!e.backward)
1.342 - return forward_map[e/*.out*/];
1.343 - else
1.344 - return backward_map[e/*.in*/];
1.345 - }
1.346 - void update() {
1.347 - forward_map.update();
1.348 - backward_map.update();
1.349 - }
1.350 -// T get(Edge e) const {
1.351 -// if (e.out_or_in)
1.352 -// return forward_map.get(e.out);
1.353 -// else
1.354 -// return backward_map.get(e.in);
1.355 -// }
1.356 - };
1.357 - };
1.358 -
1.359 -
1.360 -
1.361 /// \brief A bidirected graph template.
1.362 ///
1.363 /// A bidirected graph template.
1.364 @@ -1598,325 +1284,6 @@
1.365 };
1.366
1.367
1.368 - template<typename Graph, typename Number,
1.369 - typename CapacityMap, typename FlowMap>
1.370 - class OldResGraphWrapper : public GraphWrapper<Graph> {
1.371 - public:
1.372 - typedef GraphWrapper<Graph> Parent;
1.373 - protected:
1.374 - const CapacityMap* capacity;
1.375 - FlowMap* flow;
1.376 -
1.377 - OldResGraphWrapper() : GraphWrapper<Graph>(0),
1.378 - capacity(0), flow(0) { }
1.379 - void setCapacityMap(const CapacityMap& _capacity) {
1.380 - capacity=&_capacity;
1.381 - }
1.382 - void setFlowMap(FlowMap& _flow) {
1.383 - flow=&_flow;
1.384 - }
1.385 -
1.386 - public:
1.387 -
1.388 - OldResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1.389 - FlowMap& _flow) :
1.390 - GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
1.391 -
1.392 - class Edge;
1.393 - class OutEdgeIt;
1.394 - friend class Edge;
1.395 - friend class OutEdgeIt;
1.396 -
1.397 - typedef typename GraphWrapper<Graph>::Node Node;
1.398 - typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.399 - class Edge : public Graph::Edge {
1.400 - friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1.401 - protected:
1.402 - bool backward; //true, iff backward
1.403 -// typename Graph::Edge e;
1.404 - public:
1.405 - Edge() { }
1.406 - Edge(const typename Graph::Edge& _e, bool _backward) :
1.407 - Graph::Edge(_e), backward(_backward) { }
1.408 - Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
1.409 -//the unique invalid iterator
1.410 - friend bool operator==(const Edge& u, const Edge& v) {
1.411 - return (v.backward==u.backward &&
1.412 - static_cast<typename Graph::Edge>(u)==
1.413 - static_cast<typename Graph::Edge>(v));
1.414 - }
1.415 - friend bool operator!=(const Edge& u, const Edge& v) {
1.416 - return (v.backward!=u.backward ||
1.417 - static_cast<typename Graph::Edge>(u)!=
1.418 - static_cast<typename Graph::Edge>(v));
1.419 - }
1.420 - };
1.421 -
1.422 - class OutEdgeIt {
1.423 - friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1.424 - protected:
1.425 - typename Graph::OutEdgeIt out;
1.426 - typename Graph::InEdgeIt in;
1.427 - bool backward;
1.428 - public:
1.429 - OutEdgeIt() { }
1.430 - //FIXME
1.431 -// OutEdgeIt(const Edge& e) : Edge(e) { }
1.432 - OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1.433 -//the unique invalid iterator
1.434 - OutEdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
1.435 - backward=false;
1.436 - _G.graph->first(out, v);
1.437 - while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
1.438 - if (!_G.graph->valid(out)) {
1.439 - backward=true;
1.440 - _G.graph->first(in, v);
1.441 - while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
1.442 - }
1.443 - }
1.444 - operator Edge() const {
1.445 -// Edge e;
1.446 -// e.forward=this->forward;
1.447 -// if (this->forward) e=out; else e=in;
1.448 -// return e;
1.449 - if (this->backward)
1.450 - return Edge(in, this->backward);
1.451 - else
1.452 - return Edge(out, this->backward);
1.453 - }
1.454 - };
1.455 -
1.456 - class InEdgeIt {
1.457 - friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1.458 - protected:
1.459 - typename Graph::OutEdgeIt out;
1.460 - typename Graph::InEdgeIt in;
1.461 - bool backward;
1.462 - public:
1.463 - InEdgeIt() { }
1.464 - //FIXME
1.465 -// OutEdgeIt(const Edge& e) : Edge(e) { }
1.466 - InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1.467 -//the unique invalid iterator
1.468 - InEdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
1.469 - backward=false;
1.470 - _G.graph->first(in, v);
1.471 - while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
1.472 - if (!_G.graph->valid(in)) {
1.473 - backward=true;
1.474 - _G.graph->first(out, v);
1.475 - while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
1.476 - }
1.477 - }
1.478 - operator Edge() const {
1.479 -// Edge e;
1.480 -// e.forward=this->forward;
1.481 -// if (this->forward) e=out; else e=in;
1.482 -// return e;
1.483 - if (this->backward)
1.484 - return Edge(out, this->backward);
1.485 - else
1.486 - return Edge(in, this->backward);
1.487 - }
1.488 - };
1.489 -
1.490 - class EdgeIt {
1.491 - friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1.492 - protected:
1.493 - typename Graph::EdgeIt e;
1.494 - bool backward;
1.495 - public:
1.496 - EdgeIt() { }
1.497 - EdgeIt(const Invalid& i) : e(i), backward(true) { }
1.498 - EdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) {
1.499 - backward=false;
1.500 - _G.graph->first(e);
1.501 - while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
1.502 - if (!_G.graph->valid(e)) {
1.503 - backward=true;
1.504 - _G.graph->first(e);
1.505 - while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
1.506 - }
1.507 - }
1.508 - operator Edge() const {
1.509 - return Edge(e, this->backward);
1.510 - }
1.511 - };
1.512 -
1.513 - using GraphWrapper<Graph>::first;
1.514 -// NodeIt& first(NodeIt& i) const {
1.515 -// i=NodeIt(*this); return i;
1.516 -// }
1.517 - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.518 - i=OutEdgeIt(*this, p); return i;
1.519 - }
1.520 -// FIXME not tested
1.521 - InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.522 - i=InEdgeIt(*this, p); return i;
1.523 - }
1.524 - EdgeIt& first(EdgeIt& i) const {
1.525 - i=EdgeIt(*this); return i;
1.526 - }
1.527 -
1.528 - using GraphWrapper<Graph>::next;
1.529 -// NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
1.530 - OutEdgeIt& next(OutEdgeIt& e) const {
1.531 - if (!e.backward) {
1.532 - Node v=this->graph->aNode(e.out);
1.533 - this->graph->next(e.out);
1.534 - while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1.535 - this->graph->next(e.out); }
1.536 - if (!this->graph->valid(e.out)) {
1.537 - e.backward=true;
1.538 - this->graph->first(e.in, v);
1.539 - while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1.540 - this->graph->next(e.in); }
1.541 - }
1.542 - } else {
1.543 - this->graph->next(e.in);
1.544 - while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1.545 - this->graph->next(e.in); }
1.546 - }
1.547 - return e;
1.548 - }
1.549 -// FIXME Not tested
1.550 - InEdgeIt& next(InEdgeIt& e) const {
1.551 - if (!e.backward) {
1.552 - Node v=this->graph->aNode(e.in);
1.553 - this->graph->next(e.in);
1.554 - while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
1.555 - this->graph->next(e.in); }
1.556 - if (!this->graph->valid(e.in)) {
1.557 - e.backward=true;
1.558 - this->graph->first(e.out, v);
1.559 - while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1.560 - this->graph->next(e.out); }
1.561 - }
1.562 - } else {
1.563 - this->graph->next(e.out);
1.564 - while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
1.565 - this->graph->next(e.out); }
1.566 - }
1.567 - return e;
1.568 - }
1.569 - EdgeIt& next(EdgeIt& e) const {
1.570 - if (!e.backward) {
1.571 - this->graph->next(e.e);
1.572 - while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1.573 - this->graph->next(e.e); }
1.574 - if (!this->graph->valid(e.e)) {
1.575 - e.backward=true;
1.576 - this->graph->first(e.e);
1.577 - while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1.578 - this->graph->next(e.e); }
1.579 - }
1.580 - } else {
1.581 - this->graph->next(e.e);
1.582 - while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
1.583 - this->graph->next(e.e); }
1.584 - }
1.585 - return e;
1.586 - }
1.587 -
1.588 - Node tail(Edge e) const {
1.589 - return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
1.590 - Node head(Edge e) const {
1.591 - return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
1.592 -
1.593 - Node aNode(OutEdgeIt e) const {
1.594 - return ((!e.backward) ? this->graph->aNode(e.out) :
1.595 - this->graph->aNode(e.in)); }
1.596 - Node bNode(OutEdgeIt e) const {
1.597 - return ((!e.backward) ? this->graph->bNode(e.out) :
1.598 - this->graph->bNode(e.in)); }
1.599 -
1.600 - Node aNode(InEdgeIt e) const {
1.601 - return ((!e.backward) ? this->graph->aNode(e.in) :
1.602 - this->graph->aNode(e.out)); }
1.603 - Node bNode(InEdgeIt e) const {
1.604 - return ((!e.backward) ? this->graph->bNode(e.in) :
1.605 - this->graph->bNode(e.out)); }
1.606 -
1.607 -// int nodeNum() const { return graph->nodeNum(); }
1.608 - //FIXME
1.609 - void edgeNum() const { }
1.610 - //int edgeNum() const { return graph->edgeNum(); }
1.611 -
1.612 -
1.613 -// int id(Node v) const { return graph->id(v); }
1.614 -
1.615 - bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
1.616 - bool valid(Edge e) const {
1.617 - return this->graph->valid(e);
1.618 - //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
1.619 - }
1.620 -
1.621 - bool forward(const Edge& e) const { return !e.backward; }
1.622 - bool backward(const Edge& e) const { return e.backward; }
1.623 -
1.624 - void augment(const Edge& e, Number a) const {
1.625 - if (!e.backward)
1.626 -// flow->set(e.out, flow->get(e.out)+a);
1.627 - flow->set(e, (*flow)[e]+a);
1.628 - else
1.629 -// flow->set(e.in, flow->get(e.in)-a);
1.630 - flow->set(e, (*flow)[e]-a);
1.631 - }
1.632 -
1.633 - Number resCap(const Edge& e) const {
1.634 - if (!e.backward)
1.635 -// return (capacity->get(e.out)-flow->get(e.out));
1.636 - return ((*capacity)[e]-(*flow)[e]);
1.637 - else
1.638 -// return (flow->get(e.in));
1.639 - return ((*flow)[e]);
1.640 - }
1.641 -
1.642 -// Number resCap(typename Graph::OutEdgeIt out) const {
1.643 -// // return (capacity->get(out)-flow->get(out));
1.644 -// return ((*capacity)[out]-(*flow)[out]);
1.645 -// }
1.646 -
1.647 -// Number resCap(typename Graph::InEdgeIt in) const {
1.648 -// // return (flow->get(in));
1.649 -// return ((*flow)[in]);
1.650 -// }
1.651 -
1.652 - template <typename T>
1.653 - class EdgeMap {
1.654 - typename Graph::template EdgeMap<T> forward_map, backward_map;
1.655 - public:
1.656 - typedef T ValueType;
1.657 - typedef Edge KeyType;
1.658 - EdgeMap(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1.659 - EdgeMap(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1.660 - void set(Edge e, T a) {
1.661 - if (!e.backward)
1.662 - forward_map.set(e/*.out*/, a);
1.663 - else
1.664 - backward_map.set(e/*.in*/, a);
1.665 - }
1.666 - T operator[](Edge e) const {
1.667 - if (!e.backward)
1.668 - return forward_map[e/*.out*/];
1.669 - else
1.670 - return backward_map[e/*.in*/];
1.671 - }
1.672 - void update() {
1.673 - forward_map.update();
1.674 - backward_map.update();
1.675 - }
1.676 -// T get(Edge e) const {
1.677 -// if (e.out_or_in)
1.678 -// return forward_map.get(e.out);
1.679 -// else
1.680 -// return backward_map.get(e.in);
1.681 -// }
1.682 - };
1.683 - };
1.684 -
1.685 -
1.686 -
1.687 /// For blocking flows.
1.688
1.689 /// This graph wrapper is used for on-the-fly