1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/adaptors.h Sun Nov 30 19:18:32 2008 +0100
1.3 @@ -0,0 +1,3347 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
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_ADAPTORS_H
1.23 +#define LEMON_ADAPTORS_H
1.24 +
1.25 +/// \ingroup graph_adaptors
1.26 +/// \file
1.27 +/// \brief Several graph adaptors
1.28 +///
1.29 +/// This file contains several useful adaptors for digraphs and graphs.
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/graph_adaptor_extender.h>
1.36 +#include <lemon/tolerance.h>
1.37 +
1.38 +#include <algorithm>
1.39 +
1.40 +namespace lemon {
1.41 +
1.42 + template<typename _Digraph>
1.43 + class DigraphAdaptorBase {
1.44 + public:
1.45 + typedef _Digraph Digraph;
1.46 + typedef DigraphAdaptorBase Adaptor;
1.47 + typedef Digraph ParentDigraph;
1.48 +
1.49 + protected:
1.50 + Digraph* _digraph;
1.51 + DigraphAdaptorBase() : _digraph(0) { }
1.52 + void setDigraph(Digraph& digraph) { _digraph = &digraph; }
1.53 +
1.54 + public:
1.55 + DigraphAdaptorBase(Digraph& digraph) : _digraph(&digraph) { }
1.56 +
1.57 + typedef typename Digraph::Node Node;
1.58 + typedef typename Digraph::Arc Arc;
1.59 +
1.60 + void first(Node& i) const { _digraph->first(i); }
1.61 + void first(Arc& i) const { _digraph->first(i); }
1.62 + void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); }
1.63 + void firstOut(Arc& i, const Node& n ) const { _digraph->firstOut(i, n); }
1.64 +
1.65 + void next(Node& i) const { _digraph->next(i); }
1.66 + void next(Arc& i) const { _digraph->next(i); }
1.67 + void nextIn(Arc& i) const { _digraph->nextIn(i); }
1.68 + void nextOut(Arc& i) const { _digraph->nextOut(i); }
1.69 +
1.70 + Node source(const Arc& a) const { return _digraph->source(a); }
1.71 + Node target(const Arc& a) const { return _digraph->target(a); }
1.72 +
1.73 + typedef NodeNumTagIndicator<Digraph> NodeNumTag;
1.74 + int nodeNum() const { return _digraph->nodeNum(); }
1.75 +
1.76 + typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
1.77 + int arcNum() const { return _digraph->arcNum(); }
1.78 +
1.79 + typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
1.80 + Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
1.81 + return _digraph->findArc(u, v, prev);
1.82 + }
1.83 +
1.84 + Node addNode() { return _digraph->addNode(); }
1.85 + Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
1.86 +
1.87 + void erase(const Node& n) const { _digraph->erase(n); }
1.88 + void erase(const Arc& a) const { _digraph->erase(a); }
1.89 +
1.90 + void clear() const { _digraph->clear(); }
1.91 +
1.92 + int id(const Node& n) const { return _digraph->id(n); }
1.93 + int id(const Arc& a) const { return _digraph->id(a); }
1.94 +
1.95 + Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
1.96 + Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); }
1.97 +
1.98 + int maxNodeId() const { return _digraph->maxNodeId(); }
1.99 + int maxArcId() const { return _digraph->maxArcId(); }
1.100 +
1.101 + typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
1.102 + NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
1.103 +
1.104 + typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier;
1.105 + ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
1.106 +
1.107 + template <typename _Value>
1.108 + class NodeMap : public Digraph::template NodeMap<_Value> {
1.109 + public:
1.110 +
1.111 + typedef typename Digraph::template NodeMap<_Value> Parent;
1.112 +
1.113 + explicit NodeMap(const Adaptor& adaptor)
1.114 + : Parent(*adaptor._digraph) {}
1.115 +
1.116 + NodeMap(const Adaptor& adaptor, const _Value& value)
1.117 + : Parent(*adaptor._digraph, value) { }
1.118 +
1.119 + private:
1.120 + NodeMap& operator=(const NodeMap& cmap) {
1.121 + return operator=<NodeMap>(cmap);
1.122 + }
1.123 +
1.124 + template <typename CMap>
1.125 + NodeMap& operator=(const CMap& cmap) {
1.126 + Parent::operator=(cmap);
1.127 + return *this;
1.128 + }
1.129 +
1.130 + };
1.131 +
1.132 + template <typename _Value>
1.133 + class ArcMap : public Digraph::template ArcMap<_Value> {
1.134 + public:
1.135 +
1.136 + typedef typename Digraph::template ArcMap<_Value> Parent;
1.137 +
1.138 + explicit ArcMap(const Adaptor& adaptor)
1.139 + : Parent(*adaptor._digraph) {}
1.140 +
1.141 + ArcMap(const Adaptor& adaptor, const _Value& value)
1.142 + : Parent(*adaptor._digraph, value) {}
1.143 +
1.144 + private:
1.145 + ArcMap& operator=(const ArcMap& cmap) {
1.146 + return operator=<ArcMap>(cmap);
1.147 + }
1.148 +
1.149 + template <typename CMap>
1.150 + ArcMap& operator=(const CMap& cmap) {
1.151 + Parent::operator=(cmap);
1.152 + return *this;
1.153 + }
1.154 +
1.155 + };
1.156 +
1.157 + };
1.158 +
1.159 + template<typename _Graph>
1.160 + class GraphAdaptorBase {
1.161 + public:
1.162 + typedef _Graph Graph;
1.163 + typedef Graph ParentGraph;
1.164 +
1.165 + protected:
1.166 + Graph* _graph;
1.167 +
1.168 + GraphAdaptorBase() : _graph(0) {}
1.169 +
1.170 + void setGraph(Graph& graph) { _graph = &graph; }
1.171 +
1.172 + public:
1.173 + GraphAdaptorBase(Graph& graph) : _graph(&graph) {}
1.174 +
1.175 + typedef typename Graph::Node Node;
1.176 + typedef typename Graph::Arc Arc;
1.177 + typedef typename Graph::Edge Edge;
1.178 +
1.179 + void first(Node& i) const { _graph->first(i); }
1.180 + void first(Arc& i) const { _graph->first(i); }
1.181 + void first(Edge& i) const { _graph->first(i); }
1.182 + void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); }
1.183 + void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); }
1.184 + void firstInc(Edge &i, bool &d, const Node &n) const {
1.185 + _graph->firstInc(i, d, n);
1.186 + }
1.187 +
1.188 + void next(Node& i) const { _graph->next(i); }
1.189 + void next(Arc& i) const { _graph->next(i); }
1.190 + void next(Edge& i) const { _graph->next(i); }
1.191 + void nextIn(Arc& i) const { _graph->nextIn(i); }
1.192 + void nextOut(Arc& i) const { _graph->nextOut(i); }
1.193 + void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); }
1.194 +
1.195 + Node u(const Edge& e) const { return _graph->u(e); }
1.196 + Node v(const Edge& e) const { return _graph->v(e); }
1.197 +
1.198 + Node source(const Arc& a) const { return _graph->source(a); }
1.199 + Node target(const Arc& a) const { return _graph->target(a); }
1.200 +
1.201 + typedef NodeNumTagIndicator<Graph> NodeNumTag;
1.202 + int nodeNum() const { return _graph->nodeNum(); }
1.203 +
1.204 + typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
1.205 + int arcNum() const { return _graph->arcNum(); }
1.206 + int edgeNum() const { return _graph->edgeNum(); }
1.207 +
1.208 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1.209 + Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
1.210 + return _graph->findArc(u, v, prev);
1.211 + }
1.212 + Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) {
1.213 + return _graph->findEdge(u, v, prev);
1.214 + }
1.215 +
1.216 + Node addNode() { return _graph->addNode(); }
1.217 + Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }
1.218 +
1.219 + void erase(const Node& i) { _graph->erase(i); }
1.220 + void erase(const Edge& i) { _graph->erase(i); }
1.221 +
1.222 + void clear() { _graph->clear(); }
1.223 +
1.224 + bool direction(const Arc& a) const { return _graph->direction(a); }
1.225 + Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); }
1.226 +
1.227 + int id(const Node& v) const { return _graph->id(v); }
1.228 + int id(const Arc& a) const { return _graph->id(a); }
1.229 + int id(const Edge& e) const { return _graph->id(e); }
1.230 +
1.231 + Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
1.232 + Arc arcFromId(int ix) const { return _graph->arcFromId(ix); }
1.233 + Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); }
1.234 +
1.235 + int maxNodeId() const { return _graph->maxNodeId(); }
1.236 + int maxArcId() const { return _graph->maxArcId(); }
1.237 + int maxEdgeId() const { return _graph->maxEdgeId(); }
1.238 +
1.239 + typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
1.240 + NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
1.241 +
1.242 + typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
1.243 + ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
1.244 +
1.245 + typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
1.246 + EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
1.247 +
1.248 + template <typename _Value>
1.249 + class NodeMap : public Graph::template NodeMap<_Value> {
1.250 + public:
1.251 + typedef typename Graph::template NodeMap<_Value> Parent;
1.252 + explicit NodeMap(const GraphAdaptorBase<Graph>& adapter)
1.253 + : Parent(*adapter._graph) {}
1.254 + NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
1.255 + : Parent(*adapter._graph, value) {}
1.256 +
1.257 + private:
1.258 + NodeMap& operator=(const NodeMap& cmap) {
1.259 + return operator=<NodeMap>(cmap);
1.260 + }
1.261 +
1.262 + template <typename CMap>
1.263 + NodeMap& operator=(const CMap& cmap) {
1.264 + Parent::operator=(cmap);
1.265 + return *this;
1.266 + }
1.267 +
1.268 + };
1.269 +
1.270 + template <typename _Value>
1.271 + class ArcMap : public Graph::template ArcMap<_Value> {
1.272 + public:
1.273 + typedef typename Graph::template ArcMap<_Value> Parent;
1.274 + explicit ArcMap(const GraphAdaptorBase<Graph>& adapter)
1.275 + : Parent(*adapter._graph) {}
1.276 + ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
1.277 + : Parent(*adapter._graph, value) {}
1.278 +
1.279 + private:
1.280 + ArcMap& operator=(const ArcMap& cmap) {
1.281 + return operator=<ArcMap>(cmap);
1.282 + }
1.283 +
1.284 + template <typename CMap>
1.285 + ArcMap& operator=(const CMap& cmap) {
1.286 + Parent::operator=(cmap);
1.287 + return *this;
1.288 + }
1.289 + };
1.290 +
1.291 + template <typename _Value>
1.292 + class EdgeMap : public Graph::template EdgeMap<_Value> {
1.293 + public:
1.294 + typedef typename Graph::template EdgeMap<_Value> Parent;
1.295 + explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)
1.296 + : Parent(*adapter._graph) {}
1.297 + EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
1.298 + : Parent(*adapter._graph, value) {}
1.299 +
1.300 + private:
1.301 + EdgeMap& operator=(const EdgeMap& cmap) {
1.302 + return operator=<EdgeMap>(cmap);
1.303 + }
1.304 +
1.305 + template <typename CMap>
1.306 + EdgeMap& operator=(const CMap& cmap) {
1.307 + Parent::operator=(cmap);
1.308 + return *this;
1.309 + }
1.310 + };
1.311 +
1.312 + };
1.313 +
1.314 + template <typename _Digraph>
1.315 + class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> {
1.316 + public:
1.317 + typedef _Digraph Digraph;
1.318 + typedef DigraphAdaptorBase<_Digraph> Parent;
1.319 + protected:
1.320 + ReverseDigraphBase() : Parent() { }
1.321 + public:
1.322 + typedef typename Parent::Node Node;
1.323 + typedef typename Parent::Arc Arc;
1.324 +
1.325 + void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }
1.326 + void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); }
1.327 +
1.328 + void nextIn(Arc& a) const { Parent::nextOut(a); }
1.329 + void nextOut(Arc& a) const { Parent::nextIn(a); }
1.330 +
1.331 + Node source(const Arc& a) const { return Parent::target(a); }
1.332 + Node target(const Arc& a) const { return Parent::source(a); }
1.333 +
1.334 + Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
1.335 +
1.336 + typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
1.337 + Arc findArc(const Node& u, const Node& v,
1.338 + const Arc& prev = INVALID) {
1.339 + return Parent::findArc(v, u, prev);
1.340 + }
1.341 +
1.342 + };
1.343 +
1.344 + /// \ingroup graph_adaptors
1.345 + ///
1.346 + /// \brief A digraph adaptor which reverses the orientation of the arcs.
1.347 + ///
1.348 + /// ReverseDigraph reverses the arcs in the adapted digraph. The
1.349 + /// SubDigraph is conform to the \ref concepts::Digraph
1.350 + /// "Digraph concept".
1.351 + ///
1.352 + /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
1.353 + /// "Digraph concept". The type can be specified to be const.
1.354 + template<typename _Digraph>
1.355 + class ReverseDigraph :
1.356 + public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > {
1.357 + public:
1.358 + typedef _Digraph Digraph;
1.359 + typedef DigraphAdaptorExtender<
1.360 + ReverseDigraphBase<_Digraph> > Parent;
1.361 + protected:
1.362 + ReverseDigraph() { }
1.363 + public:
1.364 +
1.365 + /// \brief Constructor
1.366 + ///
1.367 + /// Creates a reverse digraph adaptor for the given digraph
1.368 + explicit ReverseDigraph(Digraph& digraph) {
1.369 + Parent::setDigraph(digraph);
1.370 + }
1.371 + };
1.372 +
1.373 + /// \brief Just gives back a reverse digraph adaptor
1.374 + ///
1.375 + /// Just gives back a reverse digraph adaptor
1.376 + template<typename Digraph>
1.377 + ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) {
1.378 + return ReverseDigraph<const Digraph>(digraph);
1.379 + }
1.380 +
1.381 + template <typename _Digraph, typename _NodeFilterMap,
1.382 + typename _ArcFilterMap, bool _checked = true>
1.383 + class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {
1.384 + public:
1.385 + typedef _Digraph Digraph;
1.386 + typedef _NodeFilterMap NodeFilterMap;
1.387 + typedef _ArcFilterMap ArcFilterMap;
1.388 +
1.389 + typedef SubDigraphBase Adaptor;
1.390 + typedef DigraphAdaptorBase<_Digraph> Parent;
1.391 + protected:
1.392 + NodeFilterMap* _node_filter;
1.393 + ArcFilterMap* _arc_filter;
1.394 + SubDigraphBase()
1.395 + : Parent(), _node_filter(0), _arc_filter(0) { }
1.396 +
1.397 + void setNodeFilterMap(NodeFilterMap& node_filter) {
1.398 + _node_filter = &node_filter;
1.399 + }
1.400 + void setArcFilterMap(ArcFilterMap& arc_filter) {
1.401 + _arc_filter = &arc_filter;
1.402 + }
1.403 +
1.404 + public:
1.405 +
1.406 + typedef typename Parent::Node Node;
1.407 + typedef typename Parent::Arc Arc;
1.408 +
1.409 + void first(Node& i) const {
1.410 + Parent::first(i);
1.411 + while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
1.412 + }
1.413 +
1.414 + void first(Arc& i) const {
1.415 + Parent::first(i);
1.416 + while (i != INVALID && (!(*_arc_filter)[i]
1.417 + || !(*_node_filter)[Parent::source(i)]
1.418 + || !(*_node_filter)[Parent::target(i)]))
1.419 + Parent::next(i);
1.420 + }
1.421 +
1.422 + void firstIn(Arc& i, const Node& n) const {
1.423 + Parent::firstIn(i, n);
1.424 + while (i != INVALID && (!(*_arc_filter)[i]
1.425 + || !(*_node_filter)[Parent::source(i)]))
1.426 + Parent::nextIn(i);
1.427 + }
1.428 +
1.429 + void firstOut(Arc& i, const Node& n) const {
1.430 + Parent::firstOut(i, n);
1.431 + while (i != INVALID && (!(*_arc_filter)[i]
1.432 + || !(*_node_filter)[Parent::target(i)]))
1.433 + Parent::nextOut(i);
1.434 + }
1.435 +
1.436 + void next(Node& i) const {
1.437 + Parent::next(i);
1.438 + while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
1.439 + }
1.440 +
1.441 + void next(Arc& i) const {
1.442 + Parent::next(i);
1.443 + while (i != INVALID && (!(*_arc_filter)[i]
1.444 + || !(*_node_filter)[Parent::source(i)]
1.445 + || !(*_node_filter)[Parent::target(i)]))
1.446 + Parent::next(i);
1.447 + }
1.448 +
1.449 + void nextIn(Arc& i) const {
1.450 + Parent::nextIn(i);
1.451 + while (i != INVALID && (!(*_arc_filter)[i]
1.452 + || !(*_node_filter)[Parent::source(i)]))
1.453 + Parent::nextIn(i);
1.454 + }
1.455 +
1.456 + void nextOut(Arc& i) const {
1.457 + Parent::nextOut(i);
1.458 + while (i != INVALID && (!(*_arc_filter)[i]
1.459 + || !(*_node_filter)[Parent::target(i)]))
1.460 + Parent::nextOut(i);
1.461 + }
1.462 +
1.463 + void hide(const Node& n) const { _node_filter->set(n, false); }
1.464 + void hide(const Arc& a) const { _arc_filter->set(a, false); }
1.465 +
1.466 + void unHide(const Node& n) const { _node_filter->set(n, true); }
1.467 + void unHide(const Arc& a) const { _arc_filter->set(a, true); }
1.468 +
1.469 + bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
1.470 + bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }
1.471 +
1.472 + typedef False NodeNumTag;
1.473 + typedef False EdgeNumTag;
1.474 +
1.475 + typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
1.476 + Arc findArc(const Node& source, const Node& target,
1.477 + const Arc& prev = INVALID) {
1.478 + if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
1.479 + return INVALID;
1.480 + }
1.481 + Arc arc = Parent::findArc(source, target, prev);
1.482 + while (arc != INVALID && !(*_arc_filter)[arc]) {
1.483 + arc = Parent::findArc(source, target, arc);
1.484 + }
1.485 + return arc;
1.486 + }
1.487 +
1.488 + template <typename _Value>
1.489 + class NodeMap : public SubMapExtender<Adaptor,
1.490 + typename Parent::template NodeMap<_Value> > {
1.491 + public:
1.492 + typedef _Value Value;
1.493 + typedef SubMapExtender<Adaptor, typename Parent::
1.494 + template NodeMap<Value> > MapParent;
1.495 +
1.496 + NodeMap(const Adaptor& adaptor)
1.497 + : MapParent(adaptor) {}
1.498 + NodeMap(const Adaptor& adaptor, const Value& value)
1.499 + : MapParent(adaptor, value) {}
1.500 +
1.501 + private:
1.502 + NodeMap& operator=(const NodeMap& cmap) {
1.503 + return operator=<NodeMap>(cmap);
1.504 + }
1.505 +
1.506 + template <typename CMap>
1.507 + NodeMap& operator=(const CMap& cmap) {
1.508 + MapParent::operator=(cmap);
1.509 + return *this;
1.510 + }
1.511 + };
1.512 +
1.513 + template <typename _Value>
1.514 + class ArcMap : public SubMapExtender<Adaptor,
1.515 + typename Parent::template ArcMap<_Value> > {
1.516 + public:
1.517 + typedef _Value Value;
1.518 + typedef SubMapExtender<Adaptor, typename Parent::
1.519 + template ArcMap<Value> > MapParent;
1.520 +
1.521 + ArcMap(const Adaptor& adaptor)
1.522 + : MapParent(adaptor) {}
1.523 + ArcMap(const Adaptor& adaptor, const Value& value)
1.524 + : MapParent(adaptor, value) {}
1.525 +
1.526 + private:
1.527 + ArcMap& operator=(const ArcMap& cmap) {
1.528 + return operator=<ArcMap>(cmap);
1.529 + }
1.530 +
1.531 + template <typename CMap>
1.532 + ArcMap& operator=(const CMap& cmap) {
1.533 + MapParent::operator=(cmap);
1.534 + return *this;
1.535 + }
1.536 + };
1.537 +
1.538 + };
1.539 +
1.540 + template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>
1.541 + class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>
1.542 + : public DigraphAdaptorBase<_Digraph> {
1.543 + public:
1.544 + typedef _Digraph Digraph;
1.545 + typedef _NodeFilterMap NodeFilterMap;
1.546 + typedef _ArcFilterMap ArcFilterMap;
1.547 +
1.548 + typedef SubDigraphBase Adaptor;
1.549 + typedef DigraphAdaptorBase<Digraph> Parent;
1.550 + protected:
1.551 + NodeFilterMap* _node_filter;
1.552 + ArcFilterMap* _arc_filter;
1.553 + SubDigraphBase()
1.554 + : Parent(), _node_filter(0), _arc_filter(0) { }
1.555 +
1.556 + void setNodeFilterMap(NodeFilterMap& node_filter) {
1.557 + _node_filter = &node_filter;
1.558 + }
1.559 + void setArcFilterMap(ArcFilterMap& arc_filter) {
1.560 + _arc_filter = &arc_filter;
1.561 + }
1.562 +
1.563 + public:
1.564 +
1.565 + typedef typename Parent::Node Node;
1.566 + typedef typename Parent::Arc Arc;
1.567 +
1.568 + void first(Node& i) const {
1.569 + Parent::first(i);
1.570 + while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
1.571 + }
1.572 +
1.573 + void first(Arc& i) const {
1.574 + Parent::first(i);
1.575 + while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
1.576 + }
1.577 +
1.578 + void firstIn(Arc& i, const Node& n) const {
1.579 + Parent::firstIn(i, n);
1.580 + while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
1.581 + }
1.582 +
1.583 + void firstOut(Arc& i, const Node& n) const {
1.584 + Parent::firstOut(i, n);
1.585 + while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
1.586 + }
1.587 +
1.588 + void next(Node& i) const {
1.589 + Parent::next(i);
1.590 + while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
1.591 + }
1.592 + void next(Arc& i) const {
1.593 + Parent::next(i);
1.594 + while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
1.595 + }
1.596 + void nextIn(Arc& i) const {
1.597 + Parent::nextIn(i);
1.598 + while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
1.599 + }
1.600 +
1.601 + void nextOut(Arc& i) const {
1.602 + Parent::nextOut(i);
1.603 + while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
1.604 + }
1.605 +
1.606 + void hide(const Node& n) const { _node_filter->set(n, false); }
1.607 + void hide(const Arc& e) const { _arc_filter->set(e, false); }
1.608 +
1.609 + void unHide(const Node& n) const { _node_filter->set(n, true); }
1.610 + void unHide(const Arc& e) const { _arc_filter->set(e, true); }
1.611 +
1.612 + bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
1.613 + bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }
1.614 +
1.615 + typedef False NodeNumTag;
1.616 + typedef False EdgeNumTag;
1.617 +
1.618 + typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
1.619 + Arc findArc(const Node& source, const Node& target,
1.620 + const Arc& prev = INVALID) {
1.621 + if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
1.622 + return INVALID;
1.623 + }
1.624 + Arc arc = Parent::findArc(source, target, prev);
1.625 + while (arc != INVALID && !(*_arc_filter)[arc]) {
1.626 + arc = Parent::findArc(source, target, arc);
1.627 + }
1.628 + return arc;
1.629 + }
1.630 +
1.631 + template <typename _Value>
1.632 + class NodeMap : public SubMapExtender<Adaptor,
1.633 + typename Parent::template NodeMap<_Value> > {
1.634 + public:
1.635 + typedef _Value Value;
1.636 + typedef SubMapExtender<Adaptor, typename Parent::
1.637 + template NodeMap<Value> > MapParent;
1.638 +
1.639 + NodeMap(const Adaptor& adaptor)
1.640 + : MapParent(adaptor) {}
1.641 + NodeMap(const Adaptor& adaptor, const Value& value)
1.642 + : MapParent(adaptor, value) {}
1.643 +
1.644 + private:
1.645 + NodeMap& operator=(const NodeMap& cmap) {
1.646 + return operator=<NodeMap>(cmap);
1.647 + }
1.648 +
1.649 + template <typename CMap>
1.650 + NodeMap& operator=(const CMap& cmap) {
1.651 + MapParent::operator=(cmap);
1.652 + return *this;
1.653 + }
1.654 + };
1.655 +
1.656 + template <typename _Value>
1.657 + class ArcMap : public SubMapExtender<Adaptor,
1.658 + typename Parent::template ArcMap<_Value> > {
1.659 + public:
1.660 + typedef _Value Value;
1.661 + typedef SubMapExtender<Adaptor, typename Parent::
1.662 + template ArcMap<Value> > MapParent;
1.663 +
1.664 + ArcMap(const Adaptor& adaptor)
1.665 + : MapParent(adaptor) {}
1.666 + ArcMap(const Adaptor& adaptor, const Value& value)
1.667 + : MapParent(adaptor, value) {}
1.668 +
1.669 + private:
1.670 + ArcMap& operator=(const ArcMap& cmap) {
1.671 + return operator=<ArcMap>(cmap);
1.672 + }
1.673 +
1.674 + template <typename CMap>
1.675 + ArcMap& operator=(const CMap& cmap) {
1.676 + MapParent::operator=(cmap);
1.677 + return *this;
1.678 + }
1.679 + };
1.680 +
1.681 + };
1.682 +
1.683 + /// \ingroup graph_adaptors
1.684 + ///
1.685 + /// \brief An adaptor for hiding nodes and arcs in a digraph
1.686 + ///
1.687 + /// SubDigraph hides nodes and arcs in a digraph. A bool node map
1.688 + /// and a bool arc map must be specified, which define the filters
1.689 + /// for nodes and arcs. Just the nodes and arcs with true value are
1.690 + /// shown in the subdigraph. The SubDigraph is conform to the \ref
1.691 + /// concepts::Digraph "Digraph concept". If the \c _checked parameter
1.692 + /// is true, then the arcs incident to filtered nodes are also
1.693 + /// filtered out.
1.694 + ///
1.695 + /// \tparam _Digraph It must be conform to the \ref
1.696 + /// concepts::Digraph "Digraph concept". The type can be specified
1.697 + /// to const.
1.698 + /// \tparam _NodeFilterMap A bool valued node map of the the adapted digraph.
1.699 + /// \tparam _ArcFilterMap A bool valued arc map of the the adapted digraph.
1.700 + /// \tparam _checked If the parameter is false then the arc filtering
1.701 + /// is not checked with respect to node filter. Otherwise, each arc
1.702 + /// is automatically filtered, which is incident to a filtered node.
1.703 + ///
1.704 + /// \see FilterNodes
1.705 + /// \see FilterArcs
1.706 + template<typename _Digraph,
1.707 + typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
1.708 + typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,
1.709 + bool _checked = true>
1.710 + class SubDigraph
1.711 + : public DigraphAdaptorExtender<
1.712 + SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > {
1.713 + public:
1.714 + typedef _Digraph Digraph;
1.715 + typedef _NodeFilterMap NodeFilterMap;
1.716 + typedef _ArcFilterMap ArcFilterMap;
1.717 +
1.718 + typedef DigraphAdaptorExtender<
1.719 + SubDigraphBase<Digraph, NodeFilterMap, ArcFilterMap, _checked> >
1.720 + Parent;
1.721 +
1.722 + typedef typename Parent::Node Node;
1.723 + typedef typename Parent::Arc Arc;
1.724 +
1.725 + protected:
1.726 + SubDigraph() { }
1.727 + public:
1.728 +
1.729 + /// \brief Constructor
1.730 + ///
1.731 + /// Creates a subdigraph for the given digraph with
1.732 + /// given node and arc map filters.
1.733 + SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,
1.734 + ArcFilterMap& arc_filter) {
1.735 + setDigraph(digraph);
1.736 + setNodeFilterMap(node_filter);
1.737 + setArcFilterMap(arc_filter);
1.738 + }
1.739 +
1.740 + /// \brief Hides the node of the graph
1.741 + ///
1.742 + /// This function hides \c n in the digraph, i.e. the iteration
1.743 + /// jumps over it. This is done by simply setting the value of \c n
1.744 + /// to be false in the corresponding node-map.
1.745 + void hide(const Node& n) const { Parent::hide(n); }
1.746 +
1.747 + /// \brief Hides the arc of the graph
1.748 + ///
1.749 + /// This function hides \c a in the digraph, i.e. the iteration
1.750 + /// jumps over it. This is done by simply setting the value of \c a
1.751 + /// to be false in the corresponding arc-map.
1.752 + void hide(const Arc& a) const { Parent::hide(a); }
1.753 +
1.754 + /// \brief Unhides the node of the graph
1.755 + ///
1.756 + /// The value of \c n is set to be true in the node-map which stores
1.757 + /// hide information. If \c n was hidden previuosly, then it is shown
1.758 + /// again
1.759 + void unHide(const Node& n) const { Parent::unHide(n); }
1.760 +
1.761 + /// \brief Unhides the arc of the graph
1.762 + ///
1.763 + /// The value of \c a is set to be true in the arc-map which stores
1.764 + /// hide information. If \c a was hidden previuosly, then it is shown
1.765 + /// again
1.766 + void unHide(const Arc& a) const { Parent::unHide(a); }
1.767 +
1.768 + /// \brief Returns true if \c n is hidden.
1.769 + ///
1.770 + /// Returns true if \c n is hidden.
1.771 + ///
1.772 + bool hidden(const Node& n) const { return Parent::hidden(n); }
1.773 +
1.774 + /// \brief Returns true if \c a is hidden.
1.775 + ///
1.776 + /// Returns true if \c a is hidden.
1.777 + ///
1.778 + bool hidden(const Arc& a) const { return Parent::hidden(a); }
1.779 +
1.780 + };
1.781 +
1.782 + /// \brief Just gives back a subdigraph
1.783 + ///
1.784 + /// Just gives back a subdigraph
1.785 + template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
1.786 + SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
1.787 + subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) {
1.788 + return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
1.789 + (digraph, nfm, afm);
1.790 + }
1.791 +
1.792 + template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
1.793 + SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
1.794 + subDigraph(const Digraph& digraph,
1.795 + const NodeFilterMap& nfm, ArcFilterMap& afm) {
1.796 + return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
1.797 + (digraph, nfm, afm);
1.798 + }
1.799 +
1.800 + template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
1.801 + SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
1.802 + subDigraph(const Digraph& digraph,
1.803 + NodeFilterMap& nfm, const ArcFilterMap& afm) {
1.804 + return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
1.805 + (digraph, nfm, afm);
1.806 + }
1.807 +
1.808 + template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
1.809 + SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap>
1.810 + subDigraph(const Digraph& digraph,
1.811 + const NodeFilterMap& nfm, const ArcFilterMap& afm) {
1.812 + return SubDigraph<const Digraph, const NodeFilterMap,
1.813 + const ArcFilterMap>(digraph, nfm, afm);
1.814 + }
1.815 +
1.816 +
1.817 + template <typename _Graph, typename NodeFilterMap,
1.818 + typename EdgeFilterMap, bool _checked = true>
1.819 + class SubGraphBase : public GraphAdaptorBase<_Graph> {
1.820 + public:
1.821 + typedef _Graph Graph;
1.822 + typedef SubGraphBase Adaptor;
1.823 + typedef GraphAdaptorBase<_Graph> Parent;
1.824 + protected:
1.825 +
1.826 + NodeFilterMap* _node_filter_map;
1.827 + EdgeFilterMap* _edge_filter_map;
1.828 +
1.829 + SubGraphBase()
1.830 + : Parent(), _node_filter_map(0), _edge_filter_map(0) { }
1.831 +
1.832 + void setNodeFilterMap(NodeFilterMap& node_filter_map) {
1.833 + _node_filter_map=&node_filter_map;
1.834 + }
1.835 + void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
1.836 + _edge_filter_map=&edge_filter_map;
1.837 + }
1.838 +
1.839 + public:
1.840 +
1.841 + typedef typename Parent::Node Node;
1.842 + typedef typename Parent::Arc Arc;
1.843 + typedef typename Parent::Edge Edge;
1.844 +
1.845 + void first(Node& i) const {
1.846 + Parent::first(i);
1.847 + while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
1.848 + }
1.849 +
1.850 + void first(Arc& i) const {
1.851 + Parent::first(i);
1.852 + while (i!=INVALID && (!(*_edge_filter_map)[i]
1.853 + || !(*_node_filter_map)[Parent::source(i)]
1.854 + || !(*_node_filter_map)[Parent::target(i)]))
1.855 + Parent::next(i);
1.856 + }
1.857 +
1.858 + void first(Edge& i) const {
1.859 + Parent::first(i);
1.860 + while (i!=INVALID && (!(*_edge_filter_map)[i]
1.861 + || !(*_node_filter_map)[Parent::u(i)]
1.862 + || !(*_node_filter_map)[Parent::v(i)]))
1.863 + Parent::next(i);
1.864 + }
1.865 +
1.866 + void firstIn(Arc& i, const Node& n) const {
1.867 + Parent::firstIn(i, n);
1.868 + while (i!=INVALID && (!(*_edge_filter_map)[i]
1.869 + || !(*_node_filter_map)[Parent::source(i)]))
1.870 + Parent::nextIn(i);
1.871 + }
1.872 +
1.873 + void firstOut(Arc& i, const Node& n) const {
1.874 + Parent::firstOut(i, n);
1.875 + while (i!=INVALID && (!(*_edge_filter_map)[i]
1.876 + || !(*_node_filter_map)[Parent::target(i)]))
1.877 + Parent::nextOut(i);
1.878 + }
1.879 +
1.880 + void firstInc(Edge& i, bool& d, const Node& n) const {
1.881 + Parent::firstInc(i, d, n);
1.882 + while (i!=INVALID && (!(*_edge_filter_map)[i]
1.883 + || !(*_node_filter_map)[Parent::u(i)]
1.884 + || !(*_node_filter_map)[Parent::v(i)]))
1.885 + Parent::nextInc(i, d);
1.886 + }
1.887 +
1.888 + void next(Node& i) const {
1.889 + Parent::next(i);
1.890 + while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
1.891 + }
1.892 +
1.893 + void next(Arc& i) const {
1.894 + Parent::next(i);
1.895 + while (i!=INVALID && (!(*_edge_filter_map)[i]
1.896 + || !(*_node_filter_map)[Parent::source(i)]
1.897 + || !(*_node_filter_map)[Parent::target(i)]))
1.898 + Parent::next(i);
1.899 + }
1.900 +
1.901 + void next(Edge& i) const {
1.902 + Parent::next(i);
1.903 + while (i!=INVALID && (!(*_edge_filter_map)[i]
1.904 + || !(*_node_filter_map)[Parent::u(i)]
1.905 + || !(*_node_filter_map)[Parent::v(i)]))
1.906 + Parent::next(i);
1.907 + }
1.908 +
1.909 + void nextIn(Arc& i) const {
1.910 + Parent::nextIn(i);
1.911 + while (i!=INVALID && (!(*_edge_filter_map)[i]
1.912 + || !(*_node_filter_map)[Parent::source(i)]))
1.913 + Parent::nextIn(i);
1.914 + }
1.915 +
1.916 + void nextOut(Arc& i) const {
1.917 + Parent::nextOut(i);
1.918 + while (i!=INVALID && (!(*_edge_filter_map)[i]
1.919 + || !(*_node_filter_map)[Parent::target(i)]))
1.920 + Parent::nextOut(i);
1.921 + }
1.922 +
1.923 + void nextInc(Edge& i, bool& d) const {
1.924 + Parent::nextInc(i, d);
1.925 + while (i!=INVALID && (!(*_edge_filter_map)[i]
1.926 + || !(*_node_filter_map)[Parent::u(i)]
1.927 + || !(*_node_filter_map)[Parent::v(i)]))
1.928 + Parent::nextInc(i, d);
1.929 + }
1.930 +
1.931 + void hide(const Node& n) const { _node_filter_map->set(n, false); }
1.932 + void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
1.933 +
1.934 + void unHide(const Node& n) const { _node_filter_map->set(n, true); }
1.935 + void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
1.936 +
1.937 + bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
1.938 + bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
1.939 +
1.940 + typedef False NodeNumTag;
1.941 + typedef False EdgeNumTag;
1.942 +
1.943 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1.944 + Arc findArc(const Node& u, const Node& v,
1.945 + const Arc& prev = INVALID) {
1.946 + if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
1.947 + return INVALID;
1.948 + }
1.949 + Arc arc = Parent::findArc(u, v, prev);
1.950 + while (arc != INVALID && !(*_edge_filter_map)[arc]) {
1.951 + arc = Parent::findArc(u, v, arc);
1.952 + }
1.953 + return arc;
1.954 + }
1.955 + Edge findEdge(const Node& u, const Node& v,
1.956 + const Edge& prev = INVALID) {
1.957 + if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
1.958 + return INVALID;
1.959 + }
1.960 + Edge edge = Parent::findEdge(u, v, prev);
1.961 + while (edge != INVALID && !(*_edge_filter_map)[edge]) {
1.962 + edge = Parent::findEdge(u, v, edge);
1.963 + }
1.964 + return edge;
1.965 + }
1.966 +
1.967 + template <typename _Value>
1.968 + class NodeMap : public SubMapExtender<Adaptor,
1.969 + typename Parent::template NodeMap<_Value> > {
1.970 + public:
1.971 + typedef _Value Value;
1.972 + typedef SubMapExtender<Adaptor, typename Parent::
1.973 + template NodeMap<Value> > MapParent;
1.974 +
1.975 + NodeMap(const Adaptor& adaptor)
1.976 + : MapParent(adaptor) {}
1.977 + NodeMap(const Adaptor& adaptor, const Value& value)
1.978 + : MapParent(adaptor, value) {}
1.979 +
1.980 + private:
1.981 + NodeMap& operator=(const NodeMap& cmap) {
1.982 + return operator=<NodeMap>(cmap);
1.983 + }
1.984 +
1.985 + template <typename CMap>
1.986 + NodeMap& operator=(const CMap& cmap) {
1.987 + MapParent::operator=(cmap);
1.988 + return *this;
1.989 + }
1.990 + };
1.991 +
1.992 + template <typename _Value>
1.993 + class ArcMap : public SubMapExtender<Adaptor,
1.994 + typename Parent::template ArcMap<_Value> > {
1.995 + public:
1.996 + typedef _Value Value;
1.997 + typedef SubMapExtender<Adaptor, typename Parent::
1.998 + template ArcMap<Value> > MapParent;
1.999 +
1.1000 + ArcMap(const Adaptor& adaptor)
1.1001 + : MapParent(adaptor) {}
1.1002 + ArcMap(const Adaptor& adaptor, const Value& value)
1.1003 + : MapParent(adaptor, value) {}
1.1004 +
1.1005 + private:
1.1006 + ArcMap& operator=(const ArcMap& cmap) {
1.1007 + return operator=<ArcMap>(cmap);
1.1008 + }
1.1009 +
1.1010 + template <typename CMap>
1.1011 + ArcMap& operator=(const CMap& cmap) {
1.1012 + MapParent::operator=(cmap);
1.1013 + return *this;
1.1014 + }
1.1015 + };
1.1016 +
1.1017 + template <typename _Value>
1.1018 + class EdgeMap : public SubMapExtender<Adaptor,
1.1019 + typename Parent::template EdgeMap<_Value> > {
1.1020 + public:
1.1021 + typedef _Value Value;
1.1022 + typedef SubMapExtender<Adaptor, typename Parent::
1.1023 + template EdgeMap<Value> > MapParent;
1.1024 +
1.1025 + EdgeMap(const Adaptor& adaptor)
1.1026 + : MapParent(adaptor) {}
1.1027 +
1.1028 + EdgeMap(const Adaptor& adaptor, const Value& value)
1.1029 + : MapParent(adaptor, value) {}
1.1030 +
1.1031 + private:
1.1032 + EdgeMap& operator=(const EdgeMap& cmap) {
1.1033 + return operator=<EdgeMap>(cmap);
1.1034 + }
1.1035 +
1.1036 + template <typename CMap>
1.1037 + EdgeMap& operator=(const CMap& cmap) {
1.1038 + MapParent::operator=(cmap);
1.1039 + return *this;
1.1040 + }
1.1041 + };
1.1042 +
1.1043 + };
1.1044 +
1.1045 + template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
1.1046 + class SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
1.1047 + : public GraphAdaptorBase<_Graph> {
1.1048 + public:
1.1049 + typedef _Graph Graph;
1.1050 + typedef SubGraphBase Adaptor;
1.1051 + typedef GraphAdaptorBase<_Graph> Parent;
1.1052 + protected:
1.1053 + NodeFilterMap* _node_filter_map;
1.1054 + EdgeFilterMap* _edge_filter_map;
1.1055 + SubGraphBase() : Parent(),
1.1056 + _node_filter_map(0), _edge_filter_map(0) { }
1.1057 +
1.1058 + void setNodeFilterMap(NodeFilterMap& node_filter_map) {
1.1059 + _node_filter_map=&node_filter_map;
1.1060 + }
1.1061 + void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
1.1062 + _edge_filter_map=&edge_filter_map;
1.1063 + }
1.1064 +
1.1065 + public:
1.1066 +
1.1067 + typedef typename Parent::Node Node;
1.1068 + typedef typename Parent::Arc Arc;
1.1069 + typedef typename Parent::Edge Edge;
1.1070 +
1.1071 + void first(Node& i) const {
1.1072 + Parent::first(i);
1.1073 + while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
1.1074 + }
1.1075 +
1.1076 + void first(Arc& i) const {
1.1077 + Parent::first(i);
1.1078 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1.1079 + }
1.1080 +
1.1081 + void first(Edge& i) const {
1.1082 + Parent::first(i);
1.1083 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1.1084 + }
1.1085 +
1.1086 + void firstIn(Arc& i, const Node& n) const {
1.1087 + Parent::firstIn(i, n);
1.1088 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
1.1089 + }
1.1090 +
1.1091 + void firstOut(Arc& i, const Node& n) const {
1.1092 + Parent::firstOut(i, n);
1.1093 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
1.1094 + }
1.1095 +
1.1096 + void firstInc(Edge& i, bool& d, const Node& n) const {
1.1097 + Parent::firstInc(i, d, n);
1.1098 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
1.1099 + }
1.1100 +
1.1101 + void next(Node& i) const {
1.1102 + Parent::next(i);
1.1103 + while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
1.1104 + }
1.1105 + void next(Arc& i) const {
1.1106 + Parent::next(i);
1.1107 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1.1108 + }
1.1109 + void next(Edge& i) const {
1.1110 + Parent::next(i);
1.1111 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1.1112 + }
1.1113 + void nextIn(Arc& i) const {
1.1114 + Parent::nextIn(i);
1.1115 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
1.1116 + }
1.1117 +
1.1118 + void nextOut(Arc& i) const {
1.1119 + Parent::nextOut(i);
1.1120 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
1.1121 + }
1.1122 + void nextInc(Edge& i, bool& d) const {
1.1123 + Parent::nextInc(i, d);
1.1124 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
1.1125 + }
1.1126 +
1.1127 + void hide(const Node& n) const { _node_filter_map->set(n, false); }
1.1128 + void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
1.1129 +
1.1130 + void unHide(const Node& n) const { _node_filter_map->set(n, true); }
1.1131 + void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
1.1132 +
1.1133 + bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
1.1134 + bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
1.1135 +
1.1136 + typedef False NodeNumTag;
1.1137 + typedef False EdgeNumTag;
1.1138 +
1.1139 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1.1140 + Arc findArc(const Node& u, const Node& v,
1.1141 + const Arc& prev = INVALID) {
1.1142 + Arc arc = Parent::findArc(u, v, prev);
1.1143 + while (arc != INVALID && !(*_edge_filter_map)[arc]) {
1.1144 + arc = Parent::findArc(u, v, arc);
1.1145 + }
1.1146 + return arc;
1.1147 + }
1.1148 + Edge findEdge(const Node& u, const Node& v,
1.1149 + const Edge& prev = INVALID) {
1.1150 + Edge edge = Parent::findEdge(u, v, prev);
1.1151 + while (edge != INVALID && !(*_edge_filter_map)[edge]) {
1.1152 + edge = Parent::findEdge(u, v, edge);
1.1153 + }
1.1154 + return edge;
1.1155 + }
1.1156 +
1.1157 + template <typename _Value>
1.1158 + class NodeMap : public SubMapExtender<Adaptor,
1.1159 + typename Parent::template NodeMap<_Value> > {
1.1160 + public:
1.1161 + typedef _Value Value;
1.1162 + typedef SubMapExtender<Adaptor, typename Parent::
1.1163 + template NodeMap<Value> > MapParent;
1.1164 +
1.1165 + NodeMap(const Adaptor& adaptor)
1.1166 + : MapParent(adaptor) {}
1.1167 + NodeMap(const Adaptor& adaptor, const Value& value)
1.1168 + : MapParent(adaptor, value) {}
1.1169 +
1.1170 + private:
1.1171 + NodeMap& operator=(const NodeMap& cmap) {
1.1172 + return operator=<NodeMap>(cmap);
1.1173 + }
1.1174 +
1.1175 + template <typename CMap>
1.1176 + NodeMap& operator=(const CMap& cmap) {
1.1177 + MapParent::operator=(cmap);
1.1178 + return *this;
1.1179 + }
1.1180 + };
1.1181 +
1.1182 + template <typename _Value>
1.1183 + class ArcMap : public SubMapExtender<Adaptor,
1.1184 + typename Parent::template ArcMap<_Value> > {
1.1185 + public:
1.1186 + typedef _Value Value;
1.1187 + typedef SubMapExtender<Adaptor, typename Parent::
1.1188 + template ArcMap<Value> > MapParent;
1.1189 +
1.1190 + ArcMap(const Adaptor& adaptor)
1.1191 + : MapParent(adaptor) {}
1.1192 + ArcMap(const Adaptor& adaptor, const Value& value)
1.1193 + : MapParent(adaptor, value) {}
1.1194 +
1.1195 + private:
1.1196 + ArcMap& operator=(const ArcMap& cmap) {
1.1197 + return operator=<ArcMap>(cmap);
1.1198 + }
1.1199 +
1.1200 + template <typename CMap>
1.1201 + ArcMap& operator=(const CMap& cmap) {
1.1202 + MapParent::operator=(cmap);
1.1203 + return *this;
1.1204 + }
1.1205 + };
1.1206 +
1.1207 + template <typename _Value>
1.1208 + class EdgeMap : public SubMapExtender<Adaptor,
1.1209 + typename Parent::template EdgeMap<_Value> > {
1.1210 + public:
1.1211 + typedef _Value Value;
1.1212 + typedef SubMapExtender<Adaptor, typename Parent::
1.1213 + template EdgeMap<Value> > MapParent;
1.1214 +
1.1215 + EdgeMap(const Adaptor& adaptor)
1.1216 + : MapParent(adaptor) {}
1.1217 +
1.1218 + EdgeMap(const Adaptor& adaptor, const _Value& value)
1.1219 + : MapParent(adaptor, value) {}
1.1220 +
1.1221 + private:
1.1222 + EdgeMap& operator=(const EdgeMap& cmap) {
1.1223 + return operator=<EdgeMap>(cmap);
1.1224 + }
1.1225 +
1.1226 + template <typename CMap>
1.1227 + EdgeMap& operator=(const CMap& cmap) {
1.1228 + MapParent::operator=(cmap);
1.1229 + return *this;
1.1230 + }
1.1231 + };
1.1232 +
1.1233 + };
1.1234 +
1.1235 + /// \ingroup graph_adaptors
1.1236 + ///
1.1237 + /// \brief A graph adaptor for hiding nodes and edges in an
1.1238 + /// undirected graph.
1.1239 + ///
1.1240 + /// SubGraph hides nodes and edges in a graph. A bool node map and a
1.1241 + /// bool edge map must be specified, which define the filters for
1.1242 + /// nodes and edges. Just the nodes and edges with true value are
1.1243 + /// shown in the subgraph. The SubGraph is conform to the \ref
1.1244 + /// concepts::Graph "Graph concept". If the \c _checked parameter is
1.1245 + /// true, then the edges incident to filtered nodes are also
1.1246 + /// filtered out.
1.1247 + ///
1.1248 + /// \tparam _Graph It must be conform to the \ref
1.1249 + /// concepts::Graph "Graph concept". The type can be specified
1.1250 + /// to const.
1.1251 + /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
1.1252 + /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted graph.
1.1253 + /// \tparam _checked If the parameter is false then the edge filtering
1.1254 + /// is not checked with respect to node filter. Otherwise, each edge
1.1255 + /// is automatically filtered, which is incident to a filtered node.
1.1256 + ///
1.1257 + /// \see FilterNodes
1.1258 + /// \see FilterEdges
1.1259 + template<typename _Graph, typename NodeFilterMap,
1.1260 + typename EdgeFilterMap, bool _checked = true>
1.1261 + class SubGraph
1.1262 + : public GraphAdaptorExtender<
1.1263 + SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, _checked> > {
1.1264 + public:
1.1265 + typedef _Graph Graph;
1.1266 + typedef GraphAdaptorExtender<
1.1267 + SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
1.1268 +
1.1269 + typedef typename Parent::Node Node;
1.1270 + typedef typename Parent::Edge Edge;
1.1271 +
1.1272 + protected:
1.1273 + SubGraph() { }
1.1274 + public:
1.1275 +
1.1276 + /// \brief Constructor
1.1277 + ///
1.1278 + /// Creates a subgraph for the given graph with given node and
1.1279 + /// edge map filters.
1.1280 + SubGraph(Graph& _graph, NodeFilterMap& node_filter_map,
1.1281 + EdgeFilterMap& edge_filter_map) {
1.1282 + setGraph(_graph);
1.1283 + setNodeFilterMap(node_filter_map);
1.1284 + setEdgeFilterMap(edge_filter_map);
1.1285 + }
1.1286 +
1.1287 + /// \brief Hides the node of the graph
1.1288 + ///
1.1289 + /// This function hides \c n in the graph, i.e. the iteration
1.1290 + /// jumps over it. This is done by simply setting the value of \c n
1.1291 + /// to be false in the corresponding node-map.
1.1292 + void hide(const Node& n) const { Parent::hide(n); }
1.1293 +
1.1294 + /// \brief Hides the edge of the graph
1.1295 + ///
1.1296 + /// This function hides \c e in the graph, i.e. the iteration
1.1297 + /// jumps over it. This is done by simply setting the value of \c e
1.1298 + /// to be false in the corresponding edge-map.
1.1299 + void hide(const Edge& e) const { Parent::hide(e); }
1.1300 +
1.1301 + /// \brief Unhides the node of the graph
1.1302 + ///
1.1303 + /// The value of \c n is set to be true in the node-map which stores
1.1304 + /// hide information. If \c n was hidden previuosly, then it is shown
1.1305 + /// again
1.1306 + void unHide(const Node& n) const { Parent::unHide(n); }
1.1307 +
1.1308 + /// \brief Unhides the edge of the graph
1.1309 + ///
1.1310 + /// The value of \c e is set to be true in the edge-map which stores
1.1311 + /// hide information. If \c e was hidden previuosly, then it is shown
1.1312 + /// again
1.1313 + void unHide(const Edge& e) const { Parent::unHide(e); }
1.1314 +
1.1315 + /// \brief Returns true if \c n is hidden.
1.1316 + ///
1.1317 + /// Returns true if \c n is hidden.
1.1318 + ///
1.1319 + bool hidden(const Node& n) const { return Parent::hidden(n); }
1.1320 +
1.1321 + /// \brief Returns true if \c e is hidden.
1.1322 + ///
1.1323 + /// Returns true if \c e is hidden.
1.1324 + ///
1.1325 + bool hidden(const Edge& e) const { return Parent::hidden(e); }
1.1326 + };
1.1327 +
1.1328 + /// \brief Just gives back a subgraph
1.1329 + ///
1.1330 + /// Just gives back a subgraph
1.1331 + template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1.1332 + SubGraph<const Graph, NodeFilterMap, ArcFilterMap>
1.1333 + subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) {
1.1334 + return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm);
1.1335 + }
1.1336 +
1.1337 + template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1.1338 + SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
1.1339 + subGraph(const Graph& graph,
1.1340 + const NodeFilterMap& nfm, ArcFilterMap& efm) {
1.1341 + return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
1.1342 + (graph, nfm, efm);
1.1343 + }
1.1344 +
1.1345 + template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1.1346 + SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
1.1347 + subGraph(const Graph& graph,
1.1348 + NodeFilterMap& nfm, const ArcFilterMap& efm) {
1.1349 + return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
1.1350 + (graph, nfm, efm);
1.1351 + }
1.1352 +
1.1353 + template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1.1354 + SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
1.1355 + subGraph(const Graph& graph,
1.1356 + const NodeFilterMap& nfm, const ArcFilterMap& efm) {
1.1357 + return SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
1.1358 + (graph, nfm, efm);
1.1359 + }
1.1360 +
1.1361 + /// \ingroup graph_adaptors
1.1362 + ///
1.1363 + /// \brief An adaptor for hiding nodes from a digraph or a graph.
1.1364 + ///
1.1365 + /// FilterNodes adaptor hides nodes in a graph or a digraph. A bool
1.1366 + /// node map must be specified, which defines the filters for
1.1367 + /// nodes. Just the unfiltered nodes and the arcs or edges incident
1.1368 + /// to unfiltered nodes are shown in the subdigraph or subgraph. The
1.1369 + /// FilterNodes is conform to the \ref concepts::Digraph
1.1370 + /// "Digraph concept" or \ref concepts::Graph "Graph concept" depending
1.1371 + /// on the \c _Digraph template parameter. If the \c _checked
1.1372 + /// parameter is true, then the arc or edges incident to filtered nodes
1.1373 + /// are also filtered out.
1.1374 + ///
1.1375 + /// \tparam _Digraph It must be conform to the \ref
1.1376 + /// concepts::Digraph "Digraph concept" or \ref concepts::Graph
1.1377 + /// "Graph concept". The type can be specified to be const.
1.1378 + /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
1.1379 + /// \tparam _checked If the parameter is false then the arc or edge
1.1380 + /// filtering is not checked with respect to node filter. In this
1.1381 + /// case just isolated nodes can be filtered out from the
1.1382 + /// graph.
1.1383 +#ifdef DOXYGEN
1.1384 + template<typename _Digraph,
1.1385 + typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
1.1386 + bool _checked = true>
1.1387 +#else
1.1388 + template<typename _Digraph,
1.1389 + typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
1.1390 + bool _checked = true,
1.1391 + typename Enable = void>
1.1392 +#endif
1.1393 + class FilterNodes
1.1394 + : public SubDigraph<_Digraph, _NodeFilterMap,
1.1395 + ConstMap<typename _Digraph::Arc, bool>, _checked> {
1.1396 + public:
1.1397 +
1.1398 + typedef _Digraph Digraph;
1.1399 + typedef _NodeFilterMap NodeFilterMap;
1.1400 +
1.1401 + typedef SubDigraph<Digraph, NodeFilterMap,
1.1402 + ConstMap<typename Digraph::Arc, bool>, _checked>
1.1403 + Parent;
1.1404 +
1.1405 + typedef typename Parent::Node Node;
1.1406 +
1.1407 + protected:
1.1408 + ConstMap<typename Digraph::Arc, bool> const_true_map;
1.1409 +
1.1410 + FilterNodes() : const_true_map(true) {
1.1411 + Parent::setArcFilterMap(const_true_map);
1.1412 + }
1.1413 +
1.1414 + public:
1.1415 +
1.1416 + /// \brief Constructor
1.1417 + ///
1.1418 + /// Creates an adaptor for the given digraph or graph with
1.1419 + /// given node filter map.
1.1420 + FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) :
1.1421 + Parent(), const_true_map(true) {
1.1422 + Parent::setDigraph(_digraph);
1.1423 + Parent::setNodeFilterMap(node_filter);
1.1424 + Parent::setArcFilterMap(const_true_map);
1.1425 + }
1.1426 +
1.1427 + /// \brief Hides the node of the graph
1.1428 + ///
1.1429 + /// This function hides \c n in the digraph or graph, i.e. the iteration
1.1430 + /// jumps over it. This is done by simply setting the value of \c n
1.1431 + /// to be false in the corresponding node map.
1.1432 + void hide(const Node& n) const { Parent::hide(n); }
1.1433 +
1.1434 + /// \brief Unhides the node of the graph
1.1435 + ///
1.1436 + /// The value of \c n is set to be true in the node-map which stores
1.1437 + /// hide information. If \c n was hidden previuosly, then it is shown
1.1438 + /// again
1.1439 + void unHide(const Node& n) const { Parent::unHide(n); }
1.1440 +
1.1441 + /// \brief Returns true if \c n is hidden.
1.1442 + ///
1.1443 + /// Returns true if \c n is hidden.
1.1444 + ///
1.1445 + bool hidden(const Node& n) const { return Parent::hidden(n); }
1.1446 +
1.1447 + };
1.1448 +
1.1449 + template<typename _Graph, typename _NodeFilterMap, bool _checked>
1.1450 + class FilterNodes<_Graph, _NodeFilterMap, _checked,
1.1451 + typename enable_if<UndirectedTagIndicator<_Graph> >::type>
1.1452 + : public SubGraph<_Graph, _NodeFilterMap,
1.1453 + ConstMap<typename _Graph::Edge, bool>, _checked> {
1.1454 + public:
1.1455 + typedef _Graph Graph;
1.1456 + typedef _NodeFilterMap NodeFilterMap;
1.1457 + typedef SubGraph<Graph, NodeFilterMap,
1.1458 + ConstMap<typename Graph::Edge, bool> > Parent;
1.1459 +
1.1460 + typedef typename Parent::Node Node;
1.1461 + protected:
1.1462 + ConstMap<typename Graph::Edge, bool> const_true_map;
1.1463 +
1.1464 + FilterNodes() : const_true_map(true) {
1.1465 + Parent::setEdgeFilterMap(const_true_map);
1.1466 + }
1.1467 +
1.1468 + public:
1.1469 +
1.1470 + FilterNodes(Graph& _graph, NodeFilterMap& node_filter_map) :
1.1471 + Parent(), const_true_map(true) {
1.1472 + Parent::setGraph(_graph);
1.1473 + Parent::setNodeFilterMap(node_filter_map);
1.1474 + Parent::setEdgeFilterMap(const_true_map);
1.1475 + }
1.1476 +
1.1477 + void hide(const Node& n) const { Parent::hide(n); }
1.1478 + void unHide(const Node& n) const { Parent::unHide(n); }
1.1479 + bool hidden(const Node& n) const { return Parent::hidden(n); }
1.1480 +
1.1481 + };
1.1482 +
1.1483 +
1.1484 + /// \brief Just gives back a FilterNodes adaptor
1.1485 + ///
1.1486 + /// Just gives back a FilterNodes adaptor
1.1487 + template<typename Digraph, typename NodeFilterMap>
1.1488 + FilterNodes<const Digraph, NodeFilterMap>
1.1489 + filterNodes(const Digraph& digraph, NodeFilterMap& nfm) {
1.1490 + return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm);
1.1491 + }
1.1492 +
1.1493 + template<typename Digraph, typename NodeFilterMap>
1.1494 + FilterNodes<const Digraph, const NodeFilterMap>
1.1495 + filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) {
1.1496 + return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm);
1.1497 + }
1.1498 +
1.1499 + /// \ingroup graph_adaptors
1.1500 + ///
1.1501 + /// \brief An adaptor for hiding arcs from a digraph.
1.1502 + ///
1.1503 + /// FilterArcs adaptor hides arcs in a digraph. A bool arc map must
1.1504 + /// be specified, which defines the filters for arcs. Just the
1.1505 + /// unfiltered arcs are shown in the subdigraph. The FilterArcs is
1.1506 + /// conform to the \ref concepts::Digraph "Digraph concept".
1.1507 + ///
1.1508 + /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
1.1509 + /// "Digraph concept". The type can be specified to be const.
1.1510 + /// \tparam _ArcFilterMap A bool valued arc map of the the adapted
1.1511 + /// graph.
1.1512 + template<typename _Digraph, typename _ArcFilterMap>
1.1513 + class FilterArcs :
1.1514 + public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>,
1.1515 + _ArcFilterMap, false> {
1.1516 + public:
1.1517 + typedef _Digraph Digraph;
1.1518 + typedef _ArcFilterMap ArcFilterMap;
1.1519 +
1.1520 + typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>,
1.1521 + ArcFilterMap, false> Parent;
1.1522 +
1.1523 + typedef typename Parent::Arc Arc;
1.1524 +
1.1525 + protected:
1.1526 + ConstMap<typename Digraph::Node, bool> const_true_map;
1.1527 +
1.1528 + FilterArcs() : const_true_map(true) {
1.1529 + Parent::setNodeFilterMap(const_true_map);
1.1530 + }
1.1531 +
1.1532 + public:
1.1533 +
1.1534 + /// \brief Constructor
1.1535 + ///
1.1536 + /// Creates a FilterArcs adaptor for the given graph with
1.1537 + /// given arc map filter.
1.1538 + FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
1.1539 + : Parent(), const_true_map(true) {
1.1540 + Parent::setDigraph(digraph);
1.1541 + Parent::setNodeFilterMap(const_true_map);
1.1542 + Parent::setArcFilterMap(arc_filter);
1.1543 + }
1.1544 +
1.1545 + /// \brief Hides the arc of the graph
1.1546 + ///
1.1547 + /// This function hides \c a in the graph, i.e. the iteration
1.1548 + /// jumps over it. This is done by simply setting the value of \c a
1.1549 + /// to be false in the corresponding arc map.
1.1550 + void hide(const Arc& a) const { Parent::hide(a); }
1.1551 +
1.1552 + /// \brief Unhides the arc of the graph
1.1553 + ///
1.1554 + /// The value of \c a is set to be true in the arc-map which stores
1.1555 + /// hide information. If \c a was hidden previuosly, then it is shown
1.1556 + /// again
1.1557 + void unHide(const Arc& a) const { Parent::unHide(a); }
1.1558 +
1.1559 + /// \brief Returns true if \c a is hidden.
1.1560 + ///
1.1561 + /// Returns true if \c a is hidden.
1.1562 + ///
1.1563 + bool hidden(const Arc& a) const { return Parent::hidden(a); }
1.1564 +
1.1565 + };
1.1566 +
1.1567 + /// \brief Just gives back an FilterArcs adaptor
1.1568 + ///
1.1569 + /// Just gives back an FilterArcs adaptor
1.1570 + template<typename Digraph, typename ArcFilterMap>
1.1571 + FilterArcs<const Digraph, ArcFilterMap>
1.1572 + filterArcs(const Digraph& digraph, ArcFilterMap& afm) {
1.1573 + return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm);
1.1574 + }
1.1575 +
1.1576 + template<typename Digraph, typename ArcFilterMap>
1.1577 + FilterArcs<const Digraph, const ArcFilterMap>
1.1578 + filterArcs(const Digraph& digraph, const ArcFilterMap& afm) {
1.1579 + return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm);
1.1580 + }
1.1581 +
1.1582 + /// \ingroup graph_adaptors
1.1583 + ///
1.1584 + /// \brief An adaptor for hiding edges from a graph.
1.1585 + ///
1.1586 + /// FilterEdges adaptor hides edges in a digraph. A bool edge map must
1.1587 + /// be specified, which defines the filters for edges. Just the
1.1588 + /// unfiltered edges are shown in the subdigraph. The FilterEdges is
1.1589 + /// conform to the \ref concepts::Graph "Graph concept".
1.1590 + ///
1.1591 + /// \tparam _Graph It must be conform to the \ref concepts::Graph
1.1592 + /// "Graph concept". The type can be specified to be const.
1.1593 + /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted
1.1594 + /// graph.
1.1595 + template<typename _Graph, typename _EdgeFilterMap>
1.1596 + class FilterEdges :
1.1597 + public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>,
1.1598 + _EdgeFilterMap, false> {
1.1599 + public:
1.1600 + typedef _Graph Graph;
1.1601 + typedef _EdgeFilterMap EdgeFilterMap;
1.1602 + typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>,
1.1603 + EdgeFilterMap, false> Parent;
1.1604 + typedef typename Parent::Edge Edge;
1.1605 + protected:
1.1606 + ConstMap<typename Graph::Node, bool> const_true_map;
1.1607 +
1.1608 + FilterEdges() : const_true_map(true) {
1.1609 + Parent::setNodeFilterMap(const_true_map);
1.1610 + }
1.1611 +
1.1612 + public:
1.1613 +
1.1614 + /// \brief Constructor
1.1615 + ///
1.1616 + /// Creates a FilterEdges adaptor for the given graph with
1.1617 + /// given edge map filters.
1.1618 + FilterEdges(Graph& _graph, EdgeFilterMap& edge_filter_map) :
1.1619 + Parent(), const_true_map(true) {
1.1620 + Parent::setGraph(_graph);
1.1621 + Parent::setNodeFilterMap(const_true_map);
1.1622 + Parent::setEdgeFilterMap(edge_filter_map);
1.1623 + }
1.1624 +
1.1625 + /// \brief Hides the edge of the graph
1.1626 + ///
1.1627 + /// This function hides \c e in the graph, i.e. the iteration
1.1628 + /// jumps over it. This is done by simply setting the value of \c e
1.1629 + /// to be false in the corresponding edge-map.
1.1630 + void hide(const Edge& e) const { Parent::hide(e); }
1.1631 +
1.1632 + /// \brief Unhides the edge of the graph
1.1633 + ///
1.1634 + /// The value of \c e is set to be true in the edge-map which stores
1.1635 + /// hide information. If \c e was hidden previuosly, then it is shown
1.1636 + /// again
1.1637 + void unHide(const Edge& e) const { Parent::unHide(e); }
1.1638 +
1.1639 + /// \brief Returns true if \c e is hidden.
1.1640 + ///
1.1641 + /// Returns true if \c e is hidden.
1.1642 + ///
1.1643 + bool hidden(const Edge& e) const { return Parent::hidden(e); }
1.1644 +
1.1645 + };
1.1646 +
1.1647 + /// \brief Just gives back a FilterEdges adaptor
1.1648 + ///
1.1649 + /// Just gives back a FilterEdges adaptor
1.1650 + template<typename Graph, typename EdgeFilterMap>
1.1651 + FilterEdges<const Graph, EdgeFilterMap>
1.1652 + filterEdges(const Graph& graph, EdgeFilterMap& efm) {
1.1653 + return FilterEdges<const Graph, EdgeFilterMap>(graph, efm);
1.1654 + }
1.1655 +
1.1656 + template<typename Graph, typename EdgeFilterMap>
1.1657 + FilterEdges<const Graph, const EdgeFilterMap>
1.1658 + filterEdges(const Graph& graph, const EdgeFilterMap& efm) {
1.1659 + return FilterEdges<const Graph, const EdgeFilterMap>(graph, efm);
1.1660 + }
1.1661 +
1.1662 + template <typename _Digraph>
1.1663 + class UndirectorBase {
1.1664 + public:
1.1665 + typedef _Digraph Digraph;
1.1666 + typedef UndirectorBase Adaptor;
1.1667 +
1.1668 + typedef True UndirectedTag;
1.1669 +
1.1670 + typedef typename Digraph::Arc Edge;
1.1671 + typedef typename Digraph::Node Node;
1.1672 +
1.1673 + class Arc : public Edge {
1.1674 + friend class UndirectorBase;
1.1675 + protected:
1.1676 + bool _forward;
1.1677 +
1.1678 + Arc(const Edge& edge, bool forward) :
1.1679 + Edge(edge), _forward(forward) {}
1.1680 +
1.1681 + public:
1.1682 + Arc() {}
1.1683 +
1.1684 + Arc(Invalid) : Edge(INVALID), _forward(true) {}
1.1685 +
1.1686 + bool operator==(const Arc &other) const {
1.1687 + return _forward == other._forward &&
1.1688 + static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
1.1689 + }
1.1690 + bool operator!=(const Arc &other) const {
1.1691 + return _forward != other._forward ||
1.1692 + static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
1.1693 + }
1.1694 + bool operator<(const Arc &other) const {
1.1695 + return _forward < other._forward ||
1.1696 + (_forward == other._forward &&
1.1697 + static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
1.1698 + }
1.1699 + };
1.1700 +
1.1701 +
1.1702 +
1.1703 + void first(Node& n) const {
1.1704 + _digraph->first(n);
1.1705 + }
1.1706 +
1.1707 + void next(Node& n) const {
1.1708 + _digraph->next(n);
1.1709 + }
1.1710 +
1.1711 + void first(Arc& a) const {
1.1712 + _digraph->first(a);
1.1713 + a._forward = true;
1.1714 + }
1.1715 +
1.1716 + void next(Arc& a) const {
1.1717 + if (a._forward) {
1.1718 + a._forward = false;
1.1719 + } else {
1.1720 + _digraph->next(a);
1.1721 + a._forward = true;
1.1722 + }
1.1723 + }
1.1724 +
1.1725 + void first(Edge& e) const {
1.1726 + _digraph->first(e);
1.1727 + }
1.1728 +
1.1729 + void next(Edge& e) const {
1.1730 + _digraph->next(e);
1.1731 + }
1.1732 +
1.1733 + void firstOut(Arc& a, const Node& n) const {
1.1734 + _digraph->firstIn(a, n);
1.1735 + if( static_cast<const Edge&>(a) != INVALID ) {
1.1736 + a._forward = false;
1.1737 + } else {
1.1738 + _digraph->firstOut(a, n);
1.1739 + a._forward = true;
1.1740 + }
1.1741 + }
1.1742 + void nextOut(Arc &a) const {
1.1743 + if (!a._forward) {
1.1744 + Node n = _digraph->target(a);
1.1745 + _digraph->nextIn(a);
1.1746 + if (static_cast<const Edge&>(a) == INVALID ) {
1.1747 + _digraph->firstOut(a, n);
1.1748 + a._forward = true;
1.1749 + }
1.1750 + }
1.1751 + else {
1.1752 + _digraph->nextOut(a);
1.1753 + }
1.1754 + }
1.1755 +
1.1756 + void firstIn(Arc &a, const Node &n) const {
1.1757 + _digraph->firstOut(a, n);
1.1758 + if (static_cast<const Edge&>(a) != INVALID ) {
1.1759 + a._forward = false;
1.1760 + } else {
1.1761 + _digraph->firstIn(a, n);
1.1762 + a._forward = true;
1.1763 + }
1.1764 + }
1.1765 + void nextIn(Arc &a) const {
1.1766 + if (!a._forward) {
1.1767 + Node n = _digraph->source(a);
1.1768 + _digraph->nextOut(a);
1.1769 + if( static_cast<const Edge&>(a) == INVALID ) {
1.1770 + _digraph->firstIn(a, n);
1.1771 + a._forward = true;
1.1772 + }
1.1773 + }
1.1774 + else {
1.1775 + _digraph->nextIn(a);
1.1776 + }
1.1777 + }
1.1778 +
1.1779 + void firstInc(Edge &e, bool &d, const Node &n) const {
1.1780 + d = true;
1.1781 + _digraph->firstOut(e, n);
1.1782 + if (e != INVALID) return;
1.1783 + d = false;
1.1784 + _digraph->firstIn(e, n);
1.1785 + }
1.1786 +
1.1787 + void nextInc(Edge &e, bool &d) const {
1.1788 + if (d) {
1.1789 + Node s = _digraph->source(e);
1.1790 + _digraph->nextOut(e);
1.1791 + if (e != INVALID) return;
1.1792 + d = false;
1.1793 + _digraph->firstIn(e, s);
1.1794 + } else {
1.1795 + _digraph->nextIn(e);
1.1796 + }
1.1797 + }
1.1798 +
1.1799 + Node u(const Edge& e) const {
1.1800 + return _digraph->source(e);
1.1801 + }
1.1802 +
1.1803 + Node v(const Edge& e) const {
1.1804 + return _digraph->target(e);
1.1805 + }
1.1806 +
1.1807 + Node source(const Arc &a) const {
1.1808 + return a._forward ? _digraph->source(a) : _digraph->target(a);
1.1809 + }
1.1810 +
1.1811 + Node target(const Arc &a) const {
1.1812 + return a._forward ? _digraph->target(a) : _digraph->source(a);
1.1813 + }
1.1814 +
1.1815 + static Arc direct(const Edge &e, bool d) {
1.1816 + return Arc(e, d);
1.1817 + }
1.1818 + Arc direct(const Edge &e, const Node& n) const {
1.1819 + return Arc(e, _digraph->source(e) == n);
1.1820 + }
1.1821 +
1.1822 + static bool direction(const Arc &a) { return a._forward; }
1.1823 +
1.1824 + Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
1.1825 + Arc arcFromId(int ix) const {
1.1826 + return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1));
1.1827 + }
1.1828 + Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); }
1.1829 +
1.1830 + int id(const Node &n) const { return _digraph->id(n); }
1.1831 + int id(const Arc &a) const {
1.1832 + return (_digraph->id(a) << 1) | (a._forward ? 1 : 0);
1.1833 + }
1.1834 + int id(const Edge &e) const { return _digraph->id(e); }
1.1835 +
1.1836 + int maxNodeId() const { return _digraph->maxNodeId(); }
1.1837 + int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; }
1.1838 + int maxEdgeId() const { return _digraph->maxArcId(); }
1.1839 +
1.1840 + Node addNode() { return _digraph->addNode(); }
1.1841 + Edge addEdge(const Node& u, const Node& v) {
1.1842 + return _digraph->addArc(u, v);
1.1843 + }
1.1844 +
1.1845 + void erase(const Node& i) { _digraph->erase(i); }
1.1846 + void erase(const Edge& i) { _digraph->erase(i); }
1.1847 +
1.1848 + void clear() { _digraph->clear(); }
1.1849 +
1.1850 + typedef NodeNumTagIndicator<Digraph> NodeNumTag;
1.1851 + int nodeNum() const { return 2 * _digraph->arcNum(); }
1.1852 + typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
1.1853 + int arcNum() const { return 2 * _digraph->arcNum(); }
1.1854 + int edgeNum() const { return _digraph->arcNum(); }
1.1855 +
1.1856 + typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
1.1857 + Arc findArc(Node s, Node t, Arc p = INVALID) const {
1.1858 + if (p == INVALID) {
1.1859 + Edge arc = _digraph->findArc(s, t);
1.1860 + if (arc != INVALID) return direct(arc, true);
1.1861 + arc = _digraph->findArc(t, s);
1.1862 + if (arc != INVALID) return direct(arc, false);
1.1863 + } else if (direction(p)) {
1.1864 + Edge arc = _digraph->findArc(s, t, p);
1.1865 + if (arc != INVALID) return direct(arc, true);
1.1866 + arc = _digraph->findArc(t, s);
1.1867 + if (arc != INVALID) return direct(arc, false);
1.1868 + } else {
1.1869 + Edge arc = _digraph->findArc(t, s, p);
1.1870 + if (arc != INVALID) return direct(arc, false);
1.1871 + }
1.1872 + return INVALID;
1.1873 + }
1.1874 +
1.1875 + Edge findEdge(Node s, Node t, Edge p = INVALID) const {
1.1876 + if (s != t) {
1.1877 + if (p == INVALID) {
1.1878 + Edge arc = _digraph->findArc(s, t);
1.1879 + if (arc != INVALID) return arc;
1.1880 + arc = _digraph->findArc(t, s);
1.1881 + if (arc != INVALID) return arc;
1.1882 + } else if (_digraph->s(p) == s) {
1.1883 + Edge arc = _digraph->findArc(s, t, p);
1.1884 + if (arc != INVALID) return arc;
1.1885 + arc = _digraph->findArc(t, s);
1.1886 + if (arc != INVALID) return arc;
1.1887 + } else {
1.1888 + Edge arc = _digraph->findArc(t, s, p);
1.1889 + if (arc != INVALID) return arc;
1.1890 + }
1.1891 + } else {
1.1892 + return _digraph->findArc(s, t, p);
1.1893 + }
1.1894 + return INVALID;
1.1895 + }
1.1896 +
1.1897 + private:
1.1898 +
1.1899 + template <typename _Value>
1.1900 + class ArcMapBase {
1.1901 + private:
1.1902 +
1.1903 + typedef typename Digraph::template ArcMap<_Value> MapImpl;
1.1904 +
1.1905 + public:
1.1906 +
1.1907 + typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
1.1908 +
1.1909 + typedef _Value Value;
1.1910 + typedef Arc Key;
1.1911 +
1.1912 + ArcMapBase(const Adaptor& adaptor) :
1.1913 + _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
1.1914 +
1.1915 + ArcMapBase(const Adaptor& adaptor, const Value& v)
1.1916 + : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}
1.1917 +
1.1918 + void set(const Arc& a, const Value& v) {
1.1919 + if (direction(a)) {
1.1920 + _forward.set(a, v);
1.1921 + } else {
1.1922 + _backward.set(a, v);
1.1923 + }
1.1924 + }
1.1925 +
1.1926 + typename MapTraits<MapImpl>::ConstReturnValue
1.1927 + operator[](const Arc& a) const {
1.1928 + if (direction(a)) {
1.1929 + return _forward[a];
1.1930 + } else {
1.1931 + return _backward[a];
1.1932 + }
1.1933 + }
1.1934 +
1.1935 + typename MapTraits<MapImpl>::ReturnValue
1.1936 + operator[](const Arc& a) {
1.1937 + if (direction(a)) {
1.1938 + return _forward[a];
1.1939 + } else {
1.1940 + return _backward[a];
1.1941 + }
1.1942 + }
1.1943 +
1.1944 + protected:
1.1945 +
1.1946 + MapImpl _forward, _backward;
1.1947 +
1.1948 + };
1.1949 +
1.1950 + public:
1.1951 +
1.1952 + template <typename _Value>
1.1953 + class NodeMap : public Digraph::template NodeMap<_Value> {
1.1954 + public:
1.1955 +
1.1956 + typedef _Value Value;
1.1957 + typedef typename Digraph::template NodeMap<Value> Parent;
1.1958 +
1.1959 + explicit NodeMap(const Adaptor& adaptor)
1.1960 + : Parent(*adaptor._digraph) {}
1.1961 +
1.1962 + NodeMap(const Adaptor& adaptor, const _Value& value)
1.1963 + : Parent(*adaptor._digraph, value) { }
1.1964 +
1.1965 + private:
1.1966 + NodeMap& operator=(const NodeMap& cmap) {
1.1967 + return operator=<NodeMap>(cmap);
1.1968 + }
1.1969 +
1.1970 + template <typename CMap>
1.1971 + NodeMap& operator=(const CMap& cmap) {
1.1972 + Parent::operator=(cmap);
1.1973 + return *this;
1.1974 + }
1.1975 +
1.1976 + };
1.1977 +
1.1978 + template <typename _Value>
1.1979 + class ArcMap
1.1980 + : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
1.1981 + {
1.1982 + public:
1.1983 + typedef _Value Value;
1.1984 + typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
1.1985 +
1.1986 + ArcMap(const Adaptor& adaptor)
1.1987 + : Parent(adaptor) {}
1.1988 +
1.1989 + ArcMap(const Adaptor& adaptor, const Value& value)
1.1990 + : Parent(adaptor, value) {}
1.1991 +
1.1992 + private:
1.1993 + ArcMap& operator=(const ArcMap& cmap) {
1.1994 + return operator=<ArcMap>(cmap);
1.1995 + }
1.1996 +
1.1997 + template <typename CMap>
1.1998 + ArcMap& operator=(const CMap& cmap) {
1.1999 + Parent::operator=(cmap);
1.2000 + return *this;
1.2001 + }
1.2002 + };
1.2003 +
1.2004 + template <typename _Value>
1.2005 + class EdgeMap : public Digraph::template ArcMap<_Value> {
1.2006 + public:
1.2007 +
1.2008 + typedef _Value Value;
1.2009 + typedef typename Digraph::template ArcMap<Value> Parent;
1.2010 +
1.2011 + explicit EdgeMap(const Adaptor& adaptor)
1.2012 + : Parent(*adaptor._digraph) {}
1.2013 +
1.2014 + EdgeMap(const Adaptor& adaptor, const Value& value)
1.2015 + : Parent(*adaptor._digraph, value) {}
1.2016 +
1.2017 + private:
1.2018 + EdgeMap& operator=(const EdgeMap& cmap) {
1.2019 + return operator=<EdgeMap>(cmap);
1.2020 + }
1.2021 +
1.2022 + template <typename CMap>
1.2023 + EdgeMap& operator=(const CMap& cmap) {
1.2024 + Parent::operator=(cmap);
1.2025 + return *this;
1.2026 + }
1.2027 +
1.2028 + };
1.2029 +
1.2030 + typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
1.2031 + NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
1.2032 +
1.2033 + protected:
1.2034 +
1.2035 + UndirectorBase() : _digraph(0) {}
1.2036 +
1.2037 + Digraph* _digraph;
1.2038 +
1.2039 + void setDigraph(Digraph& digraph) {
1.2040 + _digraph = &digraph;
1.2041 + }
1.2042 +
1.2043 + };
1.2044 +
1.2045 + /// \ingroup graph_adaptors
1.2046 + ///
1.2047 + /// \brief Undirect the graph
1.2048 + ///
1.2049 + /// This adaptor makes an undirected graph from a directed
1.2050 + /// graph. All arcs of the underlying digraph will be showed in the
1.2051 + /// adaptor as an edge. The Orienter adaptor is conform to the \ref
1.2052 + /// concepts::Graph "Graph concept".
1.2053 + ///
1.2054 + /// \tparam _Digraph It must be conform to the \ref
1.2055 + /// concepts::Digraph "Digraph concept". The type can be specified
1.2056 + /// to const.
1.2057 + template<typename _Digraph>
1.2058 + class Undirector
1.2059 + : public GraphAdaptorExtender<UndirectorBase<_Digraph> > {
1.2060 + public:
1.2061 + typedef _Digraph Digraph;
1.2062 + typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent;
1.2063 + protected:
1.2064 + Undirector() { }
1.2065 + public:
1.2066 +
1.2067 + /// \brief Constructor
1.2068 + ///
1.2069 + /// Creates a undirected graph from the given digraph
1.2070 + Undirector(_Digraph& digraph) {
1.2071 + setDigraph(digraph);
1.2072 + }
1.2073 +
1.2074 + /// \brief ArcMap combined from two original ArcMap
1.2075 + ///
1.2076 + /// This class adapts two original digraph ArcMap to
1.2077 + /// get an arc map on the undirected graph.
1.2078 + template <typename _ForwardMap, typename _BackwardMap>
1.2079 + class CombinedArcMap {
1.2080 + public:
1.2081 +
1.2082 + typedef _ForwardMap ForwardMap;
1.2083 + typedef _BackwardMap BackwardMap;
1.2084 +
1.2085 + typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
1.2086 +
1.2087 + typedef typename ForwardMap::Value Value;
1.2088 + typedef typename Parent::Arc Key;
1.2089 +
1.2090 + /// \brief Constructor
1.2091 + ///
1.2092 + /// Constructor
1.2093 + CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
1.2094 + : _forward(&forward), _backward(&backward) {}
1.2095 +
1.2096 +
1.2097 + /// \brief Sets the value associated with a key.
1.2098 + ///
1.2099 + /// Sets the value associated with a key.
1.2100 + void set(const Key& e, const Value& a) {
1.2101 + if (Parent::direction(e)) {
1.2102 + _forward->set(e, a);
1.2103 + } else {
1.2104 + _backward->set(e, a);
1.2105 + }
1.2106 + }
1.2107 +
1.2108 + /// \brief Returns the value associated with a key.
1.2109 + ///
1.2110 + /// Returns the value associated with a key.
1.2111 + typename MapTraits<ForwardMap>::ConstReturnValue
1.2112 + operator[](const Key& e) const {
1.2113 + if (Parent::direction(e)) {
1.2114 + return (*_forward)[e];
1.2115 + } else {
1.2116 + return (*_backward)[e];
1.2117 + }
1.2118 + }
1.2119 +
1.2120 + /// \brief Returns the value associated with a key.
1.2121 + ///
1.2122 + /// Returns the value associated with a key.
1.2123 + typename MapTraits<ForwardMap>::ReturnValue
1.2124 + operator[](const Key& e) {
1.2125 + if (Parent::direction(e)) {
1.2126 + return (*_forward)[e];
1.2127 + } else {
1.2128 + return (*_backward)[e];
1.2129 + }
1.2130 + }
1.2131 +
1.2132 + protected:
1.2133 +
1.2134 + ForwardMap* _forward;
1.2135 + BackwardMap* _backward;
1.2136 +
1.2137 + };
1.2138 +
1.2139 + /// \brief Just gives back a combined arc map
1.2140 + ///
1.2141 + /// Just gives back a combined arc map
1.2142 + template <typename ForwardMap, typename BackwardMap>
1.2143 + static CombinedArcMap<ForwardMap, BackwardMap>
1.2144 + combinedArcMap(ForwardMap& forward, BackwardMap& backward) {
1.2145 + return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward);
1.2146 + }
1.2147 +
1.2148 + template <typename ForwardMap, typename BackwardMap>
1.2149 + static CombinedArcMap<const ForwardMap, BackwardMap>
1.2150 + combinedArcMap(const ForwardMap& forward, BackwardMap& backward) {
1.2151 + return CombinedArcMap<const ForwardMap,
1.2152 + BackwardMap>(forward, backward);
1.2153 + }
1.2154 +
1.2155 + template <typename ForwardMap, typename BackwardMap>
1.2156 + static CombinedArcMap<ForwardMap, const BackwardMap>
1.2157 + combinedArcMap(ForwardMap& forward, const BackwardMap& backward) {
1.2158 + return CombinedArcMap<ForwardMap,
1.2159 + const BackwardMap>(forward, backward);
1.2160 + }
1.2161 +
1.2162 + template <typename ForwardMap, typename BackwardMap>
1.2163 + static CombinedArcMap<const ForwardMap, const BackwardMap>
1.2164 + combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) {
1.2165 + return CombinedArcMap<const ForwardMap,
1.2166 + const BackwardMap>(forward, backward);
1.2167 + }
1.2168 +
1.2169 + };
1.2170 +
1.2171 + /// \brief Just gives back an undirected view of the given digraph
1.2172 + ///
1.2173 + /// Just gives back an undirected view of the given digraph
1.2174 + template<typename Digraph>
1.2175 + Undirector<const Digraph>
1.2176 + undirector(const Digraph& digraph) {
1.2177 + return Undirector<const Digraph>(digraph);
1.2178 + }
1.2179 +
1.2180 + template <typename _Graph, typename _DirectionMap>
1.2181 + class OrienterBase {
1.2182 + public:
1.2183 +
1.2184 + typedef _Graph Graph;
1.2185 + typedef _DirectionMap DirectionMap;
1.2186 +
1.2187 + typedef typename Graph::Node Node;
1.2188 + typedef typename Graph::Edge Arc;
1.2189 +
1.2190 + void reverseArc(const Arc& arc) {
1.2191 + _direction->set(arc, !(*_direction)[arc]);
1.2192 + }
1.2193 +
1.2194 + void first(Node& i) const { _graph->first(i); }
1.2195 + void first(Arc& i) const { _graph->first(i); }
1.2196 + void firstIn(Arc& i, const Node& n) const {
1.2197 + bool d;
1.2198 + _graph->firstInc(i, d, n);
1.2199 + while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
1.2200 + }
1.2201 + void firstOut(Arc& i, const Node& n ) const {
1.2202 + bool d;
1.2203 + _graph->firstInc(i, d, n);
1.2204 + while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
1.2205 + }
1.2206 +
1.2207 + void next(Node& i) const { _graph->next(i); }
1.2208 + void next(Arc& i) const { _graph->next(i); }
1.2209 + void nextIn(Arc& i) const {
1.2210 + bool d = !(*_direction)[i];
1.2211 + _graph->nextInc(i, d);
1.2212 + while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
1.2213 + }
1.2214 + void nextOut(Arc& i) const {
1.2215 + bool d = (*_direction)[i];
1.2216 + _graph->nextInc(i, d);
1.2217 + while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
1.2218 + }
1.2219 +
1.2220 + Node source(const Arc& e) const {
1.2221 + return (*_direction)[e] ? _graph->u(e) : _graph->v(e);
1.2222 + }
1.2223 + Node target(const Arc& e) const {
1.2224 + return (*_direction)[e] ? _graph->v(e) : _graph->u(e);
1.2225 + }
1.2226 +
1.2227 + typedef NodeNumTagIndicator<Graph> NodeNumTag;
1.2228 + int nodeNum() const { return _graph->nodeNum(); }
1.2229 +
1.2230 + typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
1.2231 + int arcNum() const { return _graph->edgeNum(); }
1.2232 +
1.2233 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1.2234 + Arc findArc(const Node& u, const Node& v,
1.2235 + const Arc& prev = INVALID) {
1.2236 + Arc arc = prev;
1.2237 + bool d = arc == INVALID ? true : (*_direction)[arc];
1.2238 + if (d) {
1.2239 + arc = _graph->findEdge(u, v, arc);
1.2240 + while (arc != INVALID && !(*_direction)[arc]) {
1.2241 + _graph->findEdge(u, v, arc);
1.2242 + }
1.2243 + if (arc != INVALID) return arc;
1.2244 + }
1.2245 + _graph->findEdge(v, u, arc);
1.2246 + while (arc != INVALID && (*_direction)[arc]) {
1.2247 + _graph->findEdge(u, v, arc);
1.2248 + }
1.2249 + return arc;
1.2250 + }
1.2251 +
1.2252 + Node addNode() {
1.2253 + return Node(_graph->addNode());
1.2254 + }
1.2255 +
1.2256 + Arc addArc(const Node& u, const Node& v) {
1.2257 + Arc arc = _graph->addArc(u, v);
1.2258 + _direction->set(arc, _graph->source(arc) == u);
1.2259 + return arc;
1.2260 + }
1.2261 +
1.2262 + void erase(const Node& i) { _graph->erase(i); }
1.2263 + void erase(const Arc& i) { _graph->erase(i); }
1.2264 +
1.2265 + void clear() { _graph->clear(); }
1.2266 +
1.2267 + int id(const Node& v) const { return _graph->id(v); }
1.2268 + int id(const Arc& e) const { return _graph->id(e); }
1.2269 +
1.2270 + Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
1.2271 + Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
1.2272 +
1.2273 + int maxNodeId() const { return _graph->maxNodeId(); }
1.2274 + int maxArcId() const { return _graph->maxEdgeId(); }
1.2275 +
1.2276 + typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
1.2277 + NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
1.2278 +
1.2279 + typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
1.2280 + ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
1.2281 +
1.2282 + template <typename _Value>
1.2283 + class NodeMap : public _Graph::template NodeMap<_Value> {
1.2284 + public:
1.2285 +
1.2286 + typedef typename _Graph::template NodeMap<_Value> Parent;
1.2287 +
1.2288 + explicit NodeMap(const OrienterBase& adapter)
1.2289 + : Parent(*adapter._graph) {}
1.2290 +
1.2291 + NodeMap(const OrienterBase& adapter, const _Value& value)
1.2292 + : Parent(*adapter._graph, value) {}
1.2293 +
1.2294 + private:
1.2295 + NodeMap& operator=(const NodeMap& cmap) {
1.2296 + return operator=<NodeMap>(cmap);
1.2297 + }
1.2298 +
1.2299 + template <typename CMap>
1.2300 + NodeMap& operator=(const CMap& cmap) {
1.2301 + Parent::operator=(cmap);
1.2302 + return *this;
1.2303 + }
1.2304 +
1.2305 + };
1.2306 +
1.2307 + template <typename _Value>
1.2308 + class ArcMap : public _Graph::template EdgeMap<_Value> {
1.2309 + public:
1.2310 +
1.2311 + typedef typename Graph::template EdgeMap<_Value> Parent;
1.2312 +
1.2313 + explicit ArcMap(const OrienterBase& adapter)
1.2314 + : Parent(*adapter._graph) { }
1.2315 +
1.2316 + ArcMap(const OrienterBase& adapter, const _Value& value)
1.2317 + : Parent(*adapter._graph, value) { }
1.2318 +
1.2319 + private:
1.2320 + ArcMap& operator=(const ArcMap& cmap) {
1.2321 + return operator=<ArcMap>(cmap);
1.2322 + }
1.2323 +
1.2324 + template <typename CMap>
1.2325 + ArcMap& operator=(const CMap& cmap) {
1.2326 + Parent::operator=(cmap);
1.2327 + return *this;
1.2328 + }
1.2329 + };
1.2330 +
1.2331 +
1.2332 +
1.2333 + protected:
1.2334 + Graph* _graph;
1.2335 + DirectionMap* _direction;
1.2336 +
1.2337 + void setDirectionMap(DirectionMap& direction) {
1.2338 + _direction = &direction;
1.2339 + }
1.2340 +
1.2341 + void setGraph(Graph& graph) {
1.2342 + _graph = &graph;
1.2343 + }
1.2344 +
1.2345 + };
1.2346 +
1.2347 + /// \ingroup graph_adaptors
1.2348 + ///
1.2349 + /// \brief Orients the edges of the graph to get a digraph
1.2350 + ///
1.2351 + /// This adaptor orients each edge in the undirected graph. The
1.2352 + /// direction of the arcs stored in an edge node map. The arcs can
1.2353 + /// be easily reverted by the \c reverseArc() member function in the
1.2354 + /// adaptor. The Orienter adaptor is conform to the \ref
1.2355 + /// concepts::Digraph "Digraph concept".
1.2356 + ///
1.2357 + /// \tparam _Graph It must be conform to the \ref concepts::Graph
1.2358 + /// "Graph concept". The type can be specified to be const.
1.2359 + /// \tparam _DirectionMap A bool valued edge map of the the adapted
1.2360 + /// graph.
1.2361 + ///
1.2362 + /// \sa orienter
1.2363 + template<typename _Graph,
1.2364 + typename DirectionMap = typename _Graph::template EdgeMap<bool> >
1.2365 + class Orienter :
1.2366 + public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > {
1.2367 + public:
1.2368 + typedef _Graph Graph;
1.2369 + typedef DigraphAdaptorExtender<
1.2370 + OrienterBase<_Graph, DirectionMap> > Parent;
1.2371 + typedef typename Parent::Arc Arc;
1.2372 + protected:
1.2373 + Orienter() { }
1.2374 + public:
1.2375 +
1.2376 + /// \brief Constructor of the adaptor
1.2377 + ///
1.2378 + /// Constructor of the adaptor
1.2379 + Orienter(Graph& graph, DirectionMap& direction) {
1.2380 + setGraph(graph);
1.2381 + setDirectionMap(direction);
1.2382 + }
1.2383 +
1.2384 + /// \brief Reverse arc
1.2385 + ///
1.2386 + /// It reverse the given arc. It simply negate the direction in the map.
1.2387 + void reverseArc(const Arc& a) {
1.2388 + Parent::reverseArc(a);
1.2389 + }
1.2390 + };
1.2391 +
1.2392 + /// \brief Just gives back a Orienter
1.2393 + ///
1.2394 + /// Just gives back a Orienter
1.2395 + template<typename Graph, typename DirectionMap>
1.2396 + Orienter<const Graph, DirectionMap>
1.2397 + orienter(const Graph& graph, DirectionMap& dm) {
1.2398 + return Orienter<const Graph, DirectionMap>(graph, dm);
1.2399 + }
1.2400 +
1.2401 + template<typename Graph, typename DirectionMap>
1.2402 + Orienter<const Graph, const DirectionMap>
1.2403 + orienter(const Graph& graph, const DirectionMap& dm) {
1.2404 + return Orienter<const Graph, const DirectionMap>(graph, dm);
1.2405 + }
1.2406 +
1.2407 + namespace _adaptor_bits {
1.2408 +
1.2409 + template<typename _Digraph,
1.2410 + typename _CapacityMap = typename _Digraph::template ArcMap<int>,
1.2411 + typename _FlowMap = _CapacityMap,
1.2412 + typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
1.2413 + class ResForwardFilter {
1.2414 + public:
1.2415 +
1.2416 + typedef _Digraph Digraph;
1.2417 + typedef _CapacityMap CapacityMap;
1.2418 + typedef _FlowMap FlowMap;
1.2419 + typedef _Tolerance Tolerance;
1.2420 +
1.2421 + typedef typename Digraph::Arc Key;
1.2422 + typedef bool Value;
1.2423 +
1.2424 + private:
1.2425 +
1.2426 + const CapacityMap* _capacity;
1.2427 + const FlowMap* _flow;
1.2428 + Tolerance _tolerance;
1.2429 + public:
1.2430 +
1.2431 + ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,
1.2432 + const Tolerance& tolerance = Tolerance())
1.2433 + : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
1.2434 +
1.2435 + bool operator[](const typename Digraph::Arc& a) const {
1.2436 + return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
1.2437 + }
1.2438 + };
1.2439 +
1.2440 + template<typename _Digraph,
1.2441 + typename _CapacityMap = typename _Digraph::template ArcMap<int>,
1.2442 + typename _FlowMap = _CapacityMap,
1.2443 + typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
1.2444 + class ResBackwardFilter {
1.2445 + public:
1.2446 +
1.2447 + typedef _Digraph Digraph;
1.2448 + typedef _CapacityMap CapacityMap;
1.2449 + typedef _FlowMap FlowMap;
1.2450 + typedef _Tolerance Tolerance;
1.2451 +
1.2452 + typedef typename Digraph::Arc Key;
1.2453 + typedef bool Value;
1.2454 +
1.2455 + private:
1.2456 +
1.2457 + const CapacityMap* _capacity;
1.2458 + const FlowMap* _flow;
1.2459 + Tolerance _tolerance;
1.2460 +
1.2461 + public:
1.2462 +
1.2463 + ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,
1.2464 + const Tolerance& tolerance = Tolerance())
1.2465 + : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
1.2466 +
1.2467 + bool operator[](const typename Digraph::Arc& a) const {
1.2468 + return _tolerance.positive((*_flow)[a]);
1.2469 + }
1.2470 + };
1.2471 +
1.2472 + }
1.2473 +
1.2474 + /// \ingroup graph_adaptors
1.2475 + ///
1.2476 + /// \brief An adaptor for composing the residual graph for directed
1.2477 + /// flow and circulation problems.
1.2478 + ///
1.2479 + /// An adaptor for composing the residual graph for directed flow and
1.2480 + /// circulation problems. Let \f$ G=(V, A) \f$ be a directed graph
1.2481 + /// and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
1.2482 + /// be functions on the arc-set.
1.2483 + ///
1.2484 + /// Then Residual implements the digraph structure with
1.2485 + /// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward} \f$,
1.2486 + /// where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
1.2487 + /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so
1.2488 + /// called residual graph. When we take the union
1.2489 + /// \f$ A_{forward}\cup A_{backward} \f$, multiplicities are counted,
1.2490 + /// i.e. if an arc is in both \f$ A_{forward} \f$ and
1.2491 + /// \f$ A_{backward} \f$, then in the adaptor it appears in both
1.2492 + /// orientation.
1.2493 + ///
1.2494 + /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
1.2495 + /// "Digraph concept". The type is implicitly const.
1.2496 + /// \tparam _CapacityMap An arc map of some numeric type, it defines
1.2497 + /// the capacities in the flow problem. The map is implicitly const.
1.2498 + /// \tparam _FlowMap An arc map of some numeric type, it defines
1.2499 + /// the capacities in the flow problem.
1.2500 + /// \tparam _Tolerance Handler for inexact computation.
1.2501 + template<typename _Digraph,
1.2502 + typename _CapacityMap = typename _Digraph::template ArcMap<int>,
1.2503 + typename _FlowMap = _CapacityMap,
1.2504 + typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
1.2505 + class Residual :
1.2506 + public FilterArcs<
1.2507 + Undirector<const _Digraph>,
1.2508 + typename Undirector<const _Digraph>::template CombinedArcMap<
1.2509 + _adaptor_bits::ResForwardFilter<const _Digraph, _CapacityMap,
1.2510 + _FlowMap, _Tolerance>,
1.2511 + _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap,
1.2512 + _FlowMap, _Tolerance> > >
1.2513 + {
1.2514 + public:
1.2515 +
1.2516 + typedef _Digraph Digraph;
1.2517 + typedef _CapacityMap CapacityMap;
1.2518 + typedef _FlowMap FlowMap;
1.2519 + typedef _Tolerance Tolerance;
1.2520 +
1.2521 + typedef typename CapacityMap::Value Value;
1.2522 + typedef Residual Adaptor;
1.2523 +
1.2524 + protected:
1.2525 +
1.2526 + typedef Undirector<const Digraph> Undirected;
1.2527 +
1.2528 + typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap,
1.2529 + FlowMap, Tolerance> ForwardFilter;
1.2530 +
1.2531 + typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap,
1.2532 + FlowMap, Tolerance> BackwardFilter;
1.2533 +
1.2534 + typedef typename Undirected::
1.2535 + template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
1.2536 +
1.2537 + typedef FilterArcs<Undirected, ArcFilter> Parent;
1.2538 +
1.2539 + const CapacityMap* _capacity;
1.2540 + FlowMap* _flow;
1.2541 +
1.2542 + Undirected _graph;
1.2543 + ForwardFilter _forward_filter;
1.2544 + BackwardFilter _backward_filter;
1.2545 + ArcFilter _arc_filter;
1.2546 +
1.2547 + public:
1.2548 +
1.2549 + /// \brief Constructor of the residual digraph.
1.2550 + ///
1.2551 + /// Constructor of the residual graph. The parameters are the digraph,
1.2552 + /// the flow map, the capacity map and a tolerance object.
1.2553 + Residual(const Digraph& digraph, const CapacityMap& capacity,
1.2554 + FlowMap& flow, const Tolerance& tolerance = Tolerance())
1.2555 + : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
1.2556 + _forward_filter(capacity, flow, tolerance),
1.2557 + _backward_filter(capacity, flow, tolerance),
1.2558 + _arc_filter(_forward_filter, _backward_filter)
1.2559 + {
1.2560 + Parent::setDigraph(_graph);
1.2561 + Parent::setArcFilterMap(_arc_filter);
1.2562 + }
1.2563 +
1.2564 + typedef typename Parent::Arc Arc;
1.2565 +
1.2566 + /// \brief Gives back the residual capacity of the arc.
1.2567 + ///
1.2568 + /// Gives back the residual capacity of the arc.
1.2569 + Value residualCapacity(const Arc& a) const {
1.2570 + if (Undirected::direction(a)) {
1.2571 + return (*_capacity)[a] - (*_flow)[a];
1.2572 + } else {
1.2573 + return (*_flow)[a];
1.2574 + }
1.2575 + }
1.2576 +
1.2577 + /// \brief Augment on the given arc in the residual graph.
1.2578 + ///
1.2579 + /// Augment on the given arc in the residual graph. It increase
1.2580 + /// or decrease the flow on the original arc depend on the direction
1.2581 + /// of the residual arc.
1.2582 + void augment(const Arc& a, const Value& v) const {
1.2583 + if (Undirected::direction(a)) {
1.2584 + _flow->set(a, (*_flow)[a] + v);
1.2585 + } else {
1.2586 + _flow->set(a, (*_flow)[a] - v);
1.2587 + }
1.2588 + }
1.2589 +
1.2590 + /// \brief Returns the direction of the arc.
1.2591 + ///
1.2592 + /// Returns true when the arc is same oriented as the original arc.
1.2593 + static bool forward(const Arc& a) {
1.2594 + return Undirected::direction(a);
1.2595 + }
1.2596 +
1.2597 + /// \brief Returns the direction of the arc.
1.2598 + ///
1.2599 + /// Returns true when the arc is opposite oriented as the original arc.
1.2600 + static bool backward(const Arc& a) {
1.2601 + return !Undirected::direction(a);
1.2602 + }
1.2603 +
1.2604 + /// \brief Gives back the forward oriented residual arc.
1.2605 + ///
1.2606 + /// Gives back the forward oriented residual arc.
1.2607 + static Arc forward(const typename Digraph::Arc& a) {
1.2608 + return Undirected::direct(a, true);
1.2609 + }
1.2610 +
1.2611 + /// \brief Gives back the backward oriented residual arc.
1.2612 + ///
1.2613 + /// Gives back the backward oriented residual arc.
1.2614 + static Arc backward(const typename Digraph::Arc& a) {
1.2615 + return Undirected::direct(a, false);
1.2616 + }
1.2617 +
1.2618 + /// \brief Residual capacity map.
1.2619 + ///
1.2620 + /// In generic residual graph the residual capacity can be obtained
1.2621 + /// as a map.
1.2622 + class ResidualCapacity {
1.2623 + protected:
1.2624 + const Adaptor* _adaptor;
1.2625 + public:
1.2626 + /// The Key type
1.2627 + typedef Arc Key;
1.2628 + /// The Value type
1.2629 + typedef typename _CapacityMap::Value Value;
1.2630 +
1.2631 + /// Constructor
1.2632 + ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}
1.2633 +
1.2634 + /// \e
1.2635 + Value operator[](const Arc& a) const {
1.2636 + return _adaptor->residualCapacity(a);
1.2637 + }
1.2638 +
1.2639 + };
1.2640 +
1.2641 + };
1.2642 +
1.2643 + template <typename _Digraph>
1.2644 + class SplitNodesBase {
1.2645 + public:
1.2646 +
1.2647 + typedef _Digraph Digraph;
1.2648 + typedef DigraphAdaptorBase<const _Digraph> Parent;
1.2649 + typedef SplitNodesBase Adaptor;
1.2650 +
1.2651 + typedef typename Digraph::Node DigraphNode;
1.2652 + typedef typename Digraph::Arc DigraphArc;
1.2653 +
1.2654 + class Node;
1.2655 + class Arc;
1.2656 +
1.2657 + private:
1.2658 +
1.2659 + template <typename T> class NodeMapBase;
1.2660 + template <typename T> class ArcMapBase;
1.2661 +
1.2662 + public:
1.2663 +
1.2664 + class Node : public DigraphNode {
1.2665 + friend class SplitNodesBase;
1.2666 + template <typename T> friend class NodeMapBase;
1.2667 + private:
1.2668 +
1.2669 + bool _in;
1.2670 + Node(DigraphNode node, bool in)
1.2671 + : DigraphNode(node), _in(in) {}
1.2672 +
1.2673 + public:
1.2674 +
1.2675 + Node() {}
1.2676 + Node(Invalid) : DigraphNode(INVALID), _in(true) {}
1.2677 +
1.2678 + bool operator==(const Node& node) const {
1.2679 + return DigraphNode::operator==(node) && _in == node._in;
1.2680 + }
1.2681 +
1.2682 + bool operator!=(const Node& node) const {
1.2683 + return !(*this == node);
1.2684 + }
1.2685 +
1.2686 + bool operator<(const Node& node) const {
1.2687 + return DigraphNode::operator<(node) ||
1.2688 + (DigraphNode::operator==(node) && _in < node._in);
1.2689 + }
1.2690 + };
1.2691 +
1.2692 + class Arc {
1.2693 + friend class SplitNodesBase;
1.2694 + template <typename T> friend class ArcMapBase;
1.2695 + private:
1.2696 + typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;
1.2697 +
1.2698 + explicit Arc(const DigraphArc& arc) : _item(arc) {}
1.2699 + explicit Arc(const DigraphNode& node) : _item(node) {}
1.2700 +
1.2701 + ArcImpl _item;
1.2702 +
1.2703 + public:
1.2704 + Arc() {}
1.2705 + Arc(Invalid) : _item(DigraphArc(INVALID)) {}
1.2706 +
1.2707 + bool operator==(const Arc& arc) const {
1.2708 + if (_item.firstState()) {
1.2709 + if (arc._item.firstState()) {
1.2710 + return _item.first() == arc._item.first();
1.2711 + }
1.2712 + } else {
1.2713 + if (arc._item.secondState()) {
1.2714 + return _item.second() == arc._item.second();
1.2715 + }
1.2716 + }
1.2717 + return false;
1.2718 + }
1.2719 +
1.2720 + bool operator!=(const Arc& arc) const {
1.2721 + return !(*this == arc);
1.2722 + }
1.2723 +
1.2724 + bool operator<(const Arc& arc) const {
1.2725 + if (_item.firstState()) {
1.2726 + if (arc._item.firstState()) {
1.2727 + return _item.first() < arc._item.first();
1.2728 + }
1.2729 + return false;
1.2730 + } else {
1.2731 + if (arc._item.secondState()) {
1.2732 + return _item.second() < arc._item.second();
1.2733 + }
1.2734 + return true;
1.2735 + }
1.2736 + }
1.2737 +
1.2738 + operator DigraphArc() const { return _item.first(); }
1.2739 + operator DigraphNode() const { return _item.second(); }
1.2740 +
1.2741 + };
1.2742 +
1.2743 + void first(Node& n) const {
1.2744 + _digraph->first(n);
1.2745 + n._in = true;
1.2746 + }
1.2747 +
1.2748 + void next(Node& n) const {
1.2749 + if (n._in) {
1.2750 + n._in = false;
1.2751 + } else {
1.2752 + n._in = true;
1.2753 + _digraph->next(n);
1.2754 + }
1.2755 + }
1.2756 +
1.2757 + void first(Arc& e) const {
1.2758 + e._item.setSecond();
1.2759 + _digraph->first(e._item.second());
1.2760 + if (e._item.second() == INVALID) {
1.2761 + e._item.setFirst();
1.2762 + _digraph->first(e._item.first());
1.2763 + }
1.2764 + }
1.2765 +
1.2766 + void next(Arc& e) const {
1.2767 + if (e._item.secondState()) {
1.2768 + _digraph->next(e._item.second());
1.2769 + if (e._item.second() == INVALID) {
1.2770 + e._item.setFirst();
1.2771 + _digraph->first(e._item.first());
1.2772 + }
1.2773 + } else {
1.2774 + _digraph->next(e._item.first());
1.2775 + }
1.2776 + }
1.2777 +
1.2778 + void firstOut(Arc& e, const Node& n) const {
1.2779 + if (n._in) {
1.2780 + e._item.setSecond(n);
1.2781 + } else {
1.2782 + e._item.setFirst();
1.2783 + _digraph->firstOut(e._item.first(), n);
1.2784 + }
1.2785 + }
1.2786 +
1.2787 + void nextOut(Arc& e) const {
1.2788 + if (!e._item.firstState()) {
1.2789 + e._item.setFirst(INVALID);
1.2790 + } else {
1.2791 + _digraph->nextOut(e._item.first());
1.2792 + }
1.2793 + }
1.2794 +
1.2795 + void firstIn(Arc& e, const Node& n) const {
1.2796 + if (!n._in) {
1.2797 + e._item.setSecond(n);
1.2798 + } else {
1.2799 + e._item.setFirst();
1.2800 + _digraph->firstIn(e._item.first(), n);
1.2801 + }
1.2802 + }
1.2803 +
1.2804 + void nextIn(Arc& e) const {
1.2805 + if (!e._item.firstState()) {
1.2806 + e._item.setFirst(INVALID);
1.2807 + } else {
1.2808 + _digraph->nextIn(e._item.first());
1.2809 + }
1.2810 + }
1.2811 +
1.2812 + Node source(const Arc& e) const {
1.2813 + if (e._item.firstState()) {
1.2814 + return Node(_digraph->source(e._item.first()), false);
1.2815 + } else {
1.2816 + return Node(e._item.second(), true);
1.2817 + }
1.2818 + }
1.2819 +
1.2820 + Node target(const Arc& e) const {
1.2821 + if (e._item.firstState()) {
1.2822 + return Node(_digraph->target(e._item.first()), true);
1.2823 + } else {
1.2824 + return Node(e._item.second(), false);
1.2825 + }
1.2826 + }
1.2827 +
1.2828 + int id(const Node& n) const {
1.2829 + return (_digraph->id(n) << 1) | (n._in ? 0 : 1);
1.2830 + }
1.2831 + Node nodeFromId(int ix) const {
1.2832 + return Node(_digraph->nodeFromId(ix >> 1), (ix & 1) == 0);
1.2833 + }
1.2834 + int maxNodeId() const {
1.2835 + return 2 * _digraph->maxNodeId() + 1;
1.2836 + }
1.2837 +
1.2838 + int id(const Arc& e) const {
1.2839 + if (e._item.firstState()) {
1.2840 + return _digraph->id(e._item.first()) << 1;
1.2841 + } else {
1.2842 + return (_digraph->id(e._item.second()) << 1) | 1;
1.2843 + }
1.2844 + }
1.2845 + Arc arcFromId(int ix) const {
1.2846 + if ((ix & 1) == 0) {
1.2847 + return Arc(_digraph->arcFromId(ix >> 1));
1.2848 + } else {
1.2849 + return Arc(_digraph->nodeFromId(ix >> 1));
1.2850 + }
1.2851 + }
1.2852 + int maxArcId() const {
1.2853 + return std::max(_digraph->maxNodeId() << 1,
1.2854 + (_digraph->maxArcId() << 1) | 1);
1.2855 + }
1.2856 +
1.2857 + static bool inNode(const Node& n) {
1.2858 + return n._in;
1.2859 + }
1.2860 +
1.2861 + static bool outNode(const Node& n) {
1.2862 + return !n._in;
1.2863 + }
1.2864 +
1.2865 + static bool origArc(const Arc& e) {
1.2866 + return e._item.firstState();
1.2867 + }
1.2868 +
1.2869 + static bool bindArc(const Arc& e) {
1.2870 + return e._item.secondState();
1.2871 + }
1.2872 +
1.2873 + static Node inNode(const DigraphNode& n) {
1.2874 + return Node(n, true);
1.2875 + }
1.2876 +
1.2877 + static Node outNode(const DigraphNode& n) {
1.2878 + return Node(n, false);
1.2879 + }
1.2880 +
1.2881 + static Arc arc(const DigraphNode& n) {
1.2882 + return Arc(n);
1.2883 + }
1.2884 +
1.2885 + static Arc arc(const DigraphArc& e) {
1.2886 + return Arc(e);
1.2887 + }
1.2888 +
1.2889 + typedef True NodeNumTag;
1.2890 +
1.2891 + int nodeNum() const {
1.2892 + return 2 * countNodes(*_digraph);
1.2893 + }
1.2894 +
1.2895 + typedef True EdgeNumTag;
1.2896 + int arcNum() const {
1.2897 + return countArcs(*_digraph) + countNodes(*_digraph);
1.2898 + }
1.2899 +
1.2900 + typedef True FindEdgeTag;
1.2901 + Arc findArc(const Node& u, const Node& v,
1.2902 + const Arc& prev = INVALID) const {
1.2903 + if (inNode(u)) {
1.2904 + if (outNode(v)) {
1.2905 + if (static_cast<const DigraphNode&>(u) ==
1.2906 + static_cast<const DigraphNode&>(v) && prev == INVALID) {
1.2907 + return Arc(u);
1.2908 + }
1.2909 + }
1.2910 + } else {
1.2911 + if (inNode(v)) {
1.2912 + return Arc(::lemon::findArc(*_digraph, u, v, prev));
1.2913 + }
1.2914 + }
1.2915 + return INVALID;
1.2916 + }
1.2917 +
1.2918 + private:
1.2919 +
1.2920 + template <typename _Value>
1.2921 + class NodeMapBase
1.2922 + : public MapTraits<typename Parent::template NodeMap<_Value> > {
1.2923 + typedef typename Parent::template NodeMap<_Value> NodeImpl;
1.2924 + public:
1.2925 + typedef Node Key;
1.2926 + typedef _Value Value;
1.2927 +
1.2928 + NodeMapBase(const Adaptor& adaptor)
1.2929 + : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
1.2930 + NodeMapBase(const Adaptor& adaptor, const Value& value)
1.2931 + : _in_map(*adaptor._digraph, value),
1.2932 + _out_map(*adaptor._digraph, value) {}
1.2933 +
1.2934 + void set(const Node& key, const Value& val) {
1.2935 + if (Adaptor::inNode(key)) { _in_map.set(key, val); }
1.2936 + else {_out_map.set(key, val); }
1.2937 + }
1.2938 +
1.2939 + typename MapTraits<NodeImpl>::ReturnValue
1.2940 + operator[](const Node& key) {
1.2941 + if (Adaptor::inNode(key)) { return _in_map[key]; }
1.2942 + else { return _out_map[key]; }
1.2943 + }
1.2944 +
1.2945 + typename MapTraits<NodeImpl>::ConstReturnValue
1.2946 + operator[](const Node& key) const {
1.2947 + if (Adaptor::inNode(key)) { return _in_map[key]; }
1.2948 + else { return _out_map[key]; }
1.2949 + }
1.2950 +
1.2951 + private:
1.2952 + NodeImpl _in_map, _out_map;
1.2953 + };
1.2954 +
1.2955 + template <typename _Value>
1.2956 + class ArcMapBase
1.2957 + : public MapTraits<typename Parent::template ArcMap<_Value> > {
1.2958 + typedef typename Parent::template ArcMap<_Value> ArcImpl;
1.2959 + typedef typename Parent::template NodeMap<_Value> NodeImpl;
1.2960 + public:
1.2961 + typedef Arc Key;
1.2962 + typedef _Value Value;
1.2963 +
1.2964 + ArcMapBase(const Adaptor& adaptor)
1.2965 + : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
1.2966 + ArcMapBase(const Adaptor& adaptor, const Value& value)
1.2967 + : _arc_map(*adaptor._digraph, value),
1.2968 + _node_map(*adaptor._digraph, value) {}
1.2969 +
1.2970 + void set(const Arc& key, const Value& val) {
1.2971 + if (Adaptor::origArc(key)) {
1.2972 + _arc_map.set(key._item.first(), val);
1.2973 + } else {
1.2974 + _node_map.set(key._item.second(), val);
1.2975 + }
1.2976 + }
1.2977 +
1.2978 + typename MapTraits<ArcImpl>::ReturnValue
1.2979 + operator[](const Arc& key) {
1.2980 + if (Adaptor::origArc(key)) {
1.2981 + return _arc_map[key._item.first()];
1.2982 + } else {
1.2983 + return _node_map[key._item.second()];
1.2984 + }
1.2985 + }
1.2986 +
1.2987 + typename MapTraits<ArcImpl>::ConstReturnValue
1.2988 + operator[](const Arc& key) const {
1.2989 + if (Adaptor::origArc(key)) {
1.2990 + return _arc_map[key._item.first()];
1.2991 + } else {
1.2992 + return _node_map[key._item.second()];
1.2993 + }
1.2994 + }
1.2995 +
1.2996 + private:
1.2997 + ArcImpl _arc_map;
1.2998 + NodeImpl _node_map;
1.2999 + };
1.3000 +
1.3001 + public:
1.3002 +
1.3003 + template <typename _Value>
1.3004 + class NodeMap
1.3005 + : public SubMapExtender<Adaptor, NodeMapBase<_Value> >
1.3006 + {
1.3007 + public:
1.3008 + typedef _Value Value;
1.3009 + typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent;
1.3010 +
1.3011 + NodeMap(const Adaptor& adaptor)
1.3012 + : Parent(adaptor) {}
1.3013 +
1.3014 + NodeMap(const Adaptor& adaptor, const Value& value)
1.3015 + : Parent(adaptor, value) {}
1.3016 +
1.3017 + private:
1.3018 + NodeMap& operator=(const NodeMap& cmap) {
1.3019 + return operator=<NodeMap>(cmap);
1.3020 + }
1.3021 +
1.3022 + template <typename CMap>
1.3023 + NodeMap& operator=(const CMap& cmap) {
1.3024 + Parent::operator=(cmap);
1.3025 + return *this;
1.3026 + }
1.3027 + };
1.3028 +
1.3029 + template <typename _Value>
1.3030 + class ArcMap
1.3031 + : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
1.3032 + {
1.3033 + public:
1.3034 + typedef _Value Value;
1.3035 + typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
1.3036 +
1.3037 + ArcMap(const Adaptor& adaptor)
1.3038 + : Parent(adaptor) {}
1.3039 +
1.3040 + ArcMap(const Adaptor& adaptor, const Value& value)
1.3041 + : Parent(adaptor, value) {}
1.3042 +
1.3043 + private:
1.3044 + ArcMap& operator=(const ArcMap& cmap) {
1.3045 + return operator=<ArcMap>(cmap);
1.3046 + }
1.3047 +
1.3048 + template <typename CMap>
1.3049 + ArcMap& operator=(const CMap& cmap) {
1.3050 + Parent::operator=(cmap);
1.3051 + return *this;
1.3052 + }
1.3053 + };
1.3054 +
1.3055 + protected:
1.3056 +
1.3057 + SplitNodesBase() : _digraph(0) {}
1.3058 +
1.3059 + Digraph* _digraph;
1.3060 +
1.3061 + void setDigraph(Digraph& digraph) {
1.3062 + _digraph = &digraph;
1.3063 + }
1.3064 +
1.3065 + };
1.3066 +
1.3067 + /// \ingroup graph_adaptors
1.3068 + ///
1.3069 + /// \brief Split the nodes of a directed graph
1.3070 + ///
1.3071 + /// The SplitNodes adaptor splits each node into an in-node and an
1.3072 + /// out-node. Formaly, the adaptor replaces each \f$ u \f$ node in
1.3073 + /// the digraph with two nodes(namely node \f$ u_{in} \f$ and node
1.3074 + /// \f$ u_{out} \f$). If there is a \f$ (v, u) \f$ arc in the
1.3075 + /// original digraph the new target of the arc will be \f$ u_{in} \f$
1.3076 + /// and similarly the source of the original \f$ (u, v) \f$ arc
1.3077 + /// will be \f$ u_{out} \f$. The adaptor will add for each node in
1.3078 + /// the original digraph an additional arc which connects
1.3079 + /// \f$ (u_{in}, u_{out}) \f$.
1.3080 + ///
1.3081 + /// The aim of this class is to run algorithm with node costs if the
1.3082 + /// algorithm can use directly just arc costs. In this case we should use
1.3083 + /// a \c SplitNodes and set the node cost of the graph to the
1.3084 + /// bind arc in the adapted graph.
1.3085 + ///
1.3086 + /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
1.3087 + /// "Digraph concept". The type can be specified to be const.
1.3088 + template <typename _Digraph>
1.3089 + class SplitNodes
1.3090 + : public DigraphAdaptorExtender<SplitNodesBase<_Digraph> > {
1.3091 + public:
1.3092 + typedef _Digraph Digraph;
1.3093 + typedef DigraphAdaptorExtender<SplitNodesBase<Digraph> > Parent;
1.3094 +
1.3095 + typedef typename Digraph::Node DigraphNode;
1.3096 + typedef typename Digraph::Arc DigraphArc;
1.3097 +
1.3098 + typedef typename Parent::Node Node;
1.3099 + typedef typename Parent::Arc Arc;
1.3100 +
1.3101 + /// \brief Constructor of the adaptor.
1.3102 + ///
1.3103 + /// Constructor of the adaptor.
1.3104 + SplitNodes(Digraph& g) {
1.3105 + Parent::setDigraph(g);
1.3106 + }
1.3107 +
1.3108 + /// \brief Returns true when the node is in-node.
1.3109 + ///
1.3110 + /// Returns true when the node is in-node.
1.3111 + static bool inNode(const Node& n) {
1.3112 + return Parent::inNode(n);
1.3113 + }
1.3114 +
1.3115 + /// \brief Returns true when the node is out-node.
1.3116 + ///
1.3117 + /// Returns true when the node is out-node.
1.3118 + static bool outNode(const Node& n) {
1.3119 + return Parent::outNode(n);
1.3120 + }
1.3121 +
1.3122 + /// \brief Returns true when the arc is arc in the original digraph.
1.3123 + ///
1.3124 + /// Returns true when the arc is arc in the original digraph.
1.3125 + static bool origArc(const Arc& a) {
1.3126 + return Parent::origArc(a);
1.3127 + }
1.3128 +
1.3129 + /// \brief Returns true when the arc binds an in-node and an out-node.
1.3130 + ///
1.3131 + /// Returns true when the arc binds an in-node and an out-node.
1.3132 + static bool bindArc(const Arc& a) {
1.3133 + return Parent::bindArc(a);
1.3134 + }
1.3135 +
1.3136 + /// \brief Gives back the in-node created from the \c node.
1.3137 + ///
1.3138 + /// Gives back the in-node created from the \c node.
1.3139 + static Node inNode(const DigraphNode& n) {
1.3140 + return Parent::inNode(n);
1.3141 + }
1.3142 +
1.3143 + /// \brief Gives back the out-node created from the \c node.
1.3144 + ///
1.3145 + /// Gives back the out-node created from the \c node.
1.3146 + static Node outNode(const DigraphNode& n) {
1.3147 + return Parent::outNode(n);
1.3148 + }
1.3149 +
1.3150 + /// \brief Gives back the arc binds the two part of the node.
1.3151 + ///
1.3152 + /// Gives back the arc binds the two part of the node.
1.3153 + static Arc arc(const DigraphNode& n) {
1.3154 + return Parent::arc(n);
1.3155 + }
1.3156 +
1.3157 + /// \brief Gives back the arc of the original arc.
1.3158 + ///
1.3159 + /// Gives back the arc of the original arc.
1.3160 + static Arc arc(const DigraphArc& a) {
1.3161 + return Parent::arc(a);
1.3162 + }
1.3163 +
1.3164 + /// \brief NodeMap combined from two original NodeMap
1.3165 + ///
1.3166 + /// This class adapt two of the original digraph NodeMap to
1.3167 + /// get a node map on the adapted digraph.
1.3168 + template <typename InNodeMap, typename OutNodeMap>
1.3169 + class CombinedNodeMap {
1.3170 + public:
1.3171 +
1.3172 + typedef Node Key;
1.3173 + typedef typename InNodeMap::Value Value;
1.3174 +
1.3175 + /// \brief Constructor
1.3176 + ///
1.3177 + /// Constructor.
1.3178 + CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
1.3179 + : _in_map(in_map), _out_map(out_map) {}
1.3180 +
1.3181 + /// \brief The subscript operator.
1.3182 + ///
1.3183 + /// The subscript operator.
1.3184 + Value& operator[](const Key& key) {
1.3185 + if (Parent::inNode(key)) {
1.3186 + return _in_map[key];
1.3187 + } else {
1.3188 + return _out_map[key];
1.3189 + }
1.3190 + }
1.3191 +
1.3192 + /// \brief The const subscript operator.
1.3193 + ///
1.3194 + /// The const subscript operator.
1.3195 + Value operator[](const Key& key) const {
1.3196 + if (Parent::inNode(key)) {
1.3197 + return _in_map[key];
1.3198 + } else {
1.3199 + return _out_map[key];
1.3200 + }
1.3201 + }
1.3202 +
1.3203 + /// \brief The setter function of the map.
1.3204 + ///
1.3205 + /// The setter function of the map.
1.3206 + void set(const Key& key, const Value& value) {
1.3207 + if (Parent::inNode(key)) {
1.3208 + _in_map.set(key, value);
1.3209 + } else {
1.3210 + _out_map.set(key, value);
1.3211 + }
1.3212 + }
1.3213 +
1.3214 + private:
1.3215 +
1.3216 + InNodeMap& _in_map;
1.3217 + OutNodeMap& _out_map;
1.3218 +
1.3219 + };
1.3220 +
1.3221 +
1.3222 + /// \brief Just gives back a combined node map
1.3223 + ///
1.3224 + /// Just gives back a combined node map
1.3225 + template <typename InNodeMap, typename OutNodeMap>
1.3226 + static CombinedNodeMap<InNodeMap, OutNodeMap>
1.3227 + combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
1.3228 + return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
1.3229 + }
1.3230 +
1.3231 + template <typename InNodeMap, typename OutNodeMap>
1.3232 + static CombinedNodeMap<const InNodeMap, OutNodeMap>
1.3233 + combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
1.3234 + return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
1.3235 + }
1.3236 +
1.3237 + template <typename InNodeMap, typename OutNodeMap>
1.3238 + static CombinedNodeMap<InNodeMap, const OutNodeMap>
1.3239 + combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
1.3240 + return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
1.3241 + }
1.3242 +
1.3243 + template <typename InNodeMap, typename OutNodeMap>
1.3244 + static CombinedNodeMap<const InNodeMap, const OutNodeMap>
1.3245 + combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
1.3246 + return CombinedNodeMap<const InNodeMap,
1.3247 + const OutNodeMap>(in_map, out_map);
1.3248 + }
1.3249 +
1.3250 + /// \brief ArcMap combined from an original ArcMap and a NodeMap
1.3251 + ///
1.3252 + /// This class adapt an original ArcMap and a NodeMap to get an
1.3253 + /// arc map on the adapted digraph
1.3254 + template <typename DigraphArcMap, typename DigraphNodeMap>
1.3255 + class CombinedArcMap {
1.3256 + public:
1.3257 +
1.3258 + typedef Arc Key;
1.3259 + typedef typename DigraphArcMap::Value Value;
1.3260 +
1.3261 + /// \brief Constructor
1.3262 + ///
1.3263 + /// Constructor.
1.3264 + CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)
1.3265 + : _arc_map(arc_map), _node_map(node_map) {}
1.3266 +
1.3267 + /// \brief The subscript operator.
1.3268 + ///
1.3269 + /// The subscript operator.
1.3270 + void set(const Arc& arc, const Value& val) {
1.3271 + if (Parent::origArc(arc)) {
1.3272 + _arc_map.set(arc, val);
1.3273 + } else {
1.3274 + _node_map.set(arc, val);
1.3275 + }
1.3276 + }
1.3277 +
1.3278 + /// \brief The const subscript operator.
1.3279 + ///
1.3280 + /// The const subscript operator.
1.3281 + Value operator[](const Key& arc) const {
1.3282 + if (Parent::origArc(arc)) {
1.3283 + return _arc_map[arc];
1.3284 + } else {
1.3285 + return _node_map[arc];
1.3286 + }
1.3287 + }
1.3288 +
1.3289 + /// \brief The const subscript operator.
1.3290 + ///
1.3291 + /// The const subscript operator.
1.3292 + Value& operator[](const Key& arc) {
1.3293 + if (Parent::origArc(arc)) {
1.3294 + return _arc_map[arc];
1.3295 + } else {
1.3296 + return _node_map[arc];
1.3297 + }
1.3298 + }
1.3299 +
1.3300 + private:
1.3301 + DigraphArcMap& _arc_map;
1.3302 + DigraphNodeMap& _node_map;
1.3303 + };
1.3304 +
1.3305 + /// \brief Just gives back a combined arc map
1.3306 + ///
1.3307 + /// Just gives back a combined arc map
1.3308 + template <typename DigraphArcMap, typename DigraphNodeMap>
1.3309 + static CombinedArcMap<DigraphArcMap, DigraphNodeMap>
1.3310 + combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
1.3311 + return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map);
1.3312 + }
1.3313 +
1.3314 + template <typename DigraphArcMap, typename DigraphNodeMap>
1.3315 + static CombinedArcMap<const DigraphArcMap, DigraphNodeMap>
1.3316 + combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
1.3317 + return CombinedArcMap<const DigraphArcMap,
1.3318 + DigraphNodeMap>(arc_map, node_map);
1.3319 + }
1.3320 +
1.3321 + template <typename DigraphArcMap, typename DigraphNodeMap>
1.3322 + static CombinedArcMap<DigraphArcMap, const DigraphNodeMap>
1.3323 + combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) {
1.3324 + return CombinedArcMap<DigraphArcMap,
1.3325 + const DigraphNodeMap>(arc_map, node_map);
1.3326 + }
1.3327 +
1.3328 + template <typename DigraphArcMap, typename DigraphNodeMap>
1.3329 + static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap>
1.3330 + combinedArcMap(const DigraphArcMap& arc_map,
1.3331 + const DigraphNodeMap& node_map) {
1.3332 + return CombinedArcMap<const DigraphArcMap,
1.3333 + const DigraphNodeMap>(arc_map, node_map);
1.3334 + }
1.3335 +
1.3336 + };
1.3337 +
1.3338 + /// \brief Just gives back a node splitter
1.3339 + ///
1.3340 + /// Just gives back a node splitter
1.3341 + template<typename Digraph>
1.3342 + SplitNodes<Digraph>
1.3343 + splitNodes(const Digraph& digraph) {
1.3344 + return SplitNodes<Digraph>(digraph);
1.3345 + }
1.3346 +
1.3347 +
1.3348 +} //namespace lemon
1.3349 +
1.3350 +#endif //LEMON_ADAPTORS_H