author Alpar Juttner Tue, 02 Dec 2008 15:33:22 +0000 changeset 434 ad483acf1654 parent 429 d8b87e9b90c3 parent 433 6ff53afe98b5 child 435 9afe81e4c543 child 437 6a2a33ad261b child 451 09e416d35896 child 469 d369e885d196 child 522 7f8560cb9d65
Merge
 doc/groups.dox file | annotate | diff | comparison | revisions lemon/Makefile.am file | annotate | diff | comparison | revisions test/Makefile.am file | annotate | diff | comparison | revisions
     1.1 --- a/doc/groups.dox	Tue Dec 02 11:01:48 2008 +0000
1.2 +++ b/doc/groups.dox	Tue Dec 02 15:33:22 2008 +0000
1.3 @@ -62,6 +62,79 @@
1.4  */
1.5
1.6  /**
1.8 +@ingroup graphs
1.9 +\brief This group contains several adaptor classes for digraphs and graphs
1.10 +
1.11 +The main parts of LEMON are the different graph structures, generic
1.12 +graph algorithms, graph concepts which couple these, and graph
1.13 +adaptors. While the previous notions are more or less clear, the
1.14 +latter one needs further explanation. Graph adaptors are graph classes
1.15 +which serve for considering graph structures in different ways.
1.16 +
1.17 +A short example makes this much clearer.  Suppose that we have an
1.18 +instance \c g of a directed graph type say ListDigraph and an algorithm
1.19 +\code
1.20 +template <typename Digraph>
1.21 +int algorithm(const Digraph&);
1.22 +\endcode
1.23 +is needed to run on the reverse oriented graph.  It may be expensive
1.24 +(in time or in memory usage) to copy \c g with the reversed
1.25 +arcs.  In this case, an adaptor class is used, which (according
1.26 +to LEMON digraph concepts) works as a digraph.  The adaptor uses the
1.27 +original digraph structure and digraph operations when methods of the
1.28 +reversed oriented graph are called.  This means that the adaptor have
1.29 +minor memory usage, and do not perform sophisticated algorithmic
1.30 +actions.  The purpose of it is to give a tool for the cases when a
1.31 +graph have to be used in a specific alteration.  If this alteration is
1.32 +obtained by a usual construction like filtering the arc-set or
1.33 +considering a new orientation, then an adaptor is worthwhile to use.
1.34 +To come back to the reverse oriented graph, in this situation
1.35 +\code
1.36 +template<typename Digraph> class ReverseDigraph;
1.37 +\endcode
1.38 +template class can be used. The code looks as follows
1.39 +\code
1.40 +ListDigraph g;
1.41 +ReverseDigraph<ListGraph> rg(g);
1.42 +int result = algorithm(rg);
1.43 +\endcode
1.44 +After running the algorithm, the original graph \c g is untouched.
1.45 +This techniques gives rise to an elegant code, and based on stable
1.46 +graph adaptors, complex algorithms can be implemented easily.
1.47 +
1.48 +In flow, circulation and bipartite matching problems, the residual
1.49 +graph is of particular importance. Combining an adaptor implementing
1.50 +this, shortest path algorithms and minimum mean cycle algorithms,
1.51 +a range of weighted and cardinality optimization algorithms can be
1.52 +obtained. For other examples, the interested user is referred to the
1.53 +detailed documentation of particular adaptors.
1.54 +
1.55 +The behavior of graph adaptors can be very different. Some of them keep
1.56 +capabilities of the original graph while in other cases this would be
1.57 +meaningless. This means that the concepts that they are models of depend
1.58 +on the graph adaptor, and the wrapped graph(s).
1.59 +If an arc of \c rg is deleted, this is carried out by deleting the
1.60 +corresponding arc of \c g, thus the adaptor modifies the original graph.
1.61 +
1.62 +But for a residual graph, this operation has no sense.
1.63 +Let us stand one more example here to simplify your work.
1.65 +\code
1.66 +ReverseDigraph(Digraph& digraph);
1.67 +\endcode
1.68 +This means that in a situation, when a <tt>const ListDigraph&</tt>
1.69 +reference to a graph is given, then it have to be instantiated with
1.70 +<tt>Digraph=const ListDigraph</tt>.
1.71 +\code
1.72 +int algorithm1(const ListDigraph& g) {
1.74 +  return algorithm2(rg);
1.75 +}
1.76 +\endcode
1.77 +*/
1.78 +
1.79 +/**
1.81  @ingroup graphs
1.82  \brief Graph types between real graphs and graph adaptors.

     2.1 --- a/lemon/Makefile.am	Tue Dec 02 11:01:48 2008 +0000
2.2 +++ b/lemon/Makefile.am	Tue Dec 02 15:33:22 2008 +0000
2.3 @@ -16,6 +16,7 @@
2.4  #lemon_libemon_la_LDFLAGS = $(GLPK_LIBS)$(CPLEX_LIBS) $(SOPLEX_LIBS) 2.5 2.6 lemon_HEADERS += \ 2.7 + lemon/adaptors.h \ 2.8 lemon/arg_parser.h \ 2.9 lemon/assert.h \ 2.10 lemon/bfs.h \ 2.11 @@ -60,10 +61,12 @@ 2.12 lemon/bits/bezier.h \ 2.13 lemon/bits/default_map.h \ 2.14 lemon/bits/enable_if.h \ 2.15 + lemon/bits/graph_adaptor_extender.h \ 2.16 lemon/bits/graph_extender.h \ 2.17 lemon/bits/map_extender.h \ 2.18 lemon/bits/path_dump.h \ 2.19 lemon/bits/traits.h \ 2.20 + lemon/bits/variant.h \ 2.21 lemon/bits/vector_map.h 2.22 2.23 concept_HEADERS += \   3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 3.2 +++ b/lemon/adaptors.h Tue Dec 02 15:33:22 2008 +0000 3.3 @@ -0,0 +1,3347 @@ 3.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*- 3.5 + * 3.6 + * This file is a part of LEMON, a generic C++ optimization library. 3.7 + * 3.8 + * Copyright (C) 2003-2008 3.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 3.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES). 3.11 + * 3.12 + * Permission to use, modify and distribute this software is granted 3.13 + * provided that this copyright notice appears in all copies. For 3.14 + * precise terms see the accompanying LICENSE file. 3.15 + * 3.16 + * This software is provided "AS IS" with no warranty of any kind, 3.17 + * express or implied, and with no claim as to its suitability for any 3.18 + * purpose. 3.19 + * 3.20 + */ 3.21 + 3.22 +#ifndef LEMON_ADAPTORS_H 3.23 +#define LEMON_ADAPTORS_H 3.24 + 3.25 +/// \ingroup graph_adaptors 3.26 +/// \file 3.27 +/// \brief Several graph adaptors 3.28 +/// 3.29 +/// This file contains several useful adaptors for digraphs and graphs. 3.30 + 3.31 +#include <lemon/core.h> 3.32 +#include <lemon/maps.h> 3.33 +#include <lemon/bits/variant.h> 3.34 + 3.35 +#include <lemon/bits/graph_adaptor_extender.h> 3.36 +#include <lemon/tolerance.h> 3.37 + 3.38 +#include <algorithm> 3.39 + 3.40 +namespace lemon { 3.41 + 3.42 + template<typename _Digraph> 3.43 + class DigraphAdaptorBase { 3.44 + public: 3.45 + typedef _Digraph Digraph; 3.46 + typedef DigraphAdaptorBase Adaptor; 3.47 + typedef Digraph ParentDigraph; 3.48 + 3.49 + protected: 3.50 + Digraph* _digraph; 3.51 + DigraphAdaptorBase() : _digraph(0) { } 3.52 + void setDigraph(Digraph& digraph) { _digraph = &digraph; } 3.53 + 3.54 + public: 3.55 + DigraphAdaptorBase(Digraph& digraph) : _digraph(&digraph) { } 3.56 + 3.57 + typedef typename Digraph::Node Node; 3.58 + typedef typename Digraph::Arc Arc; 3.59 + 3.60 + void first(Node& i) const { _digraph->first(i); } 3.61 + void first(Arc& i) const { _digraph->first(i); } 3.62 + void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); } 3.63 + void firstOut(Arc& i, const Node& n ) const { _digraph->firstOut(i, n); } 3.64 + 3.65 + void next(Node& i) const { _digraph->next(i); } 3.66 + void next(Arc& i) const { _digraph->next(i); } 3.67 + void nextIn(Arc& i) const { _digraph->nextIn(i); } 3.68 + void nextOut(Arc& i) const { _digraph->nextOut(i); } 3.69 + 3.70 + Node source(const Arc& a) const { return _digraph->source(a); } 3.71 + Node target(const Arc& a) const { return _digraph->target(a); } 3.72 + 3.73 + typedef NodeNumTagIndicator<Digraph> NodeNumTag; 3.74 + int nodeNum() const { return _digraph->nodeNum(); } 3.75 + 3.76 + typedef EdgeNumTagIndicator<Digraph> EdgeNumTag; 3.77 + int arcNum() const { return _digraph->arcNum(); } 3.78 + 3.79 + typedef FindEdgeTagIndicator<Digraph> FindEdgeTag; 3.80 + Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) { 3.81 + return _digraph->findArc(u, v, prev); 3.82 + } 3.83 + 3.84 + Node addNode() { return _digraph->addNode(); } 3.85 + Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); } 3.86 + 3.87 + void erase(const Node& n) const { _digraph->erase(n); } 3.88 + void erase(const Arc& a) const { _digraph->erase(a); } 3.89 + 3.90 + void clear() const { _digraph->clear(); } 3.91 + 3.92 + int id(const Node& n) const { return _digraph->id(n); } 3.93 + int id(const Arc& a) const { return _digraph->id(a); } 3.94 + 3.95 + Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); } 3.96 + Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); } 3.97 + 3.98 + int maxNodeId() const { return _digraph->maxNodeId(); } 3.99 + int maxArcId() const { return _digraph->maxArcId(); } 3.100 + 3.101 + typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier; 3.102 + NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); } 3.103 + 3.104 + typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier; 3.105 + ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); } 3.106 + 3.107 + template <typename _Value> 3.108 + class NodeMap : public Digraph::template NodeMap<_Value> { 3.109 + public: 3.110 + 3.111 + typedef typename Digraph::template NodeMap<_Value> Parent; 3.112 + 3.113 + explicit NodeMap(const Adaptor& adaptor) 3.114 + : Parent(*adaptor._digraph) {} 3.115 + 3.116 + NodeMap(const Adaptor& adaptor, const _Value& value) 3.117 + : Parent(*adaptor._digraph, value) { } 3.118 + 3.119 + private: 3.120 + NodeMap& operator=(const NodeMap& cmap) { 3.121 + return operator=<NodeMap>(cmap); 3.122 + } 3.123 + 3.124 + template <typename CMap> 3.125 + NodeMap& operator=(const CMap& cmap) { 3.126 + Parent::operator=(cmap); 3.127 + return *this; 3.128 + } 3.129 + 3.130 + }; 3.131 + 3.132 + template <typename _Value> 3.133 + class ArcMap : public Digraph::template ArcMap<_Value> { 3.134 + public: 3.135 + 3.136 + typedef typename Digraph::template ArcMap<_Value> Parent; 3.137 + 3.138 + explicit ArcMap(const Adaptor& adaptor) 3.139 + : Parent(*adaptor._digraph) {} 3.140 + 3.141 + ArcMap(const Adaptor& adaptor, const _Value& value) 3.142 + : Parent(*adaptor._digraph, value) {} 3.143 + 3.144 + private: 3.145 + ArcMap& operator=(const ArcMap& cmap) { 3.146 + return operator=<ArcMap>(cmap); 3.147 + } 3.148 + 3.149 + template <typename CMap> 3.150 + ArcMap& operator=(const CMap& cmap) { 3.151 + Parent::operator=(cmap); 3.152 + return *this; 3.153 + } 3.154 + 3.155 + }; 3.156 + 3.157 + }; 3.158 + 3.159 + template<typename _Graph> 3.160 + class GraphAdaptorBase { 3.161 + public: 3.162 + typedef _Graph Graph; 3.163 + typedef Graph ParentGraph; 3.164 + 3.165 + protected: 3.166 + Graph* _graph; 3.167 + 3.168 + GraphAdaptorBase() : _graph(0) {} 3.169 + 3.170 + void setGraph(Graph& graph) { _graph = &graph; } 3.171 + 3.172 + public: 3.173 + GraphAdaptorBase(Graph& graph) : _graph(&graph) {} 3.174 + 3.175 + typedef typename Graph::Node Node; 3.176 + typedef typename Graph::Arc Arc; 3.177 + typedef typename Graph::Edge Edge; 3.178 + 3.179 + void first(Node& i) const { _graph->first(i); } 3.180 + void first(Arc& i) const { _graph->first(i); } 3.181 + void first(Edge& i) const { _graph->first(i); } 3.182 + void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); } 3.183 + void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); } 3.184 + void firstInc(Edge &i, bool &d, const Node &n) const { 3.185 + _graph->firstInc(i, d, n); 3.186 + } 3.187 + 3.188 + void next(Node& i) const { _graph->next(i); } 3.189 + void next(Arc& i) const { _graph->next(i); } 3.190 + void next(Edge& i) const { _graph->next(i); } 3.191 + void nextIn(Arc& i) const { _graph->nextIn(i); } 3.192 + void nextOut(Arc& i) const { _graph->nextOut(i); } 3.193 + void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); } 3.194 + 3.195 + Node u(const Edge& e) const { return _graph->u(e); } 3.196 + Node v(const Edge& e) const { return _graph->v(e); } 3.197 + 3.198 + Node source(const Arc& a) const { return _graph->source(a); } 3.199 + Node target(const Arc& a) const { return _graph->target(a); } 3.200 + 3.201 + typedef NodeNumTagIndicator<Graph> NodeNumTag; 3.202 + int nodeNum() const { return _graph->nodeNum(); } 3.203 + 3.204 + typedef EdgeNumTagIndicator<Graph> EdgeNumTag; 3.205 + int arcNum() const { return _graph->arcNum(); } 3.206 + int edgeNum() const { return _graph->edgeNum(); } 3.207 + 3.208 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag; 3.209 + Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) { 3.210 + return _graph->findArc(u, v, prev); 3.211 + } 3.212 + Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) { 3.213 + return _graph->findEdge(u, v, prev); 3.214 + } 3.215 + 3.216 + Node addNode() { return _graph->addNode(); } 3.217 + Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); } 3.218 + 3.219 + void erase(const Node& i) { _graph->erase(i); } 3.220 + void erase(const Edge& i) { _graph->erase(i); } 3.221 + 3.222 + void clear() { _graph->clear(); } 3.223 + 3.224 + bool direction(const Arc& a) const { return _graph->direction(a); } 3.225 + Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); } 3.226 + 3.227 + int id(const Node& v) const { return _graph->id(v); } 3.228 + int id(const Arc& a) const { return _graph->id(a); } 3.229 + int id(const Edge& e) const { return _graph->id(e); } 3.230 + 3.231 + Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); } 3.232 + Arc arcFromId(int ix) const { return _graph->arcFromId(ix); } 3.233 + Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); } 3.234 + 3.235 + int maxNodeId() const { return _graph->maxNodeId(); } 3.236 + int maxArcId() const { return _graph->maxArcId(); } 3.237 + int maxEdgeId() const { return _graph->maxEdgeId(); } 3.238 + 3.239 + typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier; 3.240 + NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); } 3.241 + 3.242 + typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier; 3.243 + ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); } 3.244 + 3.245 + typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier; 3.246 + EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); } 3.247 + 3.248 + template <typename _Value> 3.249 + class NodeMap : public Graph::template NodeMap<_Value> { 3.250 + public: 3.251 + typedef typename Graph::template NodeMap<_Value> Parent; 3.252 + explicit NodeMap(const GraphAdaptorBase<Graph>& adapter) 3.253 + : Parent(*adapter._graph) {} 3.254 + NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value) 3.255 + : Parent(*adapter._graph, value) {} 3.256 + 3.257 + private: 3.258 + NodeMap& operator=(const NodeMap& cmap) { 3.259 + return operator=<NodeMap>(cmap); 3.260 + } 3.261 + 3.262 + template <typename CMap> 3.263 + NodeMap& operator=(const CMap& cmap) { 3.264 + Parent::operator=(cmap); 3.265 + return *this; 3.266 + } 3.267 + 3.268 + }; 3.269 + 3.270 + template <typename _Value> 3.271 + class ArcMap : public Graph::template ArcMap<_Value> { 3.272 + public: 3.273 + typedef typename Graph::template ArcMap<_Value> Parent; 3.274 + explicit ArcMap(const GraphAdaptorBase<Graph>& adapter) 3.275 + : Parent(*adapter._graph) {} 3.276 + ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value) 3.277 + : Parent(*adapter._graph, value) {} 3.278 + 3.279 + private: 3.280 + ArcMap& operator=(const ArcMap& cmap) { 3.281 + return operator=<ArcMap>(cmap); 3.282 + } 3.283 + 3.284 + template <typename CMap> 3.285 + ArcMap& operator=(const CMap& cmap) { 3.286 + Parent::operator=(cmap); 3.287 + return *this; 3.288 + } 3.289 + }; 3.290 + 3.291 + template <typename _Value> 3.292 + class EdgeMap : public Graph::template EdgeMap<_Value> { 3.293 + public: 3.294 + typedef typename Graph::template EdgeMap<_Value> Parent; 3.295 + explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter) 3.296 + : Parent(*adapter._graph) {} 3.297 + EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value) 3.298 + : Parent(*adapter._graph, value) {} 3.299 + 3.300 + private: 3.301 + EdgeMap& operator=(const EdgeMap& cmap) { 3.302 + return operator=<EdgeMap>(cmap); 3.303 + } 3.304 + 3.305 + template <typename CMap> 3.306 + EdgeMap& operator=(const CMap& cmap) { 3.307 + Parent::operator=(cmap); 3.308 + return *this; 3.309 + } 3.310 + }; 3.311 + 3.312 + }; 3.313 + 3.314 + template <typename _Digraph> 3.315 + class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> { 3.316 + public: 3.317 + typedef _Digraph Digraph; 3.318 + typedef DigraphAdaptorBase<_Digraph> Parent; 3.319 + protected: 3.320 + ReverseDigraphBase() : Parent() { } 3.321 + public: 3.322 + typedef typename Parent::Node Node; 3.323 + typedef typename Parent::Arc Arc; 3.324 + 3.325 + void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); } 3.326 + void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); } 3.327 + 3.328 + void nextIn(Arc& a) const { Parent::nextOut(a); } 3.329 + void nextOut(Arc& a) const { Parent::nextIn(a); } 3.330 + 3.331 + Node source(const Arc& a) const { return Parent::target(a); } 3.332 + Node target(const Arc& a) const { return Parent::source(a); } 3.333 + 3.334 + Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); } 3.335 + 3.336 + typedef FindEdgeTagIndicator<Digraph> FindEdgeTag; 3.337 + Arc findArc(const Node& u, const Node& v, 3.338 + const Arc& prev = INVALID) { 3.339 + return Parent::findArc(v, u, prev); 3.340 + } 3.341 + 3.342 + }; 3.343 + 3.344 + /// \ingroup graph_adaptors 3.345 + /// 3.346 + /// \brief A digraph adaptor which reverses the orientation of the arcs. 3.347 + /// 3.348 + /// ReverseDigraph reverses the arcs in the adapted digraph. The 3.349 + /// SubDigraph is conform to the \ref concepts::Digraph 3.350 + /// "Digraph concept". 3.351 + /// 3.352 + /// \tparam _Digraph It must be conform to the \ref concepts::Digraph 3.353 + /// "Digraph concept". The type can be specified to be const. 3.354 + template<typename _Digraph> 3.355 + class ReverseDigraph : 3.356 + public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > { 3.357 + public: 3.358 + typedef _Digraph Digraph; 3.359 + typedef DigraphAdaptorExtender< 3.360 + ReverseDigraphBase<_Digraph> > Parent; 3.361 + protected: 3.362 + ReverseDigraph() { } 3.363 + public: 3.364 + 3.365 + /// \brief Constructor 3.366 + /// 3.367 + /// Creates a reverse digraph adaptor for the given digraph 3.368 + explicit ReverseDigraph(Digraph& digraph) { 3.369 + Parent::setDigraph(digraph); 3.370 + } 3.371 + }; 3.372 + 3.373 + /// \brief Just gives back a reverse digraph adaptor 3.374 + /// 3.375 + /// Just gives back a reverse digraph adaptor 3.376 + template<typename Digraph> 3.377 + ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) { 3.378 + return ReverseDigraph<const Digraph>(digraph); 3.379 + } 3.380 + 3.381 + template <typename _Digraph, typename _NodeFilterMap, 3.382 + typename _ArcFilterMap, bool _checked = true> 3.383 + class SubDigraphBase : public DigraphAdaptorBase<_Digraph> { 3.384 + public: 3.385 + typedef _Digraph Digraph; 3.386 + typedef _NodeFilterMap NodeFilterMap; 3.387 + typedef _ArcFilterMap ArcFilterMap; 3.388 + 3.389 + typedef SubDigraphBase Adaptor; 3.390 + typedef DigraphAdaptorBase<_Digraph> Parent; 3.391 + protected: 3.392 + NodeFilterMap* _node_filter; 3.393 + ArcFilterMap* _arc_filter; 3.394 + SubDigraphBase() 3.395 + : Parent(), _node_filter(0), _arc_filter(0) { } 3.396 + 3.397 + void setNodeFilterMap(NodeFilterMap& node_filter) { 3.398 + _node_filter = &node_filter; 3.399 + } 3.400 + void setArcFilterMap(ArcFilterMap& arc_filter) { 3.401 + _arc_filter = &arc_filter; 3.402 + } 3.403 + 3.404 + public: 3.405 + 3.406 + typedef typename Parent::Node Node; 3.407 + typedef typename Parent::Arc Arc; 3.408 + 3.409 + void first(Node& i) const { 3.410 + Parent::first(i); 3.411 + while (i != INVALID && !(*_node_filter)[i]) Parent::next(i); 3.412 + } 3.413 + 3.414 + void first(Arc& i) const { 3.415 + Parent::first(i); 3.416 + while (i != INVALID && (!(*_arc_filter)[i] 3.417 + || !(*_node_filter)[Parent::source(i)] 3.418 + || !(*_node_filter)[Parent::target(i)])) 3.419 + Parent::next(i); 3.420 + } 3.421 + 3.422 + void firstIn(Arc& i, const Node& n) const { 3.423 + Parent::firstIn(i, n); 3.424 + while (i != INVALID && (!(*_arc_filter)[i] 3.425 + || !(*_node_filter)[Parent::source(i)])) 3.426 + Parent::nextIn(i); 3.427 + } 3.428 + 3.429 + void firstOut(Arc& i, const Node& n) const { 3.430 + Parent::firstOut(i, n); 3.431 + while (i != INVALID && (!(*_arc_filter)[i] 3.432 + || !(*_node_filter)[Parent::target(i)])) 3.433 + Parent::nextOut(i); 3.434 + } 3.435 + 3.436 + void next(Node& i) const { 3.437 + Parent::next(i); 3.438 + while (i != INVALID && !(*_node_filter)[i]) Parent::next(i); 3.439 + } 3.440 + 3.441 + void next(Arc& i) const { 3.442 + Parent::next(i); 3.443 + while (i != INVALID && (!(*_arc_filter)[i] 3.444 + || !(*_node_filter)[Parent::source(i)] 3.445 + || !(*_node_filter)[Parent::target(i)])) 3.446 + Parent::next(i); 3.447 + } 3.448 + 3.449 + void nextIn(Arc& i) const { 3.450 + Parent::nextIn(i); 3.451 + while (i != INVALID && (!(*_arc_filter)[i] 3.452 + || !(*_node_filter)[Parent::source(i)])) 3.453 + Parent::nextIn(i); 3.454 + } 3.455 + 3.456 + void nextOut(Arc& i) const { 3.457 + Parent::nextOut(i); 3.458 + while (i != INVALID && (!(*_arc_filter)[i] 3.459 + || !(*_node_filter)[Parent::target(i)])) 3.460 + Parent::nextOut(i); 3.461 + } 3.462 + 3.463 + void hide(const Node& n) const { _node_filter->set(n, false); } 3.464 + void hide(const Arc& a) const { _arc_filter->set(a, false); } 3.465 + 3.466 + void unHide(const Node& n) const { _node_filter->set(n, true); } 3.467 + void unHide(const Arc& a) const { _arc_filter->set(a, true); } 3.468 + 3.469 + bool hidden(const Node& n) const { return !(*_node_filter)[n]; } 3.470 + bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; } 3.471 + 3.472 + typedef False NodeNumTag; 3.473 + typedef False EdgeNumTag; 3.474 + 3.475 + typedef FindEdgeTagIndicator<Digraph> FindEdgeTag; 3.476 + Arc findArc(const Node& source, const Node& target, 3.477 + const Arc& prev = INVALID) { 3.478 + if (!(*_node_filter)[source] || !(*_node_filter)[target]) { 3.479 + return INVALID; 3.480 + } 3.481 + Arc arc = Parent::findArc(source, target, prev); 3.482 + while (arc != INVALID && !(*_arc_filter)[arc]) { 3.483 + arc = Parent::findArc(source, target, arc); 3.484 + } 3.485 + return arc; 3.486 + } 3.487 + 3.488 + template <typename _Value> 3.489 + class NodeMap : public SubMapExtender<Adaptor, 3.490 + typename Parent::template NodeMap<_Value> > { 3.491 + public: 3.492 + typedef _Value Value; 3.493 + typedef SubMapExtender<Adaptor, typename Parent:: 3.494 + template NodeMap<Value> > MapParent; 3.495 + 3.496 + NodeMap(const Adaptor& adaptor) 3.497 + : MapParent(adaptor) {} 3.498 + NodeMap(const Adaptor& adaptor, const Value& value) 3.499 + : MapParent(adaptor, value) {} 3.500 + 3.501 + private: 3.502 + NodeMap& operator=(const NodeMap& cmap) { 3.503 + return operator=<NodeMap>(cmap); 3.504 + } 3.505 + 3.506 + template <typename CMap> 3.507 + NodeMap& operator=(const CMap& cmap) { 3.508 + MapParent::operator=(cmap); 3.509 + return *this; 3.510 + } 3.511 + }; 3.512 + 3.513 + template <typename _Value> 3.514 + class ArcMap : public SubMapExtender<Adaptor, 3.515 + typename Parent::template ArcMap<_Value> > { 3.516 + public: 3.517 + typedef _Value Value; 3.518 + typedef SubMapExtender<Adaptor, typename Parent:: 3.519 + template ArcMap<Value> > MapParent; 3.520 + 3.521 + ArcMap(const Adaptor& adaptor) 3.522 + : MapParent(adaptor) {} 3.523 + ArcMap(const Adaptor& adaptor, const Value& value) 3.524 + : MapParent(adaptor, value) {} 3.525 + 3.526 + private: 3.527 + ArcMap& operator=(const ArcMap& cmap) { 3.528 + return operator=<ArcMap>(cmap); 3.529 + } 3.530 + 3.531 + template <typename CMap> 3.532 + ArcMap& operator=(const CMap& cmap) { 3.533 + MapParent::operator=(cmap); 3.534 + return *this; 3.535 + } 3.536 + }; 3.537 + 3.538 + }; 3.539 + 3.540 + template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap> 3.541 + class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false> 3.542 + : public DigraphAdaptorBase<_Digraph> { 3.543 + public: 3.544 + typedef _Digraph Digraph; 3.545 + typedef _NodeFilterMap NodeFilterMap; 3.546 + typedef _ArcFilterMap ArcFilterMap; 3.547 + 3.548 + typedef SubDigraphBase Adaptor; 3.549 + typedef DigraphAdaptorBase<Digraph> Parent; 3.550 + protected: 3.551 + NodeFilterMap* _node_filter; 3.552 + ArcFilterMap* _arc_filter; 3.553 + SubDigraphBase() 3.554 + : Parent(), _node_filter(0), _arc_filter(0) { } 3.555 + 3.556 + void setNodeFilterMap(NodeFilterMap& node_filter) { 3.557 + _node_filter = &node_filter; 3.558 + } 3.559 + void setArcFilterMap(ArcFilterMap& arc_filter) { 3.560 + _arc_filter = &arc_filter; 3.561 + } 3.562 + 3.563 + public: 3.564 + 3.565 + typedef typename Parent::Node Node; 3.566 + typedef typename Parent::Arc Arc; 3.567 + 3.568 + void first(Node& i) const { 3.569 + Parent::first(i); 3.570 + while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); 3.571 + } 3.572 + 3.573 + void first(Arc& i) const { 3.574 + Parent::first(i); 3.575 + while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i); 3.576 + } 3.577 + 3.578 + void firstIn(Arc& i, const Node& n) const { 3.579 + Parent::firstIn(i, n); 3.580 + while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i); 3.581 + } 3.582 + 3.583 + void firstOut(Arc& i, const Node& n) const { 3.584 + Parent::firstOut(i, n); 3.585 + while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i); 3.586 + } 3.587 + 3.588 + void next(Node& i) const { 3.589 + Parent::next(i); 3.590 + while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); 3.591 + } 3.592 + void next(Arc& i) const { 3.593 + Parent::next(i); 3.594 + while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i); 3.595 + } 3.596 + void nextIn(Arc& i) const { 3.597 + Parent::nextIn(i); 3.598 + while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i); 3.599 + } 3.600 + 3.601 + void nextOut(Arc& i) const { 3.602 + Parent::nextOut(i); 3.603 + while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i); 3.604 + } 3.605 + 3.606 + void hide(const Node& n) const { _node_filter->set(n, false); } 3.607 + void hide(const Arc& e) const { _arc_filter->set(e, false); } 3.608 + 3.609 + void unHide(const Node& n) const { _node_filter->set(n, true); } 3.610 + void unHide(const Arc& e) const { _arc_filter->set(e, true); } 3.611 + 3.612 + bool hidden(const Node& n) const { return !(*_node_filter)[n]; } 3.613 + bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; } 3.614 + 3.615 + typedef False NodeNumTag; 3.616 + typedef False EdgeNumTag; 3.617 + 3.618 + typedef FindEdgeTagIndicator<Digraph> FindEdgeTag; 3.619 + Arc findArc(const Node& source, const Node& target, 3.620 + const Arc& prev = INVALID) { 3.621 + if (!(*_node_filter)[source] || !(*_node_filter)[target]) { 3.622 + return INVALID; 3.623 + } 3.624 + Arc arc = Parent::findArc(source, target, prev); 3.625 + while (arc != INVALID && !(*_arc_filter)[arc]) { 3.626 + arc = Parent::findArc(source, target, arc); 3.627 + } 3.628 + return arc; 3.629 + } 3.630 + 3.631 + template <typename _Value> 3.632 + class NodeMap : public SubMapExtender<Adaptor, 3.633 + typename Parent::template NodeMap<_Value> > { 3.634 + public: 3.635 + typedef _Value Value; 3.636 + typedef SubMapExtender<Adaptor, typename Parent:: 3.637 + template NodeMap<Value> > MapParent; 3.638 + 3.639 + NodeMap(const Adaptor& adaptor) 3.640 + : MapParent(adaptor) {} 3.641 + NodeMap(const Adaptor& adaptor, const Value& value) 3.642 + : MapParent(adaptor, value) {} 3.643 + 3.644 + private: 3.645 + NodeMap& operator=(const NodeMap& cmap) { 3.646 + return operator=<NodeMap>(cmap); 3.647 + } 3.648 + 3.649 + template <typename CMap> 3.650 + NodeMap& operator=(const CMap& cmap) { 3.651 + MapParent::operator=(cmap); 3.652 + return *this; 3.653 + } 3.654 + }; 3.655 + 3.656 + template <typename _Value> 3.657 + class ArcMap : public SubMapExtender<Adaptor, 3.658 + typename Parent::template ArcMap<_Value> > { 3.659 + public: 3.660 + typedef _Value Value; 3.661 + typedef SubMapExtender<Adaptor, typename Parent:: 3.662 + template ArcMap<Value> > MapParent; 3.663 + 3.664 + ArcMap(const Adaptor& adaptor) 3.665 + : MapParent(adaptor) {} 3.666 + ArcMap(const Adaptor& adaptor, const Value& value) 3.667 + : MapParent(adaptor, value) {} 3.668 + 3.669 + private: 3.670 + ArcMap& operator=(const ArcMap& cmap) { 3.671 + return operator=<ArcMap>(cmap); 3.672 + } 3.673 + 3.674 + template <typename CMap> 3.675 + ArcMap& operator=(const CMap& cmap) { 3.676 + MapParent::operator=(cmap); 3.677 + return *this; 3.678 + } 3.679 + }; 3.680 + 3.681 + }; 3.682 + 3.683 + /// \ingroup graph_adaptors 3.684 + /// 3.685 + /// \brief An adaptor for hiding nodes and arcs in a digraph 3.686 + /// 3.687 + /// SubDigraph hides nodes and arcs in a digraph. A bool node map 3.688 + /// and a bool arc map must be specified, which define the filters 3.689 + /// for nodes and arcs. Just the nodes and arcs with true value are 3.690 + /// shown in the subdigraph. The SubDigraph is conform to the \ref 3.691 + /// concepts::Digraph "Digraph concept". If the \c _checked parameter 3.692 + /// is true, then the arcs incident to filtered nodes are also 3.693 + /// filtered out. 3.694 + /// 3.695 + /// \tparam _Digraph It must be conform to the \ref 3.696 + /// concepts::Digraph "Digraph concept". The type can be specified 3.697 + /// to const. 3.698 + /// \tparam _NodeFilterMap A bool valued node map of the the adapted digraph. 3.699 + /// \tparam _ArcFilterMap A bool valued arc map of the the adapted digraph. 3.700 + /// \tparam _checked If the parameter is false then the arc filtering 3.701 + /// is not checked with respect to node filter. Otherwise, each arc 3.702 + /// is automatically filtered, which is incident to a filtered node. 3.703 + /// 3.704 + /// \see FilterNodes 3.705 + /// \see FilterArcs 3.706 + template<typename _Digraph, 3.707 + typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, 3.708 + typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>, 3.709 + bool _checked = true> 3.710 + class SubDigraph 3.711 + : public DigraphAdaptorExtender< 3.712 + SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > { 3.713 + public: 3.714 + typedef _Digraph Digraph; 3.715 + typedef _NodeFilterMap NodeFilterMap; 3.716 + typedef _ArcFilterMap ArcFilterMap; 3.717 + 3.718 + typedef DigraphAdaptorExtender< 3.719 + SubDigraphBase<Digraph, NodeFilterMap, ArcFilterMap, _checked> > 3.720 + Parent; 3.721 + 3.722 + typedef typename Parent::Node Node; 3.723 + typedef typename Parent::Arc Arc; 3.724 + 3.725 + protected: 3.726 + SubDigraph() { } 3.727 + public: 3.728 + 3.729 + /// \brief Constructor 3.730 + /// 3.731 + /// Creates a subdigraph for the given digraph with 3.732 + /// given node and arc map filters. 3.733 + SubDigraph(Digraph& digraph, NodeFilterMap& node_filter, 3.734 + ArcFilterMap& arc_filter) { 3.735 + setDigraph(digraph); 3.736 + setNodeFilterMap(node_filter); 3.737 + setArcFilterMap(arc_filter); 3.738 + } 3.739 + 3.740 + /// \brief Hides the node of the graph 3.741 + /// 3.742 + /// This function hides \c n in the digraph, i.e. the iteration 3.743 + /// jumps over it. This is done by simply setting the value of \c n 3.744 + /// to be false in the corresponding node-map. 3.745 + void hide(const Node& n) const { Parent::hide(n); } 3.746 + 3.747 + /// \brief Hides the arc of the graph 3.748 + /// 3.749 + /// This function hides \c a in the digraph, i.e. the iteration 3.750 + /// jumps over it. This is done by simply setting the value of \c a 3.751 + /// to be false in the corresponding arc-map. 3.752 + void hide(const Arc& a) const { Parent::hide(a); } 3.753 + 3.754 + /// \brief Unhides the node of the graph 3.755 + /// 3.756 + /// The value of \c n is set to be true in the node-map which stores 3.757 + /// hide information. If \c n was hidden previuosly, then it is shown 3.758 + /// again 3.759 + void unHide(const Node& n) const { Parent::unHide(n); } 3.760 + 3.761 + /// \brief Unhides the arc of the graph 3.762 + /// 3.763 + /// The value of \c a is set to be true in the arc-map which stores 3.764 + /// hide information. If \c a was hidden previuosly, then it is shown 3.765 + /// again 3.766 + void unHide(const Arc& a) const { Parent::unHide(a); } 3.767 + 3.768 + /// \brief Returns true if \c n is hidden. 3.769 + /// 3.770 + /// Returns true if \c n is hidden. 3.771 + /// 3.772 + bool hidden(const Node& n) const { return Parent::hidden(n); } 3.773 + 3.774 + /// \brief Returns true if \c a is hidden. 3.775 + /// 3.776 + /// Returns true if \c a is hidden. 3.777 + /// 3.778 + bool hidden(const Arc& a) const { return Parent::hidden(a); } 3.779 + 3.780 + }; 3.781 + 3.782 + /// \brief Just gives back a subdigraph 3.783 + /// 3.784 + /// Just gives back a subdigraph 3.785 + template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> 3.786 + SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap> 3.787 + subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) { 3.788 + return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap> 3.789 + (digraph, nfm, afm); 3.790 + } 3.791 + 3.792 + template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> 3.793 + SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap> 3.794 + subDigraph(const Digraph& digraph, 3.795 + const NodeFilterMap& nfm, ArcFilterMap& afm) { 3.796 + return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap> 3.797 + (digraph, nfm, afm); 3.798 + } 3.799 + 3.800 + template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> 3.801 + SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap> 3.802 + subDigraph(const Digraph& digraph, 3.803 + NodeFilterMap& nfm, const ArcFilterMap& afm) { 3.804 + return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap> 3.805 + (digraph, nfm, afm); 3.806 + } 3.807 + 3.808 + template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> 3.809 + SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap> 3.810 + subDigraph(const Digraph& digraph, 3.811 + const NodeFilterMap& nfm, const ArcFilterMap& afm) { 3.812 + return SubDigraph<const Digraph, const NodeFilterMap, 3.813 + const ArcFilterMap>(digraph, nfm, afm); 3.814 + } 3.815 + 3.816 + 3.817 + template <typename _Graph, typename NodeFilterMap, 3.818 + typename EdgeFilterMap, bool _checked = true> 3.819 + class SubGraphBase : public GraphAdaptorBase<_Graph> { 3.820 + public: 3.821 + typedef _Graph Graph; 3.822 + typedef SubGraphBase Adaptor; 3.823 + typedef GraphAdaptorBase<_Graph> Parent; 3.824 + protected: 3.825 + 3.826 + NodeFilterMap* _node_filter_map; 3.827 + EdgeFilterMap* _edge_filter_map; 3.828 + 3.829 + SubGraphBase() 3.830 + : Parent(), _node_filter_map(0), _edge_filter_map(0) { } 3.831 + 3.832 + void setNodeFilterMap(NodeFilterMap& node_filter_map) { 3.833 + _node_filter_map=&node_filter_map; 3.834 + } 3.835 + void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) { 3.836 + _edge_filter_map=&edge_filter_map; 3.837 + } 3.838 + 3.839 + public: 3.840 + 3.841 + typedef typename Parent::Node Node; 3.842 + typedef typename Parent::Arc Arc; 3.843 + typedef typename Parent::Edge Edge; 3.844 + 3.845 + void first(Node& i) const { 3.846 + Parent::first(i); 3.847 + while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); 3.848 + } 3.849 + 3.850 + void first(Arc& i) const { 3.851 + Parent::first(i); 3.852 + while (i!=INVALID && (!(*_edge_filter_map)[i] 3.853 + || !(*_node_filter_map)[Parent::source(i)] 3.854 + || !(*_node_filter_map)[Parent::target(i)])) 3.855 + Parent::next(i); 3.856 + } 3.857 + 3.858 + void first(Edge& i) const { 3.859 + Parent::first(i); 3.860 + while (i!=INVALID && (!(*_edge_filter_map)[i] 3.861 + || !(*_node_filter_map)[Parent::u(i)] 3.862 + || !(*_node_filter_map)[Parent::v(i)])) 3.863 + Parent::next(i); 3.864 + } 3.865 + 3.866 + void firstIn(Arc& i, const Node& n) const { 3.867 + Parent::firstIn(i, n); 3.868 + while (i!=INVALID && (!(*_edge_filter_map)[i] 3.869 + || !(*_node_filter_map)[Parent::source(i)])) 3.870 + Parent::nextIn(i); 3.871 + } 3.872 + 3.873 + void firstOut(Arc& i, const Node& n) const { 3.874 + Parent::firstOut(i, n); 3.875 + while (i!=INVALID && (!(*_edge_filter_map)[i] 3.876 + || !(*_node_filter_map)[Parent::target(i)])) 3.877 + Parent::nextOut(i); 3.878 + } 3.879 + 3.880 + void firstInc(Edge& i, bool& d, const Node& n) const { 3.881 + Parent::firstInc(i, d, n); 3.882 + while (i!=INVALID && (!(*_edge_filter_map)[i] 3.883 + || !(*_node_filter_map)[Parent::u(i)] 3.884 + || !(*_node_filter_map)[Parent::v(i)])) 3.885 + Parent::nextInc(i, d); 3.886 + } 3.887 + 3.888 + void next(Node& i) const { 3.889 + Parent::next(i); 3.890 + while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); 3.891 + } 3.892 + 3.893 + void next(Arc& i) const { 3.894 + Parent::next(i); 3.895 + while (i!=INVALID && (!(*_edge_filter_map)[i] 3.896 + || !(*_node_filter_map)[Parent::source(i)] 3.897 + || !(*_node_filter_map)[Parent::target(i)])) 3.898 + Parent::next(i); 3.899 + } 3.900 + 3.901 + void next(Edge& i) const { 3.902 + Parent::next(i); 3.903 + while (i!=INVALID && (!(*_edge_filter_map)[i] 3.904 + || !(*_node_filter_map)[Parent::u(i)] 3.905 + || !(*_node_filter_map)[Parent::v(i)])) 3.906 + Parent::next(i); 3.907 + } 3.908 + 3.909 + void nextIn(Arc& i) const { 3.910 + Parent::nextIn(i); 3.911 + while (i!=INVALID && (!(*_edge_filter_map)[i] 3.912 + || !(*_node_filter_map)[Parent::source(i)])) 3.913 + Parent::nextIn(i); 3.914 + } 3.915 + 3.916 + void nextOut(Arc& i) const { 3.917 + Parent::nextOut(i); 3.918 + while (i!=INVALID && (!(*_edge_filter_map)[i] 3.919 + || !(*_node_filter_map)[Parent::target(i)])) 3.920 + Parent::nextOut(i); 3.921 + } 3.922 + 3.923 + void nextInc(Edge& i, bool& d) const { 3.924 + Parent::nextInc(i, d); 3.925 + while (i!=INVALID && (!(*_edge_filter_map)[i] 3.926 + || !(*_node_filter_map)[Parent::u(i)] 3.927 + || !(*_node_filter_map)[Parent::v(i)])) 3.928 + Parent::nextInc(i, d); 3.929 + } 3.930 + 3.931 + void hide(const Node& n) const { _node_filter_map->set(n, false); } 3.932 + void hide(const Edge& e) const { _edge_filter_map->set(e, false); } 3.933 + 3.934 + void unHide(const Node& n) const { _node_filter_map->set(n, true); } 3.935 + void unHide(const Edge& e) const { _edge_filter_map->set(e, true); } 3.936 + 3.937 + bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; } 3.938 + bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; } 3.939 + 3.940 + typedef False NodeNumTag; 3.941 + typedef False EdgeNumTag; 3.942 + 3.943 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag; 3.944 + Arc findArc(const Node& u, const Node& v, 3.945 + const Arc& prev = INVALID) { 3.946 + if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) { 3.947 + return INVALID; 3.948 + } 3.949 + Arc arc = Parent::findArc(u, v, prev); 3.950 + while (arc != INVALID && !(*_edge_filter_map)[arc]) { 3.951 + arc = Parent::findArc(u, v, arc); 3.952 + } 3.953 + return arc; 3.954 + } 3.955 + Edge findEdge(const Node& u, const Node& v, 3.956 + const Edge& prev = INVALID) { 3.957 + if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) { 3.958 + return INVALID; 3.959 + } 3.960 + Edge edge = Parent::findEdge(u, v, prev); 3.961 + while (edge != INVALID && !(*_edge_filter_map)[edge]) { 3.962 + edge = Parent::findEdge(u, v, edge); 3.963 + } 3.964 + return edge; 3.965 + } 3.966 + 3.967 + template <typename _Value> 3.968 + class NodeMap : public SubMapExtender<Adaptor, 3.969 + typename Parent::template NodeMap<_Value> > { 3.970 + public: 3.971 + typedef _Value Value; 3.972 + typedef SubMapExtender<Adaptor, typename Parent:: 3.973 + template NodeMap<Value> > MapParent; 3.974 + 3.975 + NodeMap(const Adaptor& adaptor) 3.976 + : MapParent(adaptor) {} 3.977 + NodeMap(const Adaptor& adaptor, const Value& value) 3.978 + : MapParent(adaptor, value) {} 3.979 + 3.980 + private: 3.981 + NodeMap& operator=(const NodeMap& cmap) { 3.982 + return operator=<NodeMap>(cmap); 3.983 + } 3.984 + 3.985 + template <typename CMap> 3.986 + NodeMap& operator=(const CMap& cmap) { 3.987 + MapParent::operator=(cmap); 3.988 + return *this; 3.989 + } 3.990 + }; 3.991 + 3.992 + template <typename _Value> 3.993 + class ArcMap : public SubMapExtender<Adaptor, 3.994 + typename Parent::template ArcMap<_Value> > { 3.995 + public: 3.996 + typedef _Value Value; 3.997 + typedef SubMapExtender<Adaptor, typename Parent:: 3.998 + template ArcMap<Value> > MapParent; 3.999 + 3.1000 + ArcMap(const Adaptor& adaptor) 3.1001 + : MapParent(adaptor) {} 3.1002 + ArcMap(const Adaptor& adaptor, const Value& value) 3.1003 + : MapParent(adaptor, value) {} 3.1004 + 3.1005 + private: 3.1006 + ArcMap& operator=(const ArcMap& cmap) { 3.1007 + return operator=<ArcMap>(cmap); 3.1008 + } 3.1009 + 3.1010 + template <typename CMap> 3.1011 + ArcMap& operator=(const CMap& cmap) { 3.1012 + MapParent::operator=(cmap); 3.1013 + return *this; 3.1014 + } 3.1015 + }; 3.1016 + 3.1017 + template <typename _Value> 3.1018 + class EdgeMap : public SubMapExtender<Adaptor, 3.1019 + typename Parent::template EdgeMap<_Value> > { 3.1020 + public: 3.1021 + typedef _Value Value; 3.1022 + typedef SubMapExtender<Adaptor, typename Parent:: 3.1023 + template EdgeMap<Value> > MapParent; 3.1024 + 3.1025 + EdgeMap(const Adaptor& adaptor) 3.1026 + : MapParent(adaptor) {} 3.1027 + 3.1028 + EdgeMap(const Adaptor& adaptor, const Value& value) 3.1029 + : MapParent(adaptor, value) {} 3.1030 + 3.1031 + private: 3.1032 + EdgeMap& operator=(const EdgeMap& cmap) { 3.1033 + return operator=<EdgeMap>(cmap); 3.1034 + } 3.1035 + 3.1036 + template <typename CMap> 3.1037 + EdgeMap& operator=(const CMap& cmap) { 3.1038 + MapParent::operator=(cmap); 3.1039 + return *this; 3.1040 + } 3.1041 + }; 3.1042 + 3.1043 + }; 3.1044 + 3.1045 + template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap> 3.1046 + class SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, false> 3.1047 + : public GraphAdaptorBase<_Graph> { 3.1048 + public: 3.1049 + typedef _Graph Graph; 3.1050 + typedef SubGraphBase Adaptor; 3.1051 + typedef GraphAdaptorBase<_Graph> Parent; 3.1052 + protected: 3.1053 + NodeFilterMap* _node_filter_map; 3.1054 + EdgeFilterMap* _edge_filter_map; 3.1055 + SubGraphBase() : Parent(), 3.1056 + _node_filter_map(0), _edge_filter_map(0) { } 3.1057 + 3.1058 + void setNodeFilterMap(NodeFilterMap& node_filter_map) { 3.1059 + _node_filter_map=&node_filter_map; 3.1060 + } 3.1061 + void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) { 3.1062 + _edge_filter_map=&edge_filter_map; 3.1063 + } 3.1064 + 3.1065 + public: 3.1066 + 3.1067 + typedef typename Parent::Node Node; 3.1068 + typedef typename Parent::Arc Arc; 3.1069 + typedef typename Parent::Edge Edge; 3.1070 + 3.1071 + void first(Node& i) const { 3.1072 + Parent::first(i); 3.1073 + while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); 3.1074 + } 3.1075 + 3.1076 + void first(Arc& i) const { 3.1077 + Parent::first(i); 3.1078 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); 3.1079 + } 3.1080 + 3.1081 + void first(Edge& i) const { 3.1082 + Parent::first(i); 3.1083 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); 3.1084 + } 3.1085 + 3.1086 + void firstIn(Arc& i, const Node& n) const { 3.1087 + Parent::firstIn(i, n); 3.1088 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i); 3.1089 + } 3.1090 + 3.1091 + void firstOut(Arc& i, const Node& n) const { 3.1092 + Parent::firstOut(i, n); 3.1093 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i); 3.1094 + } 3.1095 + 3.1096 + void firstInc(Edge& i, bool& d, const Node& n) const { 3.1097 + Parent::firstInc(i, d, n); 3.1098 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d); 3.1099 + } 3.1100 + 3.1101 + void next(Node& i) const { 3.1102 + Parent::next(i); 3.1103 + while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); 3.1104 + } 3.1105 + void next(Arc& i) const { 3.1106 + Parent::next(i); 3.1107 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); 3.1108 + } 3.1109 + void next(Edge& i) const { 3.1110 + Parent::next(i); 3.1111 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); 3.1112 + } 3.1113 + void nextIn(Arc& i) const { 3.1114 + Parent::nextIn(i); 3.1115 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i); 3.1116 + } 3.1117 + 3.1118 + void nextOut(Arc& i) const { 3.1119 + Parent::nextOut(i); 3.1120 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i); 3.1121 + } 3.1122 + void nextInc(Edge& i, bool& d) const { 3.1123 + Parent::nextInc(i, d); 3.1124 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d); 3.1125 + } 3.1126 + 3.1127 + void hide(const Node& n) const { _node_filter_map->set(n, false); } 3.1128 + void hide(const Edge& e) const { _edge_filter_map->set(e, false); } 3.1129 + 3.1130 + void unHide(const Node& n) const { _node_filter_map->set(n, true); } 3.1131 + void unHide(const Edge& e) const { _edge_filter_map->set(e, true); } 3.1132 + 3.1133 + bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; } 3.1134 + bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; } 3.1135 + 3.1136 + typedef False NodeNumTag; 3.1137 + typedef False EdgeNumTag; 3.1138 + 3.1139 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag; 3.1140 + Arc findArc(const Node& u, const Node& v, 3.1141 + const Arc& prev = INVALID) { 3.1142 + Arc arc = Parent::findArc(u, v, prev); 3.1143 + while (arc != INVALID && !(*_edge_filter_map)[arc]) { 3.1144 + arc = Parent::findArc(u, v, arc); 3.1145 + } 3.1146 + return arc; 3.1147 + } 3.1148 + Edge findEdge(const Node& u, const Node& v, 3.1149 + const Edge& prev = INVALID) { 3.1150 + Edge edge = Parent::findEdge(u, v, prev); 3.1151 + while (edge != INVALID && !(*_edge_filter_map)[edge]) { 3.1152 + edge = Parent::findEdge(u, v, edge); 3.1153 + } 3.1154 + return edge; 3.1155 + } 3.1156 + 3.1157 + template <typename _Value> 3.1158 + class NodeMap : public SubMapExtender<Adaptor, 3.1159 + typename Parent::template NodeMap<_Value> > { 3.1160 + public: 3.1161 + typedef _Value Value; 3.1162 + typedef SubMapExtender<Adaptor, typename Parent:: 3.1163 + template NodeMap<Value> > MapParent; 3.1164 + 3.1165 + NodeMap(const Adaptor& adaptor) 3.1166 + : MapParent(adaptor) {} 3.1167 + NodeMap(const Adaptor& adaptor, const Value& value) 3.1168 + : MapParent(adaptor, value) {} 3.1169 + 3.1170 + private: 3.1171 + NodeMap& operator=(const NodeMap& cmap) { 3.1172 + return operator=<NodeMap>(cmap); 3.1173 + } 3.1174 + 3.1175 + template <typename CMap> 3.1176 + NodeMap& operator=(const CMap& cmap) { 3.1177 + MapParent::operator=(cmap); 3.1178 + return *this; 3.1179 + } 3.1180 + }; 3.1181 + 3.1182 + template <typename _Value> 3.1183 + class ArcMap : public SubMapExtender<Adaptor, 3.1184 + typename Parent::template ArcMap<_Value> > { 3.1185 + public: 3.1186 + typedef _Value Value; 3.1187 + typedef SubMapExtender<Adaptor, typename Parent:: 3.1188 + template ArcMap<Value> > MapParent; 3.1189 + 3.1190 + ArcMap(const Adaptor& adaptor) 3.1191 + : MapParent(adaptor) {} 3.1192 + ArcMap(const Adaptor& adaptor, const Value& value) 3.1193 + : MapParent(adaptor, value) {} 3.1194 + 3.1195 + private: 3.1196 + ArcMap& operator=(const ArcMap& cmap) { 3.1197 + return operator=<ArcMap>(cmap); 3.1198 + } 3.1199 + 3.1200 + template <typename CMap> 3.1201 + ArcMap& operator=(const CMap& cmap) { 3.1202 + MapParent::operator=(cmap); 3.1203 + return *this; 3.1204 + } 3.1205 + }; 3.1206 + 3.1207 + template <typename _Value> 3.1208 + class EdgeMap : public SubMapExtender<Adaptor, 3.1209 + typename Parent::template EdgeMap<_Value> > { 3.1210 + public: 3.1211 + typedef _Value Value; 3.1212 + typedef SubMapExtender<Adaptor, typename Parent:: 3.1213 + template EdgeMap<Value> > MapParent; 3.1214 + 3.1215 + EdgeMap(const Adaptor& adaptor) 3.1216 + : MapParent(adaptor) {} 3.1217 + 3.1218 + EdgeMap(const Adaptor& adaptor, const _Value& value) 3.1219 + : MapParent(adaptor, value) {} 3.1220 + 3.1221 + private: 3.1222 + EdgeMap& operator=(const EdgeMap& cmap) { 3.1223 + return operator=<EdgeMap>(cmap); 3.1224 + } 3.1225 + 3.1226 + template <typename CMap> 3.1227 + EdgeMap& operator=(const CMap& cmap) { 3.1228 + MapParent::operator=(cmap); 3.1229 + return *this; 3.1230 + } 3.1231 + }; 3.1232 + 3.1233 + }; 3.1234 + 3.1235 + /// \ingroup graph_adaptors 3.1236 + /// 3.1237 + /// \brief A graph adaptor for hiding nodes and edges in an 3.1238 + /// undirected graph. 3.1239 + /// 3.1240 + /// SubGraph hides nodes and edges in a graph. A bool node map and a 3.1241 + /// bool edge map must be specified, which define the filters for 3.1242 + /// nodes and edges. Just the nodes and edges with true value are 3.1243 + /// shown in the subgraph. The SubGraph is conform to the \ref 3.1244 + /// concepts::Graph "Graph concept". If the \c _checked parameter is 3.1245 + /// true, then the edges incident to filtered nodes are also 3.1246 + /// filtered out. 3.1247 + /// 3.1248 + /// \tparam _Graph It must be conform to the \ref 3.1249 + /// concepts::Graph "Graph concept". The type can be specified 3.1250 + /// to const. 3.1251 + /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph. 3.1252 + /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted graph. 3.1253 + /// \tparam _checked If the parameter is false then the edge filtering 3.1254 + /// is not checked with respect to node filter. Otherwise, each edge 3.1255 + /// is automatically filtered, which is incident to a filtered node. 3.1256 + /// 3.1257 + /// \see FilterNodes 3.1258 + /// \see FilterEdges 3.1259 + template<typename _Graph, typename NodeFilterMap, 3.1260 + typename EdgeFilterMap, bool _checked = true> 3.1261 + class SubGraph 3.1262 + : public GraphAdaptorExtender< 3.1263 + SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, _checked> > { 3.1264 + public: 3.1265 + typedef _Graph Graph; 3.1266 + typedef GraphAdaptorExtender< 3.1267 + SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent; 3.1268 + 3.1269 + typedef typename Parent::Node Node; 3.1270 + typedef typename Parent::Edge Edge; 3.1271 + 3.1272 + protected: 3.1273 + SubGraph() { } 3.1274 + public: 3.1275 + 3.1276 + /// \brief Constructor 3.1277 + /// 3.1278 + /// Creates a subgraph for the given graph with given node and 3.1279 + /// edge map filters. 3.1280 + SubGraph(Graph& _graph, NodeFilterMap& node_filter_map, 3.1281 + EdgeFilterMap& edge_filter_map) { 3.1282 + setGraph(_graph); 3.1283 + setNodeFilterMap(node_filter_map); 3.1284 + setEdgeFilterMap(edge_filter_map); 3.1285 + } 3.1286 + 3.1287 + /// \brief Hides the node of the graph 3.1288 + /// 3.1289 + /// This function hides \c n in the graph, i.e. the iteration 3.1290 + /// jumps over it. This is done by simply setting the value of \c n 3.1291 + /// to be false in the corresponding node-map. 3.1292 + void hide(const Node& n) const { Parent::hide(n); } 3.1293 + 3.1294 + /// \brief Hides the edge of the graph 3.1295 + /// 3.1296 + /// This function hides \c e in the graph, i.e. the iteration 3.1297 + /// jumps over it. This is done by simply setting the value of \c e 3.1298 + /// to be false in the corresponding edge-map. 3.1299 + void hide(const Edge& e) const { Parent::hide(e); } 3.1300 + 3.1301 + /// \brief Unhides the node of the graph 3.1302 + /// 3.1303 + /// The value of \c n is set to be true in the node-map which stores 3.1304 + /// hide information. If \c n was hidden previuosly, then it is shown 3.1305 + /// again 3.1306 + void unHide(const Node& n) const { Parent::unHide(n); } 3.1307 + 3.1308 + /// \brief Unhides the edge of the graph 3.1309 + /// 3.1310 + /// The value of \c e is set to be true in the edge-map which stores 3.1311 + /// hide information. If \c e was hidden previuosly, then it is shown 3.1312 + /// again 3.1313 + void unHide(const Edge& e) const { Parent::unHide(e); } 3.1314 + 3.1315 + /// \brief Returns true if \c n is hidden. 3.1316 + /// 3.1317 + /// Returns true if \c n is hidden. 3.1318 + /// 3.1319 + bool hidden(const Node& n) const { return Parent::hidden(n); } 3.1320 + 3.1321 + /// \brief Returns true if \c e is hidden. 3.1322 + /// 3.1323 + /// Returns true if \c e is hidden. 3.1324 + /// 3.1325 + bool hidden(const Edge& e) const { return Parent::hidden(e); } 3.1326 + }; 3.1327 + 3.1328 + /// \brief Just gives back a subgraph 3.1329 + /// 3.1330 + /// Just gives back a subgraph 3.1331 + template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> 3.1332 + SubGraph<const Graph, NodeFilterMap, ArcFilterMap> 3.1333 + subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) { 3.1334 + return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm); 3.1335 + } 3.1336 + 3.1337 + template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> 3.1338 + SubGraph<const Graph, const NodeFilterMap, ArcFilterMap> 3.1339 + subGraph(const Graph& graph, 3.1340 + const NodeFilterMap& nfm, ArcFilterMap& efm) { 3.1341 + return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap> 3.1342 + (graph, nfm, efm); 3.1343 + } 3.1344 + 3.1345 + template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> 3.1346 + SubGraph<const Graph, NodeFilterMap, const ArcFilterMap> 3.1347 + subGraph(const Graph& graph, 3.1348 + NodeFilterMap& nfm, const ArcFilterMap& efm) { 3.1349 + return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap> 3.1350 + (graph, nfm, efm); 3.1351 + } 3.1352 + 3.1353 + template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> 3.1354 + SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap> 3.1355 + subGraph(const Graph& graph, 3.1356 + const NodeFilterMap& nfm, const ArcFilterMap& efm) { 3.1357 + return SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap> 3.1358 + (graph, nfm, efm); 3.1359 + } 3.1360 + 3.1361 + /// \ingroup graph_adaptors 3.1362 + /// 3.1363 + /// \brief An adaptor for hiding nodes from a digraph or a graph. 3.1364 + /// 3.1365 + /// FilterNodes adaptor hides nodes in a graph or a digraph. A bool 3.1366 + /// node map must be specified, which defines the filters for 3.1367 + /// nodes. Just the unfiltered nodes and the arcs or edges incident 3.1368 + /// to unfiltered nodes are shown in the subdigraph or subgraph. The 3.1369 + /// FilterNodes is conform to the \ref concepts::Digraph 3.1370 + /// "Digraph concept" or \ref concepts::Graph "Graph concept" depending 3.1371 + /// on the \c _Digraph template parameter. If the \c _checked 3.1372 + /// parameter is true, then the arc or edges incident to filtered nodes 3.1373 + /// are also filtered out. 3.1374 + /// 3.1375 + /// \tparam _Digraph It must be conform to the \ref 3.1376 + /// concepts::Digraph "Digraph concept" or \ref concepts::Graph 3.1377 + /// "Graph concept". The type can be specified to be const. 3.1378 + /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph. 3.1379 + /// \tparam _checked If the parameter is false then the arc or edge 3.1380 + /// filtering is not checked with respect to node filter. In this 3.1381 + /// case just isolated nodes can be filtered out from the 3.1382 + /// graph. 3.1383 +#ifdef DOXYGEN 3.1384 + template<typename _Digraph, 3.1385 + typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, 3.1386 + bool _checked = true> 3.1387 +#else 3.1388 + template<typename _Digraph, 3.1389 + typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, 3.1390 + bool _checked = true, 3.1391 + typename Enable = void> 3.1392 +#endif 3.1393 + class FilterNodes 3.1394 + : public SubDigraph<_Digraph, _NodeFilterMap, 3.1395 + ConstMap<typename _Digraph::Arc, bool>, _checked> { 3.1396 + public: 3.1397 + 3.1398 + typedef _Digraph Digraph; 3.1399 + typedef _NodeFilterMap NodeFilterMap; 3.1400 + 3.1401 + typedef SubDigraph<Digraph, NodeFilterMap, 3.1402 + ConstMap<typename Digraph::Arc, bool>, _checked> 3.1403 + Parent; 3.1404 + 3.1405 + typedef typename Parent::Node Node; 3.1406 + 3.1407 + protected: 3.1408 + ConstMap<typename Digraph::Arc, bool> const_true_map; 3.1409 + 3.1410 + FilterNodes() : const_true_map(true) { 3.1411 + Parent::setArcFilterMap(const_true_map); 3.1412 + } 3.1413 + 3.1414 + public: 3.1415 + 3.1416 + /// \brief Constructor 3.1417 + /// 3.1418 + /// Creates an adaptor for the given digraph or graph with 3.1419 + /// given node filter map. 3.1420 + FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) : 3.1421 + Parent(), const_true_map(true) { 3.1422 + Parent::setDigraph(_digraph); 3.1423 + Parent::setNodeFilterMap(node_filter); 3.1424 + Parent::setArcFilterMap(const_true_map); 3.1425 + } 3.1426 + 3.1427 + /// \brief Hides the node of the graph 3.1428 + /// 3.1429 + /// This function hides \c n in the digraph or graph, i.e. the iteration 3.1430 + /// jumps over it. This is done by simply setting the value of \c n 3.1431 + /// to be false in the corresponding node map. 3.1432 + void hide(const Node& n) const { Parent::hide(n); } 3.1433 + 3.1434 + /// \brief Unhides the node of the graph 3.1435 + /// 3.1436 + /// The value of \c n is set to be true in the node-map which stores 3.1437 + /// hide information. If \c n was hidden previuosly, then it is shown 3.1438 + /// again 3.1439 + void unHide(const Node& n) const { Parent::unHide(n); } 3.1440 + 3.1441 + /// \brief Returns true if \c n is hidden. 3.1442 + /// 3.1443 + /// Returns true if \c n is hidden. 3.1444 + /// 3.1445 + bool hidden(const Node& n) const { return Parent::hidden(n); } 3.1446 + 3.1447 + }; 3.1448 + 3.1449 + template<typename _Graph, typename _NodeFilterMap, bool _checked> 3.1450 + class FilterNodes<_Graph, _NodeFilterMap, _checked, 3.1451 + typename enable_if<UndirectedTagIndicator<_Graph> >::type> 3.1452 + : public SubGraph<_Graph, _NodeFilterMap, 3.1453 + ConstMap<typename _Graph::Edge, bool>, _checked> { 3.1454 + public: 3.1455 + typedef _Graph Graph; 3.1456 + typedef _NodeFilterMap NodeFilterMap; 3.1457 + typedef SubGraph<Graph, NodeFilterMap, 3.1458 + ConstMap<typename Graph::Edge, bool> > Parent; 3.1459 + 3.1460 + typedef typename Parent::Node Node; 3.1461 + protected: 3.1462 + ConstMap<typename Graph::Edge, bool> const_true_map; 3.1463 + 3.1464 + FilterNodes() : const_true_map(true) { 3.1465 + Parent::setEdgeFilterMap(const_true_map); 3.1466 + } 3.1467 + 3.1468 + public: 3.1469 + 3.1470 + FilterNodes(Graph& _graph, NodeFilterMap& node_filter_map) : 3.1471 + Parent(), const_true_map(true) { 3.1472 + Parent::setGraph(_graph); 3.1473 + Parent::setNodeFilterMap(node_filter_map); 3.1474 + Parent::setEdgeFilterMap(const_true_map); 3.1475 + } 3.1476 + 3.1477 + void hide(const Node& n) const { Parent::hide(n); } 3.1478 + void unHide(const Node& n) const { Parent::unHide(n); } 3.1479 + bool hidden(const Node& n) const { return Parent::hidden(n); } 3.1480 + 3.1481 + }; 3.1482 + 3.1483 + 3.1484 + /// \brief Just gives back a FilterNodes adaptor 3.1485 + /// 3.1486 + /// Just gives back a FilterNodes adaptor 3.1487 + template<typename Digraph, typename NodeFilterMap> 3.1488 + FilterNodes<const Digraph, NodeFilterMap> 3.1489 + filterNodes(const Digraph& digraph, NodeFilterMap& nfm) { 3.1490 + return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm); 3.1491 + } 3.1492 + 3.1493 + template<typename Digraph, typename NodeFilterMap> 3.1494 + FilterNodes<const Digraph, const NodeFilterMap> 3.1495 + filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) { 3.1496 + return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm); 3.1497 + } 3.1498 + 3.1499 + /// \ingroup graph_adaptors 3.1500 + /// 3.1501 + /// \brief An adaptor for hiding arcs from a digraph. 3.1502 + /// 3.1503 + /// FilterArcs adaptor hides arcs in a digraph. A bool arc map must 3.1504 + /// be specified, which defines the filters for arcs. Just the 3.1505 + /// unfiltered arcs are shown in the subdigraph. The FilterArcs is 3.1506 + /// conform to the \ref concepts::Digraph "Digraph concept". 3.1507 + /// 3.1508 + /// \tparam _Digraph It must be conform to the \ref concepts::Digraph 3.1509 + /// "Digraph concept". The type can be specified to be const. 3.1510 + /// \tparam _ArcFilterMap A bool valued arc map of the the adapted 3.1511 + /// graph. 3.1512 + template<typename _Digraph, typename _ArcFilterMap> 3.1513 + class FilterArcs : 3.1514 + public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>, 3.1515 + _ArcFilterMap, false> { 3.1516 + public: 3.1517 + typedef _Digraph Digraph; 3.1518 + typedef _ArcFilterMap ArcFilterMap; 3.1519 + 3.1520 + typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>, 3.1521 + ArcFilterMap, false> Parent; 3.1522 + 3.1523 + typedef typename Parent::Arc Arc; 3.1524 + 3.1525 + protected: 3.1526 + ConstMap<typename Digraph::Node, bool> const_true_map; 3.1527 + 3.1528 + FilterArcs() : const_true_map(true) { 3.1529 + Parent::setNodeFilterMap(const_true_map); 3.1530 + } 3.1531 + 3.1532 + public: 3.1533 + 3.1534 + /// \brief Constructor 3.1535 + /// 3.1536 + /// Creates a FilterArcs adaptor for the given graph with 3.1537 + /// given arc map filter. 3.1538 + FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter) 3.1539 + : Parent(), const_true_map(true) { 3.1540 + Parent::setDigraph(digraph); 3.1541 + Parent::setNodeFilterMap(const_true_map); 3.1542 + Parent::setArcFilterMap(arc_filter); 3.1543 + } 3.1544 + 3.1545 + /// \brief Hides the arc of the graph 3.1546 + /// 3.1547 + /// This function hides \c a in the graph, i.e. the iteration 3.1548 + /// jumps over it. This is done by simply setting the value of \c a 3.1549 + /// to be false in the corresponding arc map. 3.1550 + void hide(const Arc& a) const { Parent::hide(a); } 3.1551 + 3.1552 + /// \brief Unhides the arc of the graph 3.1553 + /// 3.1554 + /// The value of \c a is set to be true in the arc-map which stores 3.1555 + /// hide information. If \c a was hidden previuosly, then it is shown 3.1556 + /// again 3.1557 + void unHide(const Arc& a) const { Parent::unHide(a); } 3.1558 + 3.1559 + /// \brief Returns true if \c a is hidden. 3.1560 + /// 3.1561 + /// Returns true if \c a is hidden. 3.1562 + /// 3.1563 + bool hidden(const Arc& a) const { return Parent::hidden(a); } 3.1564 + 3.1565 + }; 3.1566 + 3.1567 + /// \brief Just gives back an FilterArcs adaptor 3.1568 + /// 3.1569 + /// Just gives back an FilterArcs adaptor 3.1570 + template<typename Digraph, typename ArcFilterMap> 3.1571 + FilterArcs<const Digraph, ArcFilterMap> 3.1572 + filterArcs(const Digraph& digraph, ArcFilterMap& afm) { 3.1573 + return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm); 3.1574 + } 3.1575 + 3.1576 + template<typename Digraph, typename ArcFilterMap> 3.1577 + FilterArcs<const Digraph, const ArcFilterMap> 3.1578 + filterArcs(const Digraph& digraph, const ArcFilterMap& afm) { 3.1579 + return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm); 3.1580 + } 3.1581 + 3.1582 + /// \ingroup graph_adaptors 3.1583 + /// 3.1584 + /// \brief An adaptor for hiding edges from a graph. 3.1585 + /// 3.1586 + /// FilterEdges adaptor hides edges in a digraph. A bool edge map must 3.1587 + /// be specified, which defines the filters for edges. Just the 3.1588 + /// unfiltered edges are shown in the subdigraph. The FilterEdges is 3.1589 + /// conform to the \ref concepts::Graph "Graph concept". 3.1590 + /// 3.1591 + /// \tparam _Graph It must be conform to the \ref concepts::Graph 3.1592 + /// "Graph concept". The type can be specified to be const. 3.1593 + /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted 3.1594 + /// graph. 3.1595 + template<typename _Graph, typename _EdgeFilterMap> 3.1596 + class FilterEdges : 3.1597 + public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>, 3.1598 + _EdgeFilterMap, false> { 3.1599 + public: 3.1600 + typedef _Graph Graph; 3.1601 + typedef _EdgeFilterMap EdgeFilterMap; 3.1602 + typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>, 3.1603 + EdgeFilterMap, false> Parent; 3.1604 + typedef typename Parent::Edge Edge; 3.1605 + protected: 3.1606 + ConstMap<typename Graph::Node, bool> const_true_map; 3.1607 + 3.1608 + FilterEdges() : const_true_map(true) { 3.1609 + Parent::setNodeFilterMap(const_true_map); 3.1610 + } 3.1611 + 3.1612 + public: 3.1613 + 3.1614 + /// \brief Constructor 3.1615 + /// 3.1616 + /// Creates a FilterEdges adaptor for the given graph with 3.1617 + /// given edge map filters. 3.1618 + FilterEdges(Graph& _graph, EdgeFilterMap& edge_filter_map) : 3.1619 + Parent(), const_true_map(true) { 3.1620 + Parent::setGraph(_graph); 3.1621 + Parent::setNodeFilterMap(const_true_map); 3.1622 + Parent::setEdgeFilterMap(edge_filter_map); 3.1623 + } 3.1624 + 3.1625 + /// \brief Hides the edge of the graph 3.1626 + /// 3.1627 + /// This function hides \c e in the graph, i.e. the iteration 3.1628 + /// jumps over it. This is done by simply setting the value of \c e 3.1629 + /// to be false in the corresponding edge-map. 3.1630 + void hide(const Edge& e) const { Parent::hide(e); } 3.1631 + 3.1632 + /// \brief Unhides the edge of the graph 3.1633 + /// 3.1634 + /// The value of \c e is set to be true in the edge-map which stores 3.1635 + /// hide information. If \c e was hidden previuosly, then it is shown 3.1636 + /// again 3.1637 + void unHide(const Edge& e) const { Parent::unHide(e); } 3.1638 + 3.1639 + /// \brief Returns true if \c e is hidden. 3.1640 + /// 3.1641 + /// Returns true if \c e is hidden. 3.1642 + /// 3.1643 + bool hidden(const Edge& e) const { return Parent::hidden(e); } 3.1644 + 3.1645 + }; 3.1646 + 3.1647 + /// \brief Just gives back a FilterEdges adaptor 3.1648 + /// 3.1649 + /// Just gives back a FilterEdges adaptor 3.1650 + template<typename Graph, typename EdgeFilterMap> 3.1651 + FilterEdges<const Graph, EdgeFilterMap> 3.1652 + filterEdges(const Graph& graph, EdgeFilterMap& efm) { 3.1653 + return FilterEdges<const Graph, EdgeFilterMap>(graph, efm); 3.1654 + } 3.1655 + 3.1656 + template<typename Graph, typename EdgeFilterMap> 3.1657 + FilterEdges<const Graph, const EdgeFilterMap> 3.1658 + filterEdges(const Graph& graph, const EdgeFilterMap& efm) { 3.1659 + return FilterEdges<const Graph, const EdgeFilterMap>(graph, efm); 3.1660 + } 3.1661 + 3.1662 + template <typename _Digraph> 3.1663 + class UndirectorBase { 3.1664 + public: 3.1665 + typedef _Digraph Digraph; 3.1666 + typedef UndirectorBase Adaptor; 3.1667 + 3.1668 + typedef True UndirectedTag; 3.1669 + 3.1670 + typedef typename Digraph::Arc Edge; 3.1671 + typedef typename Digraph::Node Node; 3.1672 + 3.1673 + class Arc : public Edge { 3.1674 + friend class UndirectorBase; 3.1675 + protected: 3.1676 + bool _forward; 3.1677 + 3.1678 + Arc(const Edge& edge, bool forward) : 3.1679 + Edge(edge), _forward(forward) {} 3.1680 + 3.1681 + public: 3.1682 + Arc() {} 3.1683 + 3.1684 + Arc(Invalid) : Edge(INVALID), _forward(true) {} 3.1685 + 3.1686 + bool operator==(const Arc &other) const { 3.1687 + return _forward == other._forward && 3.1688 + static_cast<const Edge&>(*this) == static_cast<const Edge&>(other); 3.1689 + } 3.1690 + bool operator!=(const Arc &other) const { 3.1691 + return _forward != other._forward || 3.1692 + static_cast<const Edge&>(*this) != static_cast<const Edge&>(other); 3.1693 + } 3.1694 + bool operator<(const Arc &other) const { 3.1695 + return _forward < other._forward || 3.1696 + (_forward == other._forward && 3.1697 + static_cast<const Edge&>(*this) < static_cast<const Edge&>(other)); 3.1698 + } 3.1699 + }; 3.1700 + 3.1701 + 3.1702 + 3.1703 + void first(Node& n) const { 3.1704 + _digraph->first(n); 3.1705 + } 3.1706 + 3.1707 + void next(Node& n) const { 3.1708 + _digraph->next(n); 3.1709 + } 3.1710 + 3.1711 + void first(Arc& a) const { 3.1712 + _digraph->first(a); 3.1713 + a._forward = true; 3.1714 + } 3.1715 + 3.1716 + void next(Arc& a) const { 3.1717 + if (a._forward) { 3.1718 + a._forward = false; 3.1719 + } else { 3.1720 + _digraph->next(a); 3.1721 + a._forward = true; 3.1722 + } 3.1723 + } 3.1724 + 3.1725 + void first(Edge& e) const { 3.1726 + _digraph->first(e); 3.1727 + } 3.1728 + 3.1729 + void next(Edge& e) const { 3.1730 + _digraph->next(e); 3.1731 + } 3.1732 + 3.1733 + void firstOut(Arc& a, const Node& n) const { 3.1734 + _digraph->firstIn(a, n); 3.1735 + if( static_cast<const Edge&>(a) != INVALID ) { 3.1736 + a._forward = false; 3.1737 + } else { 3.1738 + _digraph->firstOut(a, n); 3.1739 + a._forward = true; 3.1740 + } 3.1741 + } 3.1742 + void nextOut(Arc &a) const { 3.1743 + if (!a._forward) { 3.1744 + Node n = _digraph->target(a); 3.1745 + _digraph->nextIn(a); 3.1746 + if (static_cast<const Edge&>(a) == INVALID ) { 3.1747 + _digraph->firstOut(a, n); 3.1748 + a._forward = true; 3.1749 + } 3.1750 + } 3.1751 + else { 3.1752 + _digraph->nextOut(a); 3.1753 + } 3.1754 + } 3.1755 + 3.1756 + void firstIn(Arc &a, const Node &n) const { 3.1757 + _digraph->firstOut(a, n); 3.1758 + if (static_cast<const Edge&>(a) != INVALID ) { 3.1759 + a._forward = false; 3.1760 + } else { 3.1761 + _digraph->firstIn(a, n); 3.1762 + a._forward = true; 3.1763 + } 3.1764 + } 3.1765 + void nextIn(Arc &a) const { 3.1766 + if (!a._forward) { 3.1767 + Node n = _digraph->source(a); 3.1768 + _digraph->nextOut(a); 3.1769 + if( static_cast<const Edge&>(a) == INVALID ) { 3.1770 + _digraph->firstIn(a, n); 3.1771 + a._forward = true; 3.1772 + } 3.1773 + } 3.1774 + else { 3.1775 + _digraph->nextIn(a); 3.1776 + } 3.1777 + } 3.1778 + 3.1779 + void firstInc(Edge &e, bool &d, const Node &n) const { 3.1780 + d = true; 3.1781 + _digraph->firstOut(e, n); 3.1782 + if (e != INVALID) return; 3.1783 + d = false; 3.1784 + _digraph->firstIn(e, n); 3.1785 + } 3.1786 + 3.1787 + void nextInc(Edge &e, bool &d) const { 3.1788 + if (d) { 3.1789 + Node s = _digraph->source(e); 3.1790 + _digraph->nextOut(e); 3.1791 + if (e != INVALID) return; 3.1792 + d = false; 3.1793 + _digraph->firstIn(e, s); 3.1794 + } else { 3.1795 + _digraph->nextIn(e); 3.1796 + } 3.1797 + } 3.1798 + 3.1799 + Node u(const Edge& e) const { 3.1800 + return _digraph->source(e); 3.1801 + } 3.1802 + 3.1803 + Node v(const Edge& e) const { 3.1804 + return _digraph->target(e); 3.1805 + } 3.1806 + 3.1807 + Node source(const Arc &a) const { 3.1808 + return a._forward ? _digraph->source(a) : _digraph->target(a); 3.1809 + } 3.1810 + 3.1811 + Node target(const Arc &a) const { 3.1812 + return a._forward ? _digraph->target(a) : _digraph->source(a); 3.1813 + } 3.1814 + 3.1815 + static Arc direct(const Edge &e, bool d) { 3.1816 + return Arc(e, d); 3.1817 + } 3.1818 + Arc direct(const Edge &e, const Node& n) const { 3.1819 + return Arc(e, _digraph->source(e) == n); 3.1820 + } 3.1821 + 3.1822 + static bool direction(const Arc &a) { return a._forward; } 3.1823 + 3.1824 + Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); } 3.1825 + Arc arcFromId(int ix) const { 3.1826 + return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1)); 3.1827 + } 3.1828 + Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); } 3.1829 + 3.1830 + int id(const Node &n) const { return _digraph->id(n); } 3.1831 + int id(const Arc &a) const { 3.1832 + return (_digraph->id(a) << 1) | (a._forward ? 1 : 0); 3.1833 + } 3.1834 + int id(const Edge &e) const { return _digraph->id(e); } 3.1835 + 3.1836 + int maxNodeId() const { return _digraph->maxNodeId(); } 3.1837 + int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; } 3.1838 + int maxEdgeId() const { return _digraph->maxArcId(); } 3.1839 + 3.1840 + Node addNode() { return _digraph->addNode(); } 3.1841 + Edge addEdge(const Node& u, const Node& v) { 3.1842 + return _digraph->addArc(u, v); 3.1843 + } 3.1844 + 3.1845 + void erase(const Node& i) { _digraph->erase(i); } 3.1846 + void erase(const Edge& i) { _digraph->erase(i); } 3.1847 + 3.1848 + void clear() { _digraph->clear(); } 3.1849 + 3.1850 + typedef NodeNumTagIndicator<Digraph> NodeNumTag; 3.1851 + int nodeNum() const { return 2 * _digraph->arcNum(); } 3.1852 + typedef EdgeNumTagIndicator<Digraph> EdgeNumTag; 3.1853 + int arcNum() const { return 2 * _digraph->arcNum(); } 3.1854 + int edgeNum() const { return _digraph->arcNum(); } 3.1855 + 3.1856 + typedef FindEdgeTagIndicator<Digraph> FindEdgeTag; 3.1857 + Arc findArc(Node s, Node t, Arc p = INVALID) const { 3.1858 + if (p == INVALID) { 3.1859 + Edge arc = _digraph->findArc(s, t); 3.1860 + if (arc != INVALID) return direct(arc, true); 3.1861 + arc = _digraph->findArc(t, s); 3.1862 + if (arc != INVALID) return direct(arc, false); 3.1863 + } else if (direction(p)) { 3.1864 + Edge arc = _digraph->findArc(s, t, p); 3.1865 + if (arc != INVALID) return direct(arc, true); 3.1866 + arc = _digraph->findArc(t, s); 3.1867 + if (arc != INVALID) return direct(arc, false); 3.1868 + } else { 3.1869 + Edge arc = _digraph->findArc(t, s, p); 3.1870 + if (arc != INVALID) return direct(arc, false); 3.1871 + } 3.1872 + return INVALID; 3.1873 + } 3.1874 + 3.1875 + Edge findEdge(Node s, Node t, Edge p = INVALID) const { 3.1876 + if (s != t) { 3.1877 + if (p == INVALID) { 3.1878 + Edge arc = _digraph->findArc(s, t); 3.1879 + if (arc != INVALID) return arc; 3.1880 + arc = _digraph->findArc(t, s); 3.1881 + if (arc != INVALID) return arc; 3.1882 + } else if (_digraph->s(p) == s) { 3.1883 + Edge arc = _digraph->findArc(s, t, p); 3.1884 + if (arc != INVALID) return arc; 3.1885 + arc = _digraph->findArc(t, s); 3.1886 + if (arc != INVALID) return arc; 3.1887 + } else { 3.1888 + Edge arc = _digraph->findArc(t, s, p); 3.1889 + if (arc != INVALID) return arc; 3.1890 + } 3.1891 + } else { 3.1892 + return _digraph->findArc(s, t, p); 3.1893 + } 3.1894 + return INVALID; 3.1895 + } 3.1896 + 3.1897 + private: 3.1898 + 3.1899 + template <typename _Value> 3.1900 + class ArcMapBase { 3.1901 + private: 3.1902 + 3.1903 + typedef typename Digraph::template ArcMap<_Value> MapImpl; 3.1904 + 3.1905 + public: 3.1906 + 3.1907 + typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag; 3.1908 + 3.1909 + typedef _Value Value; 3.1910 + typedef Arc Key; 3.1911 + 3.1912 + ArcMapBase(const Adaptor& adaptor) : 3.1913 + _forward(*adaptor._digraph), _backward(*adaptor._digraph) {} 3.1914 + 3.1915 + ArcMapBase(const Adaptor& adaptor, const Value& v) 3.1916 + : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {} 3.1917 + 3.1918 + void set(const Arc& a, const Value& v) { 3.1919 + if (direction(a)) { 3.1920 + _forward.set(a, v); 3.1921 + } else { 3.1922 + _backward.set(a, v); 3.1923 + } 3.1924 + } 3.1925 + 3.1926 + typename MapTraits<MapImpl>::ConstReturnValue 3.1927 + operator[](const Arc& a) const { 3.1928 + if (direction(a)) { 3.1929 + return _forward[a]; 3.1930 + } else { 3.1931 + return _backward[a]; 3.1932 + } 3.1933 + } 3.1934 + 3.1935 + typename MapTraits<MapImpl>::ReturnValue 3.1936 + operator[](const Arc& a) { 3.1937 + if (direction(a)) { 3.1938 + return _forward[a]; 3.1939 + } else { 3.1940 + return _backward[a]; 3.1941 + } 3.1942 + } 3.1943 + 3.1944 + protected: 3.1945 + 3.1946 + MapImpl _forward, _backward; 3.1947 + 3.1948 + }; 3.1949 + 3.1950 + public: 3.1951 + 3.1952 + template <typename _Value> 3.1953 + class NodeMap : public Digraph::template NodeMap<_Value> { 3.1954 + public: 3.1955 + 3.1956 + typedef _Value Value; 3.1957 + typedef typename Digraph::template NodeMap<Value> Parent; 3.1958 + 3.1959 + explicit NodeMap(const Adaptor& adaptor) 3.1960 + : Parent(*adaptor._digraph) {} 3.1961 + 3.1962 + NodeMap(const Adaptor& adaptor, const _Value& value) 3.1963 + : Parent(*adaptor._digraph, value) { } 3.1964 + 3.1965 + private: 3.1966 + NodeMap& operator=(const NodeMap& cmap) { 3.1967 + return operator=<NodeMap>(cmap); 3.1968 + } 3.1969 + 3.1970 + template <typename CMap> 3.1971 + NodeMap& operator=(const CMap& cmap) { 3.1972 + Parent::operator=(cmap); 3.1973 + return *this; 3.1974 + } 3.1975 + 3.1976 + }; 3.1977 + 3.1978 + template <typename _Value> 3.1979 + class ArcMap 3.1980 + : public SubMapExtender<Adaptor, ArcMapBase<_Value> > 3.1981 + { 3.1982 + public: 3.1983 + typedef _Value Value; 3.1984 + typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent; 3.1985 + 3.1986 + ArcMap(const Adaptor& adaptor) 3.1987 + : Parent(adaptor) {} 3.1988 + 3.1989 + ArcMap(const Adaptor& adaptor, const Value& value) 3.1990 + : Parent(adaptor, value) {} 3.1991 + 3.1992 + private: 3.1993 + ArcMap& operator=(const ArcMap& cmap) { 3.1994 + return operator=<ArcMap>(cmap); 3.1995 + } 3.1996 + 3.1997 + template <typename CMap> 3.1998 + ArcMap& operator=(const CMap& cmap) { 3.1999 + Parent::operator=(cmap); 3.2000 + return *this; 3.2001 + } 3.2002 + }; 3.2003 + 3.2004 + template <typename _Value> 3.2005 + class EdgeMap : public Digraph::template ArcMap<_Value> { 3.2006 + public: 3.2007 + 3.2008 + typedef _Value Value; 3.2009 + typedef typename Digraph::template ArcMap<Value> Parent; 3.2010 + 3.2011 + explicit EdgeMap(const Adaptor& adaptor) 3.2012 + : Parent(*adaptor._digraph) {} 3.2013 + 3.2014 + EdgeMap(const Adaptor& adaptor, const Value& value) 3.2015 + : Parent(*adaptor._digraph, value) {} 3.2016 + 3.2017 + private: 3.2018 + EdgeMap& operator=(const EdgeMap& cmap) { 3.2019 + return operator=<EdgeMap>(cmap); 3.2020 + } 3.2021 + 3.2022 + template <typename CMap> 3.2023 + EdgeMap& operator=(const CMap& cmap) { 3.2024 + Parent::operator=(cmap); 3.2025 + return *this; 3.2026 + } 3.2027 + 3.2028 + }; 3.2029 + 3.2030 + typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier; 3.2031 + NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); } 3.2032 + 3.2033 + protected: 3.2034 + 3.2035 + UndirectorBase() : _digraph(0) {} 3.2036 + 3.2037 + Digraph* _digraph; 3.2038 + 3.2039 + void setDigraph(Digraph& digraph) { 3.2040 + _digraph = &digraph; 3.2041 + } 3.2042 + 3.2043 + }; 3.2044 + 3.2045 + /// \ingroup graph_adaptors 3.2046 + /// 3.2047 + /// \brief Undirect the graph 3.2048 + /// 3.2049 + /// This adaptor makes an undirected graph from a directed 3.2050 + /// graph. All arcs of the underlying digraph will be showed in the 3.2051 + /// adaptor as an edge. The Orienter adaptor is conform to the \ref 3.2052 + /// concepts::Graph "Graph concept". 3.2053 + /// 3.2054 + /// \tparam _Digraph It must be conform to the \ref 3.2055 + /// concepts::Digraph "Digraph concept". The type can be specified 3.2056 + /// to const. 3.2057 + template<typename _Digraph> 3.2058 + class Undirector 3.2059 + : public GraphAdaptorExtender<UndirectorBase<_Digraph> > { 3.2060 + public: 3.2061 + typedef _Digraph Digraph; 3.2062 + typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent; 3.2063 + protected: 3.2064 + Undirector() { } 3.2065 + public: 3.2066 + 3.2067 + /// \brief Constructor 3.2068 + /// 3.2069 + /// Creates a undirected graph from the given digraph 3.2070 + Undirector(_Digraph& digraph) { 3.2071 + setDigraph(digraph); 3.2072 + } 3.2073 + 3.2074 + /// \brief ArcMap combined from two original ArcMap 3.2075 + /// 3.2076 + /// This class adapts two original digraph ArcMap to 3.2077 + /// get an arc map on the undirected graph. 3.2078 + template <typename _ForwardMap, typename _BackwardMap> 3.2079 + class CombinedArcMap { 3.2080 + public: 3.2081 + 3.2082 + typedef _ForwardMap ForwardMap; 3.2083 + typedef _BackwardMap BackwardMap; 3.2084 + 3.2085 + typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag; 3.2086 + 3.2087 + typedef typename ForwardMap::Value Value; 3.2088 + typedef typename Parent::Arc Key; 3.2089 + 3.2090 + /// \brief Constructor 3.2091 + /// 3.2092 + /// Constructor 3.2093 + CombinedArcMap(ForwardMap& forward, BackwardMap& backward) 3.2094 + : _forward(&forward), _backward(&backward) {} 3.2095 + 3.2096 + 3.2097 + /// \brief Sets the value associated with a key. 3.2098 + /// 3.2099 + /// Sets the value associated with a key. 3.2100 + void set(const Key& e, const Value& a) { 3.2101 + if (Parent::direction(e)) { 3.2102 + _forward->set(e, a); 3.2103 + } else { 3.2104 + _backward->set(e, a); 3.2105 + } 3.2106 + } 3.2107 + 3.2108 + /// \brief Returns the value associated with a key. 3.2109 + /// 3.2110 + /// Returns the value associated with a key. 3.2111 + typename MapTraits<ForwardMap>::ConstReturnValue 3.2112 + operator[](const Key& e) const { 3.2113 + if (Parent::direction(e)) { 3.2114 + return (*_forward)[e]; 3.2115 + } else { 3.2116 + return (*_backward)[e]; 3.2117 + } 3.2118 + } 3.2119 + 3.2120 + /// \brief Returns the value associated with a key. 3.2121 + /// 3.2122 + /// Returns the value associated with a key. 3.2123 + typename MapTraits<ForwardMap>::ReturnValue 3.2124 + operator[](const Key& e) { 3.2125 + if (Parent::direction(e)) { 3.2126 + return (*_forward)[e]; 3.2127 + } else { 3.2128 + return (*_backward)[e]; 3.2129 + } 3.2130 + } 3.2131 + 3.2132 + protected: 3.2133 + 3.2134 + ForwardMap* _forward; 3.2135 + BackwardMap* _backward; 3.2136 + 3.2137 + }; 3.2138 + 3.2139 + /// \brief Just gives back a combined arc map 3.2140 + /// 3.2141 + /// Just gives back a combined arc map 3.2142 + template <typename ForwardMap, typename BackwardMap> 3.2143 + static CombinedArcMap<ForwardMap, BackwardMap> 3.2144 + combinedArcMap(ForwardMap& forward, BackwardMap& backward) { 3.2145 + return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward); 3.2146 + } 3.2147 + 3.2148 + template <typename ForwardMap, typename BackwardMap> 3.2149 + static CombinedArcMap<const ForwardMap, BackwardMap> 3.2150 + combinedArcMap(const ForwardMap& forward, BackwardMap& backward) { 3.2151 + return CombinedArcMap<const ForwardMap, 3.2152 + BackwardMap>(forward, backward); 3.2153 + } 3.2154 + 3.2155 + template <typename ForwardMap, typename BackwardMap> 3.2156 + static CombinedArcMap<ForwardMap, const BackwardMap> 3.2157 + combinedArcMap(ForwardMap& forward, const BackwardMap& backward) { 3.2158 + return CombinedArcMap<ForwardMap, 3.2159 + const BackwardMap>(forward, backward); 3.2160 + } 3.2161 + 3.2162 + template <typename ForwardMap, typename BackwardMap> 3.2163 + static CombinedArcMap<const ForwardMap, const BackwardMap> 3.2164 + combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) { 3.2165 + return CombinedArcMap<const ForwardMap, 3.2166 + const BackwardMap>(forward, backward); 3.2167 + } 3.2168 + 3.2169 + }; 3.2170 + 3.2171 + /// \brief Just gives back an undirected view of the given digraph 3.2172 + /// 3.2173 + /// Just gives back an undirected view of the given digraph 3.2174 + template<typename Digraph> 3.2175 + Undirector<const Digraph> 3.2176 + undirector(const Digraph& digraph) { 3.2177 + return Undirector<const Digraph>(digraph); 3.2178 + } 3.2179 + 3.2180 + template <typename _Graph, typename _DirectionMap> 3.2181 + class OrienterBase { 3.2182 + public: 3.2183 + 3.2184 + typedef _Graph Graph; 3.2185 + typedef _DirectionMap DirectionMap; 3.2186 + 3.2187 + typedef typename Graph::Node Node; 3.2188 + typedef typename Graph::Edge Arc; 3.2189 + 3.2190 + void reverseArc(const Arc& arc) { 3.2191 + _direction->set(arc, !(*_direction)[arc]); 3.2192 + } 3.2193 + 3.2194 + void first(Node& i) const { _graph->first(i); } 3.2195 + void first(Arc& i) const { _graph->first(i); } 3.2196 + void firstIn(Arc& i, const Node& n) const { 3.2197 + bool d; 3.2198 + _graph->firstInc(i, d, n); 3.2199 + while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d); 3.2200 + } 3.2201 + void firstOut(Arc& i, const Node& n ) const { 3.2202 + bool d; 3.2203 + _graph->firstInc(i, d, n); 3.2204 + while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d); 3.2205 + } 3.2206 + 3.2207 + void next(Node& i) const { _graph->next(i); } 3.2208 + void next(Arc& i) const { _graph->next(i); } 3.2209 + void nextIn(Arc& i) const { 3.2210 + bool d = !(*_direction)[i]; 3.2211 + _graph->nextInc(i, d); 3.2212 + while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d); 3.2213 + } 3.2214 + void nextOut(Arc& i) const { 3.2215 + bool d = (*_direction)[i]; 3.2216 + _graph->nextInc(i, d); 3.2217 + while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d); 3.2218 + } 3.2219 + 3.2220 + Node source(const Arc& e) const { 3.2221 + return (*_direction)[e] ? _graph->u(e) : _graph->v(e); 3.2222 + } 3.2223 + Node target(const Arc& e) const { 3.2224 + return (*_direction)[e] ? _graph->v(e) : _graph->u(e); 3.2225 + } 3.2226 + 3.2227 + typedef NodeNumTagIndicator<Graph> NodeNumTag; 3.2228 + int nodeNum() const { return _graph->nodeNum(); } 3.2229 + 3.2230 + typedef EdgeNumTagIndicator<Graph> EdgeNumTag; 3.2231 + int arcNum() const { return _graph->edgeNum(); } 3.2232 + 3.2233 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag; 3.2234 + Arc findArc(const Node& u, const Node& v, 3.2235 + const Arc& prev = INVALID) { 3.2236 + Arc arc = prev; 3.2237 + bool d = arc == INVALID ? true : (*_direction)[arc]; 3.2238 + if (d) { 3.2239 + arc = _graph->findEdge(u, v, arc); 3.2240 + while (arc != INVALID && !(*_direction)[arc]) { 3.2241 + _graph->findEdge(u, v, arc); 3.2242 + } 3.2243 + if (arc != INVALID) return arc; 3.2244 + } 3.2245 + _graph->findEdge(v, u, arc); 3.2246 + while (arc != INVALID && (*_direction)[arc]) { 3.2247 + _graph->findEdge(u, v, arc); 3.2248 + } 3.2249 + return arc; 3.2250 + } 3.2251 + 3.2252 + Node addNode() { 3.2253 + return Node(_graph->addNode()); 3.2254 + } 3.2255 + 3.2256 + Arc addArc(const Node& u, const Node& v) { 3.2257 + Arc arc = _graph->addArc(u, v); 3.2258 + _direction->set(arc, _graph->source(arc) == u); 3.2259 + return arc; 3.2260 + } 3.2261 + 3.2262 + void erase(const Node& i) { _graph->erase(i); } 3.2263 + void erase(const Arc& i) { _graph->erase(i); } 3.2264 + 3.2265 + void clear() { _graph->clear(); } 3.2266 + 3.2267 + int id(const Node& v) const { return _graph->id(v); } 3.2268 + int id(const Arc& e) const { return _graph->id(e); } 3.2269 + 3.2270 + Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); } 3.2271 + Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); } 3.2272 + 3.2273 + int maxNodeId() const { return _graph->maxNodeId(); } 3.2274 + int maxArcId() const { return _graph->maxEdgeId(); } 3.2275 + 3.2276 + typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier; 3.2277 + NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); } 3.2278 + 3.2279 + typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier; 3.2280 + ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); } 3.2281 + 3.2282 + template <typename _Value> 3.2283 + class NodeMap : public _Graph::template NodeMap<_Value> { 3.2284 + public: 3.2285 + 3.2286 + typedef typename _Graph::template NodeMap<_Value> Parent; 3.2287 + 3.2288 + explicit NodeMap(const OrienterBase& adapter) 3.2289 + : Parent(*adapter._graph) {} 3.2290 + 3.2291 + NodeMap(const OrienterBase& adapter, const _Value& value) 3.2292 + : Parent(*adapter._graph, value) {} 3.2293 + 3.2294 + private: 3.2295 + NodeMap& operator=(const NodeMap& cmap) { 3.2296 + return operator=<NodeMap>(cmap); 3.2297 + } 3.2298 + 3.2299 + template <typename CMap> 3.2300 + NodeMap& operator=(const CMap& cmap) { 3.2301 + Parent::operator=(cmap); 3.2302 + return *this; 3.2303 + } 3.2304 + 3.2305 + }; 3.2306 + 3.2307 + template <typename _Value> 3.2308 + class ArcMap : public _Graph::template EdgeMap<_Value> { 3.2309 + public: 3.2310 + 3.2311 + typedef typename Graph::template EdgeMap<_Value> Parent; 3.2312 + 3.2313 + explicit ArcMap(const OrienterBase& adapter) 3.2314 + : Parent(*adapter._graph) { } 3.2315 + 3.2316 + ArcMap(const OrienterBase& adapter, const _Value& value) 3.2317 + : Parent(*adapter._graph, value) { } 3.2318 + 3.2319 + private: 3.2320 + ArcMap& operator=(const ArcMap& cmap) { 3.2321 + return operator=<ArcMap>(cmap); 3.2322 + } 3.2323 + 3.2324 + template <typename CMap> 3.2325 + ArcMap& operator=(const CMap& cmap) { 3.2326 + Parent::operator=(cmap); 3.2327 + return *this; 3.2328 + } 3.2329 + }; 3.2330 + 3.2331 + 3.2332 + 3.2333 + protected: 3.2334 + Graph* _graph; 3.2335 + DirectionMap* _direction; 3.2336 + 3.2337 + void setDirectionMap(DirectionMap& direction) { 3.2338 + _direction = &direction; 3.2339 + } 3.2340 + 3.2341 + void setGraph(Graph& graph) { 3.2342 + _graph = &graph; 3.2343 + } 3.2344 + 3.2345 + }; 3.2346 + 3.2347 + /// \ingroup graph_adaptors 3.2348 + /// 3.2349 + /// \brief Orients the edges of the graph to get a digraph 3.2350 + /// 3.2351 + /// This adaptor orients each edge in the undirected graph. The 3.2352 + /// direction of the arcs stored in an edge node map. The arcs can 3.2353 + /// be easily reverted by the \c reverseArc() member function in the 3.2354 + /// adaptor. The Orienter adaptor is conform to the \ref 3.2355 + /// concepts::Digraph "Digraph concept". 3.2356 + /// 3.2357 + /// \tparam _Graph It must be conform to the \ref concepts::Graph 3.2358 + /// "Graph concept". The type can be specified to be const. 3.2359 + /// \tparam _DirectionMap A bool valued edge map of the the adapted 3.2360 + /// graph. 3.2361 + /// 3.2362 + /// \sa orienter 3.2363 + template<typename _Graph, 3.2364 + typename DirectionMap = typename _Graph::template EdgeMap<bool> > 3.2365 + class Orienter : 3.2366 + public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > { 3.2367 + public: 3.2368 + typedef _Graph Graph; 3.2369 + typedef DigraphAdaptorExtender< 3.2370 + OrienterBase<_Graph, DirectionMap> > Parent; 3.2371 + typedef typename Parent::Arc Arc; 3.2372 + protected: 3.2373 + Orienter() { } 3.2374 + public: 3.2375 + 3.2376 + /// \brief Constructor of the adaptor 3.2377 + /// 3.2378 + /// Constructor of the adaptor 3.2379 + Orienter(Graph& graph, DirectionMap& direction) { 3.2380 + setGraph(graph); 3.2381 + setDirectionMap(direction); 3.2382 + } 3.2383 + 3.2384 + /// \brief Reverse arc 3.2385 + /// 3.2386 + /// It reverse the given arc. It simply negate the direction in the map. 3.2387 + void reverseArc(const Arc& a) { 3.2388 + Parent::reverseArc(a); 3.2389 + } 3.2390 + }; 3.2391 + 3.2392 + /// \brief Just gives back a Orienter 3.2393 + /// 3.2394 + /// Just gives back a Orienter 3.2395 + template<typename Graph, typename DirectionMap> 3.2396 + Orienter<const Graph, DirectionMap> 3.2397 + orienter(const Graph& graph, DirectionMap& dm) { 3.2398 + return Orienter<const Graph, DirectionMap>(graph, dm); 3.2399 + } 3.2400 + 3.2401 + template<typename Graph, typename DirectionMap> 3.2402 + Orienter<const Graph, const DirectionMap> 3.2403 + orienter(const Graph& graph, const DirectionMap& dm) { 3.2404 + return Orienter<const Graph, const DirectionMap>(graph, dm); 3.2405 + } 3.2406 + 3.2407 + namespace _adaptor_bits { 3.2408 + 3.2409 + template<typename _Digraph, 3.2410 + typename _CapacityMap = typename _Digraph::template ArcMap<int>, 3.2411 + typename _FlowMap = _CapacityMap, 3.2412 + typename _Tolerance = Tolerance<typename _CapacityMap::Value> > 3.2413 + class ResForwardFilter { 3.2414 + public: 3.2415 + 3.2416 + typedef _Digraph Digraph; 3.2417 + typedef _CapacityMap CapacityMap; 3.2418 + typedef _FlowMap FlowMap; 3.2419 + typedef _Tolerance Tolerance; 3.2420 + 3.2421 + typedef typename Digraph::Arc Key; 3.2422 + typedef bool Value; 3.2423 + 3.2424 + private: 3.2425 + 3.2426 + const CapacityMap* _capacity; 3.2427 + const FlowMap* _flow; 3.2428 + Tolerance _tolerance; 3.2429 + public: 3.2430 + 3.2431 + ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow, 3.2432 + const Tolerance& tolerance = Tolerance()) 3.2433 + : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { } 3.2434 + 3.2435 + bool operator[](const typename Digraph::Arc& a) const { 3.2436 + return _tolerance.positive((*_capacity)[a] - (*_flow)[a]); 3.2437 + } 3.2438 + }; 3.2439 + 3.2440 + template<typename _Digraph, 3.2441 + typename _CapacityMap = typename _Digraph::template ArcMap<int>, 3.2442 + typename _FlowMap = _CapacityMap, 3.2443 + typename _Tolerance = Tolerance<typename _CapacityMap::Value> > 3.2444 + class ResBackwardFilter { 3.2445 + public: 3.2446 + 3.2447 + typedef _Digraph Digraph; 3.2448 + typedef _CapacityMap CapacityMap; 3.2449 + typedef _FlowMap FlowMap; 3.2450 + typedef _Tolerance Tolerance; 3.2451 + 3.2452 + typedef typename Digraph::Arc Key; 3.2453 + typedef bool Value; 3.2454 + 3.2455 + private: 3.2456 + 3.2457 + const CapacityMap* _capacity; 3.2458 + const FlowMap* _flow; 3.2459 + Tolerance _tolerance; 3.2460 + 3.2461 + public: 3.2462 + 3.2463 + ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow, 3.2464 + const Tolerance& tolerance = Tolerance()) 3.2465 + : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { } 3.2466 + 3.2467 + bool operator[](const typename Digraph::Arc& a) const { 3.2468 + return _tolerance.positive((*_flow)[a]); 3.2469 + } 3.2470 + }; 3.2471 + 3.2472 + } 3.2473 + 3.2474 + /// \ingroup graph_adaptors 3.2475 + /// 3.2476 + /// \brief An adaptor for composing the residual graph for directed 3.2477 + /// flow and circulation problems. 3.2478 + /// 3.2479 + /// An adaptor for composing the residual graph for directed flow and 3.2480 + /// circulation problems. Let \f$ G=(V, A) \f$be a directed graph 3.2481 + /// and let \f$ F \f$be a number type. Let moreover \f$ f,c:A\to F \f$, 3.2482 + /// be functions on the arc-set. 3.2483 + /// 3.2484 + /// Then Residual implements the digraph structure with 3.2485 + /// node-set \f$ V \f$and arc-set \f$ A_{forward}\cup A_{backward} \f$, 3.2486 + /// where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$and 3.2487 + /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so 3.2488 + /// called residual graph. When we take the union 3.2489 + /// \f$ A_{forward}\cup A_{backward} \f$, multiplicities are counted, 3.2490 + /// i.e. if an arc is in both \f$ A_{forward} \f$and 3.2491 + /// \f$ A_{backward} \f$, then in the adaptor it appears in both 3.2492 + /// orientation. 3.2493 + /// 3.2494 + /// \tparam _Digraph It must be conform to the \ref concepts::Digraph 3.2495 + /// "Digraph concept". The type is implicitly const. 3.2496 + /// \tparam _CapacityMap An arc map of some numeric type, it defines 3.2497 + /// the capacities in the flow problem. The map is implicitly const. 3.2498 + /// \tparam _FlowMap An arc map of some numeric type, it defines 3.2499 + /// the capacities in the flow problem. 3.2500 + /// \tparam _Tolerance Handler for inexact computation. 3.2501 + template<typename _Digraph, 3.2502 + typename _CapacityMap = typename _Digraph::template ArcMap<int>, 3.2503 + typename _FlowMap = _CapacityMap, 3.2504 + typename _Tolerance = Tolerance<typename _CapacityMap::Value> > 3.2505 + class Residual : 3.2506 + public FilterArcs< 3.2507 + Undirector<const _Digraph>, 3.2508 + typename Undirector<const _Digraph>::template CombinedArcMap< 3.2509 + _adaptor_bits::ResForwardFilter<const _Digraph, _CapacityMap, 3.2510 + _FlowMap, _Tolerance>, 3.2511 + _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap, 3.2512 + _FlowMap, _Tolerance> > > 3.2513 + { 3.2514 + public: 3.2515 + 3.2516 + typedef _Digraph Digraph; 3.2517 + typedef _CapacityMap CapacityMap; 3.2518 + typedef _FlowMap FlowMap; 3.2519 + typedef _Tolerance Tolerance; 3.2520 + 3.2521 + typedef typename CapacityMap::Value Value; 3.2522 + typedef Residual Adaptor; 3.2523 + 3.2524 + protected: 3.2525 + 3.2526 + typedef Undirector<const Digraph> Undirected; 3.2527 + 3.2528 + typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap, 3.2529 + FlowMap, Tolerance> ForwardFilter; 3.2530 + 3.2531 + typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap, 3.2532 + FlowMap, Tolerance> BackwardFilter; 3.2533 + 3.2534 + typedef typename Undirected:: 3.2535 + template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter; 3.2536 + 3.2537 + typedef FilterArcs<Undirected, ArcFilter> Parent; 3.2538 + 3.2539 + const CapacityMap* _capacity; 3.2540 + FlowMap* _flow; 3.2541 + 3.2542 + Undirected _graph; 3.2543 + ForwardFilter _forward_filter; 3.2544 + BackwardFilter _backward_filter; 3.2545 + ArcFilter _arc_filter; 3.2546 + 3.2547 + public: 3.2548 + 3.2549 + /// \brief Constructor of the residual digraph. 3.2550 + /// 3.2551 + /// Constructor of the residual graph. The parameters are the digraph, 3.2552 + /// the flow map, the capacity map and a tolerance object. 3.2553 + Residual(const Digraph& digraph, const CapacityMap& capacity, 3.2554 + FlowMap& flow, const Tolerance& tolerance = Tolerance()) 3.2555 + : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph), 3.2556 + _forward_filter(capacity, flow, tolerance), 3.2557 + _backward_filter(capacity, flow, tolerance), 3.2558 + _arc_filter(_forward_filter, _backward_filter) 3.2559 + { 3.2560 + Parent::setDigraph(_graph); 3.2561 + Parent::setArcFilterMap(_arc_filter); 3.2562 + } 3.2563 + 3.2564 + typedef typename Parent::Arc Arc; 3.2565 + 3.2566 + /// \brief Gives back the residual capacity of the arc. 3.2567 + /// 3.2568 + /// Gives back the residual capacity of the arc. 3.2569 + Value residualCapacity(const Arc& a) const { 3.2570 + if (Undirected::direction(a)) { 3.2571 + return (*_capacity)[a] - (*_flow)[a]; 3.2572 + } else { 3.2573 + return (*_flow)[a]; 3.2574 + } 3.2575 + } 3.2576 + 3.2577 + /// \brief Augment on the given arc in the residual graph. 3.2578 + /// 3.2579 + /// Augment on the given arc in the residual graph. It increase 3.2580 + /// or decrease the flow on the original arc depend on the direction 3.2581 + /// of the residual arc. 3.2582 + void augment(const Arc& a, const Value& v) const { 3.2583 + if (Undirected::direction(a)) { 3.2584 + _flow->set(a, (*_flow)[a] + v); 3.2585 + } else { 3.2586 + _flow->set(a, (*_flow)[a] - v); 3.2587 + } 3.2588 + } 3.2589 + 3.2590 + /// \brief Returns the direction of the arc. 3.2591 + /// 3.2592 + /// Returns true when the arc is same oriented as the original arc. 3.2593 + static bool forward(const Arc& a) { 3.2594 + return Undirected::direction(a); 3.2595 + } 3.2596 + 3.2597 + /// \brief Returns the direction of the arc. 3.2598 + /// 3.2599 + /// Returns true when the arc is opposite oriented as the original arc. 3.2600 + static bool backward(const Arc& a) { 3.2601 + return !Undirected::direction(a); 3.2602 + } 3.2603 + 3.2604 + /// \brief Gives back the forward oriented residual arc. 3.2605 + /// 3.2606 + /// Gives back the forward oriented residual arc. 3.2607 + static Arc forward(const typename Digraph::Arc& a) { 3.2608 + return Undirected::direct(a, true); 3.2609 + } 3.2610 + 3.2611 + /// \brief Gives back the backward oriented residual arc. 3.2612 + /// 3.2613 + /// Gives back the backward oriented residual arc. 3.2614 + static Arc backward(const typename Digraph::Arc& a) { 3.2615 + return Undirected::direct(a, false); 3.2616 + } 3.2617 + 3.2618 + /// \brief Residual capacity map. 3.2619 + /// 3.2620 + /// In generic residual graph the residual capacity can be obtained 3.2621 + /// as a map. 3.2622 + class ResidualCapacity { 3.2623 + protected: 3.2624 + const Adaptor* _adaptor; 3.2625 + public: 3.2626 + /// The Key type 3.2627 + typedef Arc Key; 3.2628 + /// The Value type 3.2629 + typedef typename _CapacityMap::Value Value; 3.2630 + 3.2631 + /// Constructor 3.2632 + ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {} 3.2633 + 3.2634 + /// \e 3.2635 + Value operator[](const Arc& a) const { 3.2636 + return _adaptor->residualCapacity(a); 3.2637 + } 3.2638 + 3.2639 + }; 3.2640 + 3.2641 + }; 3.2642 + 3.2643 + template <typename _Digraph> 3.2644 + class SplitNodesBase { 3.2645 + public: 3.2646 + 3.2647 + typedef _Digraph Digraph; 3.2648 + typedef DigraphAdaptorBase<const _Digraph> Parent; 3.2649 + typedef SplitNodesBase Adaptor; 3.2650 + 3.2651 + typedef typename Digraph::Node DigraphNode; 3.2652 + typedef typename Digraph::Arc DigraphArc; 3.2653 + 3.2654 + class Node; 3.2655 + class Arc; 3.2656 + 3.2657 + private: 3.2658 + 3.2659 + template <typename T> class NodeMapBase; 3.2660 + template <typename T> class ArcMapBase; 3.2661 + 3.2662 + public: 3.2663 + 3.2664 + class Node : public DigraphNode { 3.2665 + friend class SplitNodesBase; 3.2666 + template <typename T> friend class NodeMapBase; 3.2667 + private: 3.2668 + 3.2669 + bool _in; 3.2670 + Node(DigraphNode node, bool in) 3.2671 + : DigraphNode(node), _in(in) {} 3.2672 + 3.2673 + public: 3.2674 + 3.2675 + Node() {} 3.2676 + Node(Invalid) : DigraphNode(INVALID), _in(true) {} 3.2677 + 3.2678 + bool operator==(const Node& node) const { 3.2679 + return DigraphNode::operator==(node) && _in == node._in; 3.2680 + } 3.2681 + 3.2682 + bool operator!=(const Node& node) const { 3.2683 + return !(*this == node); 3.2684 + } 3.2685 + 3.2686 + bool operator<(const Node& node) const { 3.2687 + return DigraphNode::operator<(node) || 3.2688 + (DigraphNode::operator==(node) && _in < node._in); 3.2689 + } 3.2690 + }; 3.2691 + 3.2692 + class Arc { 3.2693 + friend class SplitNodesBase; 3.2694 + template <typename T> friend class ArcMapBase; 3.2695 + private: 3.2696 + typedef BiVariant<DigraphArc, DigraphNode> ArcImpl; 3.2697 + 3.2698 + explicit Arc(const DigraphArc& arc) : _item(arc) {} 3.2699 + explicit Arc(const DigraphNode& node) : _item(node) {} 3.2700 + 3.2701 + ArcImpl _item; 3.2702 + 3.2703 + public: 3.2704 + Arc() {} 3.2705 + Arc(Invalid) : _item(DigraphArc(INVALID)) {} 3.2706 + 3.2707 + bool operator==(const Arc& arc) const { 3.2708 + if (_item.firstState()) { 3.2709 + if (arc._item.firstState()) { 3.2710 + return _item.first() == arc._item.first(); 3.2711 + } 3.2712 + } else { 3.2713 + if (arc._item.secondState()) { 3.2714 + return _item.second() == arc._item.second(); 3.2715 + } 3.2716 + } 3.2717 + return false; 3.2718 + } 3.2719 + 3.2720 + bool operator!=(const Arc& arc) const { 3.2721 + return !(*this == arc); 3.2722 + } 3.2723 + 3.2724 + bool operator<(const Arc& arc) const { 3.2725 + if (_item.firstState()) { 3.2726 + if (arc._item.firstState()) { 3.2727 + return _item.first() < arc._item.first(); 3.2728 + } 3.2729 + return false; 3.2730 + } else { 3.2731 + if (arc._item.secondState()) { 3.2732 + return _item.second() < arc._item.second(); 3.2733 + } 3.2734 + return true; 3.2735 + } 3.2736 + } 3.2737 + 3.2738 + operator DigraphArc() const { return _item.first(); } 3.2739 + operator DigraphNode() const { return _item.second(); } 3.2740 + 3.2741 + }; 3.2742 + 3.2743 + void first(Node& n) const { 3.2744 + _digraph->first(n); 3.2745 + n._in = true; 3.2746 + } 3.2747 + 3.2748 + void next(Node& n) const { 3.2749 + if (n._in) { 3.2750 + n._in = false; 3.2751 + } else { 3.2752 + n._in = true; 3.2753 + _digraph->next(n); 3.2754 + } 3.2755 + } 3.2756 + 3.2757 + void first(Arc& e) const { 3.2758 + e._item.setSecond(); 3.2759 + _digraph->first(e._item.second()); 3.2760 + if (e._item.second() == INVALID) { 3.2761 + e._item.setFirst(); 3.2762 + _digraph->first(e._item.first()); 3.2763 + } 3.2764 + } 3.2765 + 3.2766 + void next(Arc& e) const { 3.2767 + if (e._item.secondState()) { 3.2768 + _digraph->next(e._item.second()); 3.2769 + if (e._item.second() == INVALID) { 3.2770 + e._item.setFirst(); 3.2771 + _digraph->first(e._item.first()); 3.2772 + } 3.2773 + } else { 3.2774 + _digraph->next(e._item.first()); 3.2775 + } 3.2776 + } 3.2777 + 3.2778 + void firstOut(Arc& e, const Node& n) const { 3.2779 + if (n._in) { 3.2780 + e._item.setSecond(n); 3.2781 + } else { 3.2782 + e._item.setFirst(); 3.2783 + _digraph->firstOut(e._item.first(), n); 3.2784 + } 3.2785 + } 3.2786 + 3.2787 + void nextOut(Arc& e) const { 3.2788 + if (!e._item.firstState()) { 3.2789 + e._item.setFirst(INVALID); 3.2790 + } else { 3.2791 + _digraph->nextOut(e._item.first()); 3.2792 + } 3.2793 + } 3.2794 + 3.2795 + void firstIn(Arc& e, const Node& n) const { 3.2796 + if (!n._in) { 3.2797 + e._item.setSecond(n); 3.2798 + } else { 3.2799 + e._item.setFirst(); 3.2800 + _digraph->firstIn(e._item.first(), n); 3.2801 + } 3.2802 + } 3.2803 + 3.2804 + void nextIn(Arc& e) const { 3.2805 + if (!e._item.firstState()) { 3.2806 + e._item.setFirst(INVALID); 3.2807 + } else { 3.2808 + _digraph->nextIn(e._item.first()); 3.2809 + } 3.2810 + } 3.2811 + 3.2812 + Node source(const Arc& e) const { 3.2813 + if (e._item.firstState()) { 3.2814 + return Node(_digraph->source(e._item.first()), false); 3.2815 + } else { 3.2816 + return Node(e._item.second(), true); 3.2817 + } 3.2818 + } 3.2819 + 3.2820 + Node target(const Arc& e) const { 3.2821 + if (e._item.firstState()) { 3.2822 + return Node(_digraph->target(e._item.first()), true); 3.2823 + } else { 3.2824 + return Node(e._item.second(), false); 3.2825 + } 3.2826 + } 3.2827 + 3.2828 + int id(const Node& n) const { 3.2829 + return (_digraph->id(n) << 1) | (n._in ? 0 : 1); 3.2830 + } 3.2831 + Node nodeFromId(int ix) const { 3.2832 + return Node(_digraph->nodeFromId(ix >> 1), (ix & 1) == 0); 3.2833 + } 3.2834 + int maxNodeId() const { 3.2835 + return 2 * _digraph->maxNodeId() + 1; 3.2836 + } 3.2837 + 3.2838 + int id(const Arc& e) const { 3.2839 + if (e._item.firstState()) { 3.2840 + return _digraph->id(e._item.first()) << 1; 3.2841 + } else { 3.2842 + return (_digraph->id(e._item.second()) << 1) | 1; 3.2843 + } 3.2844 + } 3.2845 + Arc arcFromId(int ix) const { 3.2846 + if ((ix & 1) == 0) { 3.2847 + return Arc(_digraph->arcFromId(ix >> 1)); 3.2848 + } else { 3.2849 + return Arc(_digraph->nodeFromId(ix >> 1)); 3.2850 + } 3.2851 + } 3.2852 + int maxArcId() const { 3.2853 + return std::max(_digraph->maxNodeId() << 1, 3.2854 + (_digraph->maxArcId() << 1) | 1); 3.2855 + } 3.2856 + 3.2857 + static bool inNode(const Node& n) { 3.2858 + return n._in; 3.2859 + } 3.2860 + 3.2861 + static bool outNode(const Node& n) { 3.2862 + return !n._in; 3.2863 + } 3.2864 + 3.2865 + static bool origArc(const Arc& e) { 3.2866 + return e._item.firstState(); 3.2867 + } 3.2868 + 3.2869 + static bool bindArc(const Arc& e) { 3.2870 + return e._item.secondState(); 3.2871 + } 3.2872 + 3.2873 + static Node inNode(const DigraphNode& n) { 3.2874 + return Node(n, true); 3.2875 + } 3.2876 + 3.2877 + static Node outNode(const DigraphNode& n) { 3.2878 + return Node(n, false); 3.2879 + } 3.2880 + 3.2881 + static Arc arc(const DigraphNode& n) { 3.2882 + return Arc(n); 3.2883 + } 3.2884 + 3.2885 + static Arc arc(const DigraphArc& e) { 3.2886 + return Arc(e); 3.2887 + } 3.2888 + 3.2889 + typedef True NodeNumTag; 3.2890 + 3.2891 + int nodeNum() const { 3.2892 + return 2 * countNodes(*_digraph); 3.2893 + } 3.2894 + 3.2895 + typedef True EdgeNumTag; 3.2896 + int arcNum() const { 3.2897 + return countArcs(*_digraph) + countNodes(*_digraph); 3.2898 + } 3.2899 + 3.2900 + typedef True FindEdgeTag; 3.2901 + Arc findArc(const Node& u, const Node& v, 3.2902 + const Arc& prev = INVALID) const { 3.2903 + if (inNode(u)) { 3.2904 + if (outNode(v)) { 3.2905 + if (static_cast<const DigraphNode&>(u) == 3.2906 + static_cast<const DigraphNode&>(v) && prev == INVALID) { 3.2907 + return Arc(u); 3.2908 + } 3.2909 + } 3.2910 + } else { 3.2911 + if (inNode(v)) { 3.2912 + return Arc(::lemon::findArc(*_digraph, u, v, prev)); 3.2913 + } 3.2914 + } 3.2915 + return INVALID; 3.2916 + } 3.2917 + 3.2918 + private: 3.2919 + 3.2920 + template <typename _Value> 3.2921 + class NodeMapBase 3.2922 + : public MapTraits<typename Parent::template NodeMap<_Value> > { 3.2923 + typedef typename Parent::template NodeMap<_Value> NodeImpl; 3.2924 + public: 3.2925 + typedef Node Key; 3.2926 + typedef _Value Value; 3.2927 + 3.2928 + NodeMapBase(const Adaptor& adaptor) 3.2929 + : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {} 3.2930 + NodeMapBase(const Adaptor& adaptor, const Value& value) 3.2931 + : _in_map(*adaptor._digraph, value), 3.2932 + _out_map(*adaptor._digraph, value) {} 3.2933 + 3.2934 + void set(const Node& key, const Value& val) { 3.2935 + if (Adaptor::inNode(key)) { _in_map.set(key, val); } 3.2936 + else {_out_map.set(key, val); } 3.2937 + } 3.2938 + 3.2939 + typename MapTraits<NodeImpl>::ReturnValue 3.2940 + operator[](const Node& key) { 3.2941 + if (Adaptor::inNode(key)) { return _in_map[key]; } 3.2942 + else { return _out_map[key]; } 3.2943 + } 3.2944 + 3.2945 + typename MapTraits<NodeImpl>::ConstReturnValue 3.2946 + operator[](const Node& key) const { 3.2947 + if (Adaptor::inNode(key)) { return _in_map[key]; } 3.2948 + else { return _out_map[key]; } 3.2949 + } 3.2950 + 3.2951 + private: 3.2952 + NodeImpl _in_map, _out_map; 3.2953 + }; 3.2954 + 3.2955 + template <typename _Value> 3.2956 + class ArcMapBase 3.2957 + : public MapTraits<typename Parent::template ArcMap<_Value> > { 3.2958 + typedef typename Parent::template ArcMap<_Value> ArcImpl; 3.2959 + typedef typename Parent::template NodeMap<_Value> NodeImpl; 3.2960 + public: 3.2961 + typedef Arc Key; 3.2962 + typedef _Value Value; 3.2963 + 3.2964 + ArcMapBase(const Adaptor& adaptor) 3.2965 + : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {} 3.2966 + ArcMapBase(const Adaptor& adaptor, const Value& value) 3.2967 + : _arc_map(*adaptor._digraph, value), 3.2968 + _node_map(*adaptor._digraph, value) {} 3.2969 + 3.2970 + void set(const Arc& key, const Value& val) { 3.2971 + if (Adaptor::origArc(key)) { 3.2972 + _arc_map.set(key._item.first(), val); 3.2973 + } else { 3.2974 + _node_map.set(key._item.second(), val); 3.2975 + } 3.2976 + } 3.2977 + 3.2978 + typename MapTraits<ArcImpl>::ReturnValue 3.2979 + operator[](const Arc& key) { 3.2980 + if (Adaptor::origArc(key)) { 3.2981 + return _arc_map[key._item.first()]; 3.2982 + } else { 3.2983 + return _node_map[key._item.second()]; 3.2984 + } 3.2985 + } 3.2986 + 3.2987 + typename MapTraits<ArcImpl>::ConstReturnValue 3.2988 + operator[](const Arc& key) const { 3.2989 + if (Adaptor::origArc(key)) { 3.2990 + return _arc_map[key._item.first()]; 3.2991 + } else { 3.2992 + return _node_map[key._item.second()]; 3.2993 + } 3.2994 + } 3.2995 + 3.2996 + private: 3.2997 + ArcImpl _arc_map; 3.2998 + NodeImpl _node_map; 3.2999 + }; 3.3000 + 3.3001 + public: 3.3002 + 3.3003 + template <typename _Value> 3.3004 + class NodeMap 3.3005 + : public SubMapExtender<Adaptor, NodeMapBase<_Value> > 3.3006 + { 3.3007 + public: 3.3008 + typedef _Value Value; 3.3009 + typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent; 3.3010 + 3.3011 + NodeMap(const Adaptor& adaptor) 3.3012 + : Parent(adaptor) {} 3.3013 + 3.3014 + NodeMap(const Adaptor& adaptor, const Value& value) 3.3015 + : Parent(adaptor, value) {} 3.3016 + 3.3017 + private: 3.3018 + NodeMap& operator=(const NodeMap& cmap) { 3.3019 + return operator=<NodeMap>(cmap); 3.3020 + } 3.3021 + 3.3022 + template <typename CMap> 3.3023 + NodeMap& operator=(const CMap& cmap) { 3.3024 + Parent::operator=(cmap); 3.3025 + return *this; 3.3026 + } 3.3027 + }; 3.3028 + 3.3029 + template <typename _Value> 3.3030 + class ArcMap 3.3031 + : public SubMapExtender<Adaptor, ArcMapBase<_Value> > 3.3032 + { 3.3033 + public: 3.3034 + typedef _Value Value; 3.3035 + typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent; 3.3036 + 3.3037 + ArcMap(const Adaptor& adaptor) 3.3038 + : Parent(adaptor) {} 3.3039 + 3.3040 + ArcMap(const Adaptor& adaptor, const Value& value) 3.3041 + : Parent(adaptor, value) {} 3.3042 + 3.3043 + private: 3.3044 + ArcMap& operator=(const ArcMap& cmap) { 3.3045 + return operator=<ArcMap>(cmap); 3.3046 + } 3.3047 + 3.3048 + template <typename CMap> 3.3049 + ArcMap& operator=(const CMap& cmap) { 3.3050 + Parent::operator=(cmap); 3.3051 + return *this; 3.3052 + } 3.3053 + }; 3.3054 + 3.3055 + protected: 3.3056 + 3.3057 + SplitNodesBase() : _digraph(0) {} 3.3058 + 3.3059 + Digraph* _digraph; 3.3060 + 3.3061 + void setDigraph(Digraph& digraph) { 3.3062 + _digraph = &digraph; 3.3063 + } 3.3064 + 3.3065 + }; 3.3066 + 3.3067 + /// \ingroup graph_adaptors 3.3068 + /// 3.3069 + /// \brief Split the nodes of a directed graph 3.3070 + /// 3.3071 + /// The SplitNodes adaptor splits each node into an in-node and an 3.3072 + /// out-node. Formaly, the adaptor replaces each \f$ u \f$node in 3.3073 + /// the digraph with two nodes(namely node \f$ u_{in} \f$and node 3.3074 + /// \f$ u_{out} \f$). If there is a \f$ (v, u) \f$arc in the 3.3075 + /// original digraph the new target of the arc will be \f$ u_{in} \f$3.3076 + /// and similarly the source of the original \f$ (u, v) \f$arc 3.3077 + /// will be \f$ u_{out} \f$. The adaptor will add for each node in 3.3078 + /// the original digraph an additional arc which connects 3.3079 + /// \f$ (u_{in}, u_{out}) \f\$.
3.3080 +  ///
3.3081 +  /// The aim of this class is to run algorithm with node costs if the
3.3082 +  /// algorithm can use directly just arc costs. In this case we should use
3.3083 +  /// a \c SplitNodes and set the node cost of the graph to the
3.3084 +  /// bind arc in the adapted graph.
3.3085 +  ///
3.3086 +  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
3.3087 +  /// "Digraph concept". The type can be specified to be const.
3.3088 +  template <typename _Digraph>
3.3089 +  class SplitNodes
3.3090 +    : public DigraphAdaptorExtender<SplitNodesBase<_Digraph> > {
3.3091 +  public:
3.3092 +    typedef _Digraph Digraph;
3.3093 +    typedef DigraphAdaptorExtender<SplitNodesBase<Digraph> > Parent;
3.3094 +
3.3095 +    typedef typename Digraph::Node DigraphNode;
3.3096 +    typedef typename Digraph::Arc DigraphArc;
3.3097 +
3.3098 +    typedef typename Parent::Node Node;
3.3099 +    typedef typename Parent::Arc Arc;
3.3100 +
3.3101 +    /// \brief Constructor of the adaptor.
3.3102 +    ///
3.3103 +    /// Constructor of the adaptor.
3.3104 +    SplitNodes(Digraph& g) {
3.3105 +      Parent::setDigraph(g);
3.3106 +    }
3.3107 +
3.3108 +    /// \brief Returns true when the node is in-node.
3.3109 +    ///
3.3110 +    /// Returns true when the node is in-node.
3.3111 +    static bool inNode(const Node& n) {
3.3112 +      return Parent::inNode(n);
3.3113 +    }
3.3114 +
3.3115 +    /// \brief Returns true when the node is out-node.
3.3116 +    ///
3.3117 +    /// Returns true when the node is out-node.
3.3118 +    static bool outNode(const Node& n) {
3.3119 +      return Parent::outNode(n);
3.3120 +    }
3.3121 +
3.3122 +    /// \brief Returns true when the arc is arc in the original digraph.
3.3123 +    ///
3.3124 +    /// Returns true when the arc is arc in the original digraph.
3.3125 +    static bool origArc(const Arc& a) {
3.3126 +      return Parent::origArc(a);
3.3127 +    }
3.3128 +
3.3129 +    /// \brief Returns true when the arc binds an in-node and an out-node.
3.3130 +    ///
3.3131 +    /// Returns true when the arc binds an in-node and an out-node.
3.3132 +    static bool bindArc(const Arc& a) {
3.3133 +      return Parent::bindArc(a);
3.3134 +    }
3.3135 +
3.3136 +    /// \brief Gives back the in-node created from the \c node.
3.3137 +    ///
3.3138 +    /// Gives back the in-node created from the \c node.
3.3139 +    static Node inNode(const DigraphNode& n) {
3.3140 +      return Parent::inNode(n);
3.3141 +    }
3.3142 +
3.3143 +    /// \brief Gives back the out-node created from the \c node.
3.3144 +    ///
3.3145 +    /// Gives back the out-node created from the \c node.
3.3146 +    static Node outNode(const DigraphNode& n) {
3.3147 +      return Parent::outNode(n);
3.3148 +    }
3.3149 +
3.3150 +    /// \brief Gives back the arc binds the two part of the node.
3.3151 +    ///
3.3152 +    /// Gives back the arc binds the two part of the node.
3.3153 +    static Arc arc(const DigraphNode& n) {
3.3154 +      return Parent::arc(n);
3.3155 +    }
3.3156 +
3.3157 +    /// \brief Gives back the arc of the original arc.
3.3158 +    ///
3.3159 +    /// Gives back the arc of the original arc.
3.3160 +    static Arc arc(const DigraphArc& a) {
3.3161 +      return Parent::arc(a);
3.3162 +    }
3.3163 +
3.3164 +    /// \brief NodeMap combined from two original NodeMap
3.3165 +    ///
3.3166 +    /// This class adapt two of the original digraph NodeMap to
3.3167 +    /// get a node map on the adapted digraph.
3.3168 +    template <typename InNodeMap, typename OutNodeMap>
3.3169 +    class CombinedNodeMap {
3.3170 +    public:
3.3171 +
3.3172 +      typedef Node Key;
3.3173 +      typedef typename InNodeMap::Value Value;
3.3174 +
3.3175 +      /// \brief Constructor
3.3176 +      ///
3.3177 +      /// Constructor.
3.3178 +      CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
3.3179 +        : _in_map(in_map), _out_map(out_map) {}
3.3180 +
3.3181 +      /// \brief The subscript operator.
3.3182 +      ///
3.3183 +      /// The subscript operator.
3.3184 +      Value& operator[](const Key& key) {
3.3185 +        if (Parent::inNode(key)) {
3.3186 +          return _in_map[key];
3.3187 +        } else {
3.3188 +          return _out_map[key];
3.3189 +        }
3.3190 +      }
3.3191 +
3.3192 +      /// \brief The const subscript operator.
3.3193 +      ///
3.3194 +      /// The const subscript operator.
3.3195 +      Value operator[](const Key& key) const {
3.3196 +        if (Parent::inNode(key)) {
3.3197 +          return _in_map[key];
3.3198 +        } else {
3.3199 +          return _out_map[key];
3.3200 +        }
3.3201 +      }
3.3202 +
3.3203 +      /// \brief The setter function of the map.
3.3204 +      ///
3.3205 +      /// The setter function of the map.
3.3206 +      void set(const Key& key, const Value& value) {
3.3207 +        if (Parent::inNode(key)) {
3.3208 +          _in_map.set(key, value);
3.3209 +        } else {
3.3210 +          _out_map.set(key, value);
3.3211 +        }
3.3212 +      }
3.3213 +
3.3214 +    private:
3.3215 +
3.3216 +      InNodeMap& _in_map;
3.3217 +      OutNodeMap& _out_map;
3.3218 +
3.3219 +    };
3.3220 +
3.3221 +
3.3222 +    /// \brief Just gives back a combined node map
3.3223 +    ///
3.3224 +    /// Just gives back a combined node map
3.3225 +    template <typename InNodeMap, typename OutNodeMap>
3.3226 +    static CombinedNodeMap<InNodeMap, OutNodeMap>
3.3227 +    combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
3.3228 +      return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
3.3229 +    }
3.3230 +
3.3231 +    template <typename InNodeMap, typename OutNodeMap>
3.3232 +    static CombinedNodeMap<const InNodeMap, OutNodeMap>
3.3233 +    combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
3.3234 +      return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
3.3235 +    }
3.3236 +
3.3237 +    template <typename InNodeMap, typename OutNodeMap>
3.3238 +    static CombinedNodeMap<InNodeMap, const OutNodeMap>
3.3239 +    combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
3.3240 +      return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
3.3241 +    }
3.3242 +
3.3243 +    template <typename InNodeMap, typename OutNodeMap>
3.3244 +    static CombinedNodeMap<const InNodeMap, const OutNodeMap>
3.3245 +    combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
3.3246 +      return CombinedNodeMap<const InNodeMap,
3.3247 +        const OutNodeMap>(in_map, out_map);
3.3248 +    }
3.3249 +
3.3250 +    /// \brief ArcMap combined from an original ArcMap and a NodeMap
3.3251 +    ///
3.3252 +    /// This class adapt an original ArcMap and a NodeMap to get an
3.3253 +    /// arc map on the adapted digraph
3.3254 +    template <typename DigraphArcMap, typename DigraphNodeMap>
3.3255 +    class CombinedArcMap {
3.3256 +    public:
3.3257 +
3.3258 +      typedef Arc Key;
3.3259 +      typedef typename DigraphArcMap::Value Value;
3.3260 +
3.3261 +      /// \brief Constructor
3.3262 +      ///
3.3263 +      /// Constructor.
3.3264 +      CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)
3.3265 +        : _arc_map(arc_map), _node_map(node_map) {}
3.3266 +
3.3267 +      /// \brief The subscript operator.
3.3268 +      ///
3.3269 +      /// The subscript operator.
3.3270 +      void set(const Arc& arc, const Value& val) {
3.3271 +        if (Parent::origArc(arc)) {
3.3272 +          _arc_map.set(arc, val);
3.3273 +        } else {
3.3274 +          _node_map.set(arc, val);
3.3275 +        }
3.3276 +      }
3.3277 +
3.3278 +      /// \brief The const subscript operator.
3.3279 +      ///
3.3280 +      /// The const subscript operator.
3.3281 +      Value operator[](const Key& arc) const {
3.3282 +        if (Parent::origArc(arc)) {
3.3283 +          return _arc_map[arc];
3.3284 +        } else {
3.3285 +          return _node_map[arc];
3.3286 +        }
3.3287 +      }
3.3288 +
3.3289 +      /// \brief The const subscript operator.
3.3290 +      ///
3.3291 +      /// The const subscript operator.
3.3292 +      Value& operator[](const Key& arc) {
3.3293 +        if (Parent::origArc(arc)) {
3.3294 +          return _arc_map[arc];
3.3295 +        } else {
3.3296 +          return _node_map[arc];
3.3297 +        }
3.3298 +      }
3.3299 +
3.3300 +    private:
3.3301 +      DigraphArcMap& _arc_map;
3.3302 +      DigraphNodeMap& _node_map;
3.3303 +    };
3.3304 +
3.3305 +    /// \brief Just gives back a combined arc map
3.3306 +    ///
3.3307 +    /// Just gives back a combined arc map
3.3308 +    template <typename DigraphArcMap, typename DigraphNodeMap>
3.3309 +    static CombinedArcMap<DigraphArcMap, DigraphNodeMap>
3.3310 +    combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
3.3311 +      return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map);
3.3312 +    }
3.3313 +
3.3314 +    template <typename DigraphArcMap, typename DigraphNodeMap>
3.3315 +    static CombinedArcMap<const DigraphArcMap, DigraphNodeMap>
3.3316 +    combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
3.3317 +      return CombinedArcMap<const DigraphArcMap,
3.3318 +        DigraphNodeMap>(arc_map, node_map);
3.3319 +    }
3.3320 +
3.3321 +    template <typename DigraphArcMap, typename DigraphNodeMap>
3.3322 +    static CombinedArcMap<DigraphArcMap, const DigraphNodeMap>
3.3323 +    combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) {
3.3324 +      return CombinedArcMap<DigraphArcMap,
3.3325 +        const DigraphNodeMap>(arc_map, node_map);
3.3326 +    }
3.3327 +
3.3328 +    template <typename DigraphArcMap, typename DigraphNodeMap>
3.3329 +    static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap>
3.3330 +    combinedArcMap(const DigraphArcMap& arc_map,
3.3331 +                   const DigraphNodeMap& node_map) {
3.3332 +      return CombinedArcMap<const DigraphArcMap,
3.3333 +        const DigraphNodeMap>(arc_map, node_map);
3.3334 +    }
3.3335 +
3.3336 +  };
3.3337 +
3.3338 +  /// \brief Just gives back a node splitter
3.3339 +  ///
3.3340 +  /// Just gives back a node splitter
3.3341 +  template<typename Digraph>
3.3342 +  SplitNodes<Digraph>
3.3343 +  splitNodes(const Digraph& digraph) {
3.3344 +    return SplitNodes<Digraph>(digraph);
3.3345 +  }
3.3346 +
3.3347 +
3.3348 +} //namespace lemon
3.3349 +

     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/bits/graph_adaptor_extender.h	Tue Dec 02 15:33:22 2008 +0000
4.3 @@ -0,0 +1,403 @@
4.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
4.5 + *
4.6 + * This file is a part of LEMON, a generic C++ optimization library.
4.7 + *
4.8 + * Copyright (C) 2003-2008
4.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.11 + *
4.12 + * Permission to use, modify and distribute this software is granted
4.13 + * provided that this copyright notice appears in all copies. For
4.14 + * precise terms see the accompanying LICENSE file.
4.15 + *
4.16 + * This software is provided "AS IS" with no warranty of any kind,
4.17 + * express or implied, and with no claim as to its suitability for any
4.18 + * purpose.
4.19 + *
4.20 + */
4.21 +
4.24 +
4.25 +#include <lemon/core.h>
4.26 +#include <lemon/error.h>
4.27 +
4.28 +#include <lemon/bits/default_map.h>
4.29 +
4.30 +namespace lemon {
4.31 +
4.32 +  template <typename _Digraph>
4.33 +  class DigraphAdaptorExtender : public _Digraph {
4.34 +  public:
4.35 +
4.36 +    typedef _Digraph Parent;
4.37 +    typedef _Digraph Digraph;
4.39 +
4.40 +    // Base extensions
4.41 +
4.42 +    typedef typename Parent::Node Node;
4.43 +    typedef typename Parent::Arc Arc;
4.44 +
4.45 +    int maxId(Node) const {
4.46 +      return Parent::maxNodeId();
4.47 +    }
4.48 +
4.49 +    int maxId(Arc) const {
4.50 +      return Parent::maxArcId();
4.51 +    }
4.52 +
4.53 +    Node fromId(int id, Node) const {
4.54 +      return Parent::nodeFromId(id);
4.55 +    }
4.56 +
4.57 +    Arc fromId(int id, Arc) const {
4.58 +      return Parent::arcFromId(id);
4.59 +    }
4.60 +
4.61 +    Node oppositeNode(const Node &n, const Arc &e) const {
4.62 +      if (n == Parent::source(e))
4.63 +        return Parent::target(e);
4.64 +      else if(n==Parent::target(e))
4.65 +        return Parent::source(e);
4.66 +      else
4.67 +        return INVALID;
4.68 +    }
4.69 +
4.70 +    class NodeIt : public Node {
4.72 +    public:
4.73 +
4.74 +      NodeIt() {}
4.75 +
4.76 +      NodeIt(Invalid i) : Node(i) { }
4.77 +
4.80 +      }
4.81 +
4.84 +
4.85 +      NodeIt& operator++() {
4.87 +        return *this;
4.88 +      }
4.89 +
4.90 +    };
4.91 +
4.92 +
4.93 +    class ArcIt : public Arc {
4.95 +    public:
4.96 +
4.97 +      ArcIt() { }
4.98 +
4.99 +      ArcIt(Invalid i) : Arc(i) { }
4.100 +
4.103 +      }
4.104 +
4.107 +
4.108 +      ArcIt& operator++() {
4.110 +        return *this;
4.111 +      }
4.112 +
4.113 +    };
4.114 +
4.115 +
4.116 +    class OutArcIt : public Arc {
4.118 +    public:
4.119 +
4.120 +      OutArcIt() { }
4.121 +
4.122 +      OutArcIt(Invalid i) : Arc(i) { }
4.123 +
4.127 +      }
4.128 +
4.131 +
4.132 +      OutArcIt& operator++() {
4.134 +        return *this;
4.135 +      }
4.136 +
4.137 +    };
4.138 +
4.139 +
4.140 +    class InArcIt : public Arc {
4.142 +    public:
4.143 +
4.144 +      InArcIt() { }
4.145 +
4.146 +      InArcIt(Invalid i) : Arc(i) { }
4.147 +
4.151 +      }
4.152 +
4.155 +
4.156 +      InArcIt& operator++() {
4.158 +        return *this;
4.159 +      }
4.160 +
4.161 +    };
4.162 +
4.163 +    Node baseNode(const OutArcIt &e) const {
4.164 +      return Parent::source(e);
4.165 +    }
4.166 +    Node runningNode(const OutArcIt &e) const {
4.167 +      return Parent::target(e);
4.168 +    }
4.169 +
4.170 +    Node baseNode(const InArcIt &e) const {
4.171 +      return Parent::target(e);
4.172 +    }
4.173 +    Node runningNode(const InArcIt &e) const {
4.174 +      return Parent::source(e);
4.175 +    }
4.176 +
4.177 +  };
4.178 +
4.179 +
4.180 +  /// \ingroup digraphbits
4.181 +  ///
4.182 +  /// \brief Extender for the GraphAdaptors
4.183 +  template <typename _Graph>
4.184 +  class GraphAdaptorExtender : public _Graph {
4.185 +  public:
4.186 +
4.187 +    typedef _Graph Parent;
4.188 +    typedef _Graph Graph;
4.190 +
4.191 +    typedef typename Parent::Node Node;
4.192 +    typedef typename Parent::Arc Arc;
4.193 +    typedef typename Parent::Edge Edge;
4.194 +
4.195 +    // Graph extension
4.196 +
4.197 +    int maxId(Node) const {
4.198 +      return Parent::maxNodeId();
4.199 +    }
4.200 +
4.201 +    int maxId(Arc) const {
4.202 +      return Parent::maxArcId();
4.203 +    }
4.204 +
4.205 +    int maxId(Edge) const {
4.206 +      return Parent::maxEdgeId();
4.207 +    }
4.208 +
4.209 +    Node fromId(int id, Node) const {
4.210 +      return Parent::nodeFromId(id);
4.211 +    }
4.212 +
4.213 +    Arc fromId(int id, Arc) const {
4.214 +      return Parent::arcFromId(id);
4.215 +    }
4.216 +
4.217 +    Edge fromId(int id, Edge) const {
4.218 +      return Parent::edgeFromId(id);
4.219 +    }
4.220 +
4.221 +    Node oppositeNode(const Node &n, const Edge &e) const {
4.222 +      if( n == Parent::u(e))
4.223 +        return Parent::v(e);
4.224 +      else if( n == Parent::v(e))
4.225 +        return Parent::u(e);
4.226 +      else
4.227 +        return INVALID;
4.228 +    }
4.229 +
4.230 +    Arc oppositeArc(const Arc &a) const {
4.231 +      return Parent::direct(a, !Parent::direction(a));
4.232 +    }
4.233 +
4.234 +    using Parent::direct;
4.235 +    Arc direct(const Edge &e, const Node &s) const {
4.236 +      return Parent::direct(e, Parent::u(e) == s);
4.237 +    }
4.238 +
4.239 +
4.240 +    class NodeIt : public Node {
4.242 +    public:
4.243 +
4.244 +      NodeIt() {}
4.245 +
4.246 +      NodeIt(Invalid i) : Node(i) { }
4.247 +
4.250 +      }
4.251 +
4.254 +
4.255 +      NodeIt& operator++() {
4.257 +        return *this;
4.258 +      }
4.259 +
4.260 +    };
4.261 +
4.262 +
4.263 +    class ArcIt : public Arc {
4.265 +    public:
4.266 +
4.267 +      ArcIt() { }
4.268 +
4.269 +      ArcIt(Invalid i) : Arc(i) { }
4.270 +
4.273 +      }
4.274 +
4.277 +
4.278 +      ArcIt& operator++() {
4.280 +        return *this;
4.281 +      }
4.282 +
4.283 +    };
4.284 +
4.285 +
4.286 +    class OutArcIt : public Arc {
4.288 +    public:
4.289 +
4.290 +      OutArcIt() { }
4.291 +
4.292 +      OutArcIt(Invalid i) : Arc(i) { }
4.293 +
4.297 +      }
4.298 +
4.301 +
4.302 +      OutArcIt& operator++() {
4.304 +        return *this;
4.305 +      }
4.306 +
4.307 +    };
4.308 +
4.309 +
4.310 +    class InArcIt : public Arc {
4.312 +    public:
4.313 +
4.314 +      InArcIt() { }
4.315 +
4.316 +      InArcIt(Invalid i) : Arc(i) { }
4.317 +
4.321 +      }
4.322 +
4.325 +
4.326 +      InArcIt& operator++() {
4.328 +        return *this;
4.329 +      }
4.330 +
4.331 +    };
4.332 +
4.333 +    class EdgeIt : public Parent::Edge {
4.335 +    public:
4.336 +
4.337 +      EdgeIt() { }
4.338 +
4.339 +      EdgeIt(Invalid i) : Edge(i) { }
4.340 +
4.343 +      }
4.344 +
4.347 +
4.348 +      EdgeIt& operator++() {
4.350 +        return *this;
4.351 +      }
4.352 +
4.353 +    };
4.354 +
4.355 +    class IncEdgeIt : public Edge {
4.358 +      bool direction;
4.359 +    public:
4.360 +
4.361 +      IncEdgeIt() { }
4.362 +
4.363 +      IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
4.364 +
4.367 +      }
4.368 +
4.371 +        direction = (_adaptor->u(e) == n);
4.372 +      }
4.373 +
4.374 +      IncEdgeIt& operator++() {
4.376 +        return *this;
4.377 +      }
4.378 +    };
4.379 +
4.380 +    Node baseNode(const OutArcIt &a) const {
4.381 +      return Parent::source(a);
4.382 +    }
4.383 +    Node runningNode(const OutArcIt &a) const {
4.384 +      return Parent::target(a);
4.385 +    }
4.386 +
4.387 +    Node baseNode(const InArcIt &a) const {
4.388 +      return Parent::target(a);
4.389 +    }
4.390 +    Node runningNode(const InArcIt &a) const {
4.391 +      return Parent::source(a);
4.392 +    }
4.393 +
4.394 +    Node baseNode(const IncEdgeIt &e) const {
4.395 +      return e.direction ? Parent::u(e) : Parent::v(e);
4.396 +    }
4.397 +    Node runningNode(const IncEdgeIt &e) const {
4.398 +      return e.direction ? Parent::v(e) : Parent::u(e);
4.399 +    }
4.400 +
4.401 +  };
4.402 +
4.403 +}
4.404 +
4.405 +
4.406 +#endif

     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/lemon/bits/variant.h	Tue Dec 02 15:33:22 2008 +0000
5.3 @@ -0,0 +1,494 @@
5.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
5.5 + *
5.6 + * This file is a part of LEMON, a generic C++ optimization library.
5.7 + *
5.8 + * Copyright (C) 2003-2008
5.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
5.11 + *
5.12 + * Permission to use, modify and distribute this software is granted
5.13 + * provided that this copyright notice appears in all copies. For
5.14 + * precise terms see the accompanying LICENSE file.
5.15 + *
5.16 + * This software is provided "AS IS" with no warranty of any kind,
5.17 + * express or implied, and with no claim as to its suitability for any
5.18 + * purpose.
5.19 + *
5.20 + */
5.21 +
5.22 +#ifndef LEMON_BITS_VARIANT_H
5.23 +#define LEMON_BITS_VARIANT_H
5.24 +
5.25 +#include <lemon/assert.h>
5.26 +
5.27 +/// \file
5.28 +/// \brief Variant types
5.29 +
5.30 +namespace lemon {
5.31 +
5.32 +  namespace _variant_bits {
5.33 +
5.34 +    template <int left, int right>
5.35 +    struct CTMax {
5.36 +      static const int value = left < right ? right : left;
5.37 +    };
5.38 +
5.39 +  }
5.40 +
5.41 +
5.42 +  /// \brief Simple Variant type for two types
5.43 +  ///
5.44 +  /// Simple Variant type for two types. The Variant type is a type
5.45 +  /// safe union. The C++ has strong limitations for using unions, by
5.46 +  /// example we can not store type with non default constructor or
5.47 +  /// destructor in an union. This class always knowns the current
5.48 +  /// state of the variant and it cares for the proper construction
5.49 +  /// and destruction.
5.50 +  template <typename _First, typename _Second>
5.51 +  class BiVariant {
5.52 +  public:
5.53 +
5.54 +    /// \brief The \c First type.
5.55 +    typedef _First First;
5.56 +    /// \brief The \c Second type.
5.57 +    typedef _Second Second;
5.58 +
5.59 +    /// \brief Constructor
5.60 +    ///
5.61 +    /// This constructor initalizes to the default value of the \c First
5.62 +    /// type.
5.63 +    BiVariant() {
5.64 +      flag = true;
5.65 +      new(reinterpret_cast<First*>(data)) First();
5.66 +    }
5.67 +
5.68 +    /// \brief Constructor
5.69 +    ///
5.70 +    /// This constructor initalizes to the given value of the \c First
5.71 +    /// type.
5.72 +    BiVariant(const First& f) {
5.73 +      flag = true;
5.74 +      new(reinterpret_cast<First*>(data)) First(f);
5.75 +    }
5.76 +
5.77 +    /// \brief Constructor
5.78 +    ///
5.79 +    /// This constructor initalizes to the given value of the \c
5.80 +    /// Second type.
5.81 +    BiVariant(const Second& s) {
5.82 +      flag = false;
5.83 +      new(reinterpret_cast<Second*>(data)) Second(s);
5.84 +    }
5.85 +
5.86 +    /// \brief Copy constructor
5.87 +    ///
5.88 +    /// Copy constructor
5.89 +    BiVariant(const BiVariant& bivariant) {
5.90 +      flag = bivariant.flag;
5.91 +      if (flag) {
5.92 +        new(reinterpret_cast<First*>(data)) First(bivariant.first());
5.93 +      } else {
5.94 +        new(reinterpret_cast<Second*>(data)) Second(bivariant.second());
5.95 +      }
5.96 +    }
5.97 +
5.98 +    /// \brief Destrcutor
5.99 +    ///
5.100 +    /// Destructor
5.101 +    ~BiVariant() {
5.102 +      destroy();
5.103 +    }
5.104 +
5.105 +    /// \brief Set to the default value of the \c First type.
5.106 +    ///
5.107 +    /// This function sets the variant to the default value of the \c
5.108 +    /// First type.
5.109 +    BiVariant& setFirst() {
5.110 +      destroy();
5.111 +      flag = true;
5.112 +      new(reinterpret_cast<First*>(data)) First();
5.113 +      return *this;
5.114 +    }
5.115 +
5.116 +    /// \brief Set to the given value of the \c First type.
5.117 +    ///
5.118 +    /// This function sets the variant to the given value of the \c
5.119 +    /// First type.
5.120 +    BiVariant& setFirst(const First& f) {
5.121 +      destroy();
5.122 +      flag = true;
5.123 +      new(reinterpret_cast<First*>(data)) First(f);
5.124 +      return *this;
5.125 +    }
5.126 +
5.127 +    /// \brief Set to the default value of the \c Second type.
5.128 +    ///
5.129 +    /// This function sets the variant to the default value of the \c
5.130 +    /// Second type.
5.131 +    BiVariant& setSecond() {
5.132 +      destroy();
5.133 +      flag = false;
5.134 +      new(reinterpret_cast<Second*>(data)) Second();
5.135 +      return *this;
5.136 +    }
5.137 +
5.138 +    /// \brief Set to the given value of the \c Second type.
5.139 +    ///
5.140 +    /// This function sets the variant to the given value of the \c
5.141 +    /// Second type.
5.142 +    BiVariant& setSecond(const Second& s) {
5.143 +      destroy();
5.144 +      flag = false;
5.145 +      new(reinterpret_cast<Second*>(data)) Second(s);
5.146 +      return *this;
5.147 +    }
5.148 +
5.149 +    /// \brief Operator form of the \c setFirst()
5.150 +    BiVariant& operator=(const First& f) {
5.151 +      return setFirst(f);
5.152 +    }
5.153 +
5.154 +    /// \brief Operator form of the \c setSecond()
5.155 +    BiVariant& operator=(const Second& s) {
5.156 +      return setSecond(s);
5.157 +    }
5.158 +
5.159 +    /// \brief Assign operator
5.160 +    BiVariant& operator=(const BiVariant& bivariant) {
5.161 +      if (this == &bivariant) return *this;
5.162 +      destroy();
5.163 +      flag = bivariant.flag;
5.164 +      if (flag) {
5.165 +        new(reinterpret_cast<First*>(data)) First(bivariant.first());
5.166 +      } else {
5.167 +        new(reinterpret_cast<Second*>(data)) Second(bivariant.second());
5.168 +      }
5.169 +      return *this;
5.170 +    }
5.171 +
5.172 +    /// \brief Reference to the value
5.173 +    ///
5.174 +    /// Reference to the value of the \c First type.
5.175 +    /// \pre The BiVariant should store value of \c First type.
5.176 +    First& first() {
5.177 +      LEMON_DEBUG(flag, "Variant wrong state");
5.178 +      return *reinterpret_cast<First*>(data);
5.179 +    }
5.180 +
5.181 +    /// \brief Const reference to the value
5.182 +    ///
5.183 +    /// Const reference to the value of the \c First type.
5.184 +    /// \pre The BiVariant should store value of \c First type.
5.185 +    const First& first() const {
5.186 +      LEMON_DEBUG(flag, "Variant wrong state");
5.187 +      return *reinterpret_cast<const First*>(data);
5.188 +    }
5.189 +
5.190 +    /// \brief Operator form of the \c first()
5.191 +    operator First&() { return first(); }
5.192 +    /// \brief Operator form of the const \c first()
5.193 +    operator const First&() const { return first(); }
5.194 +
5.195 +    /// \brief Reference to the value
5.196 +    ///
5.197 +    /// Reference to the value of the \c Second type.
5.198 +    /// \pre The BiVariant should store value of \c Second type.
5.199 +    Second& second() {
5.200 +      LEMON_DEBUG(!flag, "Variant wrong state");
5.201 +      return *reinterpret_cast<Second*>(data);
5.202 +    }
5.203 +
5.204 +    /// \brief Const reference to the value
5.205 +    ///
5.206 +    /// Const reference to the value of the \c Second type.
5.207 +    /// \pre The BiVariant should store value of \c Second type.
5.208 +    const Second& second() const {
5.209 +      LEMON_DEBUG(!flag, "Variant wrong state");
5.210 +      return *reinterpret_cast<const Second*>(data);
5.211 +    }
5.212 +
5.213 +    /// \brief Operator form of the \c second()
5.214 +    operator Second&() { return second(); }
5.215 +    /// \brief Operator form of the const \c second()
5.216 +    operator const Second&() const { return second(); }
5.217 +
5.218 +    /// \brief %True when the variant is in the first state
5.219 +    ///
5.220 +    /// %True when the variant stores value of the \c First type.
5.221 +    bool firstState() const { return flag; }
5.222 +
5.223 +    /// \brief %True when the variant is in the second state
5.224 +    ///
5.225 +    /// %True when the variant stores value of the \c Second type.
5.226 +    bool secondState() const { return !flag; }
5.227 +
5.228 +  private:
5.229 +
5.230 +    void destroy() {
5.231 +      if (flag) {
5.232 +        reinterpret_cast<First*>(data)->~First();
5.233 +      } else {
5.234 +        reinterpret_cast<Second*>(data)->~Second();
5.235 +      }
5.236 +    }
5.237 +
5.238 +    char data[_variant_bits::CTMax<sizeof(First), sizeof(Second)>::value];
5.239 +    bool flag;
5.240 +  };
5.241 +
5.242 +  namespace _variant_bits {
5.243 +
5.244 +    template <int _idx, typename _TypeMap>
5.245 +    struct Memory {
5.246 +
5.247 +      typedef typename _TypeMap::template Map<_idx>::Type Current;
5.248 +
5.249 +      static void destroy(int index, char* place) {
5.250 +        if (index == _idx) {
5.251 +          reinterpret_cast<Current*>(place)->~Current();
5.252 +        } else {
5.253 +          Memory<_idx - 1, _TypeMap>::destroy(index, place);
5.254 +        }
5.255 +      }
5.256 +
5.257 +      static void copy(int index, char* to, const char* from) {
5.258 +        if (index == _idx) {
5.259 +          new (reinterpret_cast<Current*>(to))
5.260 +            Current(reinterpret_cast<const Current*>(from));
5.261 +        } else {
5.262 +          Memory<_idx - 1, _TypeMap>::copy(index, to, from);
5.263 +        }
5.264 +      }
5.265 +
5.266 +    };
5.267 +
5.268 +    template <typename _TypeMap>
5.269 +    struct Memory<-1, _TypeMap> {
5.270 +
5.271 +      static void destroy(int, char*) {
5.272 +        LEMON_DEBUG(false, "Variant wrong index.");
5.273 +      }
5.274 +
5.275 +      static void copy(int, char*, const char*) {
5.276 +        LEMON_DEBUG(false, "Variant wrong index.");
5.277 +      }
5.278 +    };
5.279 +
5.280 +    template <int _idx, typename _TypeMap>
5.281 +    struct Size {
5.282 +      static const int value =
5.283 +      CTMax<sizeof(typename _TypeMap::template Map<_idx>::Type),
5.284 +            Size<_idx - 1, _TypeMap>::value>::value;
5.285 +    };
5.286 +
5.287 +    template <typename _TypeMap>
5.288 +    struct Size<0, _TypeMap> {
5.289 +      static const int value =
5.290 +      sizeof(typename _TypeMap::template Map<0>::Type);
5.291 +    };
5.292 +
5.293 +  }
5.294 +
5.295 +  /// \brief Variant type
5.296 +  ///
5.297 +  /// Simple Variant type. The Variant type is a type safe union. The
5.298 +  /// C++ has strong limitations for using unions, for example we
5.299 +  /// cannot store type with non default constructor or destructor in
5.300 +  /// a union. This class always knowns the current state of the
5.301 +  /// variant and it cares for the proper construction and
5.302 +  /// destruction.
5.303 +  ///
5.304 +  /// \param _num The number of the types which can be stored in the
5.305 +  /// variant type.
5.306 +  /// \param _TypeMap This class describes the types of the Variant. The
5.307 +  /// _TypeMap::Map<index>::Type should be a valid type for each index
5.308 +  /// in the range {0, 1, ..., _num - 1}. The \c VariantTypeMap is helper
5.309 +  /// class to define such type mappings up to 10 types.
5.310 +  ///
5.311 +  /// And the usage of the class:
5.312 +  ///\code
5.313 +  /// typedef Variant<3, VariantTypeMap<int, std::string, double> > MyVariant;
5.314 +  /// MyVariant var;
5.315 +  /// var.set<0>(12);
5.316 +  /// std::cout << var.get<0>() << std::endl;
5.317 +  /// var.set<1>("alpha");
5.318 +  /// std::cout << var.get<1>() << std::endl;
5.319 +  /// var.set<2>(0.75);
5.320 +  /// std::cout << var.get<2>() << std::endl;
5.321 +  ///\endcode
5.322 +  ///
5.323 +  /// The result of course:
5.324 +  ///\code
5.325 +  /// 12
5.326 +  /// alpha
5.327 +  /// 0.75
5.328 +  ///\endcode
5.329 +  template <int _num, typename _TypeMap>
5.330 +  class Variant {
5.331 +  public:
5.332 +
5.333 +    static const int num = _num;
5.334 +
5.335 +    typedef _TypeMap TypeMap;
5.336 +
5.337 +    /// \brief Constructor
5.338 +    ///
5.339 +    /// This constructor initalizes to the default value of the \c type
5.340 +    /// with 0 index.
5.341 +    Variant() {
5.342 +      flag = 0;
5.343 +      new(reinterpret_cast<typename TypeMap::template Map<0>::Type*>(data))
5.344 +        typename TypeMap::template Map<0>::Type();
5.345 +    }
5.346 +
5.347 +
5.348 +    /// \brief Copy constructor
5.349 +    ///
5.350 +    /// Copy constructor
5.351 +    Variant(const Variant& variant) {
5.352 +      flag = variant.flag;
5.353 +      _variant_bits::Memory<num - 1, TypeMap>::copy(flag, data, variant.data);
5.354 +    }
5.355 +
5.356 +    /// \brief Assign operator
5.357 +    ///
5.358 +    /// Assign operator
5.359 +    Variant& operator=(const Variant& variant) {
5.360 +      if (this == &variant) return *this;
5.361 +      _variant_bits::Memory<num - 1, TypeMap>::
5.362 +        destroy(flag, data);
5.363 +      flag = variant.flag;
5.364 +      _variant_bits::Memory<num - 1, TypeMap>::
5.365 +        copy(flag, data, variant.data);
5.366 +      return *this;
5.367 +    }
5.368 +
5.369 +    /// \brief Destrcutor
5.370 +    ///
5.371 +    /// Destructor
5.372 +    ~Variant() {
5.373 +      _variant_bits::Memory<num - 1, TypeMap>::destroy(flag, data);
5.374 +    }
5.375 +
5.376 +    /// \brief Set to the default value of the type with \c _idx index.
5.377 +    ///
5.378 +    /// This function sets the variant to the default value of the
5.379 +    /// type with \c _idx index.
5.380 +    template <int _idx>
5.381 +    Variant& set() {
5.382 +      _variant_bits::Memory<num - 1, TypeMap>::destroy(flag, data);
5.383 +      flag = _idx;
5.384 +      new(reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>(data))
5.385 +        typename TypeMap::template Map<_idx>::Type();
5.386 +      return *this;
5.387 +    }
5.388 +
5.389 +    /// \brief Set to the given value of the type with \c _idx index.
5.390 +    ///
5.391 +    /// This function sets the variant to the given value of the type
5.392 +    /// with \c _idx index.
5.393 +    template <int _idx>
5.394 +    Variant& set(const typename _TypeMap::template Map<_idx>::Type& init) {
5.395 +      _variant_bits::Memory<num - 1, TypeMap>::destroy(flag, data);
5.396 +      flag = _idx;
5.397 +      new(reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>(data))
5.398 +        typename TypeMap::template Map<_idx>::Type(init);
5.399 +      return *this;
5.400 +    }
5.401 +
5.402 +    /// \brief Gets the current value of the type with \c _idx index.
5.403 +    ///
5.404 +    /// Gets the current value of the type with \c _idx index.
5.405 +    template <int _idx>
5.406 +    const typename TypeMap::template Map<_idx>::Type& get() const {
5.407 +      LEMON_DEBUG(_idx == flag, "Variant wrong index");
5.408 +      return *reinterpret_cast<const typename TypeMap::
5.409 +        template Map<_idx>::Type*>(data);
5.410 +    }
5.411 +
5.412 +    /// \brief Gets the current value of the type with \c _idx index.
5.413 +    ///
5.414 +    /// Gets the current value of the type with \c _idx index.
5.415 +    template <int _idx>
5.416 +    typename _TypeMap::template Map<_idx>::Type& get() {
5.417 +      LEMON_DEBUG(_idx == flag, "Variant wrong index");
5.418 +      return *reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>
5.419 +        (data);
5.420 +    }
5.421 +
5.422 +    /// \brief Returns the current state of the variant.
5.423 +    ///
5.424 +    /// Returns the current state of the variant.
5.425 +    int state() const {
5.426 +      return flag;
5.427 +    }
5.428 +
5.429 +  private:
5.430 +
5.431 +    char data[_variant_bits::Size<num - 1, TypeMap>::value];
5.432 +    int flag;
5.433 +  };
5.434 +
5.435 +  namespace _variant_bits {
5.436 +
5.437 +    template <int _index, typename _List>
5.438 +    struct Get {
5.439 +      typedef typename Get<_index - 1, typename _List::Next>::Type Type;
5.440 +    };
5.441 +
5.442 +    template <typename _List>
5.443 +    struct Get<0, _List> {
5.444 +      typedef typename _List::Type Type;
5.445 +    };
5.446 +
5.447 +    struct List {};
5.448 +
5.449 +    template <typename _Type, typename _List>
5.450 +    struct Insert {
5.451 +      typedef _List Next;
5.452 +      typedef _Type Type;
5.453 +    };
5.454 +
5.455 +    template <int _idx, typename _T0, typename _T1, typename _T2,
5.456 +              typename _T3, typename _T5, typename _T4, typename _T6,
5.457 +              typename _T7, typename _T8, typename _T9>
5.458 +    struct Mapper {
5.459 +      typedef List L10;
5.460 +      typedef Insert<_T9, L10> L9;
5.461 +      typedef Insert<_T8, L9> L8;
5.462 +      typedef Insert<_T7, L8> L7;
5.463 +      typedef Insert<_T6, L7> L6;
5.464 +      typedef Insert<_T5, L6> L5;
5.465 +      typedef Insert<_T4, L5> L4;
5.466 +      typedef Insert<_T3, L4> L3;
5.467 +      typedef Insert<_T2, L3> L2;
5.468 +      typedef Insert<_T1, L2> L1;
5.469 +      typedef Insert<_T0, L1> L0;
5.470 +      typedef typename Get<_idx, L0>::Type Type;
5.471 +    };
5.472 +
5.473 +  }
5.474 +
5.475 +  /// \brief Helper class for Variant
5.476 +  ///
5.477 +  /// Helper class to define type mappings for Variant. This class
5.478 +  /// converts the template parameters to be mappable by integer.
5.479 +  /// \see Variant
5.480 +  template <
5.481 +    typename _T0,
5.482 +    typename _T1 = void, typename _T2 = void, typename _T3 = void,
5.483 +    typename _T5 = void, typename _T4 = void, typename _T6 = void,
5.484 +    typename _T7 = void, typename _T8 = void, typename _T9 = void>
5.485 +  struct VariantTypeMap {
5.486 +    template <int _idx>
5.487 +    struct Map {
5.488 +      typedef typename _variant_bits::
5.489 +      Mapper<_idx, _T0, _T1, _T2, _T3, _T4, _T5, _T6, _T7, _T8, _T9>::Type
5.490 +      Type;
5.491 +    };
5.492 +  };
5.493 +
5.494 +}
5.495 +
5.496 +
5.497 +#endif

     6.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/lemon/connectivity.h	Tue Dec 02 15:33:22 2008 +0000
6.3 @@ -0,0 +1,1572 @@
6.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
6.5 + *
6.6 + * This file is a part of LEMON, a generic C++ optimization library.
6.7 + *
6.8 + * Copyright (C) 2003-2008
6.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
6.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
6.11 + *
6.12 + * Permission to use, modify and distribute this software is granted
6.13 + * provided that this copyright notice appears in all copies. For
6.14 + * precise terms see the accompanying LICENSE file.
6.15 + *
6.16 + * This software is provided "AS IS" with no warranty of any kind,
6.17 + * express or implied, and with no claim as to its suitability for any
6.18 + * purpose.
6.19 + *
6.20 + */
6.21 +
6.22 +#ifndef LEMON_TOPOLOGY_H
6.23 +#define LEMON_TOPOLOGY_H
6.24 +
6.25 +#include <lemon/dfs.h>
6.26 +#include <lemon/bfs.h>
6.27 +#include <lemon/core.h>
6.28 +#include <lemon/maps.h>
6.30 +
6.31 +#include <lemon/concepts/digraph.h>
6.32 +#include <lemon/concepts/graph.h>
6.33 +#include <lemon/concept_check.h>
6.34 +
6.35 +#include <stack>
6.36 +#include <functional>
6.37 +
6.38 +/// \ingroup connectivity
6.39 +/// \file
6.40 +/// \brief Connectivity algorithms
6.41 +///
6.42 +/// Connectivity algorithms
6.43 +
6.44 +namespace lemon {
6.45 +
6.46 +  /// \ingroup connectivity
6.47 +  ///
6.48 +  /// \brief Check whether the given undirected graph is connected.
6.49 +  ///
6.50 +  /// Check whether the given undirected graph is connected.
6.51 +  /// \param graph The undirected graph.
6.52 +  /// \return %True when there is path between any two nodes in the graph.
6.53 +  /// \note By definition, the empty graph is connected.
6.54 +  template <typename Graph>
6.55 +  bool connected(const Graph& graph) {
6.56 +    checkConcept<concepts::Graph, Graph>();
6.57 +    typedef typename Graph::NodeIt NodeIt;
6.58 +    if (NodeIt(graph) == INVALID) return true;
6.59 +    Dfs<Graph> dfs(graph);
6.60 +    dfs.run(NodeIt(graph));
6.61 +    for (NodeIt it(graph); it != INVALID; ++it) {
6.62 +      if (!dfs.reached(it)) {
6.63 +        return false;
6.64 +      }
6.65 +    }
6.66 +    return true;
6.67 +  }
6.68 +
6.69 +  /// \ingroup connectivity
6.70 +  ///
6.71 +  /// \brief Count the number of connected components of an undirected graph
6.72 +  ///
6.73 +  /// Count the number of connected components of an undirected graph
6.74 +  ///
6.75 +  /// \param graph The graph. It must be undirected.
6.76 +  /// \return The number of components
6.77 +  /// \note By definition, the empty graph consists
6.78 +  /// of zero connected components.
6.79 +  template <typename Graph>
6.80 +  int countConnectedComponents(const Graph &graph) {
6.81 +    checkConcept<concepts::Graph, Graph>();
6.82 +    typedef typename Graph::Node Node;
6.83 +    typedef typename Graph::Arc Arc;
6.84 +
6.85 +    typedef NullMap<Node, Arc> PredMap;
6.86 +    typedef NullMap<Node, int> DistMap;
6.87 +
6.88 +    int compNum = 0;
6.89 +    typename Bfs<Graph>::
6.90 +      template SetPredMap<PredMap>::
6.91 +      template SetDistMap<DistMap>::
6.92 +      Create bfs(graph);
6.93 +
6.94 +    PredMap predMap;
6.95 +    bfs.predMap(predMap);
6.96 +
6.97 +    DistMap distMap;
6.98 +    bfs.distMap(distMap);
6.99 +
6.100 +    bfs.init();
6.101 +    for(typename Graph::NodeIt n(graph); n != INVALID; ++n) {
6.102 +      if (!bfs.reached(n)) {
6.104 +        bfs.start();
6.105 +        ++compNum;
6.106 +      }
6.107 +    }
6.108 +    return compNum;
6.109 +  }
6.110 +
6.111 +  /// \ingroup connectivity
6.112 +  ///
6.113 +  /// \brief Find the connected components of an undirected graph
6.114 +  ///
6.115 +  /// Find the connected components of an undirected graph.
6.116 +  ///
6.117 +  /// \param graph The graph. It must be undirected.
6.118 +  /// \retval compMap A writable node map. The values will be set from 0 to
6.119 +  /// the number of the connected components minus one. Each values of the map
6.120 +  /// will be set exactly once, the values of a certain component will be
6.121 +  /// set continuously.
6.122 +  /// \return The number of components
6.123 +  ///
6.124 +  template <class Graph, class NodeMap>
6.125 +  int connectedComponents(const Graph &graph, NodeMap &compMap) {
6.126 +    checkConcept<concepts::Graph, Graph>();
6.127 +    typedef typename Graph::Node Node;
6.128 +    typedef typename Graph::Arc Arc;
6.129 +    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
6.130 +
6.131 +    typedef NullMap<Node, Arc> PredMap;
6.132 +    typedef NullMap<Node, int> DistMap;
6.133 +
6.134 +    int compNum = 0;
6.135 +    typename Bfs<Graph>::
6.136 +      template SetPredMap<PredMap>::
6.137 +      template SetDistMap<DistMap>::
6.138 +      Create bfs(graph);
6.139 +
6.140 +    PredMap predMap;
6.141 +    bfs.predMap(predMap);
6.142 +
6.143 +    DistMap distMap;
6.144 +    bfs.distMap(distMap);
6.145 +
6.146 +    bfs.init();
6.147 +    for(typename Graph::NodeIt n(graph); n != INVALID; ++n) {
6.148 +      if(!bfs.reached(n)) {
6.150 +        while (!bfs.emptyQueue()) {
6.151 +          compMap.set(bfs.nextNode(), compNum);
6.152 +          bfs.processNextNode();
6.153 +        }
6.154 +        ++compNum;
6.155 +      }
6.156 +    }
6.157 +    return compNum;
6.158 +  }
6.159 +
6.160 +  namespace _topology_bits {
6.161 +
6.162 +    template <typename Digraph, typename Iterator >
6.163 +    struct LeaveOrderVisitor : public DfsVisitor<Digraph> {
6.164 +    public:
6.165 +      typedef typename Digraph::Node Node;
6.166 +      LeaveOrderVisitor(Iterator it) : _it(it) {}
6.167 +
6.168 +      void leave(const Node& node) {
6.169 +        *(_it++) = node;
6.170 +      }
6.171 +
6.172 +    private:
6.173 +      Iterator _it;
6.174 +    };
6.175 +
6.176 +    template <typename Digraph, typename Map>
6.177 +    struct FillMapVisitor : public DfsVisitor<Digraph> {
6.178 +    public:
6.179 +      typedef typename Digraph::Node Node;
6.180 +      typedef typename Map::Value Value;
6.181 +
6.182 +      FillMapVisitor(Map& map, Value& value)
6.183 +        : _map(map), _value(value) {}
6.184 +
6.185 +      void reach(const Node& node) {
6.186 +        _map.set(node, _value);
6.187 +      }
6.188 +    private:
6.189 +      Map& _map;
6.190 +      Value& _value;
6.191 +    };
6.192 +
6.193 +    template <typename Digraph, typename ArcMap>
6.194 +    struct StronglyConnectedCutEdgesVisitor : public DfsVisitor<Digraph> {
6.195 +    public:
6.196 +      typedef typename Digraph::Node Node;
6.197 +      typedef typename Digraph::Arc Arc;
6.198 +
6.199 +      StronglyConnectedCutEdgesVisitor(const Digraph& digraph,
6.200 +                                       ArcMap& cutMap,
6.201 +                                       int& cutNum)
6.202 +        : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum),
6.203 +          _compMap(digraph), _num(0) {
6.204 +      }
6.205 +
6.206 +      void stop(const Node&) {
6.207 +        ++_num;
6.208 +      }
6.209 +
6.210 +      void reach(const Node& node) {
6.211 +        _compMap.set(node, _num);
6.212 +      }
6.213 +
6.214 +      void examine(const Arc& arc) {
6.215 +         if (_compMap[_digraph.source(arc)] !=
6.216 +             _compMap[_digraph.target(arc)]) {
6.217 +           _cutMap.set(arc, true);
6.218 +           ++_cutNum;
6.219 +         }
6.220 +      }
6.221 +    private:
6.222 +      const Digraph& _digraph;
6.223 +      ArcMap& _cutMap;
6.224 +      int& _cutNum;
6.225 +
6.226 +      typename Digraph::template NodeMap<int> _compMap;
6.227 +      int _num;
6.228 +    };
6.229 +
6.230 +  }
6.231 +
6.232 +
6.233 +  /// \ingroup connectivity
6.234 +  ///
6.235 +  /// \brief Check whether the given directed graph is strongly connected.
6.236 +  ///
6.237 +  /// Check whether the given directed graph is strongly connected. The
6.238 +  /// graph is strongly connected when any two nodes of the graph are
6.239 +  /// connected with directed paths in both direction.
6.240 +  /// \return %False when the graph is not strongly connected.
6.241 +  /// \see connected
6.242 +  ///
6.243 +  /// \note By definition, the empty graph is strongly connected.
6.244 +  template <typename Digraph>
6.245 +  bool stronglyConnected(const Digraph& digraph) {
6.246 +    checkConcept<concepts::Digraph, Digraph>();
6.247 +
6.248 +    typedef typename Digraph::Node Node;
6.249 +    typedef typename Digraph::NodeIt NodeIt;
6.250 +
6.251 +    typename Digraph::Node source = NodeIt(digraph);
6.252 +    if (source == INVALID) return true;
6.253 +
6.254 +    using namespace _topology_bits;
6.255 +
6.256 +    typedef DfsVisitor<Digraph> Visitor;
6.257 +    Visitor visitor;
6.258 +
6.259 +    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
6.260 +    dfs.init();
6.262 +    dfs.start();
6.263 +
6.264 +    for (NodeIt it(digraph); it != INVALID; ++it) {
6.265 +      if (!dfs.reached(it)) {
6.266 +        return false;
6.267 +      }
6.268 +    }
6.269 +
6.270 +    typedef ReverseDigraph<const Digraph> RDigraph;
6.271 +    RDigraph rdigraph(digraph);
6.272 +
6.273 +    typedef DfsVisitor<Digraph> RVisitor;
6.274 +    RVisitor rvisitor;
6.275 +
6.276 +    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
6.277 +    rdfs.init();
6.279 +    rdfs.start();
6.280 +
6.281 +    for (NodeIt it(rdigraph); it != INVALID; ++it) {
6.282 +      if (!rdfs.reached(it)) {
6.283 +        return false;
6.284 +      }
6.285 +    }
6.286 +
6.287 +    return true;
6.288 +  }
6.289 +
6.290 +  /// \ingroup connectivity
6.291 +  ///
6.292 +  /// \brief Count the strongly connected components of a directed graph
6.293 +  ///
6.294 +  /// Count the strongly connected components of a directed graph.
6.295 +  /// The strongly connected components are the classes of an
6.296 +  /// equivalence relation on the nodes of the graph. Two nodes are in
6.297 +  /// the same class if they are connected with directed paths in both
6.298 +  /// direction.
6.299 +  ///
6.300 +  /// \param graph The graph.
6.301 +  /// \return The number of components
6.302 +  /// \note By definition, the empty graph has zero
6.303 +  /// strongly connected components.
6.304 +  template <typename Digraph>
6.305 +  int countStronglyConnectedComponents(const Digraph& digraph) {
6.306 +    checkConcept<concepts::Digraph, Digraph>();
6.307 +
6.308 +    using namespace _topology_bits;
6.309 +
6.310 +    typedef typename Digraph::Node Node;
6.311 +    typedef typename Digraph::Arc Arc;
6.312 +    typedef typename Digraph::NodeIt NodeIt;
6.313 +    typedef typename Digraph::ArcIt ArcIt;
6.314 +
6.315 +    typedef std::vector<Node> Container;
6.316 +    typedef typename Container::iterator Iterator;
6.317 +
6.318 +    Container nodes(countNodes(digraph));
6.319 +    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
6.320 +    Visitor visitor(nodes.begin());
6.321 +
6.322 +    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
6.323 +    dfs.init();
6.324 +    for (NodeIt it(digraph); it != INVALID; ++it) {
6.325 +      if (!dfs.reached(it)) {
6.327 +        dfs.start();
6.328 +      }
6.329 +    }
6.330 +
6.331 +    typedef typename Container::reverse_iterator RIterator;
6.332 +    typedef ReverseDigraph<const Digraph> RDigraph;
6.333 +
6.334 +    RDigraph rdigraph(digraph);
6.335 +
6.336 +    typedef DfsVisitor<Digraph> RVisitor;
6.337 +    RVisitor rvisitor;
6.338 +
6.339 +    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
6.340 +
6.341 +    int compNum = 0;
6.342 +
6.343 +    rdfs.init();
6.344 +    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
6.345 +      if (!rdfs.reached(*it)) {
6.347 +        rdfs.start();
6.348 +        ++compNum;
6.349 +      }
6.350 +    }
6.351 +    return compNum;
6.352 +  }
6.353 +
6.354 +  /// \ingroup connectivity
6.355 +  ///
6.356 +  /// \brief Find the strongly connected components of a directed graph
6.357 +  ///
6.358 +  /// Find the strongly connected components of a directed graph.  The
6.359 +  /// strongly connected components are the classes of an equivalence
6.360 +  /// relation on the nodes of the graph. Two nodes are in
6.361 +  /// relationship when there are directed paths between them in both
6.362 +  /// direction. In addition, the numbering of components will satisfy
6.363 +  /// that there is no arc going from a higher numbered component to
6.364 +  /// a lower.
6.365 +  ///
6.366 +  /// \param digraph The digraph.
6.367 +  /// \retval compMap A writable node map. The values will be set from 0 to
6.368 +  /// the number of the strongly connected components minus one. Each value
6.369 +  /// of the map will be set exactly once, the values of a certain component
6.370 +  /// will be set continuously.
6.371 +  /// \return The number of components
6.372 +  ///
6.373 +  template <typename Digraph, typename NodeMap>
6.374 +  int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
6.375 +    checkConcept<concepts::Digraph, Digraph>();
6.376 +    typedef typename Digraph::Node Node;
6.377 +    typedef typename Digraph::NodeIt NodeIt;
6.378 +    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
6.379 +
6.380 +    using namespace _topology_bits;
6.381 +
6.382 +    typedef std::vector<Node> Container;
6.383 +    typedef typename Container::iterator Iterator;
6.384 +
6.385 +    Container nodes(countNodes(digraph));
6.386 +    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
6.387 +    Visitor visitor(nodes.begin());
6.388 +
6.389 +    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
6.390 +    dfs.init();
6.391 +    for (NodeIt it(digraph); it != INVALID; ++it) {
6.392 +      if (!dfs.reached(it)) {
6.394 +        dfs.start();
6.395 +      }
6.396 +    }
6.397 +
6.398 +    typedef typename Container::reverse_iterator RIterator;
6.399 +    typedef ReverseDigraph<const Digraph> RDigraph;
6.400 +
6.401 +    RDigraph rdigraph(digraph);
6.402 +
6.403 +    int compNum = 0;
6.404 +
6.405 +    typedef FillMapVisitor<RDigraph, NodeMap> RVisitor;
6.406 +    RVisitor rvisitor(compMap, compNum);
6.407 +
6.408 +    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
6.409 +
6.410 +    rdfs.init();
6.411 +    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
6.412 +      if (!rdfs.reached(*it)) {
6.414 +        rdfs.start();
6.415 +        ++compNum;
6.416 +      }
6.417 +    }
6.418 +    return compNum;
6.419 +  }
6.420 +
6.421 +  /// \ingroup connectivity
6.422 +  ///
6.423 +  /// \brief Find the cut arcs of the strongly connected components.
6.424 +  ///
6.425 +  /// Find the cut arcs of the strongly connected components.
6.426 +  /// The strongly connected components are the classes of an equivalence
6.427 +  /// relation on the nodes of the graph. Two nodes are in relationship
6.428 +  /// when there are directed paths between them in both direction.
6.429 +  /// The strongly connected components are separated by the cut arcs.
6.430 +  ///
6.431 +  /// \param graph The graph.
6.432 +  /// \retval cutMap A writable node map. The values will be set true when the
6.433 +  /// arc is a cut arc.
6.434 +  ///
6.435 +  /// \return The number of cut arcs
6.436 +  template <typename Digraph, typename ArcMap>
6.437 +  int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) {
6.438 +    checkConcept<concepts::Digraph, Digraph>();
6.439 +    typedef typename Digraph::Node Node;
6.440 +    typedef typename Digraph::Arc Arc;
6.441 +    typedef typename Digraph::NodeIt NodeIt;
6.442 +    checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>();
6.443 +
6.444 +    using namespace _topology_bits;
6.445 +
6.446 +    typedef std::vector<Node> Container;
6.447 +    typedef typename Container::iterator Iterator;
6.448 +
6.449 +    Container nodes(countNodes(graph));
6.450 +    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
6.451 +    Visitor visitor(nodes.begin());
6.452 +
6.453 +    DfsVisit<Digraph, Visitor> dfs(graph, visitor);
6.454 +    dfs.init();
6.455 +    for (NodeIt it(graph); it != INVALID; ++it) {
6.456 +      if (!dfs.reached(it)) {
6.458 +        dfs.start();
6.459 +      }
6.460 +    }
6.461 +
6.462 +    typedef typename Container::reverse_iterator RIterator;
6.463 +    typedef ReverseDigraph<const Digraph> RDigraph;
6.464 +
6.465 +    RDigraph rgraph(graph);
6.466 +
6.467 +    int cutNum = 0;
6.468 +
6.469 +    typedef StronglyConnectedCutEdgesVisitor<RDigraph, ArcMap> RVisitor;
6.470 +    RVisitor rvisitor(rgraph, cutMap, cutNum);
6.471 +
6.472 +    DfsVisit<RDigraph, RVisitor> rdfs(rgraph, rvisitor);
6.473 +
6.474 +    rdfs.init();
6.475 +    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
6.476 +      if (!rdfs.reached(*it)) {
6.478 +        rdfs.start();
6.479 +      }
6.480 +    }
6.481 +    return cutNum;
6.482 +  }
6.483 +
6.484 +  namespace _topology_bits {
6.485 +
6.486 +    template <typename Digraph>
6.487 +    class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
6.488 +    public:
6.489 +      typedef typename Digraph::Node Node;
6.490 +      typedef typename Digraph::Arc Arc;
6.491 +      typedef typename Digraph::Edge Edge;
6.492 +
6.493 +      CountBiNodeConnectedComponentsVisitor(const Digraph& graph, int &compNum)
6.494 +        : _graph(graph), _compNum(compNum),
6.495 +          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
6.496 +
6.497 +      void start(const Node& node) {
6.498 +        _predMap.set(node, INVALID);
6.499 +      }
6.500 +
6.501 +      void reach(const Node& node) {
6.502 +        _numMap.set(node, _num);
6.503 +        _retMap.set(node, _num);
6.504 +        ++_num;
6.505 +      }
6.506 +
6.507 +      void discover(const Arc& edge) {
6.508 +        _predMap.set(_graph.target(edge), _graph.source(edge));
6.509 +      }
6.510 +
6.511 +      void examine(const Arc& edge) {
6.512 +        if (_graph.source(edge) == _graph.target(edge) &&
6.513 +            _graph.direction(edge)) {
6.514 +          ++_compNum;
6.515 +          return;
6.516 +        }
6.517 +        if (_predMap[_graph.source(edge)] == _graph.target(edge)) {
6.518 +          return;
6.519 +        }
6.520 +        if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
6.521 +          _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
6.522 +        }
6.523 +      }
6.524 +
6.525 +      void backtrack(const Arc& edge) {
6.526 +        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
6.527 +          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
6.528 +        }
6.529 +        if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
6.530 +          ++_compNum;
6.531 +        }
6.532 +      }
6.533 +
6.534 +    private:
6.535 +      const Digraph& _graph;
6.536 +      int& _compNum;
6.537 +
6.538 +      typename Digraph::template NodeMap<int> _numMap;
6.539 +      typename Digraph::template NodeMap<int> _retMap;
6.540 +      typename Digraph::template NodeMap<Node> _predMap;
6.541 +      int _num;
6.542 +    };
6.543 +
6.544 +    template <typename Digraph, typename ArcMap>
6.545 +    class BiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
6.546 +    public:
6.547 +      typedef typename Digraph::Node Node;
6.548 +      typedef typename Digraph::Arc Arc;
6.549 +      typedef typename Digraph::Edge Edge;
6.550 +
6.551 +      BiNodeConnectedComponentsVisitor(const Digraph& graph,
6.552 +                                       ArcMap& compMap, int &compNum)
6.553 +        : _graph(graph), _compMap(compMap), _compNum(compNum),
6.554 +          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
6.555 +
6.556 +      void start(const Node& node) {
6.557 +        _predMap.set(node, INVALID);
6.558 +      }
6.559 +
6.560 +      void reach(const Node& node) {
6.561 +        _numMap.set(node, _num);
6.562 +        _retMap.set(node, _num);
6.563 +        ++_num;
6.564 +      }
6.565 +
6.566 +      void discover(const Arc& edge) {
6.567 +        Node target = _graph.target(edge);
6.568 +        _predMap.set(target, edge);
6.569 +        _edgeStack.push(edge);
6.570 +      }
6.571 +
6.572 +      void examine(const Arc& edge) {
6.573 +        Node source = _graph.source(edge);
6.574 +        Node target = _graph.target(edge);
6.575 +        if (source == target && _graph.direction(edge)) {
6.576 +          _compMap.set(edge, _compNum);
6.577 +          ++_compNum;
6.578 +          return;
6.579 +        }
6.580 +        if (_numMap[target] < _numMap[source]) {
6.581 +          if (_predMap[source] != _graph.oppositeArc(edge)) {
6.582 +            _edgeStack.push(edge);
6.583 +          }
6.584 +        }
6.585 +        if (_predMap[source] != INVALID &&
6.586 +            target == _graph.source(_predMap[source])) {
6.587 +          return;
6.588 +        }
6.589 +        if (_retMap[source] > _numMap[target]) {
6.590 +          _retMap.set(source, _numMap[target]);
6.591 +        }
6.592 +      }
6.593 +
6.594 +      void backtrack(const Arc& edge) {
6.595 +        Node source = _graph.source(edge);
6.596 +        Node target = _graph.target(edge);
6.597 +        if (_retMap[source] > _retMap[target]) {
6.598 +          _retMap.set(source, _retMap[target]);
6.599 +        }
6.600 +        if (_numMap[source] <= _retMap[target]) {
6.601 +          while (_edgeStack.top() != edge) {
6.602 +            _compMap.set(_edgeStack.top(), _compNum);
6.603 +            _edgeStack.pop();
6.604 +          }
6.605 +          _compMap.set(edge, _compNum);
6.606 +          _edgeStack.pop();
6.607 +          ++_compNum;
6.608 +        }
6.609 +      }
6.610 +
6.611 +    private:
6.612 +      const Digraph& _graph;
6.613 +      ArcMap& _compMap;
6.614 +      int& _compNum;
6.615 +
6.616 +      typename Digraph::template NodeMap<int> _numMap;
6.617 +      typename Digraph::template NodeMap<int> _retMap;
6.618 +      typename Digraph::template NodeMap<Arc> _predMap;
6.619 +      std::stack<Edge> _edgeStack;
6.620 +      int _num;
6.621 +    };
6.622 +
6.623 +
6.624 +    template <typename Digraph, typename NodeMap>
6.625 +    class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Digraph> {
6.626 +    public:
6.627 +      typedef typename Digraph::Node Node;
6.628 +      typedef typename Digraph::Arc Arc;
6.629 +      typedef typename Digraph::Edge Edge;
6.630 +
6.631 +      BiNodeConnectedCutNodesVisitor(const Digraph& graph, NodeMap& cutMap,
6.632 +                                     int& cutNum)
6.633 +        : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
6.634 +          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
6.635 +
6.636 +      void start(const Node& node) {
6.637 +        _predMap.set(node, INVALID);
6.638 +        rootCut = false;
6.639 +      }
6.640 +
6.641 +      void reach(const Node& node) {
6.642 +        _numMap.set(node, _num);
6.643 +        _retMap.set(node, _num);
6.644 +        ++_num;
6.645 +      }
6.646 +
6.647 +      void discover(const Arc& edge) {
6.648 +        _predMap.set(_graph.target(edge), _graph.source(edge));
6.649 +      }
6.650 +
6.651 +      void examine(const Arc& edge) {
6.652 +        if (_graph.source(edge) == _graph.target(edge) &&
6.653 +            _graph.direction(edge)) {
6.654 +          if (!_cutMap[_graph.source(edge)]) {
6.655 +            _cutMap.set(_graph.source(edge), true);
6.656 +            ++_cutNum;
6.657 +          }
6.658 +          return;
6.659 +        }
6.660 +        if (_predMap[_graph.source(edge)] == _graph.target(edge)) return;
6.661 +        if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
6.662 +          _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
6.663 +        }
6.664 +      }
6.665 +
6.666 +      void backtrack(const Arc& edge) {
6.667 +        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
6.668 +          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
6.669 +        }
6.670 +        if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
6.671 +          if (_predMap[_graph.source(edge)] != INVALID) {
6.672 +            if (!_cutMap[_graph.source(edge)]) {
6.673 +              _cutMap.set(_graph.source(edge), true);
6.674 +              ++_cutNum;
6.675 +            }
6.676 +          } else if (rootCut) {
6.677 +            if (!_cutMap[_graph.source(edge)]) {
6.678 +              _cutMap.set(_graph.source(edge), true);
6.679 +              ++_cutNum;
6.680 +            }
6.681 +          } else {
6.682 +            rootCut = true;
6.683 +          }
6.684 +        }
6.685 +      }
6.686 +
6.687 +    private:
6.688 +      const Digraph& _graph;
6.689 +      NodeMap& _cutMap;
6.690 +      int& _cutNum;
6.691 +
6.692 +      typename Digraph::template NodeMap<int> _numMap;
6.693 +      typename Digraph::template NodeMap<int> _retMap;
6.694 +      typename Digraph::template NodeMap<Node> _predMap;
6.695 +      std::stack<Edge> _edgeStack;
6.696 +      int _num;
6.697 +      bool rootCut;
6.698 +    };
6.699 +
6.700 +  }
6.701 +
6.702 +  template <typename Graph>
6.703 +  int countBiNodeConnectedComponents(const Graph& graph);
6.704 +
6.705 +  /// \ingroup connectivity
6.706 +  ///
6.707 +  /// \brief Checks the graph is bi-node-connected.
6.708 +  ///
6.709 +  /// This function checks that the undirected graph is bi-node-connected
6.710 +  /// graph. The graph is bi-node-connected if any two undirected edge is
6.711 +  /// on same circle.
6.712 +  ///
6.713 +  /// \param graph The graph.
6.714 +  /// \return %True when the graph bi-node-connected.
6.715 +  template <typename Graph>
6.716 +  bool biNodeConnected(const Graph& graph) {
6.717 +    return countBiNodeConnectedComponents(graph) <= 1;
6.718 +  }
6.719 +
6.720 +  /// \ingroup connectivity
6.721 +  ///
6.722 +  /// \brief Count the biconnected components.
6.723 +  ///
6.724 +  /// This function finds the bi-node-connected components in an undirected
6.725 +  /// graph. The biconnected components are the classes of an equivalence
6.726 +  /// relation on the undirected edges. Two undirected edge is in relationship
6.727 +  /// when they are on same circle.
6.728 +  ///
6.729 +  /// \param graph The graph.
6.730 +  /// \return The number of components.
6.731 +  template <typename Graph>
6.732 +  int countBiNodeConnectedComponents(const Graph& graph) {
6.733 +    checkConcept<concepts::Graph, Graph>();
6.734 +    typedef typename Graph::NodeIt NodeIt;
6.735 +
6.736 +    using namespace _topology_bits;
6.737 +
6.738 +    typedef CountBiNodeConnectedComponentsVisitor<Graph> Visitor;
6.739 +
6.740 +    int compNum = 0;
6.741 +    Visitor visitor(graph, compNum);
6.742 +
6.743 +    DfsVisit<Graph, Visitor> dfs(graph, visitor);
6.744 +    dfs.init();
6.745 +
6.746 +    for (NodeIt it(graph); it != INVALID; ++it) {
6.747 +      if (!dfs.reached(it)) {
6.749 +        dfs.start();
6.750 +      }
6.751 +    }
6.752 +    return compNum;
6.753 +  }
6.754 +
6.755 +  /// \ingroup connectivity
6.756 +  ///
6.757 +  /// \brief Find the bi-node-connected components.
6.758 +  ///
6.759 +  /// This function finds the bi-node-connected components in an undirected
6.760 +  /// graph. The bi-node-connected components are the classes of an equivalence
6.761 +  /// relation on the undirected edges. Two undirected edge are in relationship
6.762 +  /// when they are on same circle.
6.763 +  ///
6.764 +  /// \param graph The graph.
6.765 +  /// \retval compMap A writable uedge map. The values will be set from 0
6.766 +  /// to the number of the biconnected components minus one. Each values
6.767 +  /// of the map will be set exactly once, the values of a certain component
6.768 +  /// will be set continuously.
6.769 +  /// \return The number of components.
6.770 +  ///
6.771 +  template <typename Graph, typename EdgeMap>
6.772 +  int biNodeConnectedComponents(const Graph& graph,
6.773 +                                EdgeMap& compMap) {
6.774 +    checkConcept<concepts::Graph, Graph>();
6.775 +    typedef typename Graph::NodeIt NodeIt;
6.776 +    typedef typename Graph::Edge Edge;
6.777 +    checkConcept<concepts::WriteMap<Edge, int>, EdgeMap>();
6.778 +
6.779 +    using namespace _topology_bits;
6.780 +
6.781 +    typedef BiNodeConnectedComponentsVisitor<Graph, EdgeMap> Visitor;
6.782 +
6.783 +    int compNum = 0;
6.784 +    Visitor visitor(graph, compMap, compNum);
6.785 +
6.786 +    DfsVisit<Graph, Visitor> dfs(graph, visitor);
6.787 +    dfs.init();
6.788 +
6.789 +    for (NodeIt it(graph); it != INVALID; ++it) {
6.790 +      if (!dfs.reached(it)) {
6.792 +        dfs.start();
6.793 +      }
6.794 +    }
6.795 +    return compNum;
6.796 +  }
6.797 +
6.798 +  /// \ingroup connectivity
6.799 +  ///
6.800 +  /// \brief Find the bi-node-connected cut nodes.
6.801 +  ///
6.802 +  /// This function finds the bi-node-connected cut nodes in an undirected
6.803 +  /// graph. The bi-node-connected components are the classes of an equivalence
6.804 +  /// relation on the undirected edges. Two undirected edges are in
6.805 +  /// relationship when they are on same circle. The biconnected components
6.806 +  /// are separted by nodes which are the cut nodes of the components.
6.807 +  ///
6.808 +  /// \param graph The graph.
6.809 +  /// \retval cutMap A writable edge map. The values will be set true when
6.810 +  /// the node separate two or more components.
6.811 +  /// \return The number of the cut nodes.
6.812 +  template <typename Graph, typename NodeMap>
6.813 +  int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {
6.814 +    checkConcept<concepts::Graph, Graph>();
6.815 +    typedef typename Graph::Node Node;
6.816 +    typedef typename Graph::NodeIt NodeIt;
6.817 +    checkConcept<concepts::WriteMap<Node, bool>, NodeMap>();
6.818 +
6.819 +    using namespace _topology_bits;
6.820 +
6.821 +    typedef BiNodeConnectedCutNodesVisitor<Graph, NodeMap> Visitor;
6.822 +
6.823 +    int cutNum = 0;
6.824 +    Visitor visitor(graph, cutMap, cutNum);
6.825 +
6.826 +    DfsVisit<Graph, Visitor> dfs(graph, visitor);
6.827 +    dfs.init();
6.828 +
6.829 +    for (NodeIt it(graph); it != INVALID; ++it) {
6.830 +      if (!dfs.reached(it)) {
6.832 +        dfs.start();
6.833 +      }
6.834 +    }
6.835 +    return cutNum;
6.836 +  }
6.837 +
6.838 +  namespace _topology_bits {
6.839 +
6.840 +    template <typename Digraph>
6.841 +    class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
6.842 +    public:
6.843 +      typedef typename Digraph::Node Node;
6.844 +      typedef typename Digraph::Arc Arc;
6.845 +      typedef typename Digraph::Edge Edge;
6.846 +
6.847 +      CountBiEdgeConnectedComponentsVisitor(const Digraph& graph, int &compNum)
6.848 +        : _graph(graph), _compNum(compNum),
6.849 +          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
6.850 +
6.851 +      void start(const Node& node) {
6.852 +        _predMap.set(node, INVALID);
6.853 +      }
6.854 +
6.855 +      void reach(const Node& node) {
6.856 +        _numMap.set(node, _num);
6.857 +        _retMap.set(node, _num);
6.858 +        ++_num;
6.859 +      }
6.860 +
6.861 +      void leave(const Node& node) {
6.862 +        if (_numMap[node] <= _retMap[node]) {
6.863 +          ++_compNum;
6.864 +        }
6.865 +      }
6.866 +
6.867 +      void discover(const Arc& edge) {
6.868 +        _predMap.set(_graph.target(edge), edge);
6.869 +      }
6.870 +
6.871 +      void examine(const Arc& edge) {
6.872 +        if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
6.873 +          return;
6.874 +        }
6.875 +        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
6.876 +          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
6.877 +        }
6.878 +      }
6.879 +
6.880 +      void backtrack(const Arc& edge) {
6.881 +        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
6.882 +          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
6.883 +        }
6.884 +      }
6.885 +
6.886 +    private:
6.887 +      const Digraph& _graph;
6.888 +      int& _compNum;
6.889 +
6.890 +      typename Digraph::template NodeMap<int> _numMap;
6.891 +      typename Digraph::template NodeMap<int> _retMap;
6.892 +      typename Digraph::template NodeMap<Arc> _predMap;
6.893 +      int _num;
6.894 +    };
6.895 +
6.896 +    template <typename Digraph, typename NodeMap>
6.897 +    class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
6.898 +    public:
6.899 +      typedef typename Digraph::Node Node;
6.900 +      typedef typename Digraph::Arc Arc;
6.901 +      typedef typename Digraph::Edge Edge;
6.902 +
6.903 +      BiEdgeConnectedComponentsVisitor(const Digraph& graph,
6.904 +                                       NodeMap& compMap, int &compNum)
6.905 +        : _graph(graph), _compMap(compMap), _compNum(compNum),
6.906 +          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
6.907 +
6.908 +      void start(const Node& node) {
6.909 +        _predMap.set(node, INVALID);
6.910 +      }
6.911 +
6.912 +      void reach(const Node& node) {
6.913 +        _numMap.set(node, _num);
6.914 +        _retMap.set(node, _num);
6.915 +        _nodeStack.push(node);
6.916 +        ++_num;
6.917 +      }
6.918 +
6.919 +      void leave(const Node& node) {
6.920 +        if (_numMap[node] <= _retMap[node]) {
6.921 +          while (_nodeStack.top() != node) {
6.922 +            _compMap.set(_nodeStack.top(), _compNum);
6.923 +            _nodeStack.pop();
6.924 +          }
6.925 +          _compMap.set(node, _compNum);
6.926 +          _nodeStack.pop();
6.927 +          ++_compNum;
6.928 +        }
6.929 +      }
6.930 +
6.931 +      void discover(const Arc& edge) {
6.932 +        _predMap.set(_graph.target(edge), edge);
6.933 +      }
6.934 +
6.935 +      void examine(const Arc& edge) {
6.936 +        if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
6.937 +          return;
6.938 +        }
6.939 +        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
6.940 +          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
6.941 +        }
6.942 +      }
6.943 +
6.944 +      void backtrack(const Arc& edge) {
6.945 +        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
6.946 +          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
6.947 +        }
6.948 +      }
6.949 +
6.950 +    private:
6.951 +      const Digraph& _graph;
6.952 +      NodeMap& _compMap;
6.953 +      int& _compNum;
6.954 +
6.955 +      typename Digraph::template NodeMap<int> _numMap;
6.956 +      typename Digraph::template NodeMap<int> _retMap;
6.957 +      typename Digraph::template NodeMap<Arc> _predMap;
6.958 +      std::stack<Node> _nodeStack;
6.959 +      int _num;
6.960 +    };
6.961 +
6.962 +
6.963 +    template <typename Digraph, typename ArcMap>
6.964 +    class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Digraph> {
6.965 +    public:
6.966 +      typedef typename Digraph::Node Node;
6.967 +      typedef typename Digraph::Arc Arc;
6.968 +      typedef typename Digraph::Edge Edge;
6.969 +
6.970 +      BiEdgeConnectedCutEdgesVisitor(const Digraph& graph,
6.971 +                                     ArcMap& cutMap, int &cutNum)
6.972 +        : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
6.973 +          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
6.974 +
6.975 +      void start(const Node& node) {
6.976 +        _predMap[node] = INVALID;
6.977 +      }
6.978 +
6.979 +      void reach(const Node& node) {
6.980 +        _numMap.set(node, _num);
6.981 +        _retMap.set(node, _num);
6.982 +        ++_num;
6.983 +      }
6.984 +
6.985 +      void leave(const Node& node) {
6.986 +        if (_numMap[node] <= _retMap[node]) {
6.987 +          if (_predMap[node] != INVALID) {
6.988 +            _cutMap.set(_predMap[node], true);
6.989 +            ++_cutNum;
6.990 +          }
6.991 +        }
6.992 +      }
6.993 +
6.994 +      void discover(const Arc& edge) {
6.995 +        _predMap.set(_graph.target(edge), edge);
6.996 +      }
6.997 +
6.998 +      void examine(const Arc& edge) {
6.999 +        if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
6.1000 +          return;
6.1001 +        }
6.1002 +        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
6.1003 +          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
6.1004 +        }
6.1005 +      }
6.1006 +
6.1007 +      void backtrack(const Arc& edge) {
6.1008 +        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
6.1009 +          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
6.1010 +        }
6.1011 +      }
6.1012 +
6.1013 +    private:
6.1014 +      const Digraph& _graph;
6.1015 +      ArcMap& _cutMap;
6.1016 +      int& _cutNum;
6.1017 +
6.1018 +      typename Digraph::template NodeMap<int> _numMap;
6.1019 +      typename Digraph::template NodeMap<int> _retMap;
6.1020 +      typename Digraph::template NodeMap<Arc> _predMap;
6.1021 +      int _num;
6.1022 +    };
6.1023 +  }
6.1024 +
6.1025 +  template <typename Graph>
6.1026 +  int countBiEdgeConnectedComponents(const Graph& graph);
6.1027 +
6.1028 +  /// \ingroup connectivity
6.1029 +  ///
6.1030 +  /// \brief Checks that the graph is bi-edge-connected.
6.1031 +  ///
6.1032 +  /// This function checks that the graph is bi-edge-connected. The undirected
6.1033 +  /// graph is bi-edge-connected when any two nodes are connected with two
6.1034 +  /// edge-disjoint paths.
6.1035 +  ///
6.1036 +  /// \param graph The undirected graph.
6.1037 +  /// \return The number of components.
6.1038 +  template <typename Graph>
6.1039 +  bool biEdgeConnected(const Graph& graph) {
6.1040 +    return countBiEdgeConnectedComponents(graph) <= 1;
6.1041 +  }
6.1042 +
6.1043 +  /// \ingroup connectivity
6.1044 +  ///
6.1045 +  /// \brief Count the bi-edge-connected components.
6.1046 +  ///
6.1047 +  /// This function count the bi-edge-connected components in an undirected
6.1048 +  /// graph. The bi-edge-connected components are the classes of an equivalence
6.1049 +  /// relation on the nodes. Two nodes are in relationship when they are
6.1050 +  /// connected with at least two edge-disjoint paths.
6.1051 +  ///
6.1052 +  /// \param graph The undirected graph.
6.1053 +  /// \return The number of components.
6.1054 +  template <typename Graph>
6.1055 +  int countBiEdgeConnectedComponents(const Graph& graph) {
6.1056 +    checkConcept<concepts::Graph, Graph>();
6.1057 +    typedef typename Graph::NodeIt NodeIt;
6.1058 +
6.1059 +    using namespace _topology_bits;
6.1060 +
6.1061 +    typedef CountBiEdgeConnectedComponentsVisitor<Graph> Visitor;
6.1062 +
6.1063 +    int compNum = 0;
6.1064 +    Visitor visitor(graph, compNum);
6.1065 +
6.1066 +    DfsVisit<Graph, Visitor> dfs(graph, visitor);
6.1067 +    dfs.init();
6.1068 +
6.1069 +    for (NodeIt it(graph); it != INVALID; ++it) {
6.1070 +      if (!dfs.reached(it)) {
6.1072 +        dfs.start();
6.1073 +      }
6.1074 +    }
6.1075 +    return compNum;
6.1076 +  }
6.1077 +
6.1078 +  /// \ingroup connectivity
6.1079 +  ///
6.1080 +  /// \brief Find the bi-edge-connected components.
6.1081 +  ///
6.1082 +  /// This function finds the bi-edge-connected components in an undirected
6.1083 +  /// graph. The bi-edge-connected components are the classes of an equivalence
6.1084 +  /// relation on the nodes. Two nodes are in relationship when they are
6.1085 +  /// connected at least two edge-disjoint paths.
6.1086 +  ///
6.1087 +  /// \param graph The graph.
6.1088 +  /// \retval compMap A writable node map. The values will be set from 0 to
6.1089 +  /// the number of the biconnected components minus one. Each values
6.1090 +  /// of the map will be set exactly once, the values of a certain component
6.1091 +  /// will be set continuously.
6.1092 +  /// \return The number of components.
6.1093 +  ///
6.1094 +  template <typename Graph, typename NodeMap>
6.1095 +  int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
6.1096 +    checkConcept<concepts::Graph, Graph>();
6.1097 +    typedef typename Graph::NodeIt NodeIt;
6.1098 +    typedef typename Graph::Node Node;
6.1099 +    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
6.1100 +
6.1101 +    using namespace _topology_bits;
6.1102 +
6.1103 +    typedef BiEdgeConnectedComponentsVisitor<Graph, NodeMap> Visitor;
6.1104 +
6.1105 +    int compNum = 0;
6.1106 +    Visitor visitor(graph, compMap, compNum);
6.1107 +
6.1108 +    DfsVisit<Graph, Visitor> dfs(graph, visitor);
6.1109 +    dfs.init();
6.1110 +
6.1111 +    for (NodeIt it(graph); it != INVALID; ++it) {
6.1112 +      if (!dfs.reached(it)) {
6.1114 +        dfs.start();
6.1115 +      }
6.1116 +    }
6.1117 +    return compNum;
6.1118 +  }
6.1119 +
6.1120 +  /// \ingroup connectivity
6.1121 +  ///
6.1122 +  /// \brief Find the bi-edge-connected cut edges.
6.1123 +  ///
6.1124 +  /// This function finds the bi-edge-connected components in an undirected
6.1125 +  /// graph. The bi-edge-connected components are the classes of an equivalence
6.1126 +  /// relation on the nodes. Two nodes are in relationship when they are
6.1127 +  /// connected with at least two edge-disjoint paths. The bi-edge-connected
6.1128 +  /// components are separted by edges which are the cut edges of the
6.1129 +  /// components.
6.1130 +  ///
6.1131 +  /// \param graph The graph.
6.1132 +  /// \retval cutMap A writable node map. The values will be set true when the
6.1133 +  /// edge is a cut edge.
6.1134 +  /// \return The number of cut edges.
6.1135 +  template <typename Graph, typename EdgeMap>
6.1136 +  int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
6.1137 +    checkConcept<concepts::Graph, Graph>();
6.1138 +    typedef typename Graph::NodeIt NodeIt;
6.1139 +    typedef typename Graph::Edge Edge;
6.1140 +    checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>();
6.1141 +
6.1142 +    using namespace _topology_bits;
6.1143 +
6.1144 +    typedef BiEdgeConnectedCutEdgesVisitor<Graph, EdgeMap> Visitor;
6.1145 +
6.1146 +    int cutNum = 0;
6.1147 +    Visitor visitor(graph, cutMap, cutNum);
6.1148 +
6.1149 +    DfsVisit<Graph, Visitor> dfs(graph, visitor);
6.1150 +    dfs.init();
6.1151 +
6.1152 +    for (NodeIt it(graph); it != INVALID; ++it) {
6.1153 +      if (!dfs.reached(it)) {
6.1155 +        dfs.start();
6.1156 +      }
6.1157 +    }
6.1158 +    return cutNum;
6.1159 +  }
6.1160 +
6.1161 +
6.1162 +  namespace _topology_bits {
6.1163 +
6.1164 +    template <typename Digraph, typename IntNodeMap>
6.1165 +    class TopologicalSortVisitor : public DfsVisitor<Digraph> {
6.1166 +    public:
6.1167 +      typedef typename Digraph::Node Node;
6.1168 +      typedef typename Digraph::Arc edge;
6.1169 +
6.1170 +      TopologicalSortVisitor(IntNodeMap& order, int num)
6.1171 +        : _order(order), _num(num) {}
6.1172 +
6.1173 +      void leave(const Node& node) {
6.1174 +        _order.set(node, --_num);
6.1175 +      }
6.1176 +
6.1177 +    private:
6.1178 +      IntNodeMap& _order;
6.1179 +      int _num;
6.1180 +    };
6.1181 +
6.1182 +  }
6.1183 +
6.1184 +  /// \ingroup connectivity
6.1185 +  ///
6.1186 +  /// \brief Sort the nodes of a DAG into topolgical order.
6.1187 +  ///
6.1188 +  /// Sort the nodes of a DAG into topolgical order.
6.1189 +  ///
6.1190 +  /// \param graph The graph. It must be directed and acyclic.
6.1191 +  /// \retval order A writable node map. The values will be set from 0 to
6.1192 +  /// the number of the nodes in the graph minus one. Each values of the map
6.1193 +  /// will be set exactly once, the values  will be set descending order.
6.1194 +  ///
6.1195 +  /// \see checkedTopologicalSort
6.1196 +  /// \see dag
6.1197 +  template <typename Digraph, typename NodeMap>
6.1198 +  void topologicalSort(const Digraph& graph, NodeMap& order) {
6.1199 +    using namespace _topology_bits;
6.1200 +
6.1201 +    checkConcept<concepts::Digraph, Digraph>();
6.1202 +    checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();
6.1203 +
6.1204 +    typedef typename Digraph::Node Node;
6.1205 +    typedef typename Digraph::NodeIt NodeIt;
6.1206 +    typedef typename Digraph::Arc Arc;
6.1207 +
6.1208 +    TopologicalSortVisitor<Digraph, NodeMap>
6.1209 +      visitor(order, countNodes(graph));
6.1210 +
6.1211 +    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
6.1212 +      dfs(graph, visitor);
6.1213 +
6.1214 +    dfs.init();
6.1215 +    for (NodeIt it(graph); it != INVALID; ++it) {
6.1216 +      if (!dfs.reached(it)) {
6.1218 +        dfs.start();
6.1219 +      }
6.1220 +    }
6.1221 +  }
6.1222 +
6.1223 +  /// \ingroup connectivity
6.1224 +  ///
6.1225 +  /// \brief Sort the nodes of a DAG into topolgical order.
6.1226 +  ///
6.1227 +  /// Sort the nodes of a DAG into topolgical order. It also checks
6.1228 +  /// that the given graph is DAG.
6.1229 +  ///
6.1230 +  /// \param graph The graph. It must be directed and acyclic.
6.1231 +  /// \retval order A readable - writable node map. The values will be set
6.1232 +  /// from 0 to the number of the nodes in the graph minus one. Each values
6.1233 +  /// of the map will be set exactly once, the values will be set descending
6.1234 +  /// order.
6.1235 +  /// \return %False when the graph is not DAG.
6.1236 +  ///
6.1237 +  /// \see topologicalSort
6.1238 +  /// \see dag
6.1239 +  template <typename Digraph, typename NodeMap>
6.1240 +  bool checkedTopologicalSort(const Digraph& graph, NodeMap& order) {
6.1241 +    using namespace _topology_bits;
6.1242 +
6.1243 +    checkConcept<concepts::Digraph, Digraph>();
6.1245 +      NodeMap>();
6.1246 +
6.1247 +    typedef typename Digraph::Node Node;
6.1248 +    typedef typename Digraph::NodeIt NodeIt;
6.1249 +    typedef typename Digraph::Arc Arc;
6.1250 +
6.1251 +    order = constMap<Node, int, -1>();
6.1252 +
6.1253 +    TopologicalSortVisitor<Digraph, NodeMap>
6.1254 +      visitor(order, countNodes(graph));
6.1255 +
6.1256 +    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
6.1257 +      dfs(graph, visitor);
6.1258 +
6.1259 +    dfs.init();
6.1260 +    for (NodeIt it(graph); it != INVALID; ++it) {
6.1261 +      if (!dfs.reached(it)) {
6.1263 +        while (!dfs.emptyQueue()) {
6.1264 +           Arc edge = dfs.nextArc();
6.1265 +           Node target = graph.target(edge);
6.1266 +           if (dfs.reached(target) && order[target] == -1) {
6.1267 +             return false;
6.1268 +           }
6.1269 +           dfs.processNextArc();
6.1270 +         }
6.1271 +      }
6.1272 +    }
6.1273 +    return true;
6.1274 +  }
6.1275 +
6.1276 +  /// \ingroup connectivity
6.1277 +  ///
6.1278 +  /// \brief Check that the given directed graph is a DAG.
6.1279 +  ///
6.1280 +  /// Check that the given directed graph is a DAG. The DAG is
6.1281 +  /// an Directed Acyclic Digraph.
6.1282 +  /// \return %False when the graph is not DAG.
6.1283 +  /// \see acyclic
6.1284 +  template <typename Digraph>
6.1285 +  bool dag(const Digraph& graph) {
6.1286 +
6.1287 +    checkConcept<concepts::Digraph, Digraph>();
6.1288 +
6.1289 +    typedef typename Digraph::Node Node;
6.1290 +    typedef typename Digraph::NodeIt NodeIt;
6.1291 +    typedef typename Digraph::Arc Arc;
6.1292 +
6.1293 +    typedef typename Digraph::template NodeMap<bool> ProcessedMap;
6.1294 +
6.1295 +    typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
6.1296 +      Create dfs(graph);
6.1297 +
6.1298 +    ProcessedMap processed(graph);
6.1299 +    dfs.processedMap(processed);
6.1300 +
6.1301 +    dfs.init();
6.1302 +    for (NodeIt it(graph); it != INVALID; ++it) {
6.1303 +      if (!dfs.reached(it)) {
6.1305 +        while (!dfs.emptyQueue()) {
6.1306 +          Arc edge = dfs.nextArc();
6.1307 +          Node target = graph.target(edge);
6.1308 +          if (dfs.reached(target) && !processed[target]) {
6.1309 +            return false;
6.1310 +          }
6.1311 +          dfs.processNextArc();
6.1312 +        }
6.1313 +      }
6.1314 +    }
6.1315 +    return true;
6.1316 +  }
6.1317 +
6.1318 +  /// \ingroup connectivity
6.1319 +  ///
6.1320 +  /// \brief Check that the given undirected graph is acyclic.
6.1321 +  ///
6.1322 +  /// Check that the given undirected graph acyclic.
6.1323 +  /// \param graph The undirected graph.
6.1324 +  /// \return %True when there is no circle in the graph.
6.1325 +  /// \see dag
6.1326 +  template <typename Graph>
6.1327 +  bool acyclic(const Graph& graph) {
6.1328 +    checkConcept<concepts::Graph, Graph>();
6.1329 +    typedef typename Graph::Node Node;
6.1330 +    typedef typename Graph::NodeIt NodeIt;
6.1331 +    typedef typename Graph::Arc Arc;
6.1332 +    Dfs<Graph> dfs(graph);
6.1333 +    dfs.init();
6.1334 +    for (NodeIt it(graph); it != INVALID; ++it) {
6.1335 +      if (!dfs.reached(it)) {
6.1337 +        while (!dfs.emptyQueue()) {
6.1338 +          Arc edge = dfs.nextArc();
6.1339 +          Node source = graph.source(edge);
6.1340 +          Node target = graph.target(edge);
6.1341 +          if (dfs.reached(target) &&
6.1342 +              dfs.predArc(source) != graph.oppositeArc(edge)) {
6.1343 +            return false;
6.1344 +          }
6.1345 +          dfs.processNextArc();
6.1346 +        }
6.1347 +      }
6.1348 +    }
6.1349 +    return true;
6.1350 +  }
6.1351 +
6.1352 +  /// \ingroup connectivity
6.1353 +  ///
6.1354 +  /// \brief Check that the given undirected graph is tree.
6.1355 +  ///
6.1356 +  /// Check that the given undirected graph is tree.
6.1357 +  /// \param graph The undirected graph.
6.1358 +  /// \return %True when the graph is acyclic and connected.
6.1359 +  template <typename Graph>
6.1360 +  bool tree(const Graph& graph) {
6.1361 +    checkConcept<concepts::Graph, Graph>();
6.1362 +    typedef typename Graph::Node Node;
6.1363 +    typedef typename Graph::NodeIt NodeIt;
6.1364 +    typedef typename Graph::Arc Arc;
6.1365 +    Dfs<Graph> dfs(graph);
6.1366 +    dfs.init();
6.1368 +    while (!dfs.emptyQueue()) {
6.1369 +      Arc edge = dfs.nextArc();
6.1370 +      Node source = graph.source(edge);
6.1371 +      Node target = graph.target(edge);
6.1372 +      if (dfs.reached(target) &&
6.1373 +          dfs.predArc(source) != graph.oppositeArc(edge)) {
6.1374 +        return false;
6.1375 +      }
6.1376 +      dfs.processNextArc();
6.1377 +    }
6.1378 +    for (NodeIt it(graph); it != INVALID; ++it) {
6.1379 +      if (!dfs.reached(it)) {
6.1380 +        return false;
6.1381 +      }
6.1382 +    }
6.1383 +    return true;
6.1384 +  }
6.1385 +
6.1386 +  namespace _topology_bits {
6.1387 +
6.1388 +    template <typename Digraph>
6.1389 +    class BipartiteVisitor : public BfsVisitor<Digraph> {
6.1390 +    public:
6.1391 +      typedef typename Digraph::Arc Arc;
6.1392 +      typedef typename Digraph::Node Node;
6.1393 +
6.1394 +      BipartiteVisitor(const Digraph& graph, bool& bipartite)
6.1395 +        : _graph(graph), _part(graph), _bipartite(bipartite) {}
6.1396 +
6.1397 +      void start(const Node& node) {
6.1398 +        _part[node] = true;
6.1399 +      }
6.1400 +      void discover(const Arc& edge) {
6.1401 +        _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
6.1402 +      }
6.1403 +      void examine(const Arc& edge) {
6.1404 +        _bipartite = _bipartite &&
6.1405 +          _part[_graph.target(edge)] != _part[_graph.source(edge)];
6.1406 +      }
6.1407 +
6.1408 +    private:
6.1409 +
6.1410 +      const Digraph& _graph;
6.1411 +      typename Digraph::template NodeMap<bool> _part;
6.1412 +      bool& _bipartite;
6.1413 +    };
6.1414 +
6.1415 +    template <typename Digraph, typename PartMap>
6.1416 +    class BipartitePartitionsVisitor : public BfsVisitor<Digraph> {
6.1417 +    public:
6.1418 +      typedef typename Digraph::Arc Arc;
6.1419 +      typedef typename Digraph::Node Node;
6.1420 +
6.1421 +      BipartitePartitionsVisitor(const Digraph& graph,
6.1422 +                                 PartMap& part, bool& bipartite)
6.1423 +        : _graph(graph), _part(part), _bipartite(bipartite) {}
6.1424 +
6.1425 +      void start(const Node& node) {
6.1426 +        _part.set(node, true);
6.1427 +      }
6.1428 +      void discover(const Arc& edge) {
6.1429 +        _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
6.1430 +      }
6.1431 +      void examine(const Arc& edge) {
6.1432 +        _bipartite = _bipartite &&
6.1433 +          _part[_graph.target(edge)] != _part[_graph.source(edge)];
6.1434 +      }
6.1435 +
6.1436 +    private:
6.1437 +
6.1438 +      const Digraph& _graph;
6.1439 +      PartMap& _part;
6.1440 +      bool& _bipartite;
6.1441 +    };
6.1442 +  }
6.1443 +
6.1444 +  /// \ingroup connectivity
6.1445 +  ///
6.1446 +  /// \brief Check if the given undirected graph is bipartite or not
6.1447 +  ///
6.1448 +  /// The function checks if the given undirected \c graph graph is bipartite
6.1449 +  /// or not. The \ref Bfs algorithm is used to calculate the result.
6.1450 +  /// \param graph The undirected graph.
6.1451 +  /// \return %True if \c graph is bipartite, %false otherwise.
6.1452 +  /// \sa bipartitePartitions
6.1453 +  template<typename Graph>
6.1454 +  inline bool bipartite(const Graph &graph){
6.1455 +    using namespace _topology_bits;
6.1456 +
6.1457 +    checkConcept<concepts::Graph, Graph>();
6.1458 +
6.1459 +    typedef typename Graph::NodeIt NodeIt;
6.1460 +    typedef typename Graph::ArcIt ArcIt;
6.1461 +
6.1462 +    bool bipartite = true;
6.1463 +
6.1464 +    BipartiteVisitor<Graph>
6.1465 +      visitor(graph, bipartite);
6.1466 +    BfsVisit<Graph, BipartiteVisitor<Graph> >
6.1467 +      bfs(graph, visitor);
6.1468 +    bfs.init();
6.1469 +    for(NodeIt it(graph); it != INVALID; ++it) {
6.1470 +      if(!bfs.reached(it)){
6.1472 +        while (!bfs.emptyQueue()) {
6.1473 +          bfs.processNextNode();
6.1474 +          if (!bipartite) return false;
6.1475 +        }
6.1476 +      }
6.1477 +    }
6.1478 +    return true;
6.1479 +  }
6.1480 +
6.1481 +  /// \ingroup connectivity
6.1482 +  ///
6.1483 +  /// \brief Check if the given undirected graph is bipartite or not
6.1484 +  ///
6.1485 +  /// The function checks if the given undirected graph is bipartite
6.1486 +  /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result.
6.1487 +  /// During the execution, the \c partMap will be set as the two
6.1488 +  /// partitions of the graph.
6.1489 +  /// \param graph The undirected graph.
6.1490 +  /// \retval partMap A writable bool map of nodes. It will be set as the
6.1491 +  /// two partitions of the graph.
6.1492 +  /// \return %True if \c graph is bipartite, %false otherwise.
6.1493 +  template<typename Graph, typename NodeMap>
6.1494 +  inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
6.1495 +    using namespace _topology_bits;
6.1496 +
6.1497 +    checkConcept<concepts::Graph, Graph>();
6.1498 +
6.1499 +    typedef typename Graph::Node Node;
6.1500 +    typedef typename Graph::NodeIt NodeIt;
6.1501 +    typedef typename Graph::ArcIt ArcIt;
6.1502 +
6.1503 +    bool bipartite = true;
6.1504 +
6.1505 +    BipartitePartitionsVisitor<Graph, NodeMap>
6.1506 +      visitor(graph, partMap, bipartite);
6.1507 +    BfsVisit<Graph, BipartitePartitionsVisitor<Graph, NodeMap> >
6.1508 +      bfs(graph, visitor);
6.1509 +    bfs.init();
6.1510 +    for(NodeIt it(graph); it != INVALID; ++it) {
6.1511 +      if(!bfs.reached(it)){
6.1513 +        while (!bfs.emptyQueue()) {
6.1514 +          bfs.processNextNode();
6.1515 +          if (!bipartite) return false;
6.1516 +        }
6.1517 +      }
6.1518 +    }
6.1519 +    return true;
6.1520 +  }
6.1521 +
6.1522 +  /// \brief Returns true when there are not loop edges in the graph.
6.1523 +  ///
6.1524 +  /// Returns true when there are not loop edges in the graph.
6.1525 +  template <typename Digraph>
6.1526 +  bool loopFree(const Digraph& graph) {
6.1527 +    for (typename Digraph::ArcIt it(graph); it != INVALID; ++it) {
6.1528 +      if (graph.source(it) == graph.target(it)) return false;
6.1529 +    }
6.1530 +    return true;
6.1531 +  }
6.1532 +
6.1533 +  /// \brief Returns true when there are not parallel edges in the graph.
6.1534 +  ///
6.1535 +  /// Returns true when there are not parallel edges in the graph.
6.1536 +  template <typename Digraph>
6.1537 +  bool parallelFree(const Digraph& graph) {
6.1538 +    typename Digraph::template NodeMap<bool> reached(graph, false);
6.1539 +    for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) {
6.1540 +      for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
6.1541 +        if (reached[graph.target(e)]) return false;
6.1542 +        reached.set(graph.target(e), true);
6.1543 +      }
6.1544 +      for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
6.1545 +        reached.set(graph.target(e), false);
6.1546 +      }
6.1547 +    }
6.1548 +    return true;
6.1549 +  }
6.1550 +
6.1551 +  /// \brief Returns true when there are not loop edges and parallel
6.1552 +  /// edges in the graph.
6.1553 +  ///
6.1554 +  /// Returns true when there are not loop edges and parallel edges in
6.1555 +  /// the graph.
6.1556 +  template <typename Digraph>
6.1557 +  bool simpleDigraph(const Digraph& graph) {
6.1558 +    typename Digraph::template NodeMap<bool> reached(graph, false);
6.1559 +    for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) {
6.1560 +      reached.set(n, true);
6.1561 +      for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
6.1562 +        if (reached[graph.target(e)]) return false;
6.1563 +        reached.set(graph.target(e), true);
6.1564 +      }
6.1565 +      for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
6.1566 +        reached.set(graph.target(e), false);
6.1567 +      }
6.1568 +      reached.set(n, false);
6.1569 +    }
6.1570 +    return true;
6.1571 +  }
6.1572 +
6.1573 +} //namespace lemon
6.1574 +
6.1575 +#endif //LEMON_TOPOLOGY_H

     7.1 --- a/test/Makefile.am	Tue Dec 02 11:01:48 2008 +0000
7.2 +++ b/test/Makefile.am	Tue Dec 02 15:33:22 2008 +0000
7.3 @@ -16,6 +16,7 @@
7.4  	test/dijkstra_test \
7.5          test/dim_test \
7.6  	test/error_test \
7.8  	test/graph_copy_test \
7.9  	test/graph_test \
7.10  	test/graph_utils_test \
7.11 @@ -44,6 +45,7 @@
7.12  test_dijkstra_test_SOURCES = test/dijkstra_test.cc
7.13  test_dim_test_SOURCES = test/dim_test.cc
7.14  test_error_test_SOURCES = test/error_test.cc
7.16  test_graph_copy_test_SOURCES = test/graph_copy_test.cc
7.17  test_graph_test_SOURCES = test/graph_test.cc
7.18  test_graph_utils_test_SOURCES = test/graph_utils_test.cc

     8.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
8.2 +++ b/test/graph_adaptor_test.cc	Tue Dec 02 15:33:22 2008 +0000
8.3 @@ -0,0 +1,984 @@
8.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
8.5 + *
8.6 + * This file is a part of LEMON, a generic C++ optimization library.
8.7 + *
8.8 + * Copyright (C) 2003-2008
8.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
8.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
8.11 + *
8.12 + * Permission to use, modify and distribute this software is granted
8.13 + * provided that this copyright notice appears in all copies. For
8.14 + * precise terms see the accompanying LICENSE file.
8.15 + *
8.16 + * This software is provided "AS IS" with no warranty of any kind,
8.17 + * express or implied, and with no claim as to its suitability for any
8.18 + * purpose.
8.19 + *
8.20 + */
8.21 +
8.22 +#include<iostream>
8.23 +#include<lemon/concept_check.h>
8.24 +
8.25 +#include<lemon/list_graph.h>
8.26 +#include<lemon/smart_graph.h>
8.27 +
8.28 +#include<lemon/concepts/digraph.h>
8.29 +#include<lemon/concepts/graph.h>
8.30 +
8.32 +
8.33 +#include <limits>
8.34 +#include <lemon/bfs.h>
8.35 +#include <lemon/path.h>
8.36 +
8.37 +#include"test/test_tools.h"
8.38 +#include"test/graph_test.h"
8.39 +
8.40 +using namespace lemon;
8.41 +
8.42 +void checkReverseDigraph() {
8.43 +  checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();
8.44 +
8.45 +  typedef ListDigraph Digraph;
8.47 +
8.48 +  Digraph digraph;
8.50 +
8.51 +  Digraph::Node n1 = digraph.addNode();
8.52 +  Digraph::Node n2 = digraph.addNode();
8.53 +  Digraph::Node n3 = digraph.addNode();
8.54 +
8.55 +  Digraph::Arc a1 = digraph.addArc(n1, n2);
8.56 +  Digraph::Arc a2 = digraph.addArc(n1, n3);
8.57 +  Digraph::Arc a3 = digraph.addArc(n2, n3);
8.58 +
8.62 +
8.66 +
8.70 +
8.73 +
8.76 +
8.78 +    check(adaptor.source(a) == digraph.target(a), "Wrong reverse");
8.79 +    check(adaptor.target(a) == digraph.source(a), "Wrong reverse");
8.80 +  }
8.81 +}
8.82 +
8.83 +void checkSubDigraph() {
8.84 +  checkConcept<concepts::Digraph,
8.85 +    SubDigraph<concepts::Digraph,
8.86 +    concepts::Digraph::NodeMap<bool>,
8.87 +    concepts::Digraph::ArcMap<bool> > >();
8.88 +
8.89 +  typedef ListDigraph Digraph;
8.90 +  typedef Digraph::NodeMap<bool> NodeFilter;
8.91 +  typedef Digraph::ArcMap<bool> ArcFilter;
8.92 +  typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor;
8.93 +
8.94 +  Digraph digraph;
8.95 +  NodeFilter node_filter(digraph);
8.96 +  ArcFilter arc_filter(digraph);
8.98 +
8.99 +  Digraph::Node n1 = digraph.addNode();
8.100 +  Digraph::Node n2 = digraph.addNode();
8.101 +  Digraph::Node n3 = digraph.addNode();
8.102 +
8.103 +  Digraph::Arc a1 = digraph.addArc(n1, n2);
8.104 +  Digraph::Arc a2 = digraph.addArc(n1, n3);
8.105 +  Digraph::Arc a3 = digraph.addArc(n2, n3);
8.106 +
8.107 +  node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
8.108 +  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
8.109 +
8.113 +
8.117 +
8.121 +
8.124 +
8.127 +
8.128 +  arc_filter[a2] = false;
8.129 +
8.133 +
8.137 +
8.141 +
8.144 +
8.147 +
8.148 +  node_filter[n1] = false;
8.149 +
8.153 +
8.156 +
8.159 +
8.162 +
8.165 +
8.166 +  node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
8.167 +  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
8.168 +
8.172 +
8.175 +
8.178 +}
8.179 +
8.180 +void checkFilterNodes1() {
8.181 +  checkConcept<concepts::Digraph,
8.182 +    FilterNodes<concepts::Digraph,
8.183 +      concepts::Digraph::NodeMap<bool> > >();
8.184 +
8.185 +  typedef ListDigraph Digraph;
8.186 +  typedef Digraph::NodeMap<bool> NodeFilter;
8.187 +  typedef FilterNodes<Digraph, NodeFilter> Adaptor;
8.188 +
8.189 +  Digraph digraph;
8.190 +  NodeFilter node_filter(digraph);
8.192 +
8.193 +  Digraph::Node n1 = digraph.addNode();
8.194 +  Digraph::Node n2 = digraph.addNode();
8.195 +  Digraph::Node n3 = digraph.addNode();
8.196 +
8.197 +  Digraph::Arc a1 = digraph.addArc(n1, n2);
8.198 +  Digraph::Arc a2 = digraph.addArc(n1, n3);
8.199 +  Digraph::Arc a3 = digraph.addArc(n2, n3);
8.200 +
8.201 +  node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
8.202 +
8.206 +
8.210 +
8.214 +
8.217 +
8.220 +
8.221 +  node_filter[n1] = false;
8.222 +
8.226 +
8.229 +
8.232 +
8.235 +
8.238 +
8.239 +  node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
8.240 +
8.244 +
8.247 +
8.250 +}
8.251 +
8.252 +void checkFilterArcs() {
8.253 +  checkConcept<concepts::Digraph,
8.254 +    FilterArcs<concepts::Digraph,
8.255 +    concepts::Digraph::ArcMap<bool> > >();
8.256 +
8.257 +  typedef ListDigraph Digraph;
8.258 +  typedef Digraph::ArcMap<bool> ArcFilter;
8.259 +  typedef FilterArcs<Digraph, ArcFilter> Adaptor;
8.260 +
8.261 +  Digraph digraph;
8.262 +  ArcFilter arc_filter(digraph);
8.264 +
8.265 +  Digraph::Node n1 = digraph.addNode();
8.266 +  Digraph::Node n2 = digraph.addNode();
8.267 +  Digraph::Node n3 = digraph.addNode();
8.268 +
8.269 +  Digraph::Arc a1 = digraph.addArc(n1, n2);
8.270 +  Digraph::Arc a2 = digraph.addArc(n1, n3);
8.271 +  Digraph::Arc a3 = digraph.addArc(n2, n3);
8.272 +
8.273 +  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
8.274 +
8.278 +
8.282 +
8.286 +
8.289 +
8.292 +
8.293 +  arc_filter[a2] = false;
8.294 +
8.298 +
8.302 +
8.306 +
8.309 +
8.312 +
8.313 +  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
8.314 +
8.318 +
8.321 +
8.324 +}
8.325 +
8.326 +void checkUndirector() {
8.327 +  checkConcept<concepts::Graph, Undirector<concepts::Digraph> >();
8.328 +
8.329 +  typedef ListDigraph Digraph;
8.331 +
8.332 +  Digraph digraph;
8.334 +
8.335 +  Digraph::Node n1 = digraph.addNode();
8.336 +  Digraph::Node n2 = digraph.addNode();
8.337 +  Digraph::Node n3 = digraph.addNode();
8.338 +
8.339 +  Digraph::Arc a1 = digraph.addArc(n1, n2);
8.340 +  Digraph::Arc a2 = digraph.addArc(n1, n3);
8.341 +  Digraph::Arc a3 = digraph.addArc(n2, n3);
8.342 +
8.348 +
8.352 +
8.356 +
8.360 +
8.364 +
8.368 +
8.370 +    check(adaptor.u(e) == digraph.source(e), "Wrong undir");
8.371 +    check(adaptor.v(e) == digraph.target(e), "Wrong undir");
8.372 +  }
8.373 +
8.374 +}
8.375 +
8.376 +void checkResidual() {
8.377 +  checkConcept<concepts::Digraph,
8.378 +    Residual<concepts::Digraph,
8.379 +    concepts::Digraph::ArcMap<int>,
8.380 +    concepts::Digraph::ArcMap<int> > >();
8.381 +
8.382 +  typedef ListDigraph Digraph;
8.383 +  typedef Digraph::ArcMap<int> IntArcMap;
8.384 +  typedef Residual<Digraph, IntArcMap> Adaptor;
8.385 +
8.386 +  Digraph digraph;
8.387 +  IntArcMap capacity(digraph), flow(digraph);
8.389 +
8.390 +  Digraph::Node n1 = digraph.addNode();
8.391 +  Digraph::Node n2 = digraph.addNode();
8.392 +  Digraph::Node n3 = digraph.addNode();
8.393 +  Digraph::Node n4 = digraph.addNode();
8.394 +
8.395 +  Digraph::Arc a1 = digraph.addArc(n1, n2);
8.396 +  Digraph::Arc a2 = digraph.addArc(n1, n3);
8.397 +  Digraph::Arc a3 = digraph.addArc(n1, n4);
8.398 +  Digraph::Arc a4 = digraph.addArc(n2, n3);
8.399 +  Digraph::Arc a5 = digraph.addArc(n2, n4);
8.400 +  Digraph::Arc a6 = digraph.addArc(n3, n4);
8.401 +
8.402 +  capacity[a1] = 8;
8.403 +  capacity[a2] = 6;
8.404 +  capacity[a3] = 4;
8.405 +  capacity[a4] = 4;
8.406 +  capacity[a5] = 6;
8.407 +  capacity[a6] = 10;
8.408 +
8.410 +    flow[a] = 0;
8.411 +  }
8.412 +
8.416 +
8.421 +
8.426 +
8.428 +    flow[a] = capacity[a] / 2;
8.429 +  }
8.430 +
8.434 +
8.439 +
8.444 +
8.447 +
8.450 +
8.452 +    flow[a] = capacity[a];
8.453 +  }
8.454 +
8.458 +
8.463 +
8.468 +
8.470 +    flow[a] = 0;
8.471 +  }
8.472 +
8.473 +  int flow_value = 0;
8.474 +  while (true) {
8.475 +
8.477 +    bfs.run(n1, n4);
8.478 +
8.479 +    if (!bfs.reached(n4)) break;
8.480 +
8.481 +    Path<Adaptor> p = bfs.path(n4);
8.482 +
8.483 +    int min = std::numeric_limits<int>::max();
8.484 +    for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
8.485 +      if (adaptor.residualCapacity(a) < min)
8.487 +    }
8.488 +
8.489 +    for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
8.491 +    }
8.492 +    flow_value += min;
8.493 +  }
8.494 +
8.495 +  check(flow_value == 18, "Wrong flow with res graph adaptor");
8.496 +
8.497 +}
8.498 +
8.499 +void checkSplitNodes() {
8.500 +  checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();
8.501 +
8.502 +  typedef ListDigraph Digraph;
8.504 +
8.505 +  Digraph digraph;
8.507 +
8.508 +  Digraph::Node n1 = digraph.addNode();
8.509 +  Digraph::Node n2 = digraph.addNode();
8.510 +  Digraph::Node n3 = digraph.addNode();
8.511 +
8.512 +  Digraph::Arc a1 = digraph.addArc(n1, n2);
8.513 +  Digraph::Arc a2 = digraph.addArc(n1, n3);
8.514 +  Digraph::Arc a3 = digraph.addArc(n2, n3);
8.515 +
8.519 +
8.526 +
8.533 +
8.536 +
8.539 +
8.542 +      Digraph::Arc oa = a;
8.544 +            "Wrong split");
8.546 +            "Wrong split");
8.547 +    } else {
8.548 +      Digraph::Node on = a;
8.551 +    }
8.552 +  }
8.553 +}
8.554 +
8.555 +void checkSubGraph() {
8.556 +  checkConcept<concepts::Graph,
8.557 +    SubGraph<concepts::Graph,
8.558 +    concepts::Graph::NodeMap<bool>,
8.559 +    concepts::Graph::EdgeMap<bool> > >();
8.560 +
8.561 +  typedef ListGraph Graph;
8.562 +  typedef Graph::NodeMap<bool> NodeFilter;
8.563 +  typedef Graph::EdgeMap<bool> EdgeFilter;
8.564 +  typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor;
8.565 +
8.566 +  Graph graph;
8.567 +  NodeFilter node_filter(graph);
8.568 +  EdgeFilter edge_filter(graph);
8.570 +
8.571 +  Graph::Node n1 = graph.addNode();
8.572 +  Graph::Node n2 = graph.addNode();
8.573 +  Graph::Node n3 = graph.addNode();
8.574 +  Graph::Node n4 = graph.addNode();
8.575 +
8.576 +  Graph::Edge e1 = graph.addEdge(n1, n2);
8.577 +  Graph::Edge e2 = graph.addEdge(n1, n3);
8.578 +  Graph::Edge e3 = graph.addEdge(n2, n3);
8.579 +  Graph::Edge e4 = graph.addEdge(n3, n4);
8.580 +
8.581 +  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
8.582 +  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
8.583 +
8.589 +
8.594 +
8.599 +
8.604 +
8.608 +
8.612 +
8.613 +  edge_filter[e2] = false;
8.614 +
8.620 +
8.625 +
8.630 +
8.635 +
8.639 +
8.643 +
8.644 +  node_filter[n1] = false;
8.645 +
8.651 +
8.655 +
8.659 +
8.663 +
8.667 +
8.671 +
8.672 +  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
8.673 +  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
8.674 +
8.680 +
8.684 +
8.688 +}
8.689 +
8.690 +void checkFilterNodes2() {
8.691 +  checkConcept<concepts::Graph,
8.692 +    FilterNodes<concepts::Graph,
8.693 +      concepts::Graph::NodeMap<bool> > >();
8.694 +
8.695 +  typedef ListGraph Graph;
8.696 +  typedef Graph::NodeMap<bool> NodeFilter;
8.697 +  typedef FilterNodes<Graph, NodeFilter> Adaptor;
8.698 +
8.699 +  Graph graph;
8.700 +  NodeFilter node_filter(graph);
8.702 +
8.703 +  Graph::Node n1 = graph.addNode();
8.704 +  Graph::Node n2 = graph.addNode();
8.705 +  Graph::Node n3 = graph.addNode();
8.706 +  Graph::Node n4 = graph.addNode();
8.707 +
8.708 +  Graph::Edge e1 = graph.addEdge(n1, n2);
8.709 +  Graph::Edge e2 = graph.addEdge(n1, n3);
8.710 +  Graph::Edge e3 = graph.addEdge(n2, n3);
8.711 +  Graph::Edge e4 = graph.addEdge(n3, n4);
8.712 +
8.713 +  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
8.714 +
8.720 +
8.725 +
8.730 +
8.735 +
8.739 +
8.743 +
8.744 +  node_filter[n1] = false;
8.745 +
8.751 +
8.755 +
8.759 +
8.763 +
8.767 +
8.771 +
8.772 +  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
8.773 +
8.779 +
8.783 +
8.787 +}
8.788 +
8.789 +void checkFilterEdges() {
8.790 +  checkConcept<concepts::Graph,
8.791 +    FilterEdges<concepts::Graph,
8.792 +    concepts::Graph::EdgeMap<bool> > >();
8.793 +
8.794 +  typedef ListGraph Graph;
8.795 +  typedef Graph::EdgeMap<bool> EdgeFilter;
8.796 +  typedef FilterEdges<Graph, EdgeFilter> Adaptor;
8.797 +
8.798 +  Graph graph;
8.799 +  EdgeFilter edge_filter(graph);
8.801 +
8.802 +  Graph::Node n1 = graph.addNode();
8.803 +  Graph::Node n2 = graph.addNode();
8.804 +  Graph::Node n3 = graph.addNode();
8.805 +  Graph::Node n4 = graph.addNode();
8.806 +
8.807 +  Graph::Edge e1 = graph.addEdge(n1, n2);
8.808 +  Graph::Edge e2 = graph.addEdge(n1, n3);
8.809 +  Graph::Edge e3 = graph.addEdge(n2, n3);
8.810 +  Graph::Edge e4 = graph.addEdge(n3, n4);
8.811 +
8.812 +  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
8.813 +
8.819 +
8.824 +
8.829 +
8.834 +
8.838 +
8.842 +
8.843 +  edge_filter[e2] = false;
8.844 +
8.850 +
8.855 +
8.860 +
8.865 +
8.869 +
8.873 +
8.874 +  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
8.875 +
8.881 +
8.885 +
8.889 +}
8.890 +
8.891 +void checkOrienter() {
8.892 +  checkConcept<concepts::Digraph,
8.893 +    Orienter<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();
8.894 +
8.895 +  typedef ListGraph Graph;
8.896 +  typedef ListGraph::EdgeMap<bool> DirMap;
8.898 +
8.899 +  Graph graph;
8.900 +  DirMap dir(graph, true);
8.902 +
8.903 +  Graph::Node n1 = graph.addNode();
8.904 +  Graph::Node n2 = graph.addNode();
8.905 +  Graph::Node n3 = graph.addNode();
8.906 +
8.907 +  Graph::Edge e1 = graph.addEdge(n1, n2);
8.908 +  Graph::Edge e2 = graph.addEdge(n1, n3);
8.909 +  Graph::Edge e3 = graph.addEdge(n2, n3);
8.910 +
8.914 +
8.915 +  {
8.916 +    dir[e1] = true;
8.919 +
8.920 +    dir[e1] = false;
8.921 +    check (u == adaptor.target(e1), "Wrong dir");
8.922 +    check (v == adaptor.source(e1), "Wrong dir");
8.923 +
8.924 +    check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir");
8.925 +    dir[e1] = n1 == u;
8.926 +  }
8.927 +
8.928 +  {
8.929 +    dir[e2] = true;
8.932 +
8.933 +    dir[e2] = false;
8.934 +    check (u == adaptor.target(e2), "Wrong dir");
8.935 +    check (v == adaptor.source(e2), "Wrong dir");
8.936 +
8.937 +    check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir");
8.938 +    dir[e2] = n3 == u;
8.939 +  }
8.940 +
8.941 +  {
8.942 +    dir[e3] = true;
8.945 +
8.946 +    dir[e3] = false;
8.947 +    check (u == adaptor.target(e3), "Wrong dir");
8.948 +    check (v == adaptor.source(e3), "Wrong dir");
8.949 +
8.950 +    check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir");
8.951 +    dir[e3] = n2 == u;
8.952 +  }
8.953 +
8.957 +
8.961 +
8.964 +
8.967 +
8.968 +}
8.969 +
8.970 +
8.971 +int main(int, const char **) {
8.972 +
8.973 +  checkReverseDigraph();
8.974 +  checkSubDigraph();
8.975 +  checkFilterNodes1();
8.976 +  checkFilterArcs();
8.977 +  checkUndirector();
8.978 +  checkResidual();
8.979 +  checkSplitNodes();
8.980 +
8.981 +  checkSubGraph();
8.982 +  checkFilterNodes2();
8.983 +  checkFilterEdges();
8.984 +  checkOrienter();
8.985 +
8.986 +  return 0;
8.987 +}