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