1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/digraph_adaptor.h Sun Nov 30 18:57:18 2008 +0100
1.3 @@ -0,0 +1,2530 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2008
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_DIGRAPH_ADAPTOR_H
1.23 +#define LEMON_DIGRAPH_ADAPTOR_H
1.24 +
1.25 +///\ingroup graph_adaptors
1.26 +///\file
1.27 +///\brief Several digraph adaptors.
1.28 +///
1.29 +///This file contains several useful digraph adaptor functions.
1.30 +
1.31 +#include <lemon/core.h>
1.32 +#include <lemon/maps.h>
1.33 +#include <lemon/bits/variant.h>
1.34 +
1.35 +#include <lemon/bits/base_extender.h>
1.36 +#include <lemon/bits/graph_adaptor_extender.h>
1.37 +#include <lemon/bits/graph_extender.h>
1.38 +#include <lemon/tolerance.h>
1.39 +
1.40 +#include <algorithm>
1.41 +
1.42 +namespace lemon {
1.43 +
1.44 + ///\brief Base type for the Digraph Adaptors
1.45 + ///
1.46 + ///Base type for the Digraph Adaptors
1.47 + ///
1.48 + ///This is the base type for most of LEMON digraph adaptors. This
1.49 + ///class implements a trivial digraph adaptor i.e. it only wraps the
1.50 + ///functions and types of the digraph. The purpose of this class is
1.51 + ///to make easier implementing digraph adaptors. E.g. if an adaptor
1.52 + ///is considered which differs from the wrapped digraph only in some
1.53 + ///of its functions or types, then it can be derived from
1.54 + ///DigraphAdaptor, and only the differences should be implemented.
1.55 + template<typename _Digraph>
1.56 + class DigraphAdaptorBase {
1.57 + public:
1.58 + typedef _Digraph Digraph;
1.59 + typedef DigraphAdaptorBase Adaptor;
1.60 + typedef Digraph ParentDigraph;
1.61 +
1.62 + protected:
1.63 + Digraph* _digraph;
1.64 + DigraphAdaptorBase() : _digraph(0) { }
1.65 + void setDigraph(Digraph& digraph) { _digraph = &digraph; }
1.66 +
1.67 + public:
1.68 + DigraphAdaptorBase(Digraph& digraph) : _digraph(&digraph) { }
1.69 +
1.70 + typedef typename Digraph::Node Node;
1.71 + typedef typename Digraph::Arc Arc;
1.72 +
1.73 + void first(Node& i) const { _digraph->first(i); }
1.74 + void first(Arc& i) const { _digraph->first(i); }
1.75 + void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); }
1.76 + void firstOut(Arc& i, const Node& n ) const { _digraph->firstOut(i, n); }
1.77 +
1.78 + void next(Node& i) const { _digraph->next(i); }
1.79 + void next(Arc& i) const { _digraph->next(i); }
1.80 + void nextIn(Arc& i) const { _digraph->nextIn(i); }
1.81 + void nextOut(Arc& i) const { _digraph->nextOut(i); }
1.82 +
1.83 + Node source(const Arc& a) const { return _digraph->source(a); }
1.84 + Node target(const Arc& a) const { return _digraph->target(a); }
1.85 +
1.86 + typedef NodeNumTagIndicator<Digraph> NodeNumTag;
1.87 + int nodeNum() const { return _digraph->nodeNum(); }
1.88 +
1.89 + typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
1.90 + int arcNum() const { return _digraph->arcNum(); }
1.91 +
1.92 + typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
1.93 + Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
1.94 + return _digraph->findArc(u, v, prev);
1.95 + }
1.96 +
1.97 + Node addNode() { return _digraph->addNode(); }
1.98 + Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
1.99 +
1.100 + void erase(const Node& n) const { _digraph->erase(n); }
1.101 + void erase(const Arc& a) const { _digraph->erase(a); }
1.102 +
1.103 + void clear() const { _digraph->clear(); }
1.104 +
1.105 + int id(const Node& n) const { return _digraph->id(n); }
1.106 + int id(const Arc& a) const { return _digraph->id(a); }
1.107 +
1.108 + Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
1.109 + Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); }
1.110 +
1.111 + int maxNodeId() const { return _digraph->maxNodeId(); }
1.112 + int maxArcId() const { return _digraph->maxArcId(); }
1.113 +
1.114 + typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
1.115 + NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
1.116 +
1.117 + typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier;
1.118 + ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
1.119 +
1.120 + template <typename _Value>
1.121 + class NodeMap : public Digraph::template NodeMap<_Value> {
1.122 + public:
1.123 +
1.124 + typedef typename Digraph::template NodeMap<_Value> Parent;
1.125 +
1.126 + explicit NodeMap(const Adaptor& adaptor)
1.127 + : Parent(*adaptor._digraph) {}
1.128 +
1.129 + NodeMap(const Adaptor& adaptor, const _Value& value)
1.130 + : Parent(*adaptor._digraph, value) { }
1.131 +
1.132 + private:
1.133 + NodeMap& operator=(const NodeMap& cmap) {
1.134 + return operator=<NodeMap>(cmap);
1.135 + }
1.136 +
1.137 + template <typename CMap>
1.138 + NodeMap& operator=(const CMap& cmap) {
1.139 + Parent::operator=(cmap);
1.140 + return *this;
1.141 + }
1.142 +
1.143 + };
1.144 +
1.145 + template <typename _Value>
1.146 + class ArcMap : public Digraph::template ArcMap<_Value> {
1.147 + public:
1.148 +
1.149 + typedef typename Digraph::template ArcMap<_Value> Parent;
1.150 +
1.151 + explicit ArcMap(const Adaptor& adaptor)
1.152 + : Parent(*adaptor._digraph) {}
1.153 +
1.154 + ArcMap(const Adaptor& adaptor, const _Value& value)
1.155 + : Parent(*adaptor._digraph, value) {}
1.156 +
1.157 + private:
1.158 + ArcMap& operator=(const ArcMap& cmap) {
1.159 + return operator=<ArcMap>(cmap);
1.160 + }
1.161 +
1.162 + template <typename CMap>
1.163 + ArcMap& operator=(const CMap& cmap) {
1.164 + Parent::operator=(cmap);
1.165 + return *this;
1.166 + }
1.167 +
1.168 + };
1.169 +
1.170 + };
1.171 +
1.172 + ///\ingroup graph_adaptors
1.173 + ///
1.174 + ///\brief Trivial Digraph Adaptor
1.175 + ///
1.176 + /// This class is an adaptor which does not change the adapted
1.177 + /// digraph. It can be used only to test the digraph adaptors.
1.178 + template <typename _Digraph>
1.179 + class DigraphAdaptor :
1.180 + public DigraphAdaptorExtender<DigraphAdaptorBase<_Digraph> > {
1.181 + public:
1.182 + typedef _Digraph Digraph;
1.183 + typedef DigraphAdaptorExtender<DigraphAdaptorBase<_Digraph> > Parent;
1.184 + protected:
1.185 + DigraphAdaptor() : Parent() { }
1.186 +
1.187 + public:
1.188 + explicit DigraphAdaptor(Digraph& digraph) { setDigraph(digraph); }
1.189 + };
1.190 +
1.191 + /// \brief Just gives back a digraph adaptor
1.192 + ///
1.193 + /// Just gives back a digraph adaptor which
1.194 + /// should be provide original digraph
1.195 + template<typename Digraph>
1.196 + DigraphAdaptor<const Digraph>
1.197 + digraphAdaptor(const Digraph& digraph) {
1.198 + return DigraphAdaptor<const Digraph>(digraph);
1.199 + }
1.200 +
1.201 +
1.202 + template <typename _Digraph>
1.203 + class RevDigraphAdaptorBase : public DigraphAdaptorBase<_Digraph> {
1.204 + public:
1.205 + typedef _Digraph Digraph;
1.206 + typedef DigraphAdaptorBase<_Digraph> Parent;
1.207 + protected:
1.208 + RevDigraphAdaptorBase() : Parent() { }
1.209 + public:
1.210 + typedef typename Parent::Node Node;
1.211 + typedef typename Parent::Arc Arc;
1.212 +
1.213 + void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }
1.214 + void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); }
1.215 +
1.216 + void nextIn(Arc& a) const { Parent::nextOut(a); }
1.217 + void nextOut(Arc& a) const { Parent::nextIn(a); }
1.218 +
1.219 + Node source(const Arc& a) const { return Parent::target(a); }
1.220 + Node target(const Arc& a) const { return Parent::source(a); }
1.221 +
1.222 + typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
1.223 + Arc findArc(const Node& u, const Node& v,
1.224 + const Arc& prev = INVALID) {
1.225 + return Parent::findArc(v, u, prev);
1.226 + }
1.227 +
1.228 + };
1.229 +
1.230 +
1.231 + ///\ingroup graph_adaptors
1.232 + ///
1.233 + ///\brief A digraph adaptor which reverses the orientation of the arcs.
1.234 + ///
1.235 + /// If \c g is defined as
1.236 + ///\code
1.237 + /// ListDigraph g;
1.238 + ///\endcode
1.239 + /// then
1.240 + ///\code
1.241 + /// RevDigraphAdaptor<ListDigraph> ga(g);
1.242 + ///\endcode
1.243 + /// implements the digraph obtained from \c g by
1.244 + /// reversing the orientation of its arcs.
1.245 + ///
1.246 + /// A good example of using RevDigraphAdaptor is to decide that the
1.247 + /// directed graph is wheter strongly connected or not. If from one
1.248 + /// node each node is reachable and from each node is reachable this
1.249 + /// node then and just then the digraph is strongly
1.250 + /// connected. Instead of this condition we use a little bit
1.251 + /// different. From one node each node ahould be reachable in the
1.252 + /// digraph and in the reversed digraph. Now this condition can be
1.253 + /// checked with the Dfs algorithm class and the RevDigraphAdaptor
1.254 + /// algorithm class.
1.255 + ///
1.256 + /// And look at the code:
1.257 + ///
1.258 + ///\code
1.259 + /// bool stronglyConnected(const Digraph& digraph) {
1.260 + /// if (NodeIt(digraph) == INVALID) return true;
1.261 + /// Dfs<Digraph> dfs(digraph);
1.262 + /// dfs.run(NodeIt(digraph));
1.263 + /// for (NodeIt it(digraph); it != INVALID; ++it) {
1.264 + /// if (!dfs.reached(it)) {
1.265 + /// return false;
1.266 + /// }
1.267 + /// }
1.268 + /// typedef RevDigraphAdaptor<const Digraph> RDigraph;
1.269 + /// RDigraph rdigraph(digraph);
1.270 + /// DfsVisit<RDigraph> rdfs(rdigraph);
1.271 + /// rdfs.run(NodeIt(digraph));
1.272 + /// for (NodeIt it(digraph); it != INVALID; ++it) {
1.273 + /// if (!rdfs.reached(it)) {
1.274 + /// return false;
1.275 + /// }
1.276 + /// }
1.277 + /// return true;
1.278 + /// }
1.279 + ///\endcode
1.280 + template<typename _Digraph>
1.281 + class RevDigraphAdaptor :
1.282 + public DigraphAdaptorExtender<RevDigraphAdaptorBase<_Digraph> > {
1.283 + public:
1.284 + typedef _Digraph Digraph;
1.285 + typedef DigraphAdaptorExtender<
1.286 + RevDigraphAdaptorBase<_Digraph> > Parent;
1.287 + protected:
1.288 + RevDigraphAdaptor() { }
1.289 + public:
1.290 + explicit RevDigraphAdaptor(Digraph& digraph) {
1.291 + Parent::setDigraph(digraph);
1.292 + }
1.293 + };
1.294 +
1.295 + /// \brief Just gives back a reverse digraph adaptor
1.296 + ///
1.297 + /// Just gives back a reverse digraph adaptor
1.298 + template<typename Digraph>
1.299 + RevDigraphAdaptor<const Digraph>
1.300 + revDigraphAdaptor(const Digraph& digraph) {
1.301 + return RevDigraphAdaptor<const Digraph>(digraph);
1.302 + }
1.303 +
1.304 + template <typename _Digraph, typename _NodeFilterMap,
1.305 + typename _ArcFilterMap, bool checked = true>
1.306 + class SubDigraphAdaptorBase : public DigraphAdaptorBase<_Digraph> {
1.307 + public:
1.308 + typedef _Digraph Digraph;
1.309 + typedef _NodeFilterMap NodeFilterMap;
1.310 + typedef _ArcFilterMap ArcFilterMap;
1.311 +
1.312 + typedef SubDigraphAdaptorBase Adaptor;
1.313 + typedef DigraphAdaptorBase<_Digraph> Parent;
1.314 + protected:
1.315 + NodeFilterMap* _node_filter;
1.316 + ArcFilterMap* _arc_filter;
1.317 + SubDigraphAdaptorBase()
1.318 + : Parent(), _node_filter(0), _arc_filter(0) { }
1.319 +
1.320 + void setNodeFilterMap(NodeFilterMap& node_filter) {
1.321 + _node_filter = &node_filter;
1.322 + }
1.323 + void setArcFilterMap(ArcFilterMap& arc_filter) {
1.324 + _arc_filter = &arc_filter;
1.325 + }
1.326 +
1.327 + public:
1.328 +
1.329 + typedef typename Parent::Node Node;
1.330 + typedef typename Parent::Arc Arc;
1.331 +
1.332 + void first(Node& i) const {
1.333 + Parent::first(i);
1.334 + while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
1.335 + }
1.336 +
1.337 + void first(Arc& i) const {
1.338 + Parent::first(i);
1.339 + while (i != INVALID && (!(*_arc_filter)[i]
1.340 + || !(*_node_filter)[Parent::source(i)]
1.341 + || !(*_node_filter)[Parent::target(i)])) Parent::next(i);
1.342 + }
1.343 +
1.344 + void firstIn(Arc& i, const Node& n) const {
1.345 + Parent::firstIn(i, n);
1.346 + while (i != INVALID && (!(*_arc_filter)[i]
1.347 + || !(*_node_filter)[Parent::source(i)])) Parent::nextIn(i);
1.348 + }
1.349 +
1.350 + void firstOut(Arc& i, const Node& n) const {
1.351 + Parent::firstOut(i, n);
1.352 + while (i != INVALID && (!(*_arc_filter)[i]
1.353 + || !(*_node_filter)[Parent::target(i)])) Parent::nextOut(i);
1.354 + }
1.355 +
1.356 + void next(Node& i) const {
1.357 + Parent::next(i);
1.358 + while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
1.359 + }
1.360 +
1.361 + void next(Arc& i) const {
1.362 + Parent::next(i);
1.363 + while (i != INVALID && (!(*_arc_filter)[i]
1.364 + || !(*_node_filter)[Parent::source(i)]
1.365 + || !(*_node_filter)[Parent::target(i)])) Parent::next(i);
1.366 + }
1.367 +
1.368 + void nextIn(Arc& i) const {
1.369 + Parent::nextIn(i);
1.370 + while (i != INVALID && (!(*_arc_filter)[i]
1.371 + || !(*_node_filter)[Parent::source(i)])) Parent::nextIn(i);
1.372 + }
1.373 +
1.374 + void nextOut(Arc& i) const {
1.375 + Parent::nextOut(i);
1.376 + while (i != INVALID && (!(*_arc_filter)[i]
1.377 + || !(*_node_filter)[Parent::target(i)])) Parent::nextOut(i);
1.378 + }
1.379 +
1.380 + ///\e
1.381 +
1.382 + /// This function hides \c n in the digraph, i.e. the iteration
1.383 + /// jumps over it. This is done by simply setting the value of \c n
1.384 + /// to be false in the corresponding node-map.
1.385 + void hide(const Node& n) const { _node_filter->set(n, false); }
1.386 +
1.387 + ///\e
1.388 +
1.389 + /// This function hides \c a in the digraph, i.e. the iteration
1.390 + /// jumps over it. This is done by simply setting the value of \c a
1.391 + /// to be false in the corresponding arc-map.
1.392 + void hide(const Arc& a) const { _arc_filter->set(a, false); }
1.393 +
1.394 + ///\e
1.395 +
1.396 + /// The value of \c n is set to be true in the node-map which stores
1.397 + /// hide information. If \c n was hidden previuosly, then it is shown
1.398 + /// again
1.399 + void unHide(const Node& n) const { _node_filter->set(n, true); }
1.400 +
1.401 + ///\e
1.402 +
1.403 + /// The value of \c a is set to be true in the arc-map which stores
1.404 + /// hide information. If \c a was hidden previuosly, then it is shown
1.405 + /// again
1.406 + void unHide(const Arc& a) const { _arc_filter->set(a, true); }
1.407 +
1.408 + /// Returns true if \c n is hidden.
1.409 +
1.410 + ///\e
1.411 + ///
1.412 + bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
1.413 +
1.414 + /// Returns true if \c a is hidden.
1.415 +
1.416 + ///\e
1.417 + ///
1.418 + bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }
1.419 +
1.420 + typedef False NodeNumTag;
1.421 + typedef False EdgeNumTag;
1.422 +
1.423 + typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
1.424 + Arc findArc(const Node& source, const Node& target,
1.425 + const Arc& prev = INVALID) {
1.426 + if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
1.427 + return INVALID;
1.428 + }
1.429 + Arc arc = Parent::findArc(source, target, prev);
1.430 + while (arc != INVALID && !(*_arc_filter)[arc]) {
1.431 + arc = Parent::findArc(source, target, arc);
1.432 + }
1.433 + return arc;
1.434 + }
1.435 +
1.436 + template <typename _Value>
1.437 + class NodeMap : public SubMapExtender<Adaptor,
1.438 + typename Parent::template NodeMap<_Value> > {
1.439 + public:
1.440 + typedef _Value Value;
1.441 + typedef SubMapExtender<Adaptor, typename Parent::
1.442 + template NodeMap<Value> > MapParent;
1.443 +
1.444 + NodeMap(const Adaptor& adaptor)
1.445 + : MapParent(adaptor) {}
1.446 + NodeMap(const Adaptor& adaptor, const Value& value)
1.447 + : MapParent(adaptor, value) {}
1.448 +
1.449 + private:
1.450 + NodeMap& operator=(const NodeMap& cmap) {
1.451 + return operator=<NodeMap>(cmap);
1.452 + }
1.453 +
1.454 + template <typename CMap>
1.455 + NodeMap& operator=(const CMap& cmap) {
1.456 + MapParent::operator=(cmap);
1.457 + return *this;
1.458 + }
1.459 + };
1.460 +
1.461 + template <typename _Value>
1.462 + class ArcMap : public SubMapExtender<Adaptor,
1.463 + typename Parent::template ArcMap<_Value> > {
1.464 + public:
1.465 + typedef _Value Value;
1.466 + typedef SubMapExtender<Adaptor, typename Parent::
1.467 + template ArcMap<Value> > MapParent;
1.468 +
1.469 + ArcMap(const Adaptor& adaptor)
1.470 + : MapParent(adaptor) {}
1.471 + ArcMap(const Adaptor& adaptor, const Value& value)
1.472 + : MapParent(adaptor, value) {}
1.473 +
1.474 + private:
1.475 + ArcMap& operator=(const ArcMap& cmap) {
1.476 + return operator=<ArcMap>(cmap);
1.477 + }
1.478 +
1.479 + template <typename CMap>
1.480 + ArcMap& operator=(const CMap& cmap) {
1.481 + MapParent::operator=(cmap);
1.482 + return *this;
1.483 + }
1.484 + };
1.485 +
1.486 + };
1.487 +
1.488 + template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>
1.489 + class SubDigraphAdaptorBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>
1.490 + : public DigraphAdaptorBase<_Digraph> {
1.491 + public:
1.492 + typedef _Digraph Digraph;
1.493 + typedef _NodeFilterMap NodeFilterMap;
1.494 + typedef _ArcFilterMap ArcFilterMap;
1.495 +
1.496 + typedef SubDigraphAdaptorBase Adaptor;
1.497 + typedef DigraphAdaptorBase<Digraph> Parent;
1.498 + protected:
1.499 + NodeFilterMap* _node_filter;
1.500 + ArcFilterMap* _arc_filter;
1.501 + SubDigraphAdaptorBase()
1.502 + : Parent(), _node_filter(0), _arc_filter(0) { }
1.503 +
1.504 + void setNodeFilterMap(NodeFilterMap& node_filter) {
1.505 + _node_filter = &node_filter;
1.506 + }
1.507 + void setArcFilterMap(ArcFilterMap& arc_filter) {
1.508 + _arc_filter = &arc_filter;
1.509 + }
1.510 +
1.511 + public:
1.512 +
1.513 + typedef typename Parent::Node Node;
1.514 + typedef typename Parent::Arc Arc;
1.515 +
1.516 + void first(Node& i) const {
1.517 + Parent::first(i);
1.518 + while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
1.519 + }
1.520 +
1.521 + void first(Arc& i) const {
1.522 + Parent::first(i);
1.523 + while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
1.524 + }
1.525 +
1.526 + void firstIn(Arc& i, const Node& n) const {
1.527 + Parent::firstIn(i, n);
1.528 + while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
1.529 + }
1.530 +
1.531 + void firstOut(Arc& i, const Node& n) const {
1.532 + Parent::firstOut(i, n);
1.533 + while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
1.534 + }
1.535 +
1.536 + void next(Node& i) const {
1.537 + Parent::next(i);
1.538 + while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
1.539 + }
1.540 + void next(Arc& i) const {
1.541 + Parent::next(i);
1.542 + while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
1.543 + }
1.544 + void nextIn(Arc& i) const {
1.545 + Parent::nextIn(i);
1.546 + while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
1.547 + }
1.548 +
1.549 + void nextOut(Arc& i) const {
1.550 + Parent::nextOut(i);
1.551 + while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
1.552 + }
1.553 +
1.554 + ///\e
1.555 +
1.556 + /// This function hides \c n in the digraph, i.e. the iteration
1.557 + /// jumps over it. This is done by simply setting the value of \c n
1.558 + /// to be false in the corresponding node-map.
1.559 + void hide(const Node& n) const { _node_filter->set(n, false); }
1.560 +
1.561 + ///\e
1.562 +
1.563 + /// This function hides \c e in the digraph, i.e. the iteration
1.564 + /// jumps over it. This is done by simply setting the value of \c e
1.565 + /// to be false in the corresponding arc-map.
1.566 + void hide(const Arc& e) const { _arc_filter->set(e, false); }
1.567 +
1.568 + ///\e
1.569 +
1.570 + /// The value of \c n is set to be true in the node-map which stores
1.571 + /// hide information. If \c n was hidden previuosly, then it is shown
1.572 + /// again
1.573 + void unHide(const Node& n) const { _node_filter->set(n, true); }
1.574 +
1.575 + ///\e
1.576 +
1.577 + /// The value of \c e is set to be true in the arc-map which stores
1.578 + /// hide information. If \c e was hidden previuosly, then it is shown
1.579 + /// again
1.580 + void unHide(const Arc& e) const { _arc_filter->set(e, true); }
1.581 +
1.582 + /// Returns true if \c n is hidden.
1.583 +
1.584 + ///\e
1.585 + ///
1.586 + bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
1.587 +
1.588 + /// Returns true if \c n is hidden.
1.589 +
1.590 + ///\e
1.591 + ///
1.592 + bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }
1.593 +
1.594 + typedef False NodeNumTag;
1.595 + typedef False EdgeNumTag;
1.596 +
1.597 + typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
1.598 + Arc findArc(const Node& source, const Node& target,
1.599 + const Arc& prev = INVALID) {
1.600 + if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
1.601 + return INVALID;
1.602 + }
1.603 + Arc arc = Parent::findArc(source, target, prev);
1.604 + while (arc != INVALID && !(*_arc_filter)[arc]) {
1.605 + arc = Parent::findArc(source, target, arc);
1.606 + }
1.607 + return arc;
1.608 + }
1.609 +
1.610 + template <typename _Value>
1.611 + class NodeMap : public SubMapExtender<Adaptor,
1.612 + typename Parent::template NodeMap<_Value> > {
1.613 + public:
1.614 + typedef _Value Value;
1.615 + typedef SubMapExtender<Adaptor, typename Parent::
1.616 + template NodeMap<Value> > MapParent;
1.617 +
1.618 + NodeMap(const Adaptor& adaptor)
1.619 + : MapParent(adaptor) {}
1.620 + NodeMap(const Adaptor& adaptor, const Value& value)
1.621 + : MapParent(adaptor, value) {}
1.622 +
1.623 + private:
1.624 + NodeMap& operator=(const NodeMap& cmap) {
1.625 + return operator=<NodeMap>(cmap);
1.626 + }
1.627 +
1.628 + template <typename CMap>
1.629 + NodeMap& operator=(const CMap& cmap) {
1.630 + MapParent::operator=(cmap);
1.631 + return *this;
1.632 + }
1.633 + };
1.634 +
1.635 + template <typename _Value>
1.636 + class ArcMap : public SubMapExtender<Adaptor,
1.637 + typename Parent::template ArcMap<_Value> > {
1.638 + public:
1.639 + typedef _Value Value;
1.640 + typedef SubMapExtender<Adaptor, typename Parent::
1.641 + template ArcMap<Value> > MapParent;
1.642 +
1.643 + ArcMap(const Adaptor& adaptor)
1.644 + : MapParent(adaptor) {}
1.645 + ArcMap(const Adaptor& adaptor, const Value& value)
1.646 + : MapParent(adaptor, value) {}
1.647 +
1.648 + private:
1.649 + ArcMap& operator=(const ArcMap& cmap) {
1.650 + return operator=<ArcMap>(cmap);
1.651 + }
1.652 +
1.653 + template <typename CMap>
1.654 + ArcMap& operator=(const CMap& cmap) {
1.655 + MapParent::operator=(cmap);
1.656 + return *this;
1.657 + }
1.658 + };
1.659 +
1.660 + };
1.661 +
1.662 + /// \ingroup graph_adaptors
1.663 + ///
1.664 + /// \brief A digraph adaptor for hiding nodes and arcs from a digraph.
1.665 + ///
1.666 + /// SubDigraphAdaptor shows the digraph with filtered node-set and
1.667 + /// arc-set. If the \c checked parameter is true then it filters the arcset
1.668 + /// to do not get invalid arcs without source or target.
1.669 + /// Let \f$ G=(V, A) \f$ be a directed digraph
1.670 + /// and suppose that the digraph instance \c g of type ListDigraph
1.671 + /// implements \f$ G \f$.
1.672 + /// Let moreover \f$ b_V \f$ and \f$ b_A \f$ be bool-valued functions resp.
1.673 + /// on the node-set and arc-set.
1.674 + /// SubDigraphAdaptor<...>::NodeIt iterates
1.675 + /// on the node-set \f$ \{v\in V : b_V(v)=true\} \f$ and
1.676 + /// SubDigraphAdaptor<...>::ArcIt iterates
1.677 + /// on the arc-set \f$ \{e\in A : b_A(e)=true\} \f$. Similarly,
1.678 + /// SubDigraphAdaptor<...>::OutArcIt and
1.679 + /// SubDigraphAdaptor<...>::InArcIt iterates
1.680 + /// only on arcs leaving and entering a specific node which have true value.
1.681 + ///
1.682 + /// If the \c checked template parameter is false then we have to
1.683 + /// note that the node-iterator cares only the filter on the
1.684 + /// node-set, and the arc-iterator cares only the filter on the
1.685 + /// arc-set. This way the arc-map should filter all arcs which's
1.686 + /// source or target is filtered by the node-filter.
1.687 + ///\code
1.688 + /// typedef ListDigraph Digraph;
1.689 + /// DIGRAPH_TYPEDEFS(Digraph);
1.690 + /// Digraph g;
1.691 + /// Node u=g.addNode(); //node of id 0
1.692 + /// Node v=g.addNode(); //node of id 1
1.693 + /// Arc a=g.addArc(u, v); //arc of id 0
1.694 + /// Arc f=g.addArc(v, u); //arc of id 1
1.695 + /// BoolNodeMap nm(g, true);
1.696 + /// nm.set(u, false);
1.697 + /// BoolArcMap am(g, true);
1.698 + /// am.set(a, false);
1.699 + /// typedef SubDigraphAdaptor<Digraph, BoolNodeMap, BoolArcMap> SubGA;
1.700 + /// SubGA ga(g, nm, am);
1.701 + /// for (SubGA::NodeIt n(ga); n!=INVALID; ++n)
1.702 + /// std::cout << g.id(n) << std::endl;
1.703 + /// std::cout << ":-)" << std::endl;
1.704 + /// for (SubGA::ArcIt a(ga); a!=INVALID; ++a)
1.705 + /// std::cout << g.id(a) << std::endl;
1.706 + ///\endcode
1.707 + /// The output of the above code is the following.
1.708 + ///\code
1.709 + /// 1
1.710 + /// :-)
1.711 + /// 1
1.712 + ///\endcode
1.713 + /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
1.714 + /// \c Digraph::Node that is why \c g.id(n) can be applied.
1.715 + ///
1.716 + /// For other examples see also the documentation of
1.717 + /// NodeSubDigraphAdaptor and ArcSubDigraphAdaptor.
1.718 + template<typename _Digraph,
1.719 + typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
1.720 + typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,
1.721 + bool checked = true>
1.722 + class SubDigraphAdaptor :
1.723 + public DigraphAdaptorExtender<
1.724 + SubDigraphAdaptorBase<_Digraph, _NodeFilterMap, _ArcFilterMap, checked> > {
1.725 + public:
1.726 + typedef _Digraph Digraph;
1.727 + typedef _NodeFilterMap NodeFilterMap;
1.728 + typedef _ArcFilterMap ArcFilterMap;
1.729 +
1.730 + typedef DigraphAdaptorExtender<
1.731 + SubDigraphAdaptorBase<Digraph, NodeFilterMap, ArcFilterMap, checked> >
1.732 + Parent;
1.733 +
1.734 + protected:
1.735 + SubDigraphAdaptor() { }
1.736 + public:
1.737 +
1.738 + SubDigraphAdaptor(Digraph& digraph, NodeFilterMap& node_filter,
1.739 + ArcFilterMap& arc_filter) {
1.740 + setDigraph(digraph);
1.741 + setNodeFilterMap(node_filter);
1.742 + setArcFilterMap(arc_filter);
1.743 + }
1.744 +
1.745 + };
1.746 +
1.747 + /// \brief Just gives back a sub digraph adaptor
1.748 + ///
1.749 + /// Just gives back a sub digraph adaptor
1.750 + template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
1.751 + SubDigraphAdaptor<const Digraph, NodeFilterMap, ArcFilterMap>
1.752 + subDigraphAdaptor(const Digraph& digraph,
1.753 + NodeFilterMap& nfm, ArcFilterMap& afm) {
1.754 + return SubDigraphAdaptor<const Digraph, NodeFilterMap, ArcFilterMap>
1.755 + (digraph, nfm, afm);
1.756 + }
1.757 +
1.758 + template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
1.759 + SubDigraphAdaptor<const Digraph, const NodeFilterMap, ArcFilterMap>
1.760 + subDigraphAdaptor(const Digraph& digraph,
1.761 + NodeFilterMap& nfm, ArcFilterMap& afm) {
1.762 + return SubDigraphAdaptor<const Digraph, const NodeFilterMap, ArcFilterMap>
1.763 + (digraph, nfm, afm);
1.764 + }
1.765 +
1.766 + template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
1.767 + SubDigraphAdaptor<const Digraph, NodeFilterMap, const ArcFilterMap>
1.768 + subDigraphAdaptor(const Digraph& digraph,
1.769 + NodeFilterMap& nfm, ArcFilterMap& afm) {
1.770 + return SubDigraphAdaptor<const Digraph, NodeFilterMap, const ArcFilterMap>
1.771 + (digraph, nfm, afm);
1.772 + }
1.773 +
1.774 + template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
1.775 + SubDigraphAdaptor<const Digraph, const NodeFilterMap, const ArcFilterMap>
1.776 + subDigraphAdaptor(const Digraph& digraph,
1.777 + NodeFilterMap& nfm, ArcFilterMap& afm) {
1.778 + return SubDigraphAdaptor<const Digraph, const NodeFilterMap,
1.779 + const ArcFilterMap>(digraph, nfm, afm);
1.780 + }
1.781 +
1.782 +
1.783 +
1.784 + ///\ingroup graph_adaptors
1.785 + ///
1.786 + ///\brief An adaptor for hiding nodes from a digraph.
1.787 + ///
1.788 + ///An adaptor for hiding nodes from a digraph. This adaptor
1.789 + ///specializes SubDigraphAdaptor in the way that only the node-set
1.790 + ///can be filtered. In usual case the checked parameter is true, we
1.791 + ///get the induced subgraph. But if the checked parameter is false
1.792 + ///then we can filter only isolated nodes.
1.793 + template<typename _Digraph,
1.794 + typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
1.795 + bool checked = true>
1.796 + class NodeSubDigraphAdaptor :
1.797 + public SubDigraphAdaptor<_Digraph, _NodeFilterMap,
1.798 + ConstMap<typename _Digraph::Arc, bool>, checked> {
1.799 + public:
1.800 +
1.801 + typedef _Digraph Digraph;
1.802 + typedef _NodeFilterMap NodeFilterMap;
1.803 +
1.804 + typedef SubDigraphAdaptor<Digraph, NodeFilterMap,
1.805 + ConstMap<typename Digraph::Arc, bool>, checked>
1.806 + Parent;
1.807 +
1.808 + protected:
1.809 + ConstMap<typename Digraph::Arc, bool> const_true_map;
1.810 +
1.811 + NodeSubDigraphAdaptor() : const_true_map(true) {
1.812 + Parent::setArcFilterMap(const_true_map);
1.813 + }
1.814 +
1.815 + public:
1.816 +
1.817 + NodeSubDigraphAdaptor(Digraph& _digraph, NodeFilterMap& node_filter) :
1.818 + Parent(), const_true_map(true) {
1.819 + Parent::setDigraph(_digraph);
1.820 + Parent::setNodeFilterMap(node_filter);
1.821 + Parent::setArcFilterMap(const_true_map);
1.822 + }
1.823 +
1.824 + };
1.825 +
1.826 +
1.827 + /// \brief Just gives back a \c NodeSubDigraphAdaptor
1.828 + ///
1.829 + /// Just gives back a \c NodeSubDigraphAdaptor
1.830 + template<typename Digraph, typename NodeFilterMap>
1.831 + NodeSubDigraphAdaptor<const Digraph, NodeFilterMap>
1.832 + nodeSubDigraphAdaptor(const Digraph& digraph, NodeFilterMap& nfm) {
1.833 + return NodeSubDigraphAdaptor<const Digraph, NodeFilterMap>(digraph, nfm);
1.834 + }
1.835 +
1.836 + template<typename Digraph, typename NodeFilterMap>
1.837 + NodeSubDigraphAdaptor<const Digraph, const NodeFilterMap>
1.838 + nodeSubDigraphAdaptor(const Digraph& digraph, const NodeFilterMap& nfm) {
1.839 + return NodeSubDigraphAdaptor<const Digraph, const NodeFilterMap>
1.840 + (digraph, nfm);
1.841 + }
1.842 +
1.843 + ///\ingroup graph_adaptors
1.844 + ///
1.845 + ///\brief An adaptor for hiding arcs from a digraph.
1.846 + ///
1.847 + ///An adaptor for hiding arcs from a digraph. This adaptor
1.848 + ///specializes SubDigraphAdaptor in the way that only the arc-set
1.849 + ///can be filtered. The usefulness of this adaptor is demonstrated
1.850 + ///in the problem of searching a maximum number of arc-disjoint
1.851 + ///shortest paths between two nodes \c s and \c t. Shortest here
1.852 + ///means being shortest w.r.t. non-negative arc-lengths. Note that
1.853 + ///the comprehension of the presented solution need's some
1.854 + ///elementary knowlarc from combinatorial optimization.
1.855 + ///
1.856 + ///If a single shortest path is to be searched between \c s and \c
1.857 + ///t, then this can be done easily by applying the Dijkstra
1.858 + ///algorithm. What happens, if a maximum number of arc-disjoint
1.859 + ///shortest paths is to be computed. It can be proved that an arc
1.860 + ///can be in a shortest path if and only if it is tight with respect
1.861 + ///to the potential function computed by Dijkstra. Moreover, any
1.862 + ///path containing only such arcs is a shortest one. Thus we have
1.863 + ///to compute a maximum number of arc-disjoint paths between \c s
1.864 + ///and \c t in the digraph which has arc-set all the tight arcs. The
1.865 + ///computation will be demonstrated on the following digraph, which
1.866 + ///is read from the dimacs file \c sub_digraph_adaptor_demo.dim.
1.867 + ///The full source code is available in \ref
1.868 + ///sub_digraph_adaptor_demo.cc. If you are interested in more demo
1.869 + ///programs, you can use \ref dim_to_dot.cc to generate .dot files
1.870 + ///from dimacs files. The .dot file of the following figure was
1.871 + ///generated by the demo program \ref dim_to_dot.cc.
1.872 + ///
1.873 + ///\dot
1.874 + ///didigraph lemon_dot_example {
1.875 + ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
1.876 + ///n0 [ label="0 (s)" ];
1.877 + ///n1 [ label="1" ];
1.878 + ///n2 [ label="2" ];
1.879 + ///n3 [ label="3" ];
1.880 + ///n4 [ label="4" ];
1.881 + ///n5 [ label="5" ];
1.882 + ///n6 [ label="6 (t)" ];
1.883 + ///arc [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
1.884 + ///n5 -> n6 [ label="9, length:4" ];
1.885 + ///n4 -> n6 [ label="8, length:2" ];
1.886 + ///n3 -> n5 [ label="7, length:1" ];
1.887 + ///n2 -> n5 [ label="6, length:3" ];
1.888 + ///n2 -> n6 [ label="5, length:5" ];
1.889 + ///n2 -> n4 [ label="4, length:2" ];
1.890 + ///n1 -> n4 [ label="3, length:3" ];
1.891 + ///n0 -> n3 [ label="2, length:1" ];
1.892 + ///n0 -> n2 [ label="1, length:2" ];
1.893 + ///n0 -> n1 [ label="0, length:3" ];
1.894 + ///}
1.895 + ///\enddot
1.896 + ///
1.897 + ///\code
1.898 + ///Digraph g;
1.899 + ///Node s, t;
1.900 + ///LengthMap length(g);
1.901 + ///
1.902 + ///readDimacs(std::cin, g, length, s, t);
1.903 + ///
1.904 + ///cout << "arcs with lengths (of form id, source--length->target): " << endl;
1.905 + ///for(ArcIt e(g); e!=INVALID; ++e)
1.906 + /// cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
1.907 + /// << length[e] << "->" << g.id(g.target(e)) << endl;
1.908 + ///
1.909 + ///cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
1.910 + ///\endcode
1.911 + ///Next, the potential function is computed with Dijkstra.
1.912 + ///\code
1.913 + ///typedef Dijkstra<Digraph, LengthMap> Dijkstra;
1.914 + ///Dijkstra dijkstra(g, length);
1.915 + ///dijkstra.run(s);
1.916 + ///\endcode
1.917 + ///Next, we consrtruct a map which filters the arc-set to the tight arcs.
1.918 + ///\code
1.919 + ///typedef TightArcFilterMap<Digraph, const Dijkstra::DistMap, LengthMap>
1.920 + /// TightArcFilter;
1.921 + ///TightArcFilter tight_arc_filter(g, dijkstra.distMap(), length);
1.922 + ///
1.923 + ///typedef ArcSubDigraphAdaptor<Digraph, TightArcFilter> SubGA;
1.924 + ///SubGA ga(g, tight_arc_filter);
1.925 + ///\endcode
1.926 + ///Then, the maximum nimber of arc-disjoint \c s-\c t paths are computed
1.927 + ///with a max flow algorithm Preflow.
1.928 + ///\code
1.929 + ///ConstMap<Arc, int> const_1_map(1);
1.930 + ///Digraph::ArcMap<int> flow(g, 0);
1.931 + ///
1.932 + ///Preflow<SubGA, ConstMap<Arc, int>, Digraph::ArcMap<int> >
1.933 + /// preflow(ga, const_1_map, s, t);
1.934 + ///preflow.run();
1.935 + ///\endcode
1.936 + ///Last, the output is:
1.937 + ///\code
1.938 + ///cout << "maximum number of arc-disjoint shortest path: "
1.939 + /// << preflow.flowValue() << endl;
1.940 + ///cout << "arcs of the maximum number of arc-disjoint shortest s-t paths: "
1.941 + /// << endl;
1.942 + ///for(ArcIt e(g); e!=INVALID; ++e)
1.943 + /// if (preflow.flow(e))
1.944 + /// cout << " " << g.id(g.source(e)) << "--"
1.945 + /// << length[e] << "->" << g.id(g.target(e)) << endl;
1.946 + ///\endcode
1.947 + ///The program has the following (expected :-)) output:
1.948 + ///\code
1.949 + ///arcs with lengths (of form id, source--length->target):
1.950 + /// 9, 5--4->6
1.951 + /// 8, 4--2->6
1.952 + /// 7, 3--1->5
1.953 + /// 6, 2--3->5
1.954 + /// 5, 2--5->6
1.955 + /// 4, 2--2->4
1.956 + /// 3, 1--3->4
1.957 + /// 2, 0--1->3
1.958 + /// 1, 0--2->2
1.959 + /// 0, 0--3->1
1.960 + ///s: 0 t: 6
1.961 + ///maximum number of arc-disjoint shortest path: 2
1.962 + ///arcs of the maximum number of arc-disjoint shortest s-t paths:
1.963 + /// 9, 5--4->6
1.964 + /// 8, 4--2->6
1.965 + /// 7, 3--1->5
1.966 + /// 4, 2--2->4
1.967 + /// 2, 0--1->3
1.968 + /// 1, 0--2->2
1.969 + ///\endcode
1.970 + template<typename _Digraph, typename _ArcFilterMap>
1.971 + class ArcSubDigraphAdaptor :
1.972 + public SubDigraphAdaptor<_Digraph, ConstMap<typename _Digraph::Node, bool>,
1.973 + _ArcFilterMap, false> {
1.974 + public:
1.975 + typedef _Digraph Digraph;
1.976 + typedef _ArcFilterMap ArcFilterMap;
1.977 +
1.978 + typedef SubDigraphAdaptor<Digraph, ConstMap<typename Digraph::Node, bool>,
1.979 + ArcFilterMap, false> Parent;
1.980 + protected:
1.981 + ConstMap<typename Digraph::Node, bool> const_true_map;
1.982 +
1.983 + ArcSubDigraphAdaptor() : const_true_map(true) {
1.984 + Parent::setNodeFilterMap(const_true_map);
1.985 + }
1.986 +
1.987 + public:
1.988 +
1.989 + ArcSubDigraphAdaptor(Digraph& digraph, ArcFilterMap& arc_filter)
1.990 + : Parent(), const_true_map(true) {
1.991 + Parent::setDigraph(digraph);
1.992 + Parent::setNodeFilterMap(const_true_map);
1.993 + Parent::setArcFilterMap(arc_filter);
1.994 + }
1.995 +
1.996 + };
1.997 +
1.998 + /// \brief Just gives back an arc sub digraph adaptor
1.999 + ///
1.1000 + /// Just gives back an arc sub digraph adaptor
1.1001 + template<typename Digraph, typename ArcFilterMap>
1.1002 + ArcSubDigraphAdaptor<const Digraph, ArcFilterMap>
1.1003 + arcSubDigraphAdaptor(const Digraph& digraph, ArcFilterMap& afm) {
1.1004 + return ArcSubDigraphAdaptor<const Digraph, ArcFilterMap>(digraph, afm);
1.1005 + }
1.1006 +
1.1007 + template<typename Digraph, typename ArcFilterMap>
1.1008 + ArcSubDigraphAdaptor<const Digraph, const ArcFilterMap>
1.1009 + arcSubDigraphAdaptor(const Digraph& digraph, const ArcFilterMap& afm) {
1.1010 + return ArcSubDigraphAdaptor<const Digraph, const ArcFilterMap>
1.1011 + (digraph, afm);
1.1012 + }
1.1013 +
1.1014 + template <typename _Digraph>
1.1015 + class UndirDigraphAdaptorBase {
1.1016 + public:
1.1017 + typedef _Digraph Digraph;
1.1018 + typedef UndirDigraphAdaptorBase Adaptor;
1.1019 +
1.1020 + typedef True UndirectedTag;
1.1021 +
1.1022 + typedef typename Digraph::Arc Edge;
1.1023 + typedef typename Digraph::Node Node;
1.1024 +
1.1025 + class Arc : public Edge {
1.1026 + friend class UndirDigraphAdaptorBase;
1.1027 + protected:
1.1028 + bool _forward;
1.1029 +
1.1030 + Arc(const Edge& edge, bool forward) :
1.1031 + Edge(edge), _forward(forward) {}
1.1032 +
1.1033 + public:
1.1034 + Arc() {}
1.1035 +
1.1036 + Arc(Invalid) : Edge(INVALID), _forward(true) {}
1.1037 +
1.1038 + bool operator==(const Arc &other) const {
1.1039 + return _forward == other._forward &&
1.1040 + static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
1.1041 + }
1.1042 + bool operator!=(const Arc &other) const {
1.1043 + return _forward != other._forward ||
1.1044 + static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
1.1045 + }
1.1046 + bool operator<(const Arc &other) const {
1.1047 + return _forward < other._forward ||
1.1048 + (_forward == other._forward &&
1.1049 + static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
1.1050 + }
1.1051 + };
1.1052 +
1.1053 +
1.1054 +
1.1055 + void first(Node& n) const {
1.1056 + _digraph->first(n);
1.1057 + }
1.1058 +
1.1059 + void next(Node& n) const {
1.1060 + _digraph->next(n);
1.1061 + }
1.1062 +
1.1063 + void first(Arc& a) const {
1.1064 + _digraph->first(a);
1.1065 + a._forward = true;
1.1066 + }
1.1067 +
1.1068 + void next(Arc& a) const {
1.1069 + if (a._forward) {
1.1070 + a._forward = false;
1.1071 + } else {
1.1072 + _digraph->next(a);
1.1073 + a._forward = true;
1.1074 + }
1.1075 + }
1.1076 +
1.1077 + void first(Edge& e) const {
1.1078 + _digraph->first(e);
1.1079 + }
1.1080 +
1.1081 + void next(Edge& e) const {
1.1082 + _digraph->next(e);
1.1083 + }
1.1084 +
1.1085 + void firstOut(Arc& a, const Node& n) const {
1.1086 + _digraph->firstIn(a, n);
1.1087 + if( static_cast<const Edge&>(a) != INVALID ) {
1.1088 + a._forward = false;
1.1089 + } else {
1.1090 + _digraph->firstOut(a, n);
1.1091 + a._forward = true;
1.1092 + }
1.1093 + }
1.1094 + void nextOut(Arc &a) const {
1.1095 + if (!a._forward) {
1.1096 + Node n = _digraph->target(a);
1.1097 + _digraph->nextIn(a);
1.1098 + if (static_cast<const Edge&>(a) == INVALID ) {
1.1099 + _digraph->firstOut(a, n);
1.1100 + a._forward = true;
1.1101 + }
1.1102 + }
1.1103 + else {
1.1104 + _digraph->nextOut(a);
1.1105 + }
1.1106 + }
1.1107 +
1.1108 + void firstIn(Arc &a, const Node &n) const {
1.1109 + _digraph->firstOut(a, n);
1.1110 + if (static_cast<const Edge&>(a) != INVALID ) {
1.1111 + a._forward = false;
1.1112 + } else {
1.1113 + _digraph->firstIn(a, n);
1.1114 + a._forward = true;
1.1115 + }
1.1116 + }
1.1117 + void nextIn(Arc &a) const {
1.1118 + if (!a._forward) {
1.1119 + Node n = _digraph->source(a);
1.1120 + _digraph->nextOut(a);
1.1121 + if( static_cast<const Edge&>(a) == INVALID ) {
1.1122 + _digraph->firstIn(a, n);
1.1123 + a._forward = true;
1.1124 + }
1.1125 + }
1.1126 + else {
1.1127 + _digraph->nextIn(a);
1.1128 + }
1.1129 + }
1.1130 +
1.1131 + void firstInc(Edge &e, bool &d, const Node &n) const {
1.1132 + d = true;
1.1133 + _digraph->firstOut(e, n);
1.1134 + if (e != INVALID) return;
1.1135 + d = false;
1.1136 + _digraph->firstIn(e, n);
1.1137 + }
1.1138 +
1.1139 + void nextInc(Edge &e, bool &d) const {
1.1140 + if (d) {
1.1141 + Node s = _digraph->source(e);
1.1142 + _digraph->nextOut(e);
1.1143 + if (e != INVALID) return;
1.1144 + d = false;
1.1145 + _digraph->firstIn(e, s);
1.1146 + } else {
1.1147 + _digraph->nextIn(e);
1.1148 + }
1.1149 + }
1.1150 +
1.1151 + Node u(const Edge& e) const {
1.1152 + return _digraph->source(e);
1.1153 + }
1.1154 +
1.1155 + Node v(const Edge& e) const {
1.1156 + return _digraph->target(e);
1.1157 + }
1.1158 +
1.1159 + Node source(const Arc &a) const {
1.1160 + return a._forward ? _digraph->source(a) : _digraph->target(a);
1.1161 + }
1.1162 +
1.1163 + Node target(const Arc &a) const {
1.1164 + return a._forward ? _digraph->target(a) : _digraph->source(a);
1.1165 + }
1.1166 +
1.1167 + static Arc direct(const Edge &e, bool d) {
1.1168 + return Arc(e, d);
1.1169 + }
1.1170 + Arc direct(const Edge &e, const Node& n) const {
1.1171 + return Arc(e, _digraph->source(e) == n);
1.1172 + }
1.1173 +
1.1174 + static bool direction(const Arc &a) { return a._forward; }
1.1175 +
1.1176 + Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
1.1177 + Arc arcFromId(int ix) const {
1.1178 + return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1));
1.1179 + }
1.1180 + Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); }
1.1181 +
1.1182 + int id(const Node &n) const { return _digraph->id(n); }
1.1183 + int id(const Arc &a) const {
1.1184 + return (_digraph->id(a) << 1) | (a._forward ? 1 : 0);
1.1185 + }
1.1186 + int id(const Edge &e) const { return _digraph->id(e); }
1.1187 +
1.1188 + int maxNodeId() const { return _digraph->maxNodeId(); }
1.1189 + int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; }
1.1190 + int maxEdgeId() const { return _digraph->maxArcId(); }
1.1191 +
1.1192 + Node addNode() { return _digraph->addNode(); }
1.1193 + Edge addEdge(const Node& u, const Node& v) {
1.1194 + return _digraph->addArc(u, v);
1.1195 + }
1.1196 +
1.1197 + void erase(const Node& i) { _digraph->erase(i); }
1.1198 + void erase(const Edge& i) { _digraph->erase(i); }
1.1199 +
1.1200 + void clear() { _digraph->clear(); }
1.1201 +
1.1202 + typedef NodeNumTagIndicator<Digraph> NodeNumTag;
1.1203 + int nodeNum() const { return 2 * _digraph->arcNum(); }
1.1204 + typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
1.1205 + int arcNum() const { return 2 * _digraph->arcNum(); }
1.1206 + int edgeNum() const { return _digraph->arcNum(); }
1.1207 +
1.1208 + typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
1.1209 + Arc findArc(Node s, Node t, Arc p = INVALID) const {
1.1210 + if (p == INVALID) {
1.1211 + Edge arc = _digraph->findArc(s, t);
1.1212 + if (arc != INVALID) return direct(arc, true);
1.1213 + arc = _digraph->findArc(t, s);
1.1214 + if (arc != INVALID) return direct(arc, false);
1.1215 + } else if (direction(p)) {
1.1216 + Edge arc = _digraph->findArc(s, t, p);
1.1217 + if (arc != INVALID) return direct(arc, true);
1.1218 + arc = _digraph->findArc(t, s);
1.1219 + if (arc != INVALID) return direct(arc, false);
1.1220 + } else {
1.1221 + Edge arc = _digraph->findArc(t, s, p);
1.1222 + if (arc != INVALID) return direct(arc, false);
1.1223 + }
1.1224 + return INVALID;
1.1225 + }
1.1226 +
1.1227 + Edge findEdge(Node s, Node t, Edge p = INVALID) const {
1.1228 + if (s != t) {
1.1229 + if (p == INVALID) {
1.1230 + Edge arc = _digraph->findArc(s, t);
1.1231 + if (arc != INVALID) return arc;
1.1232 + arc = _digraph->findArc(t, s);
1.1233 + if (arc != INVALID) return arc;
1.1234 + } else if (_digraph->s(p) == s) {
1.1235 + Edge arc = _digraph->findArc(s, t, p);
1.1236 + if (arc != INVALID) return arc;
1.1237 + arc = _digraph->findArc(t, s);
1.1238 + if (arc != INVALID) return arc;
1.1239 + } else {
1.1240 + Edge arc = _digraph->findArc(t, s, p);
1.1241 + if (arc != INVALID) return arc;
1.1242 + }
1.1243 + } else {
1.1244 + return _digraph->findArc(s, t, p);
1.1245 + }
1.1246 + return INVALID;
1.1247 + }
1.1248 +
1.1249 + private:
1.1250 +
1.1251 + template <typename _Value>
1.1252 + class ArcMapBase {
1.1253 + private:
1.1254 +
1.1255 + typedef typename Digraph::template ArcMap<_Value> MapImpl;
1.1256 +
1.1257 + public:
1.1258 +
1.1259 + typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
1.1260 +
1.1261 + typedef _Value Value;
1.1262 + typedef Arc Key;
1.1263 +
1.1264 + ArcMapBase(const Adaptor& adaptor) :
1.1265 + _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
1.1266 +
1.1267 + ArcMapBase(const Adaptor& adaptor, const Value& v)
1.1268 + : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}
1.1269 +
1.1270 + void set(const Arc& a, const Value& v) {
1.1271 + if (direction(a)) {
1.1272 + _forward.set(a, v);
1.1273 + } else {
1.1274 + _backward.set(a, v);
1.1275 + }
1.1276 + }
1.1277 +
1.1278 + typename MapTraits<MapImpl>::ConstReturnValue
1.1279 + operator[](const Arc& a) const {
1.1280 + if (direction(a)) {
1.1281 + return _forward[a];
1.1282 + } else {
1.1283 + return _backward[a];
1.1284 + }
1.1285 + }
1.1286 +
1.1287 + typename MapTraits<MapImpl>::ReturnValue
1.1288 + operator[](const Arc& a) {
1.1289 + if (direction(a)) {
1.1290 + return _forward[a];
1.1291 + } else {
1.1292 + return _backward[a];
1.1293 + }
1.1294 + }
1.1295 +
1.1296 + protected:
1.1297 +
1.1298 + MapImpl _forward, _backward;
1.1299 +
1.1300 + };
1.1301 +
1.1302 + public:
1.1303 +
1.1304 + template <typename _Value>
1.1305 + class NodeMap : public Digraph::template NodeMap<_Value> {
1.1306 + public:
1.1307 +
1.1308 + typedef _Value Value;
1.1309 + typedef typename Digraph::template NodeMap<Value> Parent;
1.1310 +
1.1311 + explicit NodeMap(const Adaptor& adaptor)
1.1312 + : Parent(*adaptor._digraph) {}
1.1313 +
1.1314 + NodeMap(const Adaptor& adaptor, const _Value& value)
1.1315 + : Parent(*adaptor._digraph, value) { }
1.1316 +
1.1317 + private:
1.1318 + NodeMap& operator=(const NodeMap& cmap) {
1.1319 + return operator=<NodeMap>(cmap);
1.1320 + }
1.1321 +
1.1322 + template <typename CMap>
1.1323 + NodeMap& operator=(const CMap& cmap) {
1.1324 + Parent::operator=(cmap);
1.1325 + return *this;
1.1326 + }
1.1327 +
1.1328 + };
1.1329 +
1.1330 + template <typename _Value>
1.1331 + class ArcMap
1.1332 + : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
1.1333 + {
1.1334 + public:
1.1335 + typedef _Value Value;
1.1336 + typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
1.1337 +
1.1338 + ArcMap(const Adaptor& adaptor)
1.1339 + : Parent(adaptor) {}
1.1340 +
1.1341 + ArcMap(const Adaptor& adaptor, const Value& value)
1.1342 + : Parent(adaptor, value) {}
1.1343 +
1.1344 + private:
1.1345 + ArcMap& operator=(const ArcMap& cmap) {
1.1346 + return operator=<ArcMap>(cmap);
1.1347 + }
1.1348 +
1.1349 + template <typename CMap>
1.1350 + ArcMap& operator=(const CMap& cmap) {
1.1351 + Parent::operator=(cmap);
1.1352 + return *this;
1.1353 + }
1.1354 + };
1.1355 +
1.1356 + template <typename _Value>
1.1357 + class EdgeMap : public Digraph::template ArcMap<_Value> {
1.1358 + public:
1.1359 +
1.1360 + typedef _Value Value;
1.1361 + typedef typename Digraph::template ArcMap<Value> Parent;
1.1362 +
1.1363 + explicit EdgeMap(const Adaptor& adaptor)
1.1364 + : Parent(*adaptor._digraph) {}
1.1365 +
1.1366 + EdgeMap(const Adaptor& adaptor, const Value& value)
1.1367 + : Parent(*adaptor._digraph, value) {}
1.1368 +
1.1369 + private:
1.1370 + EdgeMap& operator=(const EdgeMap& cmap) {
1.1371 + return operator=<EdgeMap>(cmap);
1.1372 + }
1.1373 +
1.1374 + template <typename CMap>
1.1375 + EdgeMap& operator=(const CMap& cmap) {
1.1376 + Parent::operator=(cmap);
1.1377 + return *this;
1.1378 + }
1.1379 +
1.1380 + };
1.1381 +
1.1382 + typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
1.1383 + NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
1.1384 +
1.1385 + protected:
1.1386 +
1.1387 + UndirDigraphAdaptorBase() : _digraph(0) {}
1.1388 +
1.1389 + Digraph* _digraph;
1.1390 +
1.1391 + void setDigraph(Digraph& digraph) {
1.1392 + _digraph = &digraph;
1.1393 + }
1.1394 +
1.1395 + };
1.1396 +
1.1397 + ///\ingroup graph_adaptors
1.1398 + ///
1.1399 + /// \brief An graph is made from a directed digraph by an adaptor
1.1400 + ///
1.1401 + /// This adaptor makes an undirected graph from a directed
1.1402 + /// digraph. All arc of the underlying will be showed in the adaptor
1.1403 + /// as an edge. Let's see an informal example about using
1.1404 + /// this adaptor:
1.1405 + ///
1.1406 + /// There is a network of the streets of a town. Of course there are
1.1407 + /// some one-way street in the town hence the network is a directed
1.1408 + /// one. There is a crazy driver who go oppositely in the one-way
1.1409 + /// street without moral sense. Of course he can pass this streets
1.1410 + /// slower than the regular way, in fact his speed is half of the
1.1411 + /// normal speed. How long should he drive to get from a source
1.1412 + /// point to the target? Let see the example code which calculate it:
1.1413 + ///
1.1414 + /// \todo BadCode, SimpleMap does no exists
1.1415 + ///\code
1.1416 + /// typedef UndirDigraphAdaptor<Digraph> Graph;
1.1417 + /// Graph graph(digraph);
1.1418 + ///
1.1419 + /// typedef SimpleMap<LengthMap> FLengthMap;
1.1420 + /// FLengthMap flength(length);
1.1421 + ///
1.1422 + /// typedef ScaleMap<LengthMap> RLengthMap;
1.1423 + /// RLengthMap rlength(length, 2.0);
1.1424 + ///
1.1425 + /// typedef Graph::CombinedArcMap<FLengthMap, RLengthMap > ULengthMap;
1.1426 + /// ULengthMap ulength(flength, rlength);
1.1427 + ///
1.1428 + /// Dijkstra<Graph, ULengthMap> dijkstra(graph, ulength);
1.1429 + /// std::cout << "Driving time : " << dijkstra.run(src, trg) << std::endl;
1.1430 + ///\endcode
1.1431 + ///
1.1432 + /// The combined arc map makes the length map for the undirected
1.1433 + /// graph. It is created from a forward and reverse map. The forward
1.1434 + /// map is created from the original length map with a SimpleMap
1.1435 + /// adaptor which just makes a read-write map from the reference map
1.1436 + /// i.e. it forgets that it can be return reference to values. The
1.1437 + /// reverse map is just the scaled original map with the ScaleMap
1.1438 + /// adaptor. The combination solves that passing the reverse way
1.1439 + /// takes double time than the original. To get the driving time we
1.1440 + /// run the dijkstra algorithm on the graph.
1.1441 + template<typename _Digraph>
1.1442 + class UndirDigraphAdaptor
1.1443 + : public GraphAdaptorExtender<UndirDigraphAdaptorBase<_Digraph> > {
1.1444 + public:
1.1445 + typedef _Digraph Digraph;
1.1446 + typedef GraphAdaptorExtender<UndirDigraphAdaptorBase<Digraph> > Parent;
1.1447 + protected:
1.1448 + UndirDigraphAdaptor() { }
1.1449 + public:
1.1450 +
1.1451 + /// \brief Constructor
1.1452 + ///
1.1453 + /// Constructor
1.1454 + UndirDigraphAdaptor(_Digraph& _digraph) {
1.1455 + setDigraph(_digraph);
1.1456 + }
1.1457 +
1.1458 + /// \brief ArcMap combined from two original ArcMap
1.1459 + ///
1.1460 + /// This class adapts two original digraph ArcMap to
1.1461 + /// get an arc map on the adaptor.
1.1462 + template <typename _ForwardMap, typename _BackwardMap>
1.1463 + class CombinedArcMap {
1.1464 + public:
1.1465 +
1.1466 + typedef _ForwardMap ForwardMap;
1.1467 + typedef _BackwardMap BackwardMap;
1.1468 +
1.1469 + typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
1.1470 +
1.1471 + typedef typename ForwardMap::Value Value;
1.1472 + typedef typename Parent::Arc Key;
1.1473 +
1.1474 + /// \brief Constructor
1.1475 + ///
1.1476 + /// Constructor
1.1477 + CombinedArcMap() : _forward(0), _backward(0) {}
1.1478 +
1.1479 + /// \brief Constructor
1.1480 + ///
1.1481 + /// Constructor
1.1482 + CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
1.1483 + : _forward(&forward), _backward(&backward) {}
1.1484 +
1.1485 +
1.1486 + /// \brief Sets the value associated with a key.
1.1487 + ///
1.1488 + /// Sets the value associated with a key.
1.1489 + void set(const Key& e, const Value& a) {
1.1490 + if (Parent::direction(e)) {
1.1491 + _forward->set(e, a);
1.1492 + } else {
1.1493 + _backward->set(e, a);
1.1494 + }
1.1495 + }
1.1496 +
1.1497 + /// \brief Returns the value associated with a key.
1.1498 + ///
1.1499 + /// Returns the value associated with a key.
1.1500 + typename MapTraits<ForwardMap>::ConstReturnValue
1.1501 + operator[](const Key& e) const {
1.1502 + if (Parent::direction(e)) {
1.1503 + return (*_forward)[e];
1.1504 + } else {
1.1505 + return (*_backward)[e];
1.1506 + }
1.1507 + }
1.1508 +
1.1509 + /// \brief Returns the value associated with a key.
1.1510 + ///
1.1511 + /// Returns the value associated with a key.
1.1512 + typename MapTraits<ForwardMap>::ReturnValue
1.1513 + operator[](const Key& e) {
1.1514 + if (Parent::direction(e)) {
1.1515 + return (*_forward)[e];
1.1516 + } else {
1.1517 + return (*_backward)[e];
1.1518 + }
1.1519 + }
1.1520 +
1.1521 + /// \brief Sets the forward map
1.1522 + ///
1.1523 + /// Sets the forward map
1.1524 + void setForwardMap(ForwardMap& forward) {
1.1525 + _forward = &forward;
1.1526 + }
1.1527 +
1.1528 + /// \brief Sets the backward map
1.1529 + ///
1.1530 + /// Sets the backward map
1.1531 + void setBackwardMap(BackwardMap& backward) {
1.1532 + _backward = &backward;
1.1533 + }
1.1534 +
1.1535 + protected:
1.1536 +
1.1537 + ForwardMap* _forward;
1.1538 + BackwardMap* _backward;
1.1539 +
1.1540 + };
1.1541 +
1.1542 + };
1.1543 +
1.1544 + /// \brief Just gives back an undir digraph adaptor
1.1545 + ///
1.1546 + /// Just gives back an undir digraph adaptor
1.1547 + template<typename Digraph>
1.1548 + UndirDigraphAdaptor<const Digraph>
1.1549 + undirDigraphAdaptor(const Digraph& digraph) {
1.1550 + return UndirDigraphAdaptor<const Digraph>(digraph);
1.1551 + }
1.1552 +
1.1553 + template<typename _Digraph,
1.1554 + typename _CapacityMap = typename _Digraph::template ArcMap<int>,
1.1555 + typename _FlowMap = _CapacityMap,
1.1556 + typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
1.1557 + class ResForwardFilter {
1.1558 + public:
1.1559 +
1.1560 + typedef _Digraph Digraph;
1.1561 + typedef _CapacityMap CapacityMap;
1.1562 + typedef _FlowMap FlowMap;
1.1563 + typedef _Tolerance Tolerance;
1.1564 +
1.1565 + typedef typename Digraph::Arc Key;
1.1566 + typedef bool Value;
1.1567 +
1.1568 + private:
1.1569 +
1.1570 + const CapacityMap* _capacity;
1.1571 + const FlowMap* _flow;
1.1572 + Tolerance _tolerance;
1.1573 + public:
1.1574 +
1.1575 + ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,
1.1576 + const Tolerance& tolerance = Tolerance())
1.1577 + : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
1.1578 +
1.1579 + ResForwardFilter(const Tolerance& tolerance = Tolerance())
1.1580 + : _capacity(0), _flow(0), _tolerance(tolerance) { }
1.1581 +
1.1582 + void setCapacity(const CapacityMap& capacity) { _capacity = &capacity; }
1.1583 + void setFlow(const FlowMap& flow) { _flow = &flow; }
1.1584 +
1.1585 + bool operator[](const typename Digraph::Arc& a) const {
1.1586 + return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
1.1587 + }
1.1588 + };
1.1589 +
1.1590 + template<typename _Digraph,
1.1591 + typename _CapacityMap = typename _Digraph::template ArcMap<int>,
1.1592 + typename _FlowMap = _CapacityMap,
1.1593 + typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
1.1594 + class ResBackwardFilter {
1.1595 + public:
1.1596 +
1.1597 + typedef _Digraph Digraph;
1.1598 + typedef _CapacityMap CapacityMap;
1.1599 + typedef _FlowMap FlowMap;
1.1600 + typedef _Tolerance Tolerance;
1.1601 +
1.1602 + typedef typename Digraph::Arc Key;
1.1603 + typedef bool Value;
1.1604 +
1.1605 + private:
1.1606 +
1.1607 + const CapacityMap* _capacity;
1.1608 + const FlowMap* _flow;
1.1609 + Tolerance _tolerance;
1.1610 +
1.1611 + public:
1.1612 +
1.1613 + ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,
1.1614 + const Tolerance& tolerance = Tolerance())
1.1615 + : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
1.1616 + ResBackwardFilter(const Tolerance& tolerance = Tolerance())
1.1617 + : _capacity(0), _flow(0), _tolerance(tolerance) { }
1.1618 +
1.1619 + void setCapacity(const CapacityMap& capacity) { _capacity = &capacity; }
1.1620 + void setFlow(const FlowMap& flow) { _flow = &flow; }
1.1621 +
1.1622 + bool operator[](const typename Digraph::Arc& a) const {
1.1623 + return _tolerance.positive((*_flow)[a]);
1.1624 + }
1.1625 + };
1.1626 +
1.1627 +
1.1628 + ///\ingroup graph_adaptors
1.1629 + ///
1.1630 + ///\brief An adaptor for composing the residual graph for directed
1.1631 + ///flow and circulation problems.
1.1632 + ///
1.1633 + ///An adaptor for composing the residual graph for directed flow and
1.1634 + ///circulation problems. Let \f$ G=(V, A) \f$ be a directed digraph
1.1635 + ///and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F
1.1636 + ///\f$, be functions on the arc-set.
1.1637 + ///
1.1638 + ///In the appications of ResDigraphAdaptor, \f$ f \f$ usually stands
1.1639 + ///for a flow and \f$ c \f$ for a capacity function. Suppose that a
1.1640 + ///graph instance \c g of type \c ListDigraph implements \f$ G \f$.
1.1641 + ///
1.1642 + ///\code
1.1643 + /// ListDigraph g;
1.1644 + ///\endcode
1.1645 + ///
1.1646 + ///Then ResDigraphAdaptor implements the digraph structure with
1.1647 + /// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward}
1.1648 + /// \f$, where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
1.1649 + /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so
1.1650 + /// called residual graph. When we take the union \f$
1.1651 + /// A_{forward}\cup A_{backward} \f$, multilicities are counted,
1.1652 + /// i.e. if an arc is in both \f$ A_{forward} \f$ and \f$
1.1653 + /// A_{backward} \f$, then in the adaptor it appears twice. The
1.1654 + /// following code shows how such an instance can be constructed.
1.1655 + ///
1.1656 + ///\code
1.1657 + /// typedef ListDigraph Digraph;
1.1658 + /// IntArcMap f(g), c(g);
1.1659 + /// ResDigraphAdaptor<Digraph, int, IntArcMap, IntArcMap> ga(g);
1.1660 + ///\endcode
1.1661 + template<typename _Digraph,
1.1662 + typename _CapacityMap = typename _Digraph::template ArcMap<int>,
1.1663 + typename _FlowMap = _CapacityMap,
1.1664 + typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
1.1665 + class ResDigraphAdaptor :
1.1666 + public ArcSubDigraphAdaptor<
1.1667 + UndirDigraphAdaptor<const _Digraph>,
1.1668 + typename UndirDigraphAdaptor<const _Digraph>::template CombinedArcMap<
1.1669 + ResForwardFilter<const _Digraph, _CapacityMap, _FlowMap>,
1.1670 + ResBackwardFilter<const _Digraph, _CapacityMap, _FlowMap> > > {
1.1671 + public:
1.1672 +
1.1673 + typedef _Digraph Digraph;
1.1674 + typedef _CapacityMap CapacityMap;
1.1675 + typedef _FlowMap FlowMap;
1.1676 + typedef _Tolerance Tolerance;
1.1677 +
1.1678 + typedef typename CapacityMap::Value Value;
1.1679 + typedef ResDigraphAdaptor Adaptor;
1.1680 +
1.1681 + protected:
1.1682 +
1.1683 + typedef UndirDigraphAdaptor<const Digraph> UndirDigraph;
1.1684 +
1.1685 + typedef ResForwardFilter<const Digraph, CapacityMap, FlowMap>
1.1686 + ForwardFilter;
1.1687 +
1.1688 + typedef ResBackwardFilter<const Digraph, CapacityMap, FlowMap>
1.1689 + BackwardFilter;
1.1690 +
1.1691 + typedef typename UndirDigraph::
1.1692 + template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
1.1693 +
1.1694 + typedef ArcSubDigraphAdaptor<UndirDigraph, ArcFilter> Parent;
1.1695 +
1.1696 + const CapacityMap* _capacity;
1.1697 + FlowMap* _flow;
1.1698 +
1.1699 + UndirDigraph _graph;
1.1700 + ForwardFilter _forward_filter;
1.1701 + BackwardFilter _backward_filter;
1.1702 + ArcFilter _arc_filter;
1.1703 +
1.1704 + void setCapacityMap(const CapacityMap& capacity) {
1.1705 + _capacity = &capacity;
1.1706 + _forward_filter.setCapacity(capacity);
1.1707 + _backward_filter.setCapacity(capacity);
1.1708 + }
1.1709 +
1.1710 + void setFlowMap(FlowMap& flow) {
1.1711 + _flow = &flow;
1.1712 + _forward_filter.setFlow(flow);
1.1713 + _backward_filter.setFlow(flow);
1.1714 + }
1.1715 +
1.1716 + public:
1.1717 +
1.1718 + /// \brief Constructor of the residual digraph.
1.1719 + ///
1.1720 + /// Constructor of the residual graph. The parameters are the digraph type,
1.1721 + /// the flow map, the capacity map and a tolerance object.
1.1722 + ResDigraphAdaptor(const Digraph& digraph, const CapacityMap& capacity,
1.1723 + FlowMap& flow, const Tolerance& tolerance = Tolerance())
1.1724 + : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
1.1725 + _forward_filter(capacity, flow, tolerance),
1.1726 + _backward_filter(capacity, flow, tolerance),
1.1727 + _arc_filter(_forward_filter, _backward_filter)
1.1728 + {
1.1729 + Parent::setDigraph(_graph);
1.1730 + Parent::setArcFilterMap(_arc_filter);
1.1731 + }
1.1732 +
1.1733 + typedef typename Parent::Arc Arc;
1.1734 +
1.1735 + /// \brief Gives back the residual capacity of the arc.
1.1736 + ///
1.1737 + /// Gives back the residual capacity of the arc.
1.1738 + Value rescap(const Arc& arc) const {
1.1739 + if (UndirDigraph::direction(arc)) {
1.1740 + return (*_capacity)[arc] - (*_flow)[arc];
1.1741 + } else {
1.1742 + return (*_flow)[arc];
1.1743 + }
1.1744 + }
1.1745 +
1.1746 + /// \brief Augment on the given arc in the residual digraph.
1.1747 + ///
1.1748 + /// Augment on the given arc in the residual digraph. It increase
1.1749 + /// or decrease the flow on the original arc depend on the direction
1.1750 + /// of the residual arc.
1.1751 + void augment(const Arc& e, const Value& a) const {
1.1752 + if (UndirDigraph::direction(e)) {
1.1753 + _flow->set(e, (*_flow)[e] + a);
1.1754 + } else {
1.1755 + _flow->set(e, (*_flow)[e] - a);
1.1756 + }
1.1757 + }
1.1758 +
1.1759 + /// \brief Returns the direction of the arc.
1.1760 + ///
1.1761 + /// Returns true when the arc is same oriented as the original arc.
1.1762 + static bool forward(const Arc& e) {
1.1763 + return UndirDigraph::direction(e);
1.1764 + }
1.1765 +
1.1766 + /// \brief Returns the direction of the arc.
1.1767 + ///
1.1768 + /// Returns true when the arc is opposite oriented as the original arc.
1.1769 + static bool backward(const Arc& e) {
1.1770 + return !UndirDigraph::direction(e);
1.1771 + }
1.1772 +
1.1773 + /// \brief Gives back the forward oriented residual arc.
1.1774 + ///
1.1775 + /// Gives back the forward oriented residual arc.
1.1776 + static Arc forward(const typename Digraph::Arc& e) {
1.1777 + return UndirDigraph::direct(e, true);
1.1778 + }
1.1779 +
1.1780 + /// \brief Gives back the backward oriented residual arc.
1.1781 + ///
1.1782 + /// Gives back the backward oriented residual arc.
1.1783 + static Arc backward(const typename Digraph::Arc& e) {
1.1784 + return UndirDigraph::direct(e, false);
1.1785 + }
1.1786 +
1.1787 + /// \brief Residual capacity map.
1.1788 + ///
1.1789 + /// In generic residual digraphs the residual capacity can be obtained
1.1790 + /// as a map.
1.1791 + class ResCap {
1.1792 + protected:
1.1793 + const Adaptor* _adaptor;
1.1794 + public:
1.1795 + typedef Arc Key;
1.1796 + typedef typename _CapacityMap::Value Value;
1.1797 +
1.1798 + ResCap(const Adaptor& adaptor) : _adaptor(&adaptor) {}
1.1799 +
1.1800 + Value operator[](const Arc& e) const {
1.1801 + return _adaptor->rescap(e);
1.1802 + }
1.1803 +
1.1804 + };
1.1805 +
1.1806 + };
1.1807 +
1.1808 + /// \brief Base class for split digraph adaptor
1.1809 + ///
1.1810 + /// Base class of split digraph adaptor. In most case you do not need to
1.1811 + /// use it directly but the documented member functions of this class can
1.1812 + /// be used with the SplitDigraphAdaptor class.
1.1813 + /// \sa SplitDigraphAdaptor
1.1814 + template <typename _Digraph>
1.1815 + class SplitDigraphAdaptorBase {
1.1816 + public:
1.1817 +
1.1818 + typedef _Digraph Digraph;
1.1819 + typedef DigraphAdaptorBase<const _Digraph> Parent;
1.1820 + typedef SplitDigraphAdaptorBase Adaptor;
1.1821 +
1.1822 + typedef typename Digraph::Node DigraphNode;
1.1823 + typedef typename Digraph::Arc DigraphArc;
1.1824 +
1.1825 + class Node;
1.1826 + class Arc;
1.1827 +
1.1828 + private:
1.1829 +
1.1830 + template <typename T> class NodeMapBase;
1.1831 + template <typename T> class ArcMapBase;
1.1832 +
1.1833 + public:
1.1834 +
1.1835 + class Node : public DigraphNode {
1.1836 + friend class SplitDigraphAdaptorBase;
1.1837 + template <typename T> friend class NodeMapBase;
1.1838 + private:
1.1839 +
1.1840 + bool _in;
1.1841 + Node(DigraphNode node, bool in)
1.1842 + : DigraphNode(node), _in(in) {}
1.1843 +
1.1844 + public:
1.1845 +
1.1846 + Node() {}
1.1847 + Node(Invalid) : DigraphNode(INVALID), _in(true) {}
1.1848 +
1.1849 + bool operator==(const Node& node) const {
1.1850 + return DigraphNode::operator==(node) && _in == node._in;
1.1851 + }
1.1852 +
1.1853 + bool operator!=(const Node& node) const {
1.1854 + return !(*this == node);
1.1855 + }
1.1856 +
1.1857 + bool operator<(const Node& node) const {
1.1858 + return DigraphNode::operator<(node) ||
1.1859 + (DigraphNode::operator==(node) && _in < node._in);
1.1860 + }
1.1861 + };
1.1862 +
1.1863 + class Arc {
1.1864 + friend class SplitDigraphAdaptorBase;
1.1865 + template <typename T> friend class ArcMapBase;
1.1866 + private:
1.1867 + typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;
1.1868 +
1.1869 + explicit Arc(const DigraphArc& arc) : _item(arc) {}
1.1870 + explicit Arc(const DigraphNode& node) : _item(node) {}
1.1871 +
1.1872 + ArcImpl _item;
1.1873 +
1.1874 + public:
1.1875 + Arc() {}
1.1876 + Arc(Invalid) : _item(DigraphArc(INVALID)) {}
1.1877 +
1.1878 + bool operator==(const Arc& arc) const {
1.1879 + if (_item.firstState()) {
1.1880 + if (arc._item.firstState()) {
1.1881 + return _item.first() == arc._item.first();
1.1882 + }
1.1883 + } else {
1.1884 + if (arc._item.secondState()) {
1.1885 + return _item.second() == arc._item.second();
1.1886 + }
1.1887 + }
1.1888 + return false;
1.1889 + }
1.1890 +
1.1891 + bool operator!=(const Arc& arc) const {
1.1892 + return !(*this == arc);
1.1893 + }
1.1894 +
1.1895 + bool operator<(const Arc& arc) const {
1.1896 + if (_item.firstState()) {
1.1897 + if (arc._item.firstState()) {
1.1898 + return _item.first() < arc._item.first();
1.1899 + }
1.1900 + return false;
1.1901 + } else {
1.1902 + if (arc._item.secondState()) {
1.1903 + return _item.second() < arc._item.second();
1.1904 + }
1.1905 + return true;
1.1906 + }
1.1907 + }
1.1908 +
1.1909 + operator DigraphArc() const { return _item.first(); }
1.1910 + operator DigraphNode() const { return _item.second(); }
1.1911 +
1.1912 + };
1.1913 +
1.1914 + void first(Node& n) const {
1.1915 + _digraph->first(n);
1.1916 + n._in = true;
1.1917 + }
1.1918 +
1.1919 + void next(Node& n) const {
1.1920 + if (n._in) {
1.1921 + n._in = false;
1.1922 + } else {
1.1923 + n._in = true;
1.1924 + _digraph->next(n);
1.1925 + }
1.1926 + }
1.1927 +
1.1928 + void first(Arc& e) const {
1.1929 + e._item.setSecond();
1.1930 + _digraph->first(e._item.second());
1.1931 + if (e._item.second() == INVALID) {
1.1932 + e._item.setFirst();
1.1933 + _digraph->first(e._item.first());
1.1934 + }
1.1935 + }
1.1936 +
1.1937 + void next(Arc& e) const {
1.1938 + if (e._item.secondState()) {
1.1939 + _digraph->next(e._item.second());
1.1940 + if (e._item.second() == INVALID) {
1.1941 + e._item.setFirst();
1.1942 + _digraph->first(e._item.first());
1.1943 + }
1.1944 + } else {
1.1945 + _digraph->next(e._item.first());
1.1946 + }
1.1947 + }
1.1948 +
1.1949 + void firstOut(Arc& e, const Node& n) const {
1.1950 + if (n._in) {
1.1951 + e._item.setSecond(n);
1.1952 + } else {
1.1953 + e._item.setFirst();
1.1954 + _digraph->firstOut(e._item.first(), n);
1.1955 + }
1.1956 + }
1.1957 +
1.1958 + void nextOut(Arc& e) const {
1.1959 + if (!e._item.firstState()) {
1.1960 + e._item.setFirst(INVALID);
1.1961 + } else {
1.1962 + _digraph->nextOut(e._item.first());
1.1963 + }
1.1964 + }
1.1965 +
1.1966 + void firstIn(Arc& e, const Node& n) const {
1.1967 + if (!n._in) {
1.1968 + e._item.setSecond(n);
1.1969 + } else {
1.1970 + e._item.setFirst();
1.1971 + _digraph->firstIn(e._item.first(), n);
1.1972 + }
1.1973 + }
1.1974 +
1.1975 + void nextIn(Arc& e) const {
1.1976 + if (!e._item.firstState()) {
1.1977 + e._item.setFirst(INVALID);
1.1978 + } else {
1.1979 + _digraph->nextIn(e._item.first());
1.1980 + }
1.1981 + }
1.1982 +
1.1983 + Node source(const Arc& e) const {
1.1984 + if (e._item.firstState()) {
1.1985 + return Node(_digraph->source(e._item.first()), false);
1.1986 + } else {
1.1987 + return Node(e._item.second(), true);
1.1988 + }
1.1989 + }
1.1990 +
1.1991 + Node target(const Arc& e) const {
1.1992 + if (e._item.firstState()) {
1.1993 + return Node(_digraph->target(e._item.first()), true);
1.1994 + } else {
1.1995 + return Node(e._item.second(), false);
1.1996 + }
1.1997 + }
1.1998 +
1.1999 + int id(const Node& n) const {
1.2000 + return (_digraph->id(n) << 1) | (n._in ? 0 : 1);
1.2001 + }
1.2002 + Node nodeFromId(int ix) const {
1.2003 + return Node(_digraph->nodeFromId(ix >> 1), (ix & 1) == 0);
1.2004 + }
1.2005 + int maxNodeId() const {
1.2006 + return 2 * _digraph->maxNodeId() + 1;
1.2007 + }
1.2008 +
1.2009 + int id(const Arc& e) const {
1.2010 + if (e._item.firstState()) {
1.2011 + return _digraph->id(e._item.first()) << 1;
1.2012 + } else {
1.2013 + return (_digraph->id(e._item.second()) << 1) | 1;
1.2014 + }
1.2015 + }
1.2016 + Arc arcFromId(int ix) const {
1.2017 + if ((ix & 1) == 0) {
1.2018 + return Arc(_digraph->arcFromId(ix >> 1));
1.2019 + } else {
1.2020 + return Arc(_digraph->nodeFromId(ix >> 1));
1.2021 + }
1.2022 + }
1.2023 + int maxArcId() const {
1.2024 + return std::max(_digraph->maxNodeId() << 1,
1.2025 + (_digraph->maxArcId() << 1) | 1);
1.2026 + }
1.2027 +
1.2028 + /// \brief Returns true when the node is in-node.
1.2029 + ///
1.2030 + /// Returns true when the node is in-node.
1.2031 + static bool inNode(const Node& n) {
1.2032 + return n._in;
1.2033 + }
1.2034 +
1.2035 + /// \brief Returns true when the node is out-node.
1.2036 + ///
1.2037 + /// Returns true when the node is out-node.
1.2038 + static bool outNode(const Node& n) {
1.2039 + return !n._in;
1.2040 + }
1.2041 +
1.2042 + /// \brief Returns true when the arc is arc in the original digraph.
1.2043 + ///
1.2044 + /// Returns true when the arc is arc in the original digraph.
1.2045 + static bool origArc(const Arc& e) {
1.2046 + return e._item.firstState();
1.2047 + }
1.2048 +
1.2049 + /// \brief Returns true when the arc binds an in-node and an out-node.
1.2050 + ///
1.2051 + /// Returns true when the arc binds an in-node and an out-node.
1.2052 + static bool bindArc(const Arc& e) {
1.2053 + return e._item.secondState();
1.2054 + }
1.2055 +
1.2056 + /// \brief Gives back the in-node created from the \c node.
1.2057 + ///
1.2058 + /// Gives back the in-node created from the \c node.
1.2059 + static Node inNode(const DigraphNode& n) {
1.2060 + return Node(n, true);
1.2061 + }
1.2062 +
1.2063 + /// \brief Gives back the out-node created from the \c node.
1.2064 + ///
1.2065 + /// Gives back the out-node created from the \c node.
1.2066 + static Node outNode(const DigraphNode& n) {
1.2067 + return Node(n, false);
1.2068 + }
1.2069 +
1.2070 + /// \brief Gives back the arc binds the two part of the node.
1.2071 + ///
1.2072 + /// Gives back the arc binds the two part of the node.
1.2073 + static Arc arc(const DigraphNode& n) {
1.2074 + return Arc(n);
1.2075 + }
1.2076 +
1.2077 + /// \brief Gives back the arc of the original arc.
1.2078 + ///
1.2079 + /// Gives back the arc of the original arc.
1.2080 + static Arc arc(const DigraphArc& e) {
1.2081 + return Arc(e);
1.2082 + }
1.2083 +
1.2084 + typedef True NodeNumTag;
1.2085 +
1.2086 + int nodeNum() const {
1.2087 + return 2 * countNodes(*_digraph);
1.2088 + }
1.2089 +
1.2090 + typedef True EdgeNumTag;
1.2091 + int arcNum() const {
1.2092 + return countArcs(*_digraph) + countNodes(*_digraph);
1.2093 + }
1.2094 +
1.2095 + typedef True FindEdgeTag;
1.2096 + Arc findArc(const Node& u, const Node& v,
1.2097 + const Arc& prev = INVALID) const {
1.2098 + if (inNode(u)) {
1.2099 + if (outNode(v)) {
1.2100 + if (static_cast<const DigraphNode&>(u) ==
1.2101 + static_cast<const DigraphNode&>(v) && prev == INVALID) {
1.2102 + return Arc(u);
1.2103 + }
1.2104 + }
1.2105 + } else {
1.2106 + if (inNode(v)) {
1.2107 + return Arc(::lemon::findArc(*_digraph, u, v, prev));
1.2108 + }
1.2109 + }
1.2110 + return INVALID;
1.2111 + }
1.2112 +
1.2113 + private:
1.2114 +
1.2115 + template <typename _Value>
1.2116 + class NodeMapBase
1.2117 + : public MapTraits<typename Parent::template NodeMap<_Value> > {
1.2118 + typedef typename Parent::template NodeMap<_Value> NodeImpl;
1.2119 + public:
1.2120 + typedef Node Key;
1.2121 + typedef _Value Value;
1.2122 +
1.2123 + NodeMapBase(const Adaptor& adaptor)
1.2124 + : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
1.2125 + NodeMapBase(const Adaptor& adaptor, const Value& value)
1.2126 + : _in_map(*adaptor._digraph, value),
1.2127 + _out_map(*adaptor._digraph, value) {}
1.2128 +
1.2129 + void set(const Node& key, const Value& val) {
1.2130 + if (Adaptor::inNode(key)) { _in_map.set(key, val); }
1.2131 + else {_out_map.set(key, val); }
1.2132 + }
1.2133 +
1.2134 + typename MapTraits<NodeImpl>::ReturnValue
1.2135 + operator[](const Node& key) {
1.2136 + if (Adaptor::inNode(key)) { return _in_map[key]; }
1.2137 + else { return _out_map[key]; }
1.2138 + }
1.2139 +
1.2140 + typename MapTraits<NodeImpl>::ConstReturnValue
1.2141 + operator[](const Node& key) const {
1.2142 + if (Adaptor::inNode(key)) { return _in_map[key]; }
1.2143 + else { return _out_map[key]; }
1.2144 + }
1.2145 +
1.2146 + private:
1.2147 + NodeImpl _in_map, _out_map;
1.2148 + };
1.2149 +
1.2150 + template <typename _Value>
1.2151 + class ArcMapBase
1.2152 + : public MapTraits<typename Parent::template ArcMap<_Value> > {
1.2153 + typedef typename Parent::template ArcMap<_Value> ArcImpl;
1.2154 + typedef typename Parent::template NodeMap<_Value> NodeImpl;
1.2155 + public:
1.2156 + typedef Arc Key;
1.2157 + typedef _Value Value;
1.2158 +
1.2159 + ArcMapBase(const Adaptor& adaptor)
1.2160 + : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
1.2161 + ArcMapBase(const Adaptor& adaptor, const Value& value)
1.2162 + : _arc_map(*adaptor._digraph, value),
1.2163 + _node_map(*adaptor._digraph, value) {}
1.2164 +
1.2165 + void set(const Arc& key, const Value& val) {
1.2166 + if (Adaptor::origArc(key)) {
1.2167 + _arc_map.set(key._item.first(), val);
1.2168 + } else {
1.2169 + _node_map.set(key._item.second(), val);
1.2170 + }
1.2171 + }
1.2172 +
1.2173 + typename MapTraits<ArcImpl>::ReturnValue
1.2174 + operator[](const Arc& key) {
1.2175 + if (Adaptor::origArc(key)) {
1.2176 + return _arc_map[key._item.first()];
1.2177 + } else {
1.2178 + return _node_map[key._item.second()];
1.2179 + }
1.2180 + }
1.2181 +
1.2182 + typename MapTraits<ArcImpl>::ConstReturnValue
1.2183 + operator[](const Arc& key) const {
1.2184 + if (Adaptor::origArc(key)) {
1.2185 + return _arc_map[key._item.first()];
1.2186 + } else {
1.2187 + return _node_map[key._item.second()];
1.2188 + }
1.2189 + }
1.2190 +
1.2191 + private:
1.2192 + ArcImpl _arc_map;
1.2193 + NodeImpl _node_map;
1.2194 + };
1.2195 +
1.2196 + public:
1.2197 +
1.2198 + template <typename _Value>
1.2199 + class NodeMap
1.2200 + : public SubMapExtender<Adaptor, NodeMapBase<_Value> >
1.2201 + {
1.2202 + public:
1.2203 + typedef _Value Value;
1.2204 + typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent;
1.2205 +
1.2206 + NodeMap(const Adaptor& adaptor)
1.2207 + : Parent(adaptor) {}
1.2208 +
1.2209 + NodeMap(const Adaptor& adaptor, const Value& value)
1.2210 + : Parent(adaptor, value) {}
1.2211 +
1.2212 + private:
1.2213 + NodeMap& operator=(const NodeMap& cmap) {
1.2214 + return operator=<NodeMap>(cmap);
1.2215 + }
1.2216 +
1.2217 + template <typename CMap>
1.2218 + NodeMap& operator=(const CMap& cmap) {
1.2219 + Parent::operator=(cmap);
1.2220 + return *this;
1.2221 + }
1.2222 + };
1.2223 +
1.2224 + template <typename _Value>
1.2225 + class ArcMap
1.2226 + : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
1.2227 + {
1.2228 + public:
1.2229 + typedef _Value Value;
1.2230 + typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
1.2231 +
1.2232 + ArcMap(const Adaptor& adaptor)
1.2233 + : Parent(adaptor) {}
1.2234 +
1.2235 + ArcMap(const Adaptor& adaptor, const Value& value)
1.2236 + : Parent(adaptor, value) {}
1.2237 +
1.2238 + private:
1.2239 + ArcMap& operator=(const ArcMap& cmap) {
1.2240 + return operator=<ArcMap>(cmap);
1.2241 + }
1.2242 +
1.2243 + template <typename CMap>
1.2244 + ArcMap& operator=(const CMap& cmap) {
1.2245 + Parent::operator=(cmap);
1.2246 + return *this;
1.2247 + }
1.2248 + };
1.2249 +
1.2250 + protected:
1.2251 +
1.2252 + SplitDigraphAdaptorBase() : _digraph(0) {}
1.2253 +
1.2254 + Digraph* _digraph;
1.2255 +
1.2256 + void setDigraph(Digraph& digraph) {
1.2257 + _digraph = &digraph;
1.2258 + }
1.2259 +
1.2260 + };
1.2261 +
1.2262 + /// \ingroup graph_adaptors
1.2263 + ///
1.2264 + /// \brief Split digraph adaptor class
1.2265 + ///
1.2266 + /// This is an digraph adaptor which splits all node into an in-node
1.2267 + /// and an out-node. Formaly, the adaptor replaces each \f$ u \f$
1.2268 + /// node in the digraph with two node, \f$ u_{in} \f$ node and
1.2269 + /// \f$ u_{out} \f$ node. If there is an \f$ (v, u) \f$ arc in the
1.2270 + /// original digraph the new target of the arc will be \f$ u_{in} \f$ and
1.2271 + /// similarly the source of the original \f$ (u, v) \f$ arc will be
1.2272 + /// \f$ u_{out} \f$. The adaptor will add for each node in the
1.2273 + /// original digraph an additional arc which will connect
1.2274 + /// \f$ (u_{in}, u_{out}) \f$.
1.2275 + ///
1.2276 + /// The aim of this class is to run algorithm with node costs if the
1.2277 + /// algorithm can use directly just arc costs. In this case we should use
1.2278 + /// a \c SplitDigraphAdaptor and set the node cost of the digraph to the
1.2279 + /// bind arc in the adapted digraph.
1.2280 + ///
1.2281 + /// By example a maximum flow algoritm can compute how many arc
1.2282 + /// disjoint paths are in the digraph. But we would like to know how
1.2283 + /// many node disjoint paths are in the digraph. First we have to
1.2284 + /// adapt the digraph with the \c SplitDigraphAdaptor. Then run the flow
1.2285 + /// algorithm on the adapted digraph. The bottleneck of the flow will
1.2286 + /// be the bind arcs which bounds the flow with the count of the
1.2287 + /// node disjoint paths.
1.2288 + ///
1.2289 + ///\code
1.2290 + ///
1.2291 + /// typedef SplitDigraphAdaptor<SmartDigraph> SDigraph;
1.2292 + ///
1.2293 + /// SDigraph sdigraph(digraph);
1.2294 + ///
1.2295 + /// typedef ConstMap<SDigraph::Arc, int> SCapacity;
1.2296 + /// SCapacity scapacity(1);
1.2297 + ///
1.2298 + /// SDigraph::ArcMap<int> sflow(sdigraph);
1.2299 + ///
1.2300 + /// Preflow<SDigraph, SCapacity>
1.2301 + /// spreflow(sdigraph, scapacity,
1.2302 + /// SDigraph::outNode(source), SDigraph::inNode(target));
1.2303 + ///
1.2304 + /// spreflow.run();
1.2305 + ///
1.2306 + ///\endcode
1.2307 + ///
1.2308 + /// The result of the mamixum flow on the original digraph
1.2309 + /// shows the next figure:
1.2310 + ///
1.2311 + /// \image html arc_disjoint.png
1.2312 + /// \image latex arc_disjoint.eps "Arc disjoint paths" width=\textwidth
1.2313 + ///
1.2314 + /// And the maximum flow on the adapted digraph:
1.2315 + ///
1.2316 + /// \image html node_disjoint.png
1.2317 + /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth
1.2318 + ///
1.2319 + /// The second solution contains just 3 disjoint paths while the first 4.
1.2320 + /// The full code can be found in the \ref disjoint_paths_demo.cc demo file.
1.2321 + ///
1.2322 + /// This digraph adaptor is fully conform to the
1.2323 + /// \ref concepts::Digraph "Digraph" concept and
1.2324 + /// contains some additional member functions and types. The
1.2325 + /// documentation of some member functions may be found just in the
1.2326 + /// SplitDigraphAdaptorBase class.
1.2327 + ///
1.2328 + /// \sa SplitDigraphAdaptorBase
1.2329 + template <typename _Digraph>
1.2330 + class SplitDigraphAdaptor
1.2331 + : public DigraphAdaptorExtender<SplitDigraphAdaptorBase<_Digraph> > {
1.2332 + public:
1.2333 + typedef _Digraph Digraph;
1.2334 + typedef DigraphAdaptorExtender<SplitDigraphAdaptorBase<Digraph> > Parent;
1.2335 +
1.2336 + typedef typename Parent::Node Node;
1.2337 + typedef typename Parent::Arc Arc;
1.2338 +
1.2339 + /// \brief Constructor of the adaptor.
1.2340 + ///
1.2341 + /// Constructor of the adaptor.
1.2342 + SplitDigraphAdaptor(Digraph& g) {
1.2343 + Parent::setDigraph(g);
1.2344 + }
1.2345 +
1.2346 + /// \brief NodeMap combined from two original NodeMap
1.2347 + ///
1.2348 + /// This class adapt two of the original digraph NodeMap to
1.2349 + /// get a node map on the adapted digraph.
1.2350 + template <typename InNodeMap, typename OutNodeMap>
1.2351 + class CombinedNodeMap {
1.2352 + public:
1.2353 +
1.2354 + typedef Node Key;
1.2355 + typedef typename InNodeMap::Value Value;
1.2356 +
1.2357 + /// \brief Constructor
1.2358 + ///
1.2359 + /// Constructor.
1.2360 + CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
1.2361 + : _in_map(in_map), _out_map(out_map) {}
1.2362 +
1.2363 + /// \brief The subscript operator.
1.2364 + ///
1.2365 + /// The subscript operator.
1.2366 + Value& operator[](const Key& key) {
1.2367 + if (Parent::inNode(key)) {
1.2368 + return _in_map[key];
1.2369 + } else {
1.2370 + return _out_map[key];
1.2371 + }
1.2372 + }
1.2373 +
1.2374 + /// \brief The const subscript operator.
1.2375 + ///
1.2376 + /// The const subscript operator.
1.2377 + Value operator[](const Key& key) const {
1.2378 + if (Parent::inNode(key)) {
1.2379 + return _in_map[key];
1.2380 + } else {
1.2381 + return _out_map[key];
1.2382 + }
1.2383 + }
1.2384 +
1.2385 + /// \brief The setter function of the map.
1.2386 + ///
1.2387 + /// The setter function of the map.
1.2388 + void set(const Key& key, const Value& value) {
1.2389 + if (Parent::inNode(key)) {
1.2390 + _in_map.set(key, value);
1.2391 + } else {
1.2392 + _out_map.set(key, value);
1.2393 + }
1.2394 + }
1.2395 +
1.2396 + private:
1.2397 +
1.2398 + InNodeMap& _in_map;
1.2399 + OutNodeMap& _out_map;
1.2400 +
1.2401 + };
1.2402 +
1.2403 +
1.2404 + /// \brief Just gives back a combined node map.
1.2405 + ///
1.2406 + /// Just gives back a combined node map.
1.2407 + template <typename InNodeMap, typename OutNodeMap>
1.2408 + static CombinedNodeMap<InNodeMap, OutNodeMap>
1.2409 + combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
1.2410 + return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
1.2411 + }
1.2412 +
1.2413 + template <typename InNodeMap, typename OutNodeMap>
1.2414 + static CombinedNodeMap<const InNodeMap, OutNodeMap>
1.2415 + combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
1.2416 + return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
1.2417 + }
1.2418 +
1.2419 + template <typename InNodeMap, typename OutNodeMap>
1.2420 + static CombinedNodeMap<InNodeMap, const OutNodeMap>
1.2421 + combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
1.2422 + return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
1.2423 + }
1.2424 +
1.2425 + template <typename InNodeMap, typename OutNodeMap>
1.2426 + static CombinedNodeMap<const InNodeMap, const OutNodeMap>
1.2427 + combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
1.2428 + return CombinedNodeMap<const InNodeMap,
1.2429 + const OutNodeMap>(in_map, out_map);
1.2430 + }
1.2431 +
1.2432 + /// \brief ArcMap combined from an original ArcMap and NodeMap
1.2433 + ///
1.2434 + /// This class adapt an original digraph ArcMap and NodeMap to
1.2435 + /// get an arc map on the adapted digraph.
1.2436 + template <typename DigraphArcMap, typename DigraphNodeMap>
1.2437 + class CombinedArcMap {
1.2438 + public:
1.2439 +
1.2440 + typedef Arc Key;
1.2441 + typedef typename DigraphArcMap::Value Value;
1.2442 +
1.2443 + /// \brief Constructor
1.2444 + ///
1.2445 + /// Constructor.
1.2446 + CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)
1.2447 + : _arc_map(arc_map), _node_map(node_map) {}
1.2448 +
1.2449 + /// \brief The subscript operator.
1.2450 + ///
1.2451 + /// The subscript operator.
1.2452 + void set(const Arc& arc, const Value& val) {
1.2453 + if (Parent::origArc(arc)) {
1.2454 + _arc_map.set(arc, val);
1.2455 + } else {
1.2456 + _node_map.set(arc, val);
1.2457 + }
1.2458 + }
1.2459 +
1.2460 + /// \brief The const subscript operator.
1.2461 + ///
1.2462 + /// The const subscript operator.
1.2463 + Value operator[](const Key& arc) const {
1.2464 + if (Parent::origArc(arc)) {
1.2465 + return _arc_map[arc];
1.2466 + } else {
1.2467 + return _node_map[arc];
1.2468 + }
1.2469 + }
1.2470 +
1.2471 + /// \brief The const subscript operator.
1.2472 + ///
1.2473 + /// The const subscript operator.
1.2474 + Value& operator[](const Key& arc) {
1.2475 + if (Parent::origArc(arc)) {
1.2476 + return _arc_map[arc];
1.2477 + } else {
1.2478 + return _node_map[arc];
1.2479 + }
1.2480 + }
1.2481 +
1.2482 + private:
1.2483 + DigraphArcMap& _arc_map;
1.2484 + DigraphNodeMap& _node_map;
1.2485 + };
1.2486 +
1.2487 + /// \brief Just gives back a combined arc map.
1.2488 + ///
1.2489 + /// Just gives back a combined arc map.
1.2490 + template <typename DigraphArcMap, typename DigraphNodeMap>
1.2491 + static CombinedArcMap<DigraphArcMap, DigraphNodeMap>
1.2492 + combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
1.2493 + return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map);
1.2494 + }
1.2495 +
1.2496 + template <typename DigraphArcMap, typename DigraphNodeMap>
1.2497 + static CombinedArcMap<const DigraphArcMap, DigraphNodeMap>
1.2498 + combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
1.2499 + return CombinedArcMap<const DigraphArcMap,
1.2500 + DigraphNodeMap>(arc_map, node_map);
1.2501 + }
1.2502 +
1.2503 + template <typename DigraphArcMap, typename DigraphNodeMap>
1.2504 + static CombinedArcMap<DigraphArcMap, const DigraphNodeMap>
1.2505 + combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) {
1.2506 + return CombinedArcMap<DigraphArcMap,
1.2507 + const DigraphNodeMap>(arc_map, node_map);
1.2508 + }
1.2509 +
1.2510 + template <typename DigraphArcMap, typename DigraphNodeMap>
1.2511 + static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap>
1.2512 + combinedArcMap(const DigraphArcMap& arc_map,
1.2513 + const DigraphNodeMap& node_map) {
1.2514 + return CombinedArcMap<const DigraphArcMap,
1.2515 + const DigraphNodeMap>(arc_map, node_map);
1.2516 + }
1.2517 +
1.2518 + };
1.2519 +
1.2520 + /// \brief Just gives back a split digraph adaptor
1.2521 + ///
1.2522 + /// Just gives back a split digraph adaptor
1.2523 + template<typename Digraph>
1.2524 + SplitDigraphAdaptor<Digraph>
1.2525 + splitDigraphAdaptor(const Digraph& digraph) {
1.2526 + return SplitDigraphAdaptor<Digraph>(digraph);
1.2527 + }
1.2528 +
1.2529 +
1.2530 +} //namespace lemon
1.2531 +
1.2532 +#endif //LEMON_DIGRAPH_ADAPTOR_H
1.2533 +