1.1 --- a/src/hugo/graph_wrapper.h Thu May 20 17:21:55 2004 +0000
1.2 +++ b/src/hugo/graph_wrapper.h Fri May 21 08:15:45 2004 +0000
1.3 @@ -1012,346 +1012,340 @@
1.4
1.5
1.6
1.7 -// ///\brief A wrapper for composing bidirected graph from a directed one.
1.8 -// /// experimental, for fezso's sake.
1.9 -// ///
1.10 -// /// A wrapper for composing bidirected graph from a directed one.
1.11 -// /// experimental, for fezso's sake.
1.12 -// /// A bidirected graph is composed over the directed one without physical
1.13 -// /// storage. As the oppositely directed edges are logically different ones
1.14 -// /// the maps are able to attach different values for them.
1.15 -// template<typename Graph>
1.16 -// class BidirGraphWrapper : public GraphWrapper<Graph> {
1.17 -// public:
1.18 -// typedef GraphWrapper<Graph> Parent;
1.19 -// protected:
1.20 -// //const CapacityMap* capacity;
1.21 -// //FlowMap* flow;
1.22 + template<typename Graph>
1.23 + class OldBidirGraphWrapper : public GraphWrapper<Graph> {
1.24 + public:
1.25 + typedef GraphWrapper<Graph> Parent;
1.26 + protected:
1.27 + //const CapacityMap* capacity;
1.28 + //FlowMap* flow;
1.29
1.30 -// BidirGraphWrapper() : GraphWrapper<Graph>()/*,
1.31 -// capacity(0), flow(0)*/ { }
1.32 -// // void setCapacityMap(const CapacityMap& _capacity) {
1.33 -// // capacity=&_capacity;
1.34 -// // }
1.35 -// // void setFlowMap(FlowMap& _flow) {
1.36 -// // flow=&_flow;
1.37 -// // }
1.38 -
1.39 -// public:
1.40 -
1.41 -// BidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity,
1.42 -// FlowMap& _flow*/) :
1.43 -// GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
1.44 -
1.45 -// class Edge;
1.46 -// class OutEdgeIt;
1.47 -// friend class Edge;
1.48 -// friend class OutEdgeIt;
1.49 -
1.50 -// //template<typename T> class NodeMap;
1.51 -// template<typename T> class EdgeMap;
1.52 -
1.53 -// typedef typename GraphWrapper<Graph>::Node Node;
1.54 -// typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.55 -
1.56 -// class Edge : public Graph::Edge {
1.57 -// friend class BidirGraphWrapper<Graph>;
1.58 -// ///\bug ez nem is kell
1.59 -// //template<typename T> friend class NodeMap;
1.60 -// template<typename T> friend class EdgeMap;
1.61 -// protected:
1.62 -// bool backward; //true, iff backward
1.63 -// // typename Graph::Edge e;
1.64 -// public:
1.65 -// Edge() { }
1.66 -// ///\bug =false kell-e? zsoltnak kell az addEdge miatt
1.67 -// Edge(const typename Graph::Edge& _e, bool _backward=false) :
1.68 -// Graph::Edge(_e), backward(_backward) { }
1.69 -// Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
1.70 -// //the unique invalid iterator
1.71 -// friend bool operator==(const Edge& u, const Edge& v) {
1.72 -// return (v.backward==u.backward &&
1.73 -// static_cast<typename Graph::Edge>(u)==
1.74 -// static_cast<typename Graph::Edge>(v));
1.75 -// }
1.76 -// friend bool operator!=(const Edge& u, const Edge& v) {
1.77 -// return (v.backward!=u.backward ||
1.78 -// static_cast<typename Graph::Edge>(u)!=
1.79 -// static_cast<typename Graph::Edge>(v));
1.80 -// }
1.81 -// };
1.82 -
1.83 -// class OutEdgeIt {
1.84 -// friend class BidirGraphWrapper<Graph>;
1.85 -// protected:
1.86 -// typename Graph::OutEdgeIt out;
1.87 -// typename Graph::InEdgeIt in;
1.88 -// bool backward;
1.89 -// public:
1.90 -// OutEdgeIt() { }
1.91 -// //FIXME
1.92 -// // OutEdgeIt(const Edge& e) : Edge(e) { }
1.93 -// OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1.94 -// //the unique invalid iterator
1.95 -// OutEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) {
1.96 -// backward=false;
1.97 -// _G.graph->first(out, v);
1.98 -// while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
1.99 -// if (!_G.graph->valid(out)) {
1.100 -// backward=true;
1.101 -// _G.graph->first(in, v);
1.102 -// while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
1.103 -// }
1.104 -// }
1.105 -// operator Edge() const {
1.106 -// // Edge e;
1.107 -// // e.forward=this->forward;
1.108 -// // if (this->forward) e=out; else e=in;
1.109 -// // return e;
1.110 -// if (this->backward)
1.111 -// return Edge(in, this->backward);
1.112 -// else
1.113 -// return Edge(out, this->backward);
1.114 -// }
1.115 -// };
1.116 -
1.117 -// class InEdgeIt {
1.118 -// friend class BidirGraphWrapper<Graph>;
1.119 -// protected:
1.120 -// typename Graph::OutEdgeIt out;
1.121 -// typename Graph::InEdgeIt in;
1.122 -// bool backward;
1.123 -// public:
1.124 -// InEdgeIt() { }
1.125 -// //FIXME
1.126 -// // OutEdgeIt(const Edge& e) : Edge(e) { }
1.127 -// InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1.128 -// //the unique invalid iterator
1.129 -// InEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) {
1.130 -// backward=false;
1.131 -// _G.graph->first(in, v);
1.132 -// while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
1.133 -// if (!_G.graph->valid(in)) {
1.134 -// backward=true;
1.135 -// _G.graph->first(out, v);
1.136 -// while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
1.137 -// }
1.138 -// }
1.139 -// operator Edge() const {
1.140 -// // Edge e;
1.141 -// // e.forward=this->forward;
1.142 -// // if (this->forward) e=out; else e=in;
1.143 -// // return e;
1.144 -// if (this->backward)
1.145 -// return Edge(out, this->backward);
1.146 -// else
1.147 -// return Edge(in, this->backward);
1.148 -// }
1.149 -// };
1.150 -
1.151 -// class EdgeIt {
1.152 -// friend class BidirGraphWrapper<Graph>;
1.153 -// protected:
1.154 -// typename Graph::EdgeIt e;
1.155 -// bool backward;
1.156 -// public:
1.157 -// EdgeIt() { }
1.158 -// EdgeIt(const Invalid& i) : e(i), backward(true) { }
1.159 -// EdgeIt(const BidirGraphWrapper<Graph>& _G) {
1.160 -// backward=false;
1.161 -// _G.graph->first(e);
1.162 -// while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
1.163 -// if (!_G.graph->valid(e)) {
1.164 -// backward=true;
1.165 -// _G.graph->first(e);
1.166 -// while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
1.167 -// }
1.168 -// }
1.169 -// operator Edge() const {
1.170 -// return Edge(e, this->backward);
1.171 -// }
1.172 -// };
1.173 -
1.174 -// using GraphWrapper<Graph>::first;
1.175 -// // NodeIt& first(NodeIt& i) const {
1.176 -// // i=NodeIt(*this); return i;
1.177 -// // }
1.178 -// OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.179 -// i=OutEdgeIt(*this, p); return i;
1.180 + OldBidirGraphWrapper() : GraphWrapper<Graph>()/*,
1.181 + capacity(0), flow(0)*/ { }
1.182 +// void setCapacityMap(const CapacityMap& _capacity) {
1.183 +// capacity=&_capacity;
1.184 // }
1.185 -// // FIXME not tested
1.186 -// InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.187 -// i=InEdgeIt(*this, p); return i;
1.188 -// }
1.189 -// EdgeIt& first(EdgeIt& i) const {
1.190 -// i=EdgeIt(*this); return i;
1.191 -// }
1.192 -
1.193 -// using GraphWrapper<Graph>::next;
1.194 -// // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
1.195 -// OutEdgeIt& next(OutEdgeIt& e) const {
1.196 -// if (!e.backward) {
1.197 -// Node v=this->graph->aNode(e.out);
1.198 -// this->graph->next(e.out);
1.199 -// while(this->graph->valid(e.out) && !enabled(e)) {
1.200 -// this->graph->next(e.out); }
1.201 -// if (!this->graph->valid(e.out)) {
1.202 -// e.backward=true;
1.203 -// this->graph->first(e.in, v);
1.204 -// while(this->graph->valid(e.in) && !enabled(e)) {
1.205 -// this->graph->next(e.in); }
1.206 -// }
1.207 -// } else {
1.208 -// this->graph->next(e.in);
1.209 -// while(this->graph->valid(e.in) && !enabled(e)) {
1.210 -// this->graph->next(e.in); }
1.211 -// }
1.212 -// return e;
1.213 -// }
1.214 -// // FIXME Not tested
1.215 -// InEdgeIt& next(InEdgeIt& e) const {
1.216 -// if (!e.backward) {
1.217 -// Node v=this->graph->aNode(e.in);
1.218 -// this->graph->next(e.in);
1.219 -// while(this->graph->valid(e.in) && !enabled(e)) {
1.220 -// this->graph->next(e.in); }
1.221 -// if (!this->graph->valid(e.in)) {
1.222 -// e.backward=true;
1.223 -// this->graph->first(e.out, v);
1.224 -// while(this->graph->valid(e.out) && !enabled(e)) {
1.225 -// this->graph->next(e.out); }
1.226 -// }
1.227 -// } else {
1.228 -// this->graph->next(e.out);
1.229 -// while(this->graph->valid(e.out) && !enabled(e)) {
1.230 -// this->graph->next(e.out); }
1.231 -// }
1.232 -// return e;
1.233 -// }
1.234 -// EdgeIt& next(EdgeIt& e) const {
1.235 -// if (!e.backward) {
1.236 -// this->graph->next(e.e);
1.237 -// while(this->graph->valid(e.e) && !enabled(e)) {
1.238 -// this->graph->next(e.e); }
1.239 -// if (!this->graph->valid(e.e)) {
1.240 -// e.backward=true;
1.241 -// this->graph->first(e.e);
1.242 -// while(this->graph->valid(e.e) && !enabled(e)) {
1.243 -// this->graph->next(e.e); }
1.244 -// }
1.245 -// } else {
1.246 -// this->graph->next(e.e);
1.247 -// while(this->graph->valid(e.e) && !enabled(e)) {
1.248 -// this->graph->next(e.e); }
1.249 -// }
1.250 -// return e;
1.251 +// void setFlowMap(FlowMap& _flow) {
1.252 +// flow=&_flow;
1.253 // }
1.254
1.255 -// Node tail(Edge e) const {
1.256 -// return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
1.257 -// Node head(Edge e) const {
1.258 -// return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
1.259 + public:
1.260
1.261 -// Node aNode(OutEdgeIt e) const {
1.262 -// return ((!e.backward) ? this->graph->aNode(e.out) :
1.263 -// this->graph->aNode(e.in)); }
1.264 -// Node bNode(OutEdgeIt e) const {
1.265 -// return ((!e.backward) ? this->graph->bNode(e.out) :
1.266 -// this->graph->bNode(e.in)); }
1.267 + OldBidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity,
1.268 + FlowMap& _flow*/) :
1.269 + GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
1.270
1.271 -// Node aNode(InEdgeIt e) const {
1.272 -// return ((!e.backward) ? this->graph->aNode(e.in) :
1.273 -// this->graph->aNode(e.out)); }
1.274 -// Node bNode(InEdgeIt e) const {
1.275 -// return ((!e.backward) ? this->graph->bNode(e.in) :
1.276 -// this->graph->bNode(e.out)); }
1.277 + class Edge;
1.278 + class OutEdgeIt;
1.279 + friend class Edge;
1.280 + friend class OutEdgeIt;
1.281
1.282 -// /// Gives back the opposite edge.
1.283 -// Edge opposite(const Edge& e) const {
1.284 -// Edge f=e;
1.285 -// f.backward=!f.backward;
1.286 -// return f;
1.287 + //template<typename T> class NodeMap;
1.288 + template<typename T> class EdgeMap;
1.289 +
1.290 + typedef typename GraphWrapper<Graph>::Node Node;
1.291 + typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.292 +
1.293 + class Edge : public Graph::Edge {
1.294 + friend class OldBidirGraphWrapper<Graph>;
1.295 + ///\bug ez nem is kell
1.296 + //template<typename T> friend class NodeMap;
1.297 + template<typename T> friend class EdgeMap;
1.298 + protected:
1.299 + bool backward; //true, iff backward
1.300 +// typename Graph::Edge e;
1.301 + public:
1.302 + Edge() { }
1.303 + ///\bug =false kell-e? zsoltnak kell az addEdge miatt
1.304 + Edge(const typename Graph::Edge& _e, bool _backward=false) :
1.305 + Graph::Edge(_e), backward(_backward) { }
1.306 + Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
1.307 +//the unique invalid iterator
1.308 + friend bool operator==(const Edge& u, const Edge& v) {
1.309 + return (v.backward==u.backward &&
1.310 + static_cast<typename Graph::Edge>(u)==
1.311 + static_cast<typename Graph::Edge>(v));
1.312 + }
1.313 + friend bool operator!=(const Edge& u, const Edge& v) {
1.314 + return (v.backward!=u.backward ||
1.315 + static_cast<typename Graph::Edge>(u)!=
1.316 + static_cast<typename Graph::Edge>(v));
1.317 + }
1.318 + };
1.319 +
1.320 + class OutEdgeIt {
1.321 + friend class OldBidirGraphWrapper<Graph>;
1.322 + protected:
1.323 + typename Graph::OutEdgeIt out;
1.324 + typename Graph::InEdgeIt in;
1.325 + bool backward;
1.326 + public:
1.327 + OutEdgeIt() { }
1.328 + //FIXME
1.329 +// OutEdgeIt(const Edge& e) : Edge(e) { }
1.330 + OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1.331 +//the unique invalid iterator
1.332 + OutEdgeIt(const OldBidirGraphWrapper<Graph>& _G, Node v) {
1.333 + backward=false;
1.334 + _G.graph->first(out, v);
1.335 + while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
1.336 + if (!_G.graph->valid(out)) {
1.337 + backward=true;
1.338 + _G.graph->first(in, v);
1.339 + while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
1.340 + }
1.341 + }
1.342 + operator Edge() const {
1.343 +// Edge e;
1.344 +// e.forward=this->forward;
1.345 +// if (this->forward) e=out; else e=in;
1.346 +// return e;
1.347 + if (this->backward)
1.348 + return Edge(in, this->backward);
1.349 + else
1.350 + return Edge(out, this->backward);
1.351 + }
1.352 + };
1.353 +
1.354 + class InEdgeIt {
1.355 + friend class OldBidirGraphWrapper<Graph>;
1.356 + protected:
1.357 + typename Graph::OutEdgeIt out;
1.358 + typename Graph::InEdgeIt in;
1.359 + bool backward;
1.360 + public:
1.361 + InEdgeIt() { }
1.362 + //FIXME
1.363 +// OutEdgeIt(const Edge& e) : Edge(e) { }
1.364 + InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1.365 +//the unique invalid iterator
1.366 + InEdgeIt(const OldBidirGraphWrapper<Graph>& _G, Node v) {
1.367 + backward=false;
1.368 + _G.graph->first(in, v);
1.369 + while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
1.370 + if (!_G.graph->valid(in)) {
1.371 + backward=true;
1.372 + _G.graph->first(out, v);
1.373 + while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
1.374 + }
1.375 + }
1.376 + operator Edge() const {
1.377 +// Edge e;
1.378 +// e.forward=this->forward;
1.379 +// if (this->forward) e=out; else e=in;
1.380 +// return e;
1.381 + if (this->backward)
1.382 + return Edge(out, this->backward);
1.383 + else
1.384 + return Edge(in, this->backward);
1.385 + }
1.386 + };
1.387 +
1.388 + class EdgeIt {
1.389 + friend class OldBidirGraphWrapper<Graph>;
1.390 + protected:
1.391 + typename Graph::EdgeIt e;
1.392 + bool backward;
1.393 + public:
1.394 + EdgeIt() { }
1.395 + EdgeIt(const Invalid& i) : e(i), backward(true) { }
1.396 + EdgeIt(const OldBidirGraphWrapper<Graph>& _G) {
1.397 + backward=false;
1.398 + _G.graph->first(e);
1.399 + while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
1.400 + if (!_G.graph->valid(e)) {
1.401 + backward=true;
1.402 + _G.graph->first(e);
1.403 + while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
1.404 + }
1.405 + }
1.406 + operator Edge() const {
1.407 + return Edge(e, this->backward);
1.408 + }
1.409 + };
1.410 +
1.411 + using GraphWrapper<Graph>::first;
1.412 +// NodeIt& first(NodeIt& i) const {
1.413 +// i=NodeIt(*this); return i;
1.414 +// }
1.415 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1.416 + i=OutEdgeIt(*this, p); return i;
1.417 + }
1.418 +// FIXME not tested
1.419 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1.420 + i=InEdgeIt(*this, p); return i;
1.421 + }
1.422 + EdgeIt& first(EdgeIt& i) const {
1.423 + i=EdgeIt(*this); return i;
1.424 + }
1.425 +
1.426 + using GraphWrapper<Graph>::next;
1.427 +// NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
1.428 + OutEdgeIt& next(OutEdgeIt& e) const {
1.429 + if (!e.backward) {
1.430 + Node v=this->graph->aNode(e.out);
1.431 + this->graph->next(e.out);
1.432 + while(this->graph->valid(e.out) && !enabled(e)) {
1.433 + this->graph->next(e.out); }
1.434 + if (!this->graph->valid(e.out)) {
1.435 + e.backward=true;
1.436 + this->graph->first(e.in, v);
1.437 + while(this->graph->valid(e.in) && !enabled(e)) {
1.438 + this->graph->next(e.in); }
1.439 + }
1.440 + } else {
1.441 + this->graph->next(e.in);
1.442 + while(this->graph->valid(e.in) && !enabled(e)) {
1.443 + this->graph->next(e.in); }
1.444 + }
1.445 + return e;
1.446 + }
1.447 +// FIXME Not tested
1.448 + InEdgeIt& next(InEdgeIt& e) const {
1.449 + if (!e.backward) {
1.450 + Node v=this->graph->aNode(e.in);
1.451 + this->graph->next(e.in);
1.452 + while(this->graph->valid(e.in) && !enabled(e)) {
1.453 + this->graph->next(e.in); }
1.454 + if (!this->graph->valid(e.in)) {
1.455 + e.backward=true;
1.456 + this->graph->first(e.out, v);
1.457 + while(this->graph->valid(e.out) && !enabled(e)) {
1.458 + this->graph->next(e.out); }
1.459 + }
1.460 + } else {
1.461 + this->graph->next(e.out);
1.462 + while(this->graph->valid(e.out) && !enabled(e)) {
1.463 + this->graph->next(e.out); }
1.464 + }
1.465 + return e;
1.466 + }
1.467 + EdgeIt& next(EdgeIt& e) const {
1.468 + if (!e.backward) {
1.469 + this->graph->next(e.e);
1.470 + while(this->graph->valid(e.e) && !enabled(e)) {
1.471 + this->graph->next(e.e); }
1.472 + if (!this->graph->valid(e.e)) {
1.473 + e.backward=true;
1.474 + this->graph->first(e.e);
1.475 + while(this->graph->valid(e.e) && !enabled(e)) {
1.476 + this->graph->next(e.e); }
1.477 + }
1.478 + } else {
1.479 + this->graph->next(e.e);
1.480 + while(this->graph->valid(e.e) && !enabled(e)) {
1.481 + this->graph->next(e.e); }
1.482 + }
1.483 + return e;
1.484 + }
1.485 +
1.486 + Node tail(Edge e) const {
1.487 + return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
1.488 + Node head(Edge e) const {
1.489 + return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
1.490 +
1.491 + Node aNode(OutEdgeIt e) const {
1.492 + return ((!e.backward) ? this->graph->aNode(e.out) :
1.493 + this->graph->aNode(e.in)); }
1.494 + Node bNode(OutEdgeIt e) const {
1.495 + return ((!e.backward) ? this->graph->bNode(e.out) :
1.496 + this->graph->bNode(e.in)); }
1.497 +
1.498 + Node aNode(InEdgeIt e) const {
1.499 + return ((!e.backward) ? this->graph->aNode(e.in) :
1.500 + this->graph->aNode(e.out)); }
1.501 + Node bNode(InEdgeIt e) const {
1.502 + return ((!e.backward) ? this->graph->bNode(e.in) :
1.503 + this->graph->bNode(e.out)); }
1.504 +
1.505 + /// Gives back the opposite edge.
1.506 + Edge opposite(const Edge& e) const {
1.507 + Edge f=e;
1.508 + f.backward=!f.backward;
1.509 + return f;
1.510 + }
1.511 +
1.512 +// int nodeNum() const { return graph->nodeNum(); }
1.513 + //FIXME
1.514 + void edgeNum() const { }
1.515 + //int edgeNum() const { return graph->edgeNum(); }
1.516 +
1.517 +
1.518 +// int id(Node v) const { return graph->id(v); }
1.519 +
1.520 + bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
1.521 + bool valid(Edge e) const {
1.522 + return this->graph->valid(e);
1.523 + //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
1.524 + }
1.525 +
1.526 + bool forward(const Edge& e) const { return !e.backward; }
1.527 + bool backward(const Edge& e) const { return e.backward; }
1.528 +
1.529 +// void augment(const Edge& e, Number a) const {
1.530 +// if (!e.backward)
1.531 +// // flow->set(e.out, flow->get(e.out)+a);
1.532 +// flow->set(e, (*flow)[e]+a);
1.533 +// else
1.534 +// // flow->set(e.in, flow->get(e.in)-a);
1.535 +// flow->set(e, (*flow)[e]-a);
1.536 // }
1.537
1.538 -// // int nodeNum() const { return graph->nodeNum(); }
1.539 -// //FIXME
1.540 -// void edgeNum() const { }
1.541 -// //int edgeNum() const { return graph->edgeNum(); }
1.542 + bool enabled(const Edge& e) const {
1.543 + if (!e.backward)
1.544 +// return (capacity->get(e.out)-flow->get(e.out));
1.545 + //return ((*capacity)[e]-(*flow)[e]);
1.546 + return true;
1.547 + else
1.548 +// return (flow->get(e.in));
1.549 + //return ((*flow)[e]);
1.550 + return true;
1.551 + }
1.552
1.553 -
1.554 -// // int id(Node v) const { return graph->id(v); }
1.555 -
1.556 -// bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
1.557 -// bool valid(Edge e) const {
1.558 -// return this->graph->valid(e);
1.559 -// //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
1.560 +// Number enabled(typename Graph::OutEdgeIt out) const {
1.561 +// // return (capacity->get(out)-flow->get(out));
1.562 +// return ((*capacity)[out]-(*flow)[out]);
1.563 +// }
1.564 +
1.565 +// Number enabled(typename Graph::InEdgeIt in) const {
1.566 +// // return (flow->get(in));
1.567 +// return ((*flow)[in]);
1.568 // }
1.569
1.570 -// bool forward(const Edge& e) const { return !e.backward; }
1.571 -// bool backward(const Edge& e) const { return e.backward; }
1.572 + template <typename T>
1.573 + class EdgeMap {
1.574 + typename Graph::template EdgeMap<T> forward_map, backward_map;
1.575 + public:
1.576 + typedef T ValueType;
1.577 + typedef Edge KeyType;
1.578 + EdgeMap(const OldBidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1.579 + EdgeMap(const OldBidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1.580 + void set(Edge e, T a) {
1.581 + if (!e.backward)
1.582 + forward_map.set(e/*.out*/, a);
1.583 + else
1.584 + backward_map.set(e/*.in*/, a);
1.585 + }
1.586 + T operator[](Edge e) const {
1.587 + if (!e.backward)
1.588 + return forward_map[e/*.out*/];
1.589 + else
1.590 + return backward_map[e/*.in*/];
1.591 + }
1.592 + void update() {
1.593 + forward_map.update();
1.594 + backward_map.update();
1.595 + }
1.596 +// T get(Edge e) const {
1.597 +// if (e.out_or_in)
1.598 +// return forward_map.get(e.out);
1.599 +// else
1.600 +// return backward_map.get(e.in);
1.601 +// }
1.602 + };
1.603 + };
1.604
1.605 -// // void augment(const Edge& e, Number a) const {
1.606 -// // if (!e.backward)
1.607 -// // // flow->set(e.out, flow->get(e.out)+a);
1.608 -// // flow->set(e, (*flow)[e]+a);
1.609 -// // else
1.610 -// // // flow->set(e.in, flow->get(e.in)-a);
1.611 -// // flow->set(e, (*flow)[e]-a);
1.612 -// // }
1.613
1.614 -// bool enabled(const Edge& e) const {
1.615 -// if (!e.backward)
1.616 -// // return (capacity->get(e.out)-flow->get(e.out));
1.617 -// //return ((*capacity)[e]-(*flow)[e]);
1.618 -// return true;
1.619 -// else
1.620 -// // return (flow->get(e.in));
1.621 -// //return ((*flow)[e]);
1.622 -// return true;
1.623 -// }
1.624 -
1.625 -// // Number enabled(typename Graph::OutEdgeIt out) const {
1.626 -// // // return (capacity->get(out)-flow->get(out));
1.627 -// // return ((*capacity)[out]-(*flow)[out]);
1.628 -// // }
1.629 -
1.630 -// // Number enabled(typename Graph::InEdgeIt in) const {
1.631 -// // // return (flow->get(in));
1.632 -// // return ((*flow)[in]);
1.633 -// // }
1.634 -
1.635 -// template <typename T>
1.636 -// class EdgeMap {
1.637 -// typename Graph::template EdgeMap<T> forward_map, backward_map;
1.638 -// public:
1.639 -// typedef T ValueType;
1.640 -// typedef Edge KeyType;
1.641 -// EdgeMap(const BidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1.642 -// EdgeMap(const BidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1.643 -// void set(Edge e, T a) {
1.644 -// if (!e.backward)
1.645 -// forward_map.set(e/*.out*/, a);
1.646 -// else
1.647 -// backward_map.set(e/*.in*/, a);
1.648 -// }
1.649 -// T operator[](Edge e) const {
1.650 -// if (!e.backward)
1.651 -// return forward_map[e/*.out*/];
1.652 -// else
1.653 -// return backward_map[e/*.in*/];
1.654 -// }
1.655 -// void update() {
1.656 -// forward_map.update();
1.657 -// backward_map.update();
1.658 -// }
1.659 -// // T get(Edge e) const {
1.660 -// // if (e.out_or_in)
1.661 -// // return forward_map.get(e.out);
1.662 -// // else
1.663 -// // return backward_map.get(e.in);
1.664 -// // }
1.665 -// };
1.666 -// };
1.667
1.668 /// \brief A bidirected graph template.
1.669 ///
1.670 @@ -1376,7 +1370,6 @@
1.671
1.672
1.673
1.674 - /// An experiment for ResGraphWrapper.
1.675 template<typename Graph, typename Number,
1.676 typename CapacityMap, typename FlowMap>
1.677 class ForwardFilter {
1.678 @@ -1392,7 +1385,6 @@
1.679 }
1.680 };
1.681
1.682 - /// An experiment for ResGraphWrapper.
1.683 template<typename Graph, typename Number,
1.684 typename CapacityMap, typename FlowMap>
1.685 class BackwardFilter {
1.686 @@ -1408,11 +1400,13 @@
1.687 }
1.688 };
1.689
1.690 +
1.691 + /// A wrapper for composing the residual graph for directed flow and circulation problems.
1.692
1.693 - /// An experiment for ResGraphWrapper.
1.694 + /// A wrapper for composing the residual graph for directed flow and circulation problems.
1.695 template<typename Graph, typename Number,
1.696 typename CapacityMap, typename FlowMap>
1.697 - class ExpResGraphWrapper :
1.698 + class ResGraphWrapper :
1.699 public SubBidirGraphWrapper<
1.700 Graph,
1.701 ForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1.702 @@ -1428,7 +1422,7 @@
1.703 ForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1.704 BackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1.705 public:
1.706 - ExpResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1.707 + ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1.708 FlowMap& _flow) :
1.709 Parent(), capacity(&_capacity), flow(&_flow),
1.710 forward_filter(_graph, _capacity, _flow),
1.711 @@ -1464,77 +1458,16 @@
1.712
1.713
1.714
1.715 -// /// An experiment for ResGraphWrapper.
1.716 -// template<typename Graph, typename Number,
1.717 -// typename CapacityMap, typename FlowMap>
1.718 -// class ExpResGraphWrapper :
1.719 -// public SubGraphWrapper< BidirGraphWrapper<Graph>,
1.720 -// ConstMap<typename BidirGraphWrapper<Graph>::Node,
1.721 -// bool>,
1.722 -// EdgeFilter< BidirGraphWrapper<Graph>,
1.723 -// CapacityMap, FlowMap> > {
1.724 -// public:
1.725 -// typedef SubGraphWrapper< BidirGraphWrapper<Graph>,
1.726 -// ConstMap<typename BidirGraphWrapper<Graph>::Node,
1.727 -// bool>,
1.728 -// EdgeFilter< BidirGraphWrapper<Graph>,
1.729 -// CapacityMap, FlowMap> > Parent;
1.730 -// protected:
1.731 -// const CapacityMap* capacity;
1.732 -// FlowMap* flow;
1.733 -// BidirGraphWrapper<Graph> bidir_graph;
1.734 -// ConstMap<typename BidirGraphWrapper<Graph>::Node, bool> node_filter;
1.735 -// EdgeFilter< BidirGraphWrapper<Graph>, CapacityMap, FlowMap> edge_filter;
1.736 -// public:
1.737 -// ExpResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1.738 -// FlowMap& _flow) :
1.739 -// Parent(), capacity(&_capacity), flow(&_flow),
1.740 -// bidir_graph(_graph),
1.741 -// node_filter(true),
1.742 -// edge_filter(bidir_graph, *capacity, *flow) {
1.743 -// Parent::setGraph(bidir_graph);
1.744 -// Parent::setNodeFilterMap(node_filter);
1.745 -// Parent::setEdgeFilterMap(edge_filter);
1.746 -// }
1.747 -
1.748 -// // bool forward(const Parent::Edge& e) const { return Parent::forward(e); }
1.749 -// //bool backward(const Edge& e) const { return e.backward; }
1.750 -
1.751 -// void augment(const typename Parent::Edge& e, Number a) const {
1.752 -// if (Parent::forward(e))
1.753 -// // flow->set(e.out, flow->get(e.out)+a);
1.754 -// flow->set(e, (*flow)[e]+a);
1.755 -// else
1.756 -// // flow->set(e.in, flow->get(e.in)-a);
1.757 -// flow->set(e, (*flow)[e]-a);
1.758 -// }
1.759 -
1.760 -// Number resCap(const typename Parent::Edge& e) const {
1.761 -// if (Parent::forward(e))
1.762 -// // return (capacity->get(e.out)-flow->get(e.out));
1.763 -// return ((*capacity)[e]-(*flow)[e]);
1.764 -// else
1.765 -// // return (flow->get(e.in));
1.766 -// return ((*flow)[e]);
1.767 -// }
1.768 -
1.769 -// };
1.770 -
1.771 -
1.772 -
1.773 - /// A wrapper for composing the residual graph for directed flow and circulation problems.
1.774 -
1.775 - /// A wrapper for composing the residual graph for directed flow and circulation problems.
1.776 template<typename Graph, typename Number,
1.777 typename CapacityMap, typename FlowMap>
1.778 - class ResGraphWrapper : public GraphWrapper<Graph> {
1.779 + class OldResGraphWrapper : public GraphWrapper<Graph> {
1.780 public:
1.781 typedef GraphWrapper<Graph> Parent;
1.782 protected:
1.783 const CapacityMap* capacity;
1.784 FlowMap* flow;
1.785
1.786 - ResGraphWrapper() : GraphWrapper<Graph>(0),
1.787 + OldResGraphWrapper() : GraphWrapper<Graph>(0),
1.788 capacity(0), flow(0) { }
1.789 void setCapacityMap(const CapacityMap& _capacity) {
1.790 capacity=&_capacity;
1.791 @@ -1545,7 +1478,7 @@
1.792
1.793 public:
1.794
1.795 - ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1.796 + OldResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1.797 FlowMap& _flow) :
1.798 GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
1.799
1.800 @@ -1557,7 +1490,7 @@
1.801 typedef typename GraphWrapper<Graph>::Node Node;
1.802 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
1.803 class Edge : public Graph::Edge {
1.804 - friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1.805 + friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1.806 protected:
1.807 bool backward; //true, iff backward
1.808 // typename Graph::Edge e;
1.809 @@ -1580,7 +1513,7 @@
1.810 };
1.811
1.812 class OutEdgeIt {
1.813 - friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1.814 + friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1.815 protected:
1.816 typename Graph::OutEdgeIt out;
1.817 typename Graph::InEdgeIt in;
1.818 @@ -1591,7 +1524,7 @@
1.819 // OutEdgeIt(const Edge& e) : Edge(e) { }
1.820 OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1.821 //the unique invalid iterator
1.822 - OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
1.823 + OutEdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
1.824 backward=false;
1.825 _G.graph->first(out, v);
1.826 while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
1.827 @@ -1614,7 +1547,7 @@
1.828 };
1.829
1.830 class InEdgeIt {
1.831 - friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1.832 + friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1.833 protected:
1.834 typename Graph::OutEdgeIt out;
1.835 typename Graph::InEdgeIt in;
1.836 @@ -1625,7 +1558,7 @@
1.837 // OutEdgeIt(const Edge& e) : Edge(e) { }
1.838 InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
1.839 //the unique invalid iterator
1.840 - InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
1.841 + InEdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
1.842 backward=false;
1.843 _G.graph->first(in, v);
1.844 while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
1.845 @@ -1648,14 +1581,14 @@
1.846 };
1.847
1.848 class EdgeIt {
1.849 - friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1.850 + friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
1.851 protected:
1.852 typename Graph::EdgeIt e;
1.853 bool backward;
1.854 public:
1.855 EdgeIt() { }
1.856 EdgeIt(const Invalid& i) : e(i), backward(true) { }
1.857 - EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) {
1.858 + EdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) {
1.859 backward=false;
1.860 _G.graph->first(e);
1.861 while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
1.862 @@ -1815,8 +1748,8 @@
1.863 public:
1.864 typedef T ValueType;
1.865 typedef Edge KeyType;
1.866 - EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1.867 - EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1.868 + EdgeMap(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
1.869 + EdgeMap(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
1.870 void set(Edge e, T a) {
1.871 if (!e.backward)
1.872 forward_map.set(e/*.out*/, a);