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