Index: doc/groups.dox
===================================================================
--- doc/groups.dox (revision 403)
+++ doc/groups.dox (revision 432)
@@ -58,4 +58,77 @@
See also: \ref graph_concepts "Graph Structure Concepts".
+*/
+
+/**
+@defgroup graph_adaptors Adaptor Classes for graphs
+@ingroup graphs
+\brief This group contains several adaptor classes for digraphs and graphs
+
+The main parts of LEMON are the different graph structures, generic
+graph algorithms, graph concepts which couple these, and graph
+adaptors. While the previous notions are more or less clear, the
+latter one needs further explanation. Graph adaptors are graph classes
+which serve for considering graph structures in different ways.
+
+A short example makes this much clearer. Suppose that we have an
+instance \c g of a directed graph type say ListDigraph and an algorithm
+\code
+template
+int algorithm(const Digraph&);
+\endcode
+is needed to run on the reverse oriented graph. It may be expensive
+(in time or in memory usage) to copy \c g with the reversed
+arcs. In this case, an adaptor class is used, which (according
+to LEMON digraph concepts) works as a digraph. The adaptor uses the
+original digraph structure and digraph operations when methods of the
+reversed oriented graph are called. This means that the adaptor have
+minor memory usage, and do not perform sophisticated algorithmic
+actions. The purpose of it is to give a tool for the cases when a
+graph have to be used in a specific alteration. If this alteration is
+obtained by a usual construction like filtering the arc-set or
+considering a new orientation, then an adaptor is worthwhile to use.
+To come back to the reverse oriented graph, in this situation
+\code
+template class ReverseDigraph;
+\endcode
+template class can be used. The code looks as follows
+\code
+ListDigraph g;
+ReverseDigraph rg(g);
+int result = algorithm(rg);
+\endcode
+After running the algorithm, the original graph \c g is untouched.
+This techniques gives rise to an elegant code, and based on stable
+graph adaptors, complex algorithms can be implemented easily.
+
+In flow, circulation and bipartite matching problems, the residual
+graph is of particular importance. Combining an adaptor implementing
+this, shortest path algorithms and minimum mean cycle algorithms,
+a range of weighted and cardinality optimization algorithms can be
+obtained. For other examples, the interested user is referred to the
+detailed documentation of particular adaptors.
+
+The behavior of graph adaptors can be very different. Some of them keep
+capabilities of the original graph while in other cases this would be
+meaningless. This means that the concepts that they are models of depend
+on the graph adaptor, and the wrapped graph(s).
+If an arc of \c rg is deleted, this is carried out by deleting the
+corresponding arc of \c g, thus the adaptor modifies the original graph.
+
+But for a residual graph, this operation has no sense.
+Let us stand one more example here to simplify your work.
+RevGraphAdaptor has constructor
+\code
+ReverseDigraph(Digraph& digraph);
+\endcode
+This means that in a situation, when a const ListDigraph&
+reference to a graph is given, then it have to be instantiated with
+Digraph=const ListDigraph.
+\code
+int algorithm1(const ListDigraph& g) {
+ RevGraphAdaptor rg(g);
+ return algorithm2(rg);
+}
+\endcode
*/
Index: lemon/Makefile.am
===================================================================
--- lemon/Makefile.am (revision 430)
+++ lemon/Makefile.am (revision 432)
@@ -17,4 +17,5 @@
lemon_HEADERS += \
+ lemon/adaptors.h \
lemon/arg_parser.h \
lemon/assert.h \
Index: lemon/adaptors.h
===================================================================
--- lemon/adaptors.h (revision 432)
+++ lemon/adaptors.h (revision 432)
@@ -0,0 +1,3347 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2008
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_ADAPTORS_H
+#define LEMON_ADAPTORS_H
+
+/// \ingroup graph_adaptors
+/// \file
+/// \brief Several graph adaptors
+///
+/// This file contains several useful adaptors for digraphs and graphs.
+
+#include
+#include
+#include
+
+#include
+#include
+
+#include
+
+namespace lemon {
+
+ template
+ class DigraphAdaptorBase {
+ public:
+ typedef _Digraph Digraph;
+ typedef DigraphAdaptorBase Adaptor;
+ typedef Digraph ParentDigraph;
+
+ protected:
+ Digraph* _digraph;
+ DigraphAdaptorBase() : _digraph(0) { }
+ void setDigraph(Digraph& digraph) { _digraph = &digraph; }
+
+ public:
+ DigraphAdaptorBase(Digraph& digraph) : _digraph(&digraph) { }
+
+ typedef typename Digraph::Node Node;
+ typedef typename Digraph::Arc Arc;
+
+ void first(Node& i) const { _digraph->first(i); }
+ void first(Arc& i) const { _digraph->first(i); }
+ void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); }
+ void firstOut(Arc& i, const Node& n ) const { _digraph->firstOut(i, n); }
+
+ void next(Node& i) const { _digraph->next(i); }
+ void next(Arc& i) const { _digraph->next(i); }
+ void nextIn(Arc& i) const { _digraph->nextIn(i); }
+ void nextOut(Arc& i) const { _digraph->nextOut(i); }
+
+ Node source(const Arc& a) const { return _digraph->source(a); }
+ Node target(const Arc& a) const { return _digraph->target(a); }
+
+ typedef NodeNumTagIndicator NodeNumTag;
+ int nodeNum() const { return _digraph->nodeNum(); }
+
+ typedef EdgeNumTagIndicator EdgeNumTag;
+ int arcNum() const { return _digraph->arcNum(); }
+
+ typedef FindEdgeTagIndicator FindEdgeTag;
+ Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
+ return _digraph->findArc(u, v, prev);
+ }
+
+ Node addNode() { return _digraph->addNode(); }
+ Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
+
+ void erase(const Node& n) const { _digraph->erase(n); }
+ void erase(const Arc& a) const { _digraph->erase(a); }
+
+ void clear() const { _digraph->clear(); }
+
+ int id(const Node& n) const { return _digraph->id(n); }
+ int id(const Arc& a) const { return _digraph->id(a); }
+
+ Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
+ Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); }
+
+ int maxNodeId() const { return _digraph->maxNodeId(); }
+ int maxArcId() const { return _digraph->maxArcId(); }
+
+ typedef typename ItemSetTraits::ItemNotifier NodeNotifier;
+ NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
+
+ typedef typename ItemSetTraits::ItemNotifier ArcNotifier;
+ ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
+
+ template
+ class NodeMap : public Digraph::template NodeMap<_Value> {
+ public:
+
+ typedef typename Digraph::template NodeMap<_Value> Parent;
+
+ explicit NodeMap(const Adaptor& adaptor)
+ : Parent(*adaptor._digraph) {}
+
+ NodeMap(const Adaptor& adaptor, const _Value& value)
+ : Parent(*adaptor._digraph, value) { }
+
+ private:
+ NodeMap& operator=(const NodeMap& cmap) {
+ return operator=(cmap);
+ }
+
+ template
+ NodeMap& operator=(const CMap& cmap) {
+ Parent::operator=(cmap);
+ return *this;
+ }
+
+ };
+
+ template
+ class ArcMap : public Digraph::template ArcMap<_Value> {
+ public:
+
+ typedef typename Digraph::template ArcMap<_Value> Parent;
+
+ explicit ArcMap(const Adaptor& adaptor)
+ : Parent(*adaptor._digraph) {}
+
+ ArcMap(const Adaptor& adaptor, const _Value& value)
+ : Parent(*adaptor._digraph, value) {}
+
+ private:
+ ArcMap& operator=(const ArcMap& cmap) {
+ return operator=(cmap);
+ }
+
+ template
+ ArcMap& operator=(const CMap& cmap) {
+ Parent::operator=(cmap);
+ return *this;
+ }
+
+ };
+
+ };
+
+ template
+ class GraphAdaptorBase {
+ public:
+ typedef _Graph Graph;
+ typedef Graph ParentGraph;
+
+ protected:
+ Graph* _graph;
+
+ GraphAdaptorBase() : _graph(0) {}
+
+ void setGraph(Graph& graph) { _graph = &graph; }
+
+ public:
+ GraphAdaptorBase(Graph& graph) : _graph(&graph) {}
+
+ typedef typename Graph::Node Node;
+ typedef typename Graph::Arc Arc;
+ typedef typename Graph::Edge Edge;
+
+ void first(Node& i) const { _graph->first(i); }
+ void first(Arc& i) const { _graph->first(i); }
+ void first(Edge& i) const { _graph->first(i); }
+ void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); }
+ void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); }
+ void firstInc(Edge &i, bool &d, const Node &n) const {
+ _graph->firstInc(i, d, n);
+ }
+
+ void next(Node& i) const { _graph->next(i); }
+ void next(Arc& i) const { _graph->next(i); }
+ void next(Edge& i) const { _graph->next(i); }
+ void nextIn(Arc& i) const { _graph->nextIn(i); }
+ void nextOut(Arc& i) const { _graph->nextOut(i); }
+ void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); }
+
+ Node u(const Edge& e) const { return _graph->u(e); }
+ Node v(const Edge& e) const { return _graph->v(e); }
+
+ Node source(const Arc& a) const { return _graph->source(a); }
+ Node target(const Arc& a) const { return _graph->target(a); }
+
+ typedef NodeNumTagIndicator NodeNumTag;
+ int nodeNum() const { return _graph->nodeNum(); }
+
+ typedef EdgeNumTagIndicator EdgeNumTag;
+ int arcNum() const { return _graph->arcNum(); }
+ int edgeNum() const { return _graph->edgeNum(); }
+
+ typedef FindEdgeTagIndicator FindEdgeTag;
+ Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
+ return _graph->findArc(u, v, prev);
+ }
+ Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) {
+ return _graph->findEdge(u, v, prev);
+ }
+
+ Node addNode() { return _graph->addNode(); }
+ Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }
+
+ void erase(const Node& i) { _graph->erase(i); }
+ void erase(const Edge& i) { _graph->erase(i); }
+
+ void clear() { _graph->clear(); }
+
+ bool direction(const Arc& a) const { return _graph->direction(a); }
+ Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); }
+
+ int id(const Node& v) const { return _graph->id(v); }
+ int id(const Arc& a) const { return _graph->id(a); }
+ int id(const Edge& e) const { return _graph->id(e); }
+
+ Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
+ Arc arcFromId(int ix) const { return _graph->arcFromId(ix); }
+ Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); }
+
+ int maxNodeId() const { return _graph->maxNodeId(); }
+ int maxArcId() const { return _graph->maxArcId(); }
+ int maxEdgeId() const { return _graph->maxEdgeId(); }
+
+ typedef typename ItemSetTraits::ItemNotifier NodeNotifier;
+ NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
+
+ typedef typename ItemSetTraits::ItemNotifier ArcNotifier;
+ ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
+
+ typedef typename ItemSetTraits::ItemNotifier EdgeNotifier;
+ EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
+
+ template
+ class NodeMap : public Graph::template NodeMap<_Value> {
+ public:
+ typedef typename Graph::template NodeMap<_Value> Parent;
+ explicit NodeMap(const GraphAdaptorBase& adapter)
+ : Parent(*adapter._graph) {}
+ NodeMap(const GraphAdaptorBase& adapter, const _Value& value)
+ : Parent(*adapter._graph, value) {}
+
+ private:
+ NodeMap& operator=(const NodeMap& cmap) {
+ return operator=(cmap);
+ }
+
+ template
+ NodeMap& operator=(const CMap& cmap) {
+ Parent::operator=(cmap);
+ return *this;
+ }
+
+ };
+
+ template
+ class ArcMap : public Graph::template ArcMap<_Value> {
+ public:
+ typedef typename Graph::template ArcMap<_Value> Parent;
+ explicit ArcMap(const GraphAdaptorBase& adapter)
+ : Parent(*adapter._graph) {}
+ ArcMap(const GraphAdaptorBase& adapter, const _Value& value)
+ : Parent(*adapter._graph, value) {}
+
+ private:
+ ArcMap& operator=(const ArcMap& cmap) {
+ return operator=(cmap);
+ }
+
+ template
+ ArcMap& operator=(const CMap& cmap) {
+ Parent::operator=(cmap);
+ return *this;
+ }
+ };
+
+ template
+ class EdgeMap : public Graph::template EdgeMap<_Value> {
+ public:
+ typedef typename Graph::template EdgeMap<_Value> Parent;
+ explicit EdgeMap(const GraphAdaptorBase& adapter)
+ : Parent(*adapter._graph) {}
+ EdgeMap(const GraphAdaptorBase& adapter, const _Value& value)
+ : Parent(*adapter._graph, value) {}
+
+ private:
+ EdgeMap& operator=(const EdgeMap& cmap) {
+ return operator=(cmap);
+ }
+
+ template
+ EdgeMap& operator=(const CMap& cmap) {
+ Parent::operator=(cmap);
+ return *this;
+ }
+ };
+
+ };
+
+ template
+ class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> {
+ public:
+ typedef _Digraph Digraph;
+ typedef DigraphAdaptorBase<_Digraph> Parent;
+ protected:
+ ReverseDigraphBase() : Parent() { }
+ public:
+ typedef typename Parent::Node Node;
+ typedef typename Parent::Arc Arc;
+
+ void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }
+ void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); }
+
+ void nextIn(Arc& a) const { Parent::nextOut(a); }
+ void nextOut(Arc& a) const { Parent::nextIn(a); }
+
+ Node source(const Arc& a) const { return Parent::target(a); }
+ Node target(const Arc& a) const { return Parent::source(a); }
+
+ Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
+
+ typedef FindEdgeTagIndicator FindEdgeTag;
+ Arc findArc(const Node& u, const Node& v,
+ const Arc& prev = INVALID) {
+ return Parent::findArc(v, u, prev);
+ }
+
+ };
+
+ /// \ingroup graph_adaptors
+ ///
+ /// \brief A digraph adaptor which reverses the orientation of the arcs.
+ ///
+ /// ReverseDigraph reverses the arcs in the adapted digraph. The
+ /// SubDigraph is conform to the \ref concepts::Digraph
+ /// "Digraph concept".
+ ///
+ /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
+ /// "Digraph concept". The type can be specified to be const.
+ template
+ class ReverseDigraph :
+ public DigraphAdaptorExtender > {
+ public:
+ typedef _Digraph Digraph;
+ typedef DigraphAdaptorExtender<
+ ReverseDigraphBase<_Digraph> > Parent;
+ protected:
+ ReverseDigraph() { }
+ public:
+
+ /// \brief Constructor
+ ///
+ /// Creates a reverse digraph adaptor for the given digraph
+ explicit ReverseDigraph(Digraph& digraph) {
+ Parent::setDigraph(digraph);
+ }
+ };
+
+ /// \brief Just gives back a reverse digraph adaptor
+ ///
+ /// Just gives back a reverse digraph adaptor
+ template
+ ReverseDigraph reverseDigraph(const Digraph& digraph) {
+ return ReverseDigraph(digraph);
+ }
+
+ template
+ class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {
+ public:
+ typedef _Digraph Digraph;
+ typedef _NodeFilterMap NodeFilterMap;
+ typedef _ArcFilterMap ArcFilterMap;
+
+ typedef SubDigraphBase Adaptor;
+ typedef DigraphAdaptorBase<_Digraph> Parent;
+ protected:
+ NodeFilterMap* _node_filter;
+ ArcFilterMap* _arc_filter;
+ SubDigraphBase()
+ : Parent(), _node_filter(0), _arc_filter(0) { }
+
+ void setNodeFilterMap(NodeFilterMap& node_filter) {
+ _node_filter = &node_filter;
+ }
+ void setArcFilterMap(ArcFilterMap& arc_filter) {
+ _arc_filter = &arc_filter;
+ }
+
+ public:
+
+ typedef typename Parent::Node Node;
+ typedef typename Parent::Arc Arc;
+
+ void first(Node& i) const {
+ Parent::first(i);
+ while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
+ }
+
+ void first(Arc& i) const {
+ Parent::first(i);
+ while (i != INVALID && (!(*_arc_filter)[i]
+ || !(*_node_filter)[Parent::source(i)]
+ || !(*_node_filter)[Parent::target(i)]))
+ Parent::next(i);
+ }
+
+ void firstIn(Arc& i, const Node& n) const {
+ Parent::firstIn(i, n);
+ while (i != INVALID && (!(*_arc_filter)[i]
+ || !(*_node_filter)[Parent::source(i)]))
+ Parent::nextIn(i);
+ }
+
+ void firstOut(Arc& i, const Node& n) const {
+ Parent::firstOut(i, n);
+ while (i != INVALID && (!(*_arc_filter)[i]
+ || !(*_node_filter)[Parent::target(i)]))
+ Parent::nextOut(i);
+ }
+
+ void next(Node& i) const {
+ Parent::next(i);
+ while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
+ }
+
+ void next(Arc& i) const {
+ Parent::next(i);
+ while (i != INVALID && (!(*_arc_filter)[i]
+ || !(*_node_filter)[Parent::source(i)]
+ || !(*_node_filter)[Parent::target(i)]))
+ Parent::next(i);
+ }
+
+ void nextIn(Arc& i) const {
+ Parent::nextIn(i);
+ while (i != INVALID && (!(*_arc_filter)[i]
+ || !(*_node_filter)[Parent::source(i)]))
+ Parent::nextIn(i);
+ }
+
+ void nextOut(Arc& i) const {
+ Parent::nextOut(i);
+ while (i != INVALID && (!(*_arc_filter)[i]
+ || !(*_node_filter)[Parent::target(i)]))
+ Parent::nextOut(i);
+ }
+
+ void hide(const Node& n) const { _node_filter->set(n, false); }
+ void hide(const Arc& a) const { _arc_filter->set(a, false); }
+
+ void unHide(const Node& n) const { _node_filter->set(n, true); }
+ void unHide(const Arc& a) const { _arc_filter->set(a, true); }
+
+ bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
+ bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }
+
+ typedef False NodeNumTag;
+ typedef False EdgeNumTag;
+
+ typedef FindEdgeTagIndicator FindEdgeTag;
+ Arc findArc(const Node& source, const Node& target,
+ const Arc& prev = INVALID) {
+ if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
+ return INVALID;
+ }
+ Arc arc = Parent::findArc(source, target, prev);
+ while (arc != INVALID && !(*_arc_filter)[arc]) {
+ arc = Parent::findArc(source, target, arc);
+ }
+ return arc;
+ }
+
+ template
+ class NodeMap : public SubMapExtender > {
+ public:
+ typedef _Value Value;
+ typedef SubMapExtender > MapParent;
+
+ NodeMap(const Adaptor& adaptor)
+ : MapParent(adaptor) {}
+ NodeMap(const Adaptor& adaptor, const Value& value)
+ : MapParent(adaptor, value) {}
+
+ private:
+ NodeMap& operator=(const NodeMap& cmap) {
+ return operator=(cmap);
+ }
+
+ template
+ NodeMap& operator=(const CMap& cmap) {
+ MapParent::operator=(cmap);
+ return *this;
+ }
+ };
+
+ template
+ class ArcMap : public SubMapExtender > {
+ public:
+ typedef _Value Value;
+ typedef SubMapExtender > MapParent;
+
+ ArcMap(const Adaptor& adaptor)
+ : MapParent(adaptor) {}
+ ArcMap(const Adaptor& adaptor, const Value& value)
+ : MapParent(adaptor, value) {}
+
+ private:
+ ArcMap& operator=(const ArcMap& cmap) {
+ return operator=(cmap);
+ }
+
+ template
+ ArcMap& operator=(const CMap& cmap) {
+ MapParent::operator=(cmap);
+ return *this;
+ }
+ };
+
+ };
+
+ template
+ class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>
+ : public DigraphAdaptorBase<_Digraph> {
+ public:
+ typedef _Digraph Digraph;
+ typedef _NodeFilterMap NodeFilterMap;
+ typedef _ArcFilterMap ArcFilterMap;
+
+ typedef SubDigraphBase Adaptor;
+ typedef DigraphAdaptorBase Parent;
+ protected:
+ NodeFilterMap* _node_filter;
+ ArcFilterMap* _arc_filter;
+ SubDigraphBase()
+ : Parent(), _node_filter(0), _arc_filter(0) { }
+
+ void setNodeFilterMap(NodeFilterMap& node_filter) {
+ _node_filter = &node_filter;
+ }
+ void setArcFilterMap(ArcFilterMap& arc_filter) {
+ _arc_filter = &arc_filter;
+ }
+
+ public:
+
+ typedef typename Parent::Node Node;
+ typedef typename Parent::Arc Arc;
+
+ void first(Node& i) const {
+ Parent::first(i);
+ while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
+ }
+
+ void first(Arc& i) const {
+ Parent::first(i);
+ while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
+ }
+
+ void firstIn(Arc& i, const Node& n) const {
+ Parent::firstIn(i, n);
+ while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
+ }
+
+ void firstOut(Arc& i, const Node& n) const {
+ Parent::firstOut(i, n);
+ while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
+ }
+
+ void next(Node& i) const {
+ Parent::next(i);
+ while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
+ }
+ void next(Arc& i) const {
+ Parent::next(i);
+ while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
+ }
+ void nextIn(Arc& i) const {
+ Parent::nextIn(i);
+ while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
+ }
+
+ void nextOut(Arc& i) const {
+ Parent::nextOut(i);
+ while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
+ }
+
+ void hide(const Node& n) const { _node_filter->set(n, false); }
+ void hide(const Arc& e) const { _arc_filter->set(e, false); }
+
+ void unHide(const Node& n) const { _node_filter->set(n, true); }
+ void unHide(const Arc& e) const { _arc_filter->set(e, true); }
+
+ bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
+ bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }
+
+ typedef False NodeNumTag;
+ typedef False EdgeNumTag;
+
+ typedef FindEdgeTagIndicator FindEdgeTag;
+ Arc findArc(const Node& source, const Node& target,
+ const Arc& prev = INVALID) {
+ if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
+ return INVALID;
+ }
+ Arc arc = Parent::findArc(source, target, prev);
+ while (arc != INVALID && !(*_arc_filter)[arc]) {
+ arc = Parent::findArc(source, target, arc);
+ }
+ return arc;
+ }
+
+ template
+ class NodeMap : public SubMapExtender > {
+ public:
+ typedef _Value Value;
+ typedef SubMapExtender > MapParent;
+
+ NodeMap(const Adaptor& adaptor)
+ : MapParent(adaptor) {}
+ NodeMap(const Adaptor& adaptor, const Value& value)
+ : MapParent(adaptor, value) {}
+
+ private:
+ NodeMap& operator=(const NodeMap& cmap) {
+ return operator=(cmap);
+ }
+
+ template
+ NodeMap& operator=(const CMap& cmap) {
+ MapParent::operator=(cmap);
+ return *this;
+ }
+ };
+
+ template
+ class ArcMap : public SubMapExtender > {
+ public:
+ typedef _Value Value;
+ typedef SubMapExtender > MapParent;
+
+ ArcMap(const Adaptor& adaptor)
+ : MapParent(adaptor) {}
+ ArcMap(const Adaptor& adaptor, const Value& value)
+ : MapParent(adaptor, value) {}
+
+ private:
+ ArcMap& operator=(const ArcMap& cmap) {
+ return operator=(cmap);
+ }
+
+ template
+ ArcMap& operator=(const CMap& cmap) {
+ MapParent::operator=(cmap);
+ return *this;
+ }
+ };
+
+ };
+
+ /// \ingroup graph_adaptors
+ ///
+ /// \brief An adaptor for hiding nodes and arcs in a digraph
+ ///
+ /// SubDigraph hides nodes and arcs in a digraph. A bool node map
+ /// and a bool arc map must be specified, which define the filters
+ /// for nodes and arcs. Just the nodes and arcs with true value are
+ /// shown in the subdigraph. The SubDigraph is conform to the \ref
+ /// concepts::Digraph "Digraph concept". If the \c _checked parameter
+ /// is true, then the arcs incident to filtered nodes are also
+ /// filtered out.
+ ///
+ /// \tparam _Digraph It must be conform to the \ref
+ /// concepts::Digraph "Digraph concept". The type can be specified
+ /// to const.
+ /// \tparam _NodeFilterMap A bool valued node map of the the adapted digraph.
+ /// \tparam _ArcFilterMap A bool valued arc map of the the adapted digraph.
+ /// \tparam _checked If the parameter is false then the arc filtering
+ /// is not checked with respect to node filter. Otherwise, each arc
+ /// is automatically filtered, which is incident to a filtered node.
+ ///
+ /// \see FilterNodes
+ /// \see FilterArcs
+ template,
+ typename _ArcFilterMap = typename _Digraph::template ArcMap,
+ bool _checked = true>
+ class SubDigraph
+ : public DigraphAdaptorExtender<
+ SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > {
+ public:
+ typedef _Digraph Digraph;
+ typedef _NodeFilterMap NodeFilterMap;
+ typedef _ArcFilterMap ArcFilterMap;
+
+ typedef DigraphAdaptorExtender<
+ SubDigraphBase >
+ Parent;
+
+ typedef typename Parent::Node Node;
+ typedef typename Parent::Arc Arc;
+
+ protected:
+ SubDigraph() { }
+ public:
+
+ /// \brief Constructor
+ ///
+ /// Creates a subdigraph for the given digraph with
+ /// given node and arc map filters.
+ SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,
+ ArcFilterMap& arc_filter) {
+ setDigraph(digraph);
+ setNodeFilterMap(node_filter);
+ setArcFilterMap(arc_filter);
+ }
+
+ /// \brief Hides the node of the graph
+ ///
+ /// This function hides \c n in the digraph, i.e. the iteration
+ /// jumps over it. This is done by simply setting the value of \c n
+ /// to be false in the corresponding node-map.
+ void hide(const Node& n) const { Parent::hide(n); }
+
+ /// \brief Hides the arc of the graph
+ ///
+ /// This function hides \c a in the digraph, i.e. the iteration
+ /// jumps over it. This is done by simply setting the value of \c a
+ /// to be false in the corresponding arc-map.
+ void hide(const Arc& a) const { Parent::hide(a); }
+
+ /// \brief Unhides the node of the graph
+ ///
+ /// The value of \c n is set to be true in the node-map which stores
+ /// hide information. If \c n was hidden previuosly, then it is shown
+ /// again
+ void unHide(const Node& n) const { Parent::unHide(n); }
+
+ /// \brief Unhides the arc of the graph
+ ///
+ /// The value of \c a is set to be true in the arc-map which stores
+ /// hide information. If \c a was hidden previuosly, then it is shown
+ /// again
+ void unHide(const Arc& a) const { Parent::unHide(a); }
+
+ /// \brief Returns true if \c n is hidden.
+ ///
+ /// Returns true if \c n is hidden.
+ ///
+ bool hidden(const Node& n) const { return Parent::hidden(n); }
+
+ /// \brief Returns true if \c a is hidden.
+ ///
+ /// Returns true if \c a is hidden.
+ ///
+ bool hidden(const Arc& a) const { return Parent::hidden(a); }
+
+ };
+
+ /// \brief Just gives back a subdigraph
+ ///
+ /// Just gives back a subdigraph
+ template
+ SubDigraph
+ subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) {
+ return SubDigraph
+ (digraph, nfm, afm);
+ }
+
+ template
+ SubDigraph
+ subDigraph(const Digraph& digraph,
+ const NodeFilterMap& nfm, ArcFilterMap& afm) {
+ return SubDigraph
+ (digraph, nfm, afm);
+ }
+
+ template
+ SubDigraph
+ subDigraph(const Digraph& digraph,
+ NodeFilterMap& nfm, const ArcFilterMap& afm) {
+ return SubDigraph
+ (digraph, nfm, afm);
+ }
+
+ template
+ SubDigraph
+ subDigraph(const Digraph& digraph,
+ const NodeFilterMap& nfm, const ArcFilterMap& afm) {
+ return SubDigraph(digraph, nfm, afm);
+ }
+
+
+ template
+ class SubGraphBase : public GraphAdaptorBase<_Graph> {
+ public:
+ typedef _Graph Graph;
+ typedef SubGraphBase Adaptor;
+ typedef GraphAdaptorBase<_Graph> Parent;
+ protected:
+
+ NodeFilterMap* _node_filter_map;
+ EdgeFilterMap* _edge_filter_map;
+
+ SubGraphBase()
+ : Parent(), _node_filter_map(0), _edge_filter_map(0) { }
+
+ void setNodeFilterMap(NodeFilterMap& node_filter_map) {
+ _node_filter_map=&node_filter_map;
+ }
+ void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
+ _edge_filter_map=&edge_filter_map;
+ }
+
+ public:
+
+ typedef typename Parent::Node Node;
+ typedef typename Parent::Arc Arc;
+ typedef typename Parent::Edge Edge;
+
+ void first(Node& i) const {
+ Parent::first(i);
+ while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
+ }
+
+ void first(Arc& i) const {
+ Parent::first(i);
+ while (i!=INVALID && (!(*_edge_filter_map)[i]
+ || !(*_node_filter_map)[Parent::source(i)]
+ || !(*_node_filter_map)[Parent::target(i)]))
+ Parent::next(i);
+ }
+
+ void first(Edge& i) const {
+ Parent::first(i);
+ while (i!=INVALID && (!(*_edge_filter_map)[i]
+ || !(*_node_filter_map)[Parent::u(i)]
+ || !(*_node_filter_map)[Parent::v(i)]))
+ Parent::next(i);
+ }
+
+ void firstIn(Arc& i, const Node& n) const {
+ Parent::firstIn(i, n);
+ while (i!=INVALID && (!(*_edge_filter_map)[i]
+ || !(*_node_filter_map)[Parent::source(i)]))
+ Parent::nextIn(i);
+ }
+
+ void firstOut(Arc& i, const Node& n) const {
+ Parent::firstOut(i, n);
+ while (i!=INVALID && (!(*_edge_filter_map)[i]
+ || !(*_node_filter_map)[Parent::target(i)]))
+ Parent::nextOut(i);
+ }
+
+ void firstInc(Edge& i, bool& d, const Node& n) const {
+ Parent::firstInc(i, d, n);
+ while (i!=INVALID && (!(*_edge_filter_map)[i]
+ || !(*_node_filter_map)[Parent::u(i)]
+ || !(*_node_filter_map)[Parent::v(i)]))
+ Parent::nextInc(i, d);
+ }
+
+ void next(Node& i) const {
+ Parent::next(i);
+ while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
+ }
+
+ void next(Arc& i) const {
+ Parent::next(i);
+ while (i!=INVALID && (!(*_edge_filter_map)[i]
+ || !(*_node_filter_map)[Parent::source(i)]
+ || !(*_node_filter_map)[Parent::target(i)]))
+ Parent::next(i);
+ }
+
+ void next(Edge& i) const {
+ Parent::next(i);
+ while (i!=INVALID && (!(*_edge_filter_map)[i]
+ || !(*_node_filter_map)[Parent::u(i)]
+ || !(*_node_filter_map)[Parent::v(i)]))
+ Parent::next(i);
+ }
+
+ void nextIn(Arc& i) const {
+ Parent::nextIn(i);
+ while (i!=INVALID && (!(*_edge_filter_map)[i]
+ || !(*_node_filter_map)[Parent::source(i)]))
+ Parent::nextIn(i);
+ }
+
+ void nextOut(Arc& i) const {
+ Parent::nextOut(i);
+ while (i!=INVALID && (!(*_edge_filter_map)[i]
+ || !(*_node_filter_map)[Parent::target(i)]))
+ Parent::nextOut(i);
+ }
+
+ void nextInc(Edge& i, bool& d) const {
+ Parent::nextInc(i, d);
+ while (i!=INVALID && (!(*_edge_filter_map)[i]
+ || !(*_node_filter_map)[Parent::u(i)]
+ || !(*_node_filter_map)[Parent::v(i)]))
+ Parent::nextInc(i, d);
+ }
+
+ void hide(const Node& n) const { _node_filter_map->set(n, false); }
+ void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
+
+ void unHide(const Node& n) const { _node_filter_map->set(n, true); }
+ void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
+
+ bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
+ bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
+
+ typedef False NodeNumTag;
+ typedef False EdgeNumTag;
+
+ typedef FindEdgeTagIndicator FindEdgeTag;
+ Arc findArc(const Node& u, const Node& v,
+ const Arc& prev = INVALID) {
+ if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
+ return INVALID;
+ }
+ Arc arc = Parent::findArc(u, v, prev);
+ while (arc != INVALID && !(*_edge_filter_map)[arc]) {
+ arc = Parent::findArc(u, v, arc);
+ }
+ return arc;
+ }
+ Edge findEdge(const Node& u, const Node& v,
+ const Edge& prev = INVALID) {
+ if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
+ return INVALID;
+ }
+ Edge edge = Parent::findEdge(u, v, prev);
+ while (edge != INVALID && !(*_edge_filter_map)[edge]) {
+ edge = Parent::findEdge(u, v, edge);
+ }
+ return edge;
+ }
+
+ template
+ class NodeMap : public SubMapExtender > {
+ public:
+ typedef _Value Value;
+ typedef SubMapExtender > MapParent;
+
+ NodeMap(const Adaptor& adaptor)
+ : MapParent(adaptor) {}
+ NodeMap(const Adaptor& adaptor, const Value& value)
+ : MapParent(adaptor, value) {}
+
+ private:
+ NodeMap& operator=(const NodeMap& cmap) {
+ return operator=(cmap);
+ }
+
+ template
+ NodeMap& operator=(const CMap& cmap) {
+ MapParent::operator=(cmap);
+ return *this;
+ }
+ };
+
+ template
+ class ArcMap : public SubMapExtender > {
+ public:
+ typedef _Value Value;
+ typedef SubMapExtender > MapParent;
+
+ ArcMap(const Adaptor& adaptor)
+ : MapParent(adaptor) {}
+ ArcMap(const Adaptor& adaptor, const Value& value)
+ : MapParent(adaptor, value) {}
+
+ private:
+ ArcMap& operator=(const ArcMap& cmap) {
+ return operator=(cmap);
+ }
+
+ template
+ ArcMap& operator=(const CMap& cmap) {
+ MapParent::operator=(cmap);
+ return *this;
+ }
+ };
+
+ template
+ class EdgeMap : public SubMapExtender > {
+ public:
+ typedef _Value Value;
+ typedef SubMapExtender > MapParent;
+
+ EdgeMap(const Adaptor& adaptor)
+ : MapParent(adaptor) {}
+
+ EdgeMap(const Adaptor& adaptor, const Value& value)
+ : MapParent(adaptor, value) {}
+
+ private:
+ EdgeMap& operator=(const EdgeMap& cmap) {
+ return operator=(cmap);
+ }
+
+ template
+ EdgeMap& operator=(const CMap& cmap) {
+ MapParent::operator=(cmap);
+ return *this;
+ }
+ };
+
+ };
+
+ template
+ class SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
+ : public GraphAdaptorBase<_Graph> {
+ public:
+ typedef _Graph Graph;
+ typedef SubGraphBase Adaptor;
+ typedef GraphAdaptorBase<_Graph> Parent;
+ protected:
+ NodeFilterMap* _node_filter_map;
+ EdgeFilterMap* _edge_filter_map;
+ SubGraphBase() : Parent(),
+ _node_filter_map(0), _edge_filter_map(0) { }
+
+ void setNodeFilterMap(NodeFilterMap& node_filter_map) {
+ _node_filter_map=&node_filter_map;
+ }
+ void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
+ _edge_filter_map=&edge_filter_map;
+ }
+
+ public:
+
+ typedef typename Parent::Node Node;
+ typedef typename Parent::Arc Arc;
+ typedef typename Parent::Edge Edge;
+
+ void first(Node& i) const {
+ Parent::first(i);
+ while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
+ }
+
+ void first(Arc& i) const {
+ Parent::first(i);
+ while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
+ }
+
+ void first(Edge& i) const {
+ Parent::first(i);
+ while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
+ }
+
+ void firstIn(Arc& i, const Node& n) const {
+ Parent::firstIn(i, n);
+ while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
+ }
+
+ void firstOut(Arc& i, const Node& n) const {
+ Parent::firstOut(i, n);
+ while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
+ }
+
+ void firstInc(Edge& i, bool& d, const Node& n) const {
+ Parent::firstInc(i, d, n);
+ while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
+ }
+
+ void next(Node& i) const {
+ Parent::next(i);
+ while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
+ }
+ void next(Arc& i) const {
+ Parent::next(i);
+ while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
+ }
+ void next(Edge& i) const {
+ Parent::next(i);
+ while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
+ }
+ void nextIn(Arc& i) const {
+ Parent::nextIn(i);
+ while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
+ }
+
+ void nextOut(Arc& i) const {
+ Parent::nextOut(i);
+ while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
+ }
+ void nextInc(Edge& i, bool& d) const {
+ Parent::nextInc(i, d);
+ while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
+ }
+
+ void hide(const Node& n) const { _node_filter_map->set(n, false); }
+ void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
+
+ void unHide(const Node& n) const { _node_filter_map->set(n, true); }
+ void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
+
+ bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
+ bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
+
+ typedef False NodeNumTag;
+ typedef False EdgeNumTag;
+
+ typedef FindEdgeTagIndicator FindEdgeTag;
+ Arc findArc(const Node& u, const Node& v,
+ const Arc& prev = INVALID) {
+ Arc arc = Parent::findArc(u, v, prev);
+ while (arc != INVALID && !(*_edge_filter_map)[arc]) {
+ arc = Parent::findArc(u, v, arc);
+ }
+ return arc;
+ }
+ Edge findEdge(const Node& u, const Node& v,
+ const Edge& prev = INVALID) {
+ Edge edge = Parent::findEdge(u, v, prev);
+ while (edge != INVALID && !(*_edge_filter_map)[edge]) {
+ edge = Parent::findEdge(u, v, edge);
+ }
+ return edge;
+ }
+
+ template
+ class NodeMap : public SubMapExtender > {
+ public:
+ typedef _Value Value;
+ typedef SubMapExtender > MapParent;
+
+ NodeMap(const Adaptor& adaptor)
+ : MapParent(adaptor) {}
+ NodeMap(const Adaptor& adaptor, const Value& value)
+ : MapParent(adaptor, value) {}
+
+ private:
+ NodeMap& operator=(const NodeMap& cmap) {
+ return operator=(cmap);
+ }
+
+ template
+ NodeMap& operator=(const CMap& cmap) {
+ MapParent::operator=(cmap);
+ return *this;
+ }
+ };
+
+ template
+ class ArcMap : public SubMapExtender > {
+ public:
+ typedef _Value Value;
+ typedef SubMapExtender > MapParent;
+
+ ArcMap(const Adaptor& adaptor)
+ : MapParent(adaptor) {}
+ ArcMap(const Adaptor& adaptor, const Value& value)
+ : MapParent(adaptor, value) {}
+
+ private:
+ ArcMap& operator=(const ArcMap& cmap) {
+ return operator=(cmap);
+ }
+
+ template
+ ArcMap& operator=(const CMap& cmap) {
+ MapParent::operator=(cmap);
+ return *this;
+ }
+ };
+
+ template
+ class EdgeMap : public SubMapExtender > {
+ public:
+ typedef _Value Value;
+ typedef SubMapExtender > MapParent;
+
+ EdgeMap(const Adaptor& adaptor)
+ : MapParent(adaptor) {}
+
+ EdgeMap(const Adaptor& adaptor, const _Value& value)
+ : MapParent(adaptor, value) {}
+
+ private:
+ EdgeMap& operator=(const EdgeMap& cmap) {
+ return operator=(cmap);
+ }
+
+ template
+ EdgeMap& operator=(const CMap& cmap) {
+ MapParent::operator=(cmap);
+ return *this;
+ }
+ };
+
+ };
+
+ /// \ingroup graph_adaptors
+ ///
+ /// \brief A graph adaptor for hiding nodes and edges in an
+ /// undirected graph.
+ ///
+ /// SubGraph hides nodes and edges in a graph. A bool node map and a
+ /// bool edge map must be specified, which define the filters for
+ /// nodes and edges. Just the nodes and edges with true value are
+ /// shown in the subgraph. The SubGraph is conform to the \ref
+ /// concepts::Graph "Graph concept". If the \c _checked parameter is
+ /// true, then the edges incident to filtered nodes are also
+ /// filtered out.
+ ///
+ /// \tparam _Graph It must be conform to the \ref
+ /// concepts::Graph "Graph concept". The type can be specified
+ /// to const.
+ /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
+ /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted graph.
+ /// \tparam _checked If the parameter is false then the edge filtering
+ /// is not checked with respect to node filter. Otherwise, each edge
+ /// is automatically filtered, which is incident to a filtered node.
+ ///
+ /// \see FilterNodes
+ /// \see FilterEdges
+ template
+ class SubGraph
+ : public GraphAdaptorExtender<
+ SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, _checked> > {
+ public:
+ typedef _Graph Graph;
+ typedef GraphAdaptorExtender<
+ SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
+
+ typedef typename Parent::Node Node;
+ typedef typename Parent::Edge Edge;
+
+ protected:
+ SubGraph() { }
+ public:
+
+ /// \brief Constructor
+ ///
+ /// Creates a subgraph for the given graph with given node and
+ /// edge map filters.
+ SubGraph(Graph& _graph, NodeFilterMap& node_filter_map,
+ EdgeFilterMap& edge_filter_map) {
+ setGraph(_graph);
+ setNodeFilterMap(node_filter_map);
+ setEdgeFilterMap(edge_filter_map);
+ }
+
+ /// \brief Hides the node of the graph
+ ///
+ /// This function hides \c n in the graph, i.e. the iteration
+ /// jumps over it. This is done by simply setting the value of \c n
+ /// to be false in the corresponding node-map.
+ void hide(const Node& n) const { Parent::hide(n); }
+
+ /// \brief Hides the edge of the graph
+ ///
+ /// This function hides \c e in the graph, i.e. the iteration
+ /// jumps over it. This is done by simply setting the value of \c e
+ /// to be false in the corresponding edge-map.
+ void hide(const Edge& e) const { Parent::hide(e); }
+
+ /// \brief Unhides the node of the graph
+ ///
+ /// The value of \c n is set to be true in the node-map which stores
+ /// hide information. If \c n was hidden previuosly, then it is shown
+ /// again
+ void unHide(const Node& n) const { Parent::unHide(n); }
+
+ /// \brief Unhides the edge of the graph
+ ///
+ /// The value of \c e is set to be true in the edge-map which stores
+ /// hide information. If \c e was hidden previuosly, then it is shown
+ /// again
+ void unHide(const Edge& e) const { Parent::unHide(e); }
+
+ /// \brief Returns true if \c n is hidden.
+ ///
+ /// Returns true if \c n is hidden.
+ ///
+ bool hidden(const Node& n) const { return Parent::hidden(n); }
+
+ /// \brief Returns true if \c e is hidden.
+ ///
+ /// Returns true if \c e is hidden.
+ ///
+ bool hidden(const Edge& e) const { return Parent::hidden(e); }
+ };
+
+ /// \brief Just gives back a subgraph
+ ///
+ /// Just gives back a subgraph
+ template
+ SubGraph
+ subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) {
+ return SubGraph(graph, nfm, efm);
+ }
+
+ template
+ SubGraph
+ subGraph(const Graph& graph,
+ const NodeFilterMap& nfm, ArcFilterMap& efm) {
+ return SubGraph
+ (graph, nfm, efm);
+ }
+
+ template
+ SubGraph
+ subGraph(const Graph& graph,
+ NodeFilterMap& nfm, const ArcFilterMap& efm) {
+ return SubGraph
+ (graph, nfm, efm);
+ }
+
+ template
+ SubGraph
+ subGraph(const Graph& graph,
+ const NodeFilterMap& nfm, const ArcFilterMap& efm) {
+ return SubGraph
+ (graph, nfm, efm);
+ }
+
+ /// \ingroup graph_adaptors
+ ///
+ /// \brief An adaptor for hiding nodes from a digraph or a graph.
+ ///
+ /// FilterNodes adaptor hides nodes in a graph or a digraph. A bool
+ /// node map must be specified, which defines the filters for
+ /// nodes. Just the unfiltered nodes and the arcs or edges incident
+ /// to unfiltered nodes are shown in the subdigraph or subgraph. The
+ /// FilterNodes is conform to the \ref concepts::Digraph
+ /// "Digraph concept" or \ref concepts::Graph "Graph concept" depending
+ /// on the \c _Digraph template parameter. If the \c _checked
+ /// parameter is true, then the arc or edges incident to filtered nodes
+ /// are also filtered out.
+ ///
+ /// \tparam _Digraph It must be conform to the \ref
+ /// concepts::Digraph "Digraph concept" or \ref concepts::Graph
+ /// "Graph concept". The type can be specified to be const.
+ /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
+ /// \tparam _checked If the parameter is false then the arc or edge
+ /// filtering is not checked with respect to node filter. In this
+ /// case just isolated nodes can be filtered out from the
+ /// graph.
+#ifdef DOXYGEN
+ template,
+ bool _checked = true>
+#else
+ template,
+ bool _checked = true,
+ typename Enable = void>
+#endif
+ class FilterNodes
+ : public SubDigraph<_Digraph, _NodeFilterMap,
+ ConstMap, _checked> {
+ public:
+
+ typedef _Digraph Digraph;
+ typedef _NodeFilterMap NodeFilterMap;
+
+ typedef SubDigraph, _checked>
+ Parent;
+
+ typedef typename Parent::Node Node;
+
+ protected:
+ ConstMap const_true_map;
+
+ FilterNodes() : const_true_map(true) {
+ Parent::setArcFilterMap(const_true_map);
+ }
+
+ public:
+
+ /// \brief Constructor
+ ///
+ /// Creates an adaptor for the given digraph or graph with
+ /// given node filter map.
+ FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) :
+ Parent(), const_true_map(true) {
+ Parent::setDigraph(_digraph);
+ Parent::setNodeFilterMap(node_filter);
+ Parent::setArcFilterMap(const_true_map);
+ }
+
+ /// \brief Hides the node of the graph
+ ///
+ /// This function hides \c n in the digraph or graph, i.e. the iteration
+ /// jumps over it. This is done by simply setting the value of \c n
+ /// to be false in the corresponding node map.
+ void hide(const Node& n) const { Parent::hide(n); }
+
+ /// \brief Unhides the node of the graph
+ ///
+ /// The value of \c n is set to be true in the node-map which stores
+ /// hide information. If \c n was hidden previuosly, then it is shown
+ /// again
+ void unHide(const Node& n) const { Parent::unHide(n); }
+
+ /// \brief Returns true if \c n is hidden.
+ ///
+ /// Returns true if \c n is hidden.
+ ///
+ bool hidden(const Node& n) const { return Parent::hidden(n); }
+
+ };
+
+ template
+ class FilterNodes<_Graph, _NodeFilterMap, _checked,
+ typename enable_if >::type>
+ : public SubGraph<_Graph, _NodeFilterMap,
+ ConstMap, _checked> {
+ public:
+ typedef _Graph Graph;
+ typedef _NodeFilterMap NodeFilterMap;
+ typedef SubGraph > Parent;
+
+ typedef typename Parent::Node Node;
+ protected:
+ ConstMap const_true_map;
+
+ FilterNodes() : const_true_map(true) {
+ Parent::setEdgeFilterMap(const_true_map);
+ }
+
+ public:
+
+ FilterNodes(Graph& _graph, NodeFilterMap& node_filter_map) :
+ Parent(), const_true_map(true) {
+ Parent::setGraph(_graph);
+ Parent::setNodeFilterMap(node_filter_map);
+ Parent::setEdgeFilterMap(const_true_map);
+ }
+
+ void hide(const Node& n) const { Parent::hide(n); }
+ void unHide(const Node& n) const { Parent::unHide(n); }
+ bool hidden(const Node& n) const { return Parent::hidden(n); }
+
+ };
+
+
+ /// \brief Just gives back a FilterNodes adaptor
+ ///
+ /// Just gives back a FilterNodes adaptor
+ template
+ FilterNodes
+ filterNodes(const Digraph& digraph, NodeFilterMap& nfm) {
+ return FilterNodes(digraph, nfm);
+ }
+
+ template
+ FilterNodes
+ filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) {
+ return FilterNodes(digraph, nfm);
+ }
+
+ /// \ingroup graph_adaptors
+ ///
+ /// \brief An adaptor for hiding arcs from a digraph.
+ ///
+ /// FilterArcs adaptor hides arcs in a digraph. A bool arc map must
+ /// be specified, which defines the filters for arcs. Just the
+ /// unfiltered arcs are shown in the subdigraph. The FilterArcs is
+ /// conform to the \ref concepts::Digraph "Digraph concept".
+ ///
+ /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
+ /// "Digraph concept". The type can be specified to be const.
+ /// \tparam _ArcFilterMap A bool valued arc map of the the adapted
+ /// graph.
+ template
+ class FilterArcs :
+ public SubDigraph<_Digraph, ConstMap,
+ _ArcFilterMap, false> {
+ public:
+ typedef _Digraph Digraph;
+ typedef _ArcFilterMap ArcFilterMap;
+
+ typedef SubDigraph,
+ ArcFilterMap, false> Parent;
+
+ typedef typename Parent::Arc Arc;
+
+ protected:
+ ConstMap const_true_map;
+
+ FilterArcs() : const_true_map(true) {
+ Parent::setNodeFilterMap(const_true_map);
+ }
+
+ public:
+
+ /// \brief Constructor
+ ///
+ /// Creates a FilterArcs adaptor for the given graph with
+ /// given arc map filter.
+ FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
+ : Parent(), const_true_map(true) {
+ Parent::setDigraph(digraph);
+ Parent::setNodeFilterMap(const_true_map);
+ Parent::setArcFilterMap(arc_filter);
+ }
+
+ /// \brief Hides the arc of the graph
+ ///
+ /// This function hides \c a in the graph, i.e. the iteration
+ /// jumps over it. This is done by simply setting the value of \c a
+ /// to be false in the corresponding arc map.
+ void hide(const Arc& a) const { Parent::hide(a); }
+
+ /// \brief Unhides the arc of the graph
+ ///
+ /// The value of \c a is set to be true in the arc-map which stores
+ /// hide information. If \c a was hidden previuosly, then it is shown
+ /// again
+ void unHide(const Arc& a) const { Parent::unHide(a); }
+
+ /// \brief Returns true if \c a is hidden.
+ ///
+ /// Returns true if \c a is hidden.
+ ///
+ bool hidden(const Arc& a) const { return Parent::hidden(a); }
+
+ };
+
+ /// \brief Just gives back an FilterArcs adaptor
+ ///
+ /// Just gives back an FilterArcs adaptor
+ template
+ FilterArcs
+ filterArcs(const Digraph& digraph, ArcFilterMap& afm) {
+ return FilterArcs(digraph, afm);
+ }
+
+ template
+ FilterArcs
+ filterArcs(const Digraph& digraph, const ArcFilterMap& afm) {
+ return FilterArcs(digraph, afm);
+ }
+
+ /// \ingroup graph_adaptors
+ ///
+ /// \brief An adaptor for hiding edges from a graph.
+ ///
+ /// FilterEdges adaptor hides edges in a digraph. A bool edge map must
+ /// be specified, which defines the filters for edges. Just the
+ /// unfiltered edges are shown in the subdigraph. The FilterEdges is
+ /// conform to the \ref concepts::Graph "Graph concept".
+ ///
+ /// \tparam _Graph It must be conform to the \ref concepts::Graph
+ /// "Graph concept". The type can be specified to be const.
+ /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted
+ /// graph.
+ template
+ class FilterEdges :
+ public SubGraph<_Graph, ConstMap,
+ _EdgeFilterMap, false> {
+ public:
+ typedef _Graph Graph;
+ typedef _EdgeFilterMap EdgeFilterMap;
+ typedef SubGraph,
+ EdgeFilterMap, false> Parent;
+ typedef typename Parent::Edge Edge;
+ protected:
+ ConstMap const_true_map;
+
+ FilterEdges() : const_true_map(true) {
+ Parent::setNodeFilterMap(const_true_map);
+ }
+
+ public:
+
+ /// \brief Constructor
+ ///
+ /// Creates a FilterEdges adaptor for the given graph with
+ /// given edge map filters.
+ FilterEdges(Graph& _graph, EdgeFilterMap& edge_filter_map) :
+ Parent(), const_true_map(true) {
+ Parent::setGraph(_graph);
+ Parent::setNodeFilterMap(const_true_map);
+ Parent::setEdgeFilterMap(edge_filter_map);
+ }
+
+ /// \brief Hides the edge of the graph
+ ///
+ /// This function hides \c e in the graph, i.e. the iteration
+ /// jumps over it. This is done by simply setting the value of \c e
+ /// to be false in the corresponding edge-map.
+ void hide(const Edge& e) const { Parent::hide(e); }
+
+ /// \brief Unhides the edge of the graph
+ ///
+ /// The value of \c e is set to be true in the edge-map which stores
+ /// hide information. If \c e was hidden previuosly, then it is shown
+ /// again
+ void unHide(const Edge& e) const { Parent::unHide(e); }
+
+ /// \brief Returns true if \c e is hidden.
+ ///
+ /// Returns true if \c e is hidden.
+ ///
+ bool hidden(const Edge& e) const { return Parent::hidden(e); }
+
+ };
+
+ /// \brief Just gives back a FilterEdges adaptor
+ ///
+ /// Just gives back a FilterEdges adaptor
+ template
+ FilterEdges
+ filterEdges(const Graph& graph, EdgeFilterMap& efm) {
+ return FilterEdges(graph, efm);
+ }
+
+ template
+ FilterEdges
+ filterEdges(const Graph& graph, const EdgeFilterMap& efm) {
+ return FilterEdges(graph, efm);
+ }
+
+ template
+ class UndirectorBase {
+ public:
+ typedef _Digraph Digraph;
+ typedef UndirectorBase Adaptor;
+
+ typedef True UndirectedTag;
+
+ typedef typename Digraph::Arc Edge;
+ typedef typename Digraph::Node Node;
+
+ class Arc : public Edge {
+ friend class UndirectorBase;
+ protected:
+ bool _forward;
+
+ Arc(const Edge& edge, bool forward) :
+ Edge(edge), _forward(forward) {}
+
+ public:
+ Arc() {}
+
+ Arc(Invalid) : Edge(INVALID), _forward(true) {}
+
+ bool operator==(const Arc &other) const {
+ return _forward == other._forward &&
+ static_cast(*this) == static_cast(other);
+ }
+ bool operator!=(const Arc &other) const {
+ return _forward != other._forward ||
+ static_cast(*this) != static_cast(other);
+ }
+ bool operator<(const Arc &other) const {
+ return _forward < other._forward ||
+ (_forward == other._forward &&
+ static_cast(*this) < static_cast(other));
+ }
+ };
+
+
+
+ void first(Node& n) const {
+ _digraph->first(n);
+ }
+
+ void next(Node& n) const {
+ _digraph->next(n);
+ }
+
+ void first(Arc& a) const {
+ _digraph->first(a);
+ a._forward = true;
+ }
+
+ void next(Arc& a) const {
+ if (a._forward) {
+ a._forward = false;
+ } else {
+ _digraph->next(a);
+ a._forward = true;
+ }
+ }
+
+ void first(Edge& e) const {
+ _digraph->first(e);
+ }
+
+ void next(Edge& e) const {
+ _digraph->next(e);
+ }
+
+ void firstOut(Arc& a, const Node& n) const {
+ _digraph->firstIn(a, n);
+ if( static_cast(a) != INVALID ) {
+ a._forward = false;
+ } else {
+ _digraph->firstOut(a, n);
+ a._forward = true;
+ }
+ }
+ void nextOut(Arc &a) const {
+ if (!a._forward) {
+ Node n = _digraph->target(a);
+ _digraph->nextIn(a);
+ if (static_cast(a) == INVALID ) {
+ _digraph->firstOut(a, n);
+ a._forward = true;
+ }
+ }
+ else {
+ _digraph->nextOut(a);
+ }
+ }
+
+ void firstIn(Arc &a, const Node &n) const {
+ _digraph->firstOut(a, n);
+ if (static_cast(a) != INVALID ) {
+ a._forward = false;
+ } else {
+ _digraph->firstIn(a, n);
+ a._forward = true;
+ }
+ }
+ void nextIn(Arc &a) const {
+ if (!a._forward) {
+ Node n = _digraph->source(a);
+ _digraph->nextOut(a);
+ if( static_cast(a) == INVALID ) {
+ _digraph->firstIn(a, n);
+ a._forward = true;
+ }
+ }
+ else {
+ _digraph->nextIn(a);
+ }
+ }
+
+ void firstInc(Edge &e, bool &d, const Node &n) const {
+ d = true;
+ _digraph->firstOut(e, n);
+ if (e != INVALID) return;
+ d = false;
+ _digraph->firstIn(e, n);
+ }
+
+ void nextInc(Edge &e, bool &d) const {
+ if (d) {
+ Node s = _digraph->source(e);
+ _digraph->nextOut(e);
+ if (e != INVALID) return;
+ d = false;
+ _digraph->firstIn(e, s);
+ } else {
+ _digraph->nextIn(e);
+ }
+ }
+
+ Node u(const Edge& e) const {
+ return _digraph->source(e);
+ }
+
+ Node v(const Edge& e) const {
+ return _digraph->target(e);
+ }
+
+ Node source(const Arc &a) const {
+ return a._forward ? _digraph->source(a) : _digraph->target(a);
+ }
+
+ Node target(const Arc &a) const {
+ return a._forward ? _digraph->target(a) : _digraph->source(a);
+ }
+
+ static Arc direct(const Edge &e, bool d) {
+ return Arc(e, d);
+ }
+ Arc direct(const Edge &e, const Node& n) const {
+ return Arc(e, _digraph->source(e) == n);
+ }
+
+ static bool direction(const Arc &a) { return a._forward; }
+
+ Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
+ Arc arcFromId(int ix) const {
+ return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1));
+ }
+ Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); }
+
+ int id(const Node &n) const { return _digraph->id(n); }
+ int id(const Arc &a) const {
+ return (_digraph->id(a) << 1) | (a._forward ? 1 : 0);
+ }
+ int id(const Edge &e) const { return _digraph->id(e); }
+
+ int maxNodeId() const { return _digraph->maxNodeId(); }
+ int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; }
+ int maxEdgeId() const { return _digraph->maxArcId(); }
+
+ Node addNode() { return _digraph->addNode(); }
+ Edge addEdge(const Node& u, const Node& v) {
+ return _digraph->addArc(u, v);
+ }
+
+ void erase(const Node& i) { _digraph->erase(i); }
+ void erase(const Edge& i) { _digraph->erase(i); }
+
+ void clear() { _digraph->clear(); }
+
+ typedef NodeNumTagIndicator NodeNumTag;
+ int nodeNum() const { return 2 * _digraph->arcNum(); }
+ typedef EdgeNumTagIndicator EdgeNumTag;
+ int arcNum() const { return 2 * _digraph->arcNum(); }
+ int edgeNum() const { return _digraph->arcNum(); }
+
+ typedef FindEdgeTagIndicator FindEdgeTag;
+ Arc findArc(Node s, Node t, Arc p = INVALID) const {
+ if (p == INVALID) {
+ Edge arc = _digraph->findArc(s, t);
+ if (arc != INVALID) return direct(arc, true);
+ arc = _digraph->findArc(t, s);
+ if (arc != INVALID) return direct(arc, false);
+ } else if (direction(p)) {
+ Edge arc = _digraph->findArc(s, t, p);
+ if (arc != INVALID) return direct(arc, true);
+ arc = _digraph->findArc(t, s);
+ if (arc != INVALID) return direct(arc, false);
+ } else {
+ Edge arc = _digraph->findArc(t, s, p);
+ if (arc != INVALID) return direct(arc, false);
+ }
+ return INVALID;
+ }
+
+ Edge findEdge(Node s, Node t, Edge p = INVALID) const {
+ if (s != t) {
+ if (p == INVALID) {
+ Edge arc = _digraph->findArc(s, t);
+ if (arc != INVALID) return arc;
+ arc = _digraph->findArc(t, s);
+ if (arc != INVALID) return arc;
+ } else if (_digraph->s(p) == s) {
+ Edge arc = _digraph->findArc(s, t, p);
+ if (arc != INVALID) return arc;
+ arc = _digraph->findArc(t, s);
+ if (arc != INVALID) return arc;
+ } else {
+ Edge arc = _digraph->findArc(t, s, p);
+ if (arc != INVALID) return arc;
+ }
+ } else {
+ return _digraph->findArc(s, t, p);
+ }
+ return INVALID;
+ }
+
+ private:
+
+ template
+ class ArcMapBase {
+ private:
+
+ typedef typename Digraph::template ArcMap<_Value> MapImpl;
+
+ public:
+
+ typedef typename MapTraits::ReferenceMapTag ReferenceMapTag;
+
+ typedef _Value Value;
+ typedef Arc Key;
+
+ ArcMapBase(const Adaptor& adaptor) :
+ _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
+
+ ArcMapBase(const Adaptor& adaptor, const Value& v)
+ : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}
+
+ void set(const Arc& a, const Value& v) {
+ if (direction(a)) {
+ _forward.set(a, v);
+ } else {
+ _backward.set(a, v);
+ }
+ }
+
+ typename MapTraits::ConstReturnValue
+ operator[](const Arc& a) const {
+ if (direction(a)) {
+ return _forward[a];
+ } else {
+ return _backward[a];
+ }
+ }
+
+ typename MapTraits::ReturnValue
+ operator[](const Arc& a) {
+ if (direction(a)) {
+ return _forward[a];
+ } else {
+ return _backward[a];
+ }
+ }
+
+ protected:
+
+ MapImpl _forward, _backward;
+
+ };
+
+ public:
+
+ template
+ class NodeMap : public Digraph::template NodeMap<_Value> {
+ public:
+
+ typedef _Value Value;
+ typedef typename Digraph::template NodeMap Parent;
+
+ explicit NodeMap(const Adaptor& adaptor)
+ : Parent(*adaptor._digraph) {}
+
+ NodeMap(const Adaptor& adaptor, const _Value& value)
+ : Parent(*adaptor._digraph, value) { }
+
+ private:
+ NodeMap& operator=(const NodeMap& cmap) {
+ return operator=(cmap);
+ }
+
+ template
+ NodeMap& operator=(const CMap& cmap) {
+ Parent::operator=(cmap);
+ return *this;
+ }
+
+ };
+
+ template
+ class ArcMap
+ : public SubMapExtender >
+ {
+ public:
+ typedef _Value Value;
+ typedef SubMapExtender > Parent;
+
+ ArcMap(const Adaptor& adaptor)
+ : Parent(adaptor) {}
+
+ ArcMap(const Adaptor& adaptor, const Value& value)
+ : Parent(adaptor, value) {}
+
+ private:
+ ArcMap& operator=(const ArcMap& cmap) {
+ return operator=(cmap);
+ }
+
+ template
+ ArcMap& operator=(const CMap& cmap) {
+ Parent::operator=(cmap);
+ return *this;
+ }
+ };
+
+ template
+ class EdgeMap : public Digraph::template ArcMap<_Value> {
+ public:
+
+ typedef _Value Value;
+ typedef typename Digraph::template ArcMap Parent;
+
+ explicit EdgeMap(const Adaptor& adaptor)
+ : Parent(*adaptor._digraph) {}
+
+ EdgeMap(const Adaptor& adaptor, const Value& value)
+ : Parent(*adaptor._digraph, value) {}
+
+ private:
+ EdgeMap& operator=(const EdgeMap& cmap) {
+ return operator=(cmap);
+ }
+
+ template
+ EdgeMap& operator=(const CMap& cmap) {
+ Parent::operator=(cmap);
+ return *this;
+ }
+
+ };
+
+ typedef typename ItemSetTraits::ItemNotifier NodeNotifier;
+ NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
+
+ protected:
+
+ UndirectorBase() : _digraph(0) {}
+
+ Digraph* _digraph;
+
+ void setDigraph(Digraph& digraph) {
+ _digraph = &digraph;
+ }
+
+ };
+
+ /// \ingroup graph_adaptors
+ ///
+ /// \brief Undirect the graph
+ ///
+ /// This adaptor makes an undirected graph from a directed
+ /// graph. All arcs of the underlying digraph will be showed in the
+ /// adaptor as an edge. The Orienter adaptor is conform to the \ref
+ /// concepts::Graph "Graph concept".
+ ///
+ /// \tparam _Digraph It must be conform to the \ref
+ /// concepts::Digraph "Digraph concept". The type can be specified
+ /// to const.
+ template
+ class Undirector
+ : public GraphAdaptorExtender > {
+ public:
+ typedef _Digraph Digraph;
+ typedef GraphAdaptorExtender > Parent;
+ protected:
+ Undirector() { }
+ public:
+
+ /// \brief Constructor
+ ///
+ /// Creates a undirected graph from the given digraph
+ Undirector(_Digraph& digraph) {
+ setDigraph(digraph);
+ }
+
+ /// \brief ArcMap combined from two original ArcMap
+ ///
+ /// This class adapts two original digraph ArcMap to
+ /// get an arc map on the undirected graph.
+ template
+ class CombinedArcMap {
+ public:
+
+ typedef _ForwardMap ForwardMap;
+ typedef _BackwardMap BackwardMap;
+
+ typedef typename MapTraits::ReferenceMapTag ReferenceMapTag;
+
+ typedef typename ForwardMap::Value Value;
+ typedef typename Parent::Arc Key;
+
+ /// \brief Constructor
+ ///
+ /// Constructor
+ CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
+ : _forward(&forward), _backward(&backward) {}
+
+
+ /// \brief Sets the value associated with a key.
+ ///
+ /// Sets the value associated with a key.
+ void set(const Key& e, const Value& a) {
+ if (Parent::direction(e)) {
+ _forward->set(e, a);
+ } else {
+ _backward->set(e, a);
+ }
+ }
+
+ /// \brief Returns the value associated with a key.
+ ///
+ /// Returns the value associated with a key.
+ typename MapTraits::ConstReturnValue
+ operator[](const Key& e) const {
+ if (Parent::direction(e)) {
+ return (*_forward)[e];
+ } else {
+ return (*_backward)[e];
+ }
+ }
+
+ /// \brief Returns the value associated with a key.
+ ///
+ /// Returns the value associated with a key.
+ typename MapTraits::ReturnValue
+ operator[](const Key& e) {
+ if (Parent::direction(e)) {
+ return (*_forward)[e];
+ } else {
+ return (*_backward)[e];
+ }
+ }
+
+ protected:
+
+ ForwardMap* _forward;
+ BackwardMap* _backward;
+
+ };
+
+ /// \brief Just gives back a combined arc map
+ ///
+ /// Just gives back a combined arc map
+ template
+ static CombinedArcMap
+ combinedArcMap(ForwardMap& forward, BackwardMap& backward) {
+ return CombinedArcMap(forward, backward);
+ }
+
+ template
+ static CombinedArcMap
+ combinedArcMap(const ForwardMap& forward, BackwardMap& backward) {
+ return CombinedArcMap(forward, backward);
+ }
+
+ template
+ static CombinedArcMap
+ combinedArcMap(ForwardMap& forward, const BackwardMap& backward) {
+ return CombinedArcMap(forward, backward);
+ }
+
+ template
+ static CombinedArcMap
+ combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) {
+ return CombinedArcMap(forward, backward);
+ }
+
+ };
+
+ /// \brief Just gives back an undirected view of the given digraph
+ ///
+ /// Just gives back an undirected view of the given digraph
+ template
+ Undirector
+ undirector(const Digraph& digraph) {
+ return Undirector(digraph);
+ }
+
+ template
+ class OrienterBase {
+ public:
+
+ typedef _Graph Graph;
+ typedef _DirectionMap DirectionMap;
+
+ typedef typename Graph::Node Node;
+ typedef typename Graph::Edge Arc;
+
+ void reverseArc(const Arc& arc) {
+ _direction->set(arc, !(*_direction)[arc]);
+ }
+
+ void first(Node& i) const { _graph->first(i); }
+ void first(Arc& i) const { _graph->first(i); }
+ void firstIn(Arc& i, const Node& n) const {
+ bool d;
+ _graph->firstInc(i, d, n);
+ while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
+ }
+ void firstOut(Arc& i, const Node& n ) const {
+ bool d;
+ _graph->firstInc(i, d, n);
+ while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
+ }
+
+ void next(Node& i) const { _graph->next(i); }
+ void next(Arc& i) const { _graph->next(i); }
+ void nextIn(Arc& i) const {
+ bool d = !(*_direction)[i];
+ _graph->nextInc(i, d);
+ while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
+ }
+ void nextOut(Arc& i) const {
+ bool d = (*_direction)[i];
+ _graph->nextInc(i, d);
+ while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
+ }
+
+ Node source(const Arc& e) const {
+ return (*_direction)[e] ? _graph->u(e) : _graph->v(e);
+ }
+ Node target(const Arc& e) const {
+ return (*_direction)[e] ? _graph->v(e) : _graph->u(e);
+ }
+
+ typedef NodeNumTagIndicator NodeNumTag;
+ int nodeNum() const { return _graph->nodeNum(); }
+
+ typedef EdgeNumTagIndicator EdgeNumTag;
+ int arcNum() const { return _graph->edgeNum(); }
+
+ typedef FindEdgeTagIndicator FindEdgeTag;
+ Arc findArc(const Node& u, const Node& v,
+ const Arc& prev = INVALID) {
+ Arc arc = prev;
+ bool d = arc == INVALID ? true : (*_direction)[arc];
+ if (d) {
+ arc = _graph->findEdge(u, v, arc);
+ while (arc != INVALID && !(*_direction)[arc]) {
+ _graph->findEdge(u, v, arc);
+ }
+ if (arc != INVALID) return arc;
+ }
+ _graph->findEdge(v, u, arc);
+ while (arc != INVALID && (*_direction)[arc]) {
+ _graph->findEdge(u, v, arc);
+ }
+ return arc;
+ }
+
+ Node addNode() {
+ return Node(_graph->addNode());
+ }
+
+ Arc addArc(const Node& u, const Node& v) {
+ Arc arc = _graph->addArc(u, v);
+ _direction->set(arc, _graph->source(arc) == u);
+ return arc;
+ }
+
+ void erase(const Node& i) { _graph->erase(i); }
+ void erase(const Arc& i) { _graph->erase(i); }
+
+ void clear() { _graph->clear(); }
+
+ int id(const Node& v) const { return _graph->id(v); }
+ int id(const Arc& e) const { return _graph->id(e); }
+
+ Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
+ Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
+
+ int maxNodeId() const { return _graph->maxNodeId(); }
+ int maxArcId() const { return _graph->maxEdgeId(); }
+
+ typedef typename ItemSetTraits::ItemNotifier NodeNotifier;
+ NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
+
+ typedef typename ItemSetTraits::ItemNotifier ArcNotifier;
+ ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
+
+ template
+ class NodeMap : public _Graph::template NodeMap<_Value> {
+ public:
+
+ typedef typename _Graph::template NodeMap<_Value> Parent;
+
+ explicit NodeMap(const OrienterBase& adapter)
+ : Parent(*adapter._graph) {}
+
+ NodeMap(const OrienterBase& adapter, const _Value& value)
+ : Parent(*adapter._graph, value) {}
+
+ private:
+ NodeMap& operator=(const NodeMap& cmap) {
+ return operator=(cmap);
+ }
+
+ template
+ NodeMap& operator=(const CMap& cmap) {
+ Parent::operator=(cmap);
+ return *this;
+ }
+
+ };
+
+ template
+ class ArcMap : public _Graph::template EdgeMap<_Value> {
+ public:
+
+ typedef typename Graph::template EdgeMap<_Value> Parent;
+
+ explicit ArcMap(const OrienterBase& adapter)
+ : Parent(*adapter._graph) { }
+
+ ArcMap(const OrienterBase& adapter, const _Value& value)
+ : Parent(*adapter._graph, value) { }
+
+ private:
+ ArcMap& operator=(const ArcMap& cmap) {
+ return operator=(cmap);
+ }
+
+ template
+ ArcMap& operator=(const CMap& cmap) {
+ Parent::operator=(cmap);
+ return *this;
+ }
+ };
+
+
+
+ protected:
+ Graph* _graph;
+ DirectionMap* _direction;
+
+ void setDirectionMap(DirectionMap& direction) {
+ _direction = &direction;
+ }
+
+ void setGraph(Graph& graph) {
+ _graph = &graph;
+ }
+
+ };
+
+ /// \ingroup graph_adaptors
+ ///
+ /// \brief Orients the edges of the graph to get a digraph
+ ///
+ /// This adaptor orients each edge in the undirected graph. The
+ /// direction of the arcs stored in an edge node map. The arcs can
+ /// be easily reverted by the \c reverseArc() member function in the
+ /// adaptor. The Orienter adaptor is conform to the \ref
+ /// concepts::Digraph "Digraph concept".
+ ///
+ /// \tparam _Graph It must be conform to the \ref concepts::Graph
+ /// "Graph concept". The type can be specified to be const.
+ /// \tparam _DirectionMap A bool valued edge map of the the adapted
+ /// graph.
+ ///
+ /// \sa orienter
+ template >
+ class Orienter :
+ public DigraphAdaptorExtender > {
+ public:
+ typedef _Graph Graph;
+ typedef DigraphAdaptorExtender<
+ OrienterBase<_Graph, DirectionMap> > Parent;
+ typedef typename Parent::Arc Arc;
+ protected:
+ Orienter() { }
+ public:
+
+ /// \brief Constructor of the adaptor
+ ///
+ /// Constructor of the adaptor
+ Orienter(Graph& graph, DirectionMap& direction) {
+ setGraph(graph);
+ setDirectionMap(direction);
+ }
+
+ /// \brief Reverse arc
+ ///
+ /// It reverse the given arc. It simply negate the direction in the map.
+ void reverseArc(const Arc& a) {
+ Parent::reverseArc(a);
+ }
+ };
+
+ /// \brief Just gives back a Orienter
+ ///
+ /// Just gives back a Orienter
+ template
+ Orienter
+ orienter(const Graph& graph, DirectionMap& dm) {
+ return Orienter(graph, dm);
+ }
+
+ template
+ Orienter
+ orienter(const Graph& graph, const DirectionMap& dm) {
+ return Orienter(graph, dm);
+ }
+
+ namespace _adaptor_bits {
+
+ template,
+ typename _FlowMap = _CapacityMap,
+ typename _Tolerance = Tolerance >
+ class ResForwardFilter {
+ public:
+
+ typedef _Digraph Digraph;
+ typedef _CapacityMap CapacityMap;
+ typedef _FlowMap FlowMap;
+ typedef _Tolerance Tolerance;
+
+ typedef typename Digraph::Arc Key;
+ typedef bool Value;
+
+ private:
+
+ const CapacityMap* _capacity;
+ const FlowMap* _flow;
+ Tolerance _tolerance;
+ public:
+
+ ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,
+ const Tolerance& tolerance = Tolerance())
+ : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
+
+ bool operator[](const typename Digraph::Arc& a) const {
+ return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
+ }
+ };
+
+ template,
+ typename _FlowMap = _CapacityMap,
+ typename _Tolerance = Tolerance >
+ class ResBackwardFilter {
+ public:
+
+ typedef _Digraph Digraph;
+ typedef _CapacityMap CapacityMap;
+ typedef _FlowMap FlowMap;
+ typedef _Tolerance Tolerance;
+
+ typedef typename Digraph::Arc Key;
+ typedef bool Value;
+
+ private:
+
+ const CapacityMap* _capacity;
+ const FlowMap* _flow;
+ Tolerance _tolerance;
+
+ public:
+
+ ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,
+ const Tolerance& tolerance = Tolerance())
+ : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
+
+ bool operator[](const typename Digraph::Arc& a) const {
+ return _tolerance.positive((*_flow)[a]);
+ }
+ };
+
+ }
+
+ /// \ingroup graph_adaptors
+ ///
+ /// \brief An adaptor for composing the residual graph for directed
+ /// flow and circulation problems.
+ ///
+ /// An adaptor for composing the residual graph for directed flow and
+ /// circulation problems. Let \f$ G=(V, A) \f$ be a directed graph
+ /// and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
+ /// be functions on the arc-set.
+ ///
+ /// Then Residual implements the digraph structure with
+ /// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward} \f$,
+ /// where \f$ A_{forward}=\{uv : uv\in A, f(uv)0\} \f$, i.e. the so
+ /// called residual graph. When we take the union
+ /// \f$ A_{forward}\cup A_{backward} \f$, multiplicities are counted,
+ /// i.e. if an arc is in both \f$ A_{forward} \f$ and
+ /// \f$ A_{backward} \f$, then in the adaptor it appears in both
+ /// orientation.
+ ///
+ /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
+ /// "Digraph concept". The type is implicitly const.
+ /// \tparam _CapacityMap An arc map of some numeric type, it defines
+ /// the capacities in the flow problem. The map is implicitly const.
+ /// \tparam _FlowMap An arc map of some numeric type, it defines
+ /// the capacities in the flow problem.
+ /// \tparam _Tolerance Handler for inexact computation.
+ template,
+ typename _FlowMap = _CapacityMap,
+ typename _Tolerance = Tolerance