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