LEMON/LEMON-main Changeset - r416:76287c8caa26

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r416:76287c8caa26

« 415:4b6112

417:6ff53a »

r416:76287c8caa26

Sun, 30 Nov 2008 19:18:32

[Not Reviewed]

0 comments (0 inline)

deba@inf.elte.hu
deba@inf.elte.hu

Reorganication of graph adaptors and doc improvements (#67) - Moving to one file, lemon/adaptors.h - Renamings - Doc cleanings

2 5 1

default

8 files changed with 1505 insertions and 1836 deletions:

doc/groups.dox

lemon/Makefile.am

lemon/adaptors.h

1378

578

lemon/bits/graph_adaptor_extender.h

lemon/bits/variant.h

test/graph_adaptor_test.cc

lemon/graph_adaptor.h

1164

↑ Collapse diff ↑

doc/groups.dox

Show inline comments

@@ -60,6 +60,79 @@
 		*/
 		/**
 		@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 <typename Digraph>
 		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<typename Digraph> class ReverseDigraph;
 		\endcode
 		template class can be used. The code looks as follows
 		\code
 		ListDigraph g;
 		ReverseDigraph<ListGraph> 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 <tt>const ListDigraph&</tt>
 		reference to a graph is given, then it have to be instantiated with
 		<tt>Digraph=const ListDigraph</tt>.
 		\code
 		int algorithm1(const ListDigraph& g) {
 		  RevGraphAdaptor<const ListDigraph> rg(g);
 		  return algorithm2(rg);
+		}
 		\endcode
 		*/
 		/**
 		@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
 		@ingroup graphs
 		\brief Graph types between real graphs and graph adaptors.

lemon/Makefile.am

Show inline comments

@@ -16,6 +16,7 @@
 		#lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
 		lemon_HEADERS += \
 			lemon/adaptors.h \
 		        lemon/arg_parser.h \
 			lemon/assert.h \
 		        lemon/bfs.h \

lemon/adaptors.h

Show inline comments

 		/* -*- C++ -*-
+		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
@@ -16,22 +16,20 @@
+		 *
 		 */
 		#ifndef LEMON_DIGRAPH_ADAPTOR_H
 		#define LEMON_DIGRAPH_ADAPTOR_H
 		#ifndef LEMON_ADAPTORS_H
 		#define LEMON_ADAPTORS_H
 		///\ingroup graph_adaptors
 		///\file
-		///\brief Several digraph adaptors.
+		/// \brief Several graph adaptors
 		///
-		///This file contains several useful digraph adaptor classes.
+		/// This file contains several useful adaptors for digraphs and graphs.
 		#include <lemon/core.h>
 		#include <lemon/maps.h>
 		#include <lemon/bits/variant.h>
 		#include <lemon/bits/base_extender.h>
 		#include <lemon/bits/graph_adaptor_extender.h>
 		#include <lemon/bits/graph_extender.h>
 		#include <lemon/tolerance.h>
 		#include <algorithm>
@@ -155,14 +153,168 @@
 		  };
 		  template<typename _Graph>
 		  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<Graph> NodeNumTag;
 		    int nodeNum() const { return _graph->nodeNum(); }
 		    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
 		    int arcNum() const { return _graph->arcNum(); }
 		    int edgeNum() const { return _graph->edgeNum(); }
 		    typedef FindEdgeTagIndicator<Graph> 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<Graph, Node>::ItemNotifier NodeNotifier;
 		    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
 		    typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
 		    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
 		    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
 		    EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
 		    template <typename _Value>
 		    class NodeMap : public Graph::template NodeMap<_Value> {
 		    public:
 		      typedef typename Graph::template NodeMap<_Value> Parent;
 		      explicit NodeMap(const GraphAdaptorBase<Graph>& adapter)
 		        : Parent(*adapter._graph) {}
 		      NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
 		        : Parent(*adapter._graph, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class ArcMap : public Graph::template ArcMap<_Value> {
 		    public:
 		      typedef typename Graph::template ArcMap<_Value> Parent;
 		      explicit ArcMap(const GraphAdaptorBase<Graph>& adapter)
 		        : Parent(*adapter._graph) {}
 		      ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
 		        : Parent(*adapter._graph, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class EdgeMap : public Graph::template EdgeMap<_Value> {
 		    public:
 		      typedef typename Graph::template EdgeMap<_Value> Parent;
 		      explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)
 		        : Parent(*adapter._graph) {}
 		      EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
 		        : Parent(*adapter._graph, value) {}
 		    private:
 		      EdgeMap& operator=(const EdgeMap& cmap) {
 		        return operator=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  template <typename _Digraph>
-		  class RevDigraphAdaptorBase : public DigraphAdaptorBase<_Digraph> {
+		  class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef DigraphAdaptorBase<_Digraph> Parent;
 		  protected:
-		    RevDigraphAdaptorBase() : Parent() { }
+		    ReverseDigraphBase() : Parent() { }
 		  public:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
@@ -176,6 +328,8 @@
 		    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<Digraph> FindEdgeTag;
 		    Arc findArc(const Node& u, const Node& v,
 				const Arc& prev = INVALID) {
@@ -184,69 +338,31 @@
 		  };
 		  ///\ingroup graph_adaptors
 		  ///
 		  ///\brief A digraph adaptor which reverses the orientation of the arcs.
 		  ///
 		  /// If \c g is defined as
 		  ///\code
 		  /// ListDigraph dg;
 		  ///\endcode
 		  /// then
 		  ///\code
 		  /// RevDigraphAdaptor<ListDigraph> dga(dg);
 		  ///\endcode
 		  /// implements the digraph obtained from \c dg by
 		  /// reversing the orientation of its arcs.
 		  /// ReverseDigraph reverses the arcs in the adapted digraph. The
 		  /// SubDigraph is conform to the \ref concepts::Digraph
 		  /// "Digraph concept".
 		  ///
 		  /// A good example of using RevDigraphAdaptor is to decide whether
 		  /// the directed graph is strongly connected or not. The digraph is
 		  /// strongly connected iff each node is reachable from one node and
 		  /// this node is reachable from the others. Instead of this
 		  /// condition we use a slightly different, from one node each node
 		  /// is reachable both in the digraph and the reversed digraph. Now
 		  /// this condition can be checked with the Dfs algorithm and the
 		  /// RevDigraphAdaptor class.
 		  ///
 		  /// The implementation:
 		  ///\code
 		  /// bool stronglyConnected(const Digraph& digraph) {
 		  ///   if (NodeIt(digraph) == INVALID) return true;
 		  ///   Dfs<Digraph> dfs(digraph);
 		  ///   dfs.run(NodeIt(digraph));
 		  ///   for (NodeIt it(digraph); it != INVALID; ++it) {
 		  ///     if (!dfs.reached(it)) {
 		  ///       return false;
 		  ///     }
 		  ///   }
 		  ///   typedef RevDigraphAdaptor<const Digraph> RDigraph;
 		  ///   RDigraph rdigraph(digraph);
 		  ///   DfsVisit<RDigraph> rdfs(rdigraph);
 		  ///   rdfs.run(NodeIt(digraph));
 		  ///   for (NodeIt it(digraph); it != INVALID; ++it) {
 		  ///     if (!rdfs.reached(it)) {
 		  ///       return false;
 		  ///     }
 		  ///   }
 		  ///   return true;
 		  /// }
 		  ///\endcode
 		  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
 		  /// "Digraph concept". The type can be specified to be const.
 		  template<typename _Digraph>
 		  class RevDigraphAdaptor :
 		    public DigraphAdaptorExtender<RevDigraphAdaptorBase<_Digraph> > {
 		  class ReverseDigraph :
 		    public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef DigraphAdaptorExtender<
-		      RevDigraphAdaptorBase<_Digraph> > Parent;
+		      ReverseDigraphBase<_Digraph> > Parent;
 		  protected:
-		    RevDigraphAdaptor() { }
+		    ReverseDigraph() { }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a reverse graph adaptor for the given digraph
 		    explicit RevDigraphAdaptor(Digraph& digraph) {
 		    /// Creates a reverse digraph adaptor for the given digraph
 		    explicit ReverseDigraph(Digraph& digraph) {
 		      Parent::setDigraph(digraph);
+		    }
 		  };
@@ -255,25 +371,24 @@
 		  ///
 		  /// Just gives back a reverse digraph adaptor
 		  template<typename Digraph>
 		  RevDigraphAdaptor<const Digraph>
 		  revDigraphAdaptor(const Digraph& digraph) {
-		    return RevDigraphAdaptor<const Digraph>(digraph);
+		  ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) {
 		    return ReverseDigraph<const Digraph>(digraph);
+		  }
 		  template <typename _Digraph, typename _NodeFilterMap,
 			    typename _ArcFilterMap, bool checked = true>
 		  class SubDigraphAdaptorBase : public DigraphAdaptorBase<_Digraph> {
 		            typename _ArcFilterMap, bool _checked = true>
 		  class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef _NodeFilterMap NodeFilterMap;
 		    typedef _ArcFilterMap ArcFilterMap;
-		    typedef SubDigraphAdaptorBase Adaptor;
+		    typedef SubDigraphBase Adaptor;
 		    typedef DigraphAdaptorBase<_Digraph> Parent;
 		  protected:
 		    NodeFilterMap* _node_filter;
 		    ArcFilterMap* _arc_filter;
-		    SubDigraphAdaptorBase()
+		    SubDigraphBase()
 		      : Parent(), _node_filter(0), _arc_filter(0) { }
 		    void setNodeFilterMap(NodeFilterMap& node_filter) {
@@ -297,19 +412,22 @@
 		      Parent::first(i);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 			     || !(*_node_filter)[Parent::source(i)]
-			     || !(*_node_filter)[Parent::target(i)])) Parent::next(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);
+		                              || !(*_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);
+		                              || !(*_node_filter)[Parent::target(i)]))
 		        Parent::nextOut(i);
+		    }
 		    void next(Node& i) const {
@@ -321,19 +439,22 @@
 		      Parent::next(i);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 			     || !(*_node_filter)[Parent::source(i)]
-			     || !(*_node_filter)[Parent::target(i)])) Parent::next(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);
+		                              || !(*_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);
+		                              || !(*_node_filter)[Parent::target(i)]))
 		        Parent::nextOut(i);
+		    }
 		    void hide(const Node& n) const { _node_filter->set(n, false); }
@@ -414,19 +535,19 @@
 		  };
 		  template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>
-		  class SubDigraphAdaptorBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>
+		  class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>
 		    : public DigraphAdaptorBase<_Digraph> {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef _NodeFilterMap NodeFilterMap;
 		    typedef _ArcFilterMap ArcFilterMap;
-		    typedef SubDigraphAdaptorBase Adaptor;
+		    typedef SubDigraphBase Adaptor;
 		    typedef DigraphAdaptorBase<Digraph> Parent;
 		  protected:
 		    NodeFilterMap* _node_filter;
 		    ArcFilterMap* _arc_filter;
-		    SubDigraphAdaptorBase()
+		    SubDigraphBase()
 		      : Parent(), _node_filter(0), _arc_filter(0) { }
 		    void setNodeFilterMap(NodeFilterMap& node_filter) {
@@ -558,74 +679,55 @@
 		  /// \ingroup graph_adaptors
 		  ///
-		  /// \brief A digraph adaptor for hiding nodes and arcs from a digraph.
+		  /// \brief An adaptor for hiding nodes and arcs in a digraph
 		  ///
 		  /// SubDigraphAdaptor shows the digraph with filtered node-set and
 		  /// arc-set. If the \c checked parameter is true then it filters the arc-set
-		  /// respect to the source and target.
+		  /// 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.
 		  ///
 		  /// If the \c checked template parameter is false then the
 		  /// node-iterator cares only the filter on the node-set, and the
 		  /// arc-iterator cares only the filter on the arc-set.  Therefore
 		  /// the arc-map have to filter all arcs which's source or target is
 		  /// filtered by the node-filter.
 		  ///\code
 		  /// typedef ListDigraph Digraph;
 		  /// DIGRAPH_TYPEDEFS(Digraph);
 		  /// Digraph g;
 		  /// Node u=g.addNode(); //node of id 0
 		  /// Node v=g.addNode(); //node of id 1
 		  /// Arc a=g.addArc(u, v); //arc of id 0
 		  /// Arc f=g.addArc(v, u); //arc of id 1
 		  /// BoolNodeMap nm(g, true);
 		  /// nm.set(u, false);
 		  /// BoolArcMap am(g, true);
 		  /// am.set(a, false);
 		  /// typedef SubDigraphAdaptor<Digraph, BoolNodeMap, BoolArcMap> SubDGA;
 		  /// SubDGA ga(g, nm, am);
 		  /// for (SubDGA::NodeIt n(ga); n!=INVALID; ++n)
 		  ///   std::cout << g.id(n) << std::endl;
 		  /// for (SubDGA::ArcIt a(ga); a!=INVALID; ++a)
 		  ///   std::cout << g.id(a) << std::endl;
 		  ///\endcode
 		  /// The output of the above code is the following.
 		  ///\code
 		  /// 1
 		  /// 1
 		  ///\endcode
 		  /// Note that \c n is of type \c SubDGA::NodeIt, but it can be converted to
-		  /// \c Digraph::Node that is why \c g.id(n) can be applied.
+		  /// \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.
 		  ///
 		  /// For other examples see also the documentation of
 		  /// NodeSubDigraphAdaptor and ArcSubDigraphAdaptor.
 		  /// \see FilterNodes
 		  /// \see FilterArcs
 		  template<typename _Digraph,
 			   typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
 			   typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,
 			   bool checked = true>
 		  class SubDigraphAdaptor :
 		    public DigraphAdaptorExtender<
 		    SubDigraphAdaptorBase<_Digraph, _NodeFilterMap, _ArcFilterMap, checked> > {
 		           bool _checked = true>
 		  class SubDigraph
 		    : public DigraphAdaptorExtender<
 		      SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef _NodeFilterMap NodeFilterMap;
 		    typedef _ArcFilterMap ArcFilterMap;
 		    typedef DigraphAdaptorExtender<
-		      SubDigraphAdaptorBase<Digraph, NodeFilterMap, ArcFilterMap, checked> >
+		      SubDigraphBase<Digraph, NodeFilterMap, ArcFilterMap, _checked> >
 		    Parent;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		  protected:
-		    SubDigraphAdaptor() { }
+		    SubDigraph() { }
 		  public:
 		    /// \brief Constructor
 		    ///
-		    /// Creates a sub-digraph-adaptor for the given digraph with
+		    /// Creates a subdigraph for the given digraph with
 		    /// given node and arc map filters.
-		    SubDigraphAdaptor(Digraph& digraph, NodeFilterMap& node_filter,
+		    SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,
 				      ArcFilterMap& arc_filter) {
 		      setDigraph(digraph);
 		      setNodeFilterMap(node_filter);
@@ -674,97 +776,525 @@
 		  };
-		  /// \brief Just gives back a sub-digraph-adaptor
+		  /// \brief Just gives back a subdigraph
 		  ///
-		  /// Just gives back a sub-digraph-adaptor
+		  /// Just gives back a subdigraph
 		  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
 		  SubDigraphAdaptor<const Digraph, NodeFilterMap, ArcFilterMap>
 		  subDigraphAdaptor(const Digraph& digraph,
 				    NodeFilterMap& nfm, ArcFilterMap& afm) {
 		    return SubDigraphAdaptor<const Digraph, NodeFilterMap, ArcFilterMap>
 		  SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
 		  subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) {
 		    return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
 		      (digraph, nfm, afm);
+		  }
 		  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
 		  SubDigraphAdaptor<const Digraph, const NodeFilterMap, ArcFilterMap>
 		  subDigraphAdaptor(const Digraph& digraph,
 		                   NodeFilterMap& nfm, ArcFilterMap& afm) {
 		    return SubDigraphAdaptor<const Digraph, const NodeFilterMap, ArcFilterMap>
 		  SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
 		  subDigraph(const Digraph& digraph,
 		             const NodeFilterMap& nfm, ArcFilterMap& afm) {
 		    return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
 		      (digraph, nfm, afm);
+		  }
 		  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
 		  SubDigraphAdaptor<const Digraph, NodeFilterMap, const ArcFilterMap>
 		  subDigraphAdaptor(const Digraph& digraph,
 		                   NodeFilterMap& nfm, ArcFilterMap& afm) {
 		    return SubDigraphAdaptor<const Digraph, NodeFilterMap, const ArcFilterMap>
 		  SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
 		  subDigraph(const Digraph& digraph,
 		             NodeFilterMap& nfm, const ArcFilterMap& afm) {
 		    return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
 		      (digraph, nfm, afm);
+		  }
 		  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
 		  SubDigraphAdaptor<const Digraph, const NodeFilterMap, const ArcFilterMap>
 		  subDigraphAdaptor(const Digraph& digraph,
 		                   NodeFilterMap& nfm, ArcFilterMap& afm) {
 		    return SubDigraphAdaptor<const Digraph, const NodeFilterMap,
 		  SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap>
 		  subDigraph(const Digraph& digraph,
 		             const NodeFilterMap& nfm, const ArcFilterMap& afm) {
 		    return SubDigraph<const Digraph, const NodeFilterMap,
 		      const ArcFilterMap>(digraph, nfm, afm);
+		  }
+		  }
 		  template <typename _Graph, typename NodeFilterMap,
 		            typename EdgeFilterMap, bool _checked = true>
 		  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<Graph> 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 <typename _Value>
 		    class NodeMap : public SubMapExtender<Adaptor,
 		      typename Parent::template NodeMap<_Value> > {
 		    public:
 		      typedef _Value Value;
 		      typedef SubMapExtender<Adaptor, typename Parent::
 		                             template NodeMap<Value> > 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=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        MapParent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class ArcMap : public SubMapExtender<Adaptor,
 		      typename Parent::template ArcMap<_Value> > {
 		    public:
 		      typedef _Value Value;
 		      typedef SubMapExtender<Adaptor, typename Parent::
 		                             template ArcMap<Value> > 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=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        MapParent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class EdgeMap : public SubMapExtender<Adaptor,
 		      typename Parent::template EdgeMap<_Value> > {
 		    public:
 		      typedef _Value Value;
 		      typedef SubMapExtender<Adaptor, typename Parent::
 		                             template EdgeMap<Value> > 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=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        MapParent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
 		  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<Graph> 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 <typename _Value>
 		    class NodeMap : public SubMapExtender<Adaptor,
 		      typename Parent::template NodeMap<_Value> > {
 		    public:
 		      typedef _Value Value;
 		      typedef SubMapExtender<Adaptor, typename Parent::
 		                             template NodeMap<Value> > 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=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        MapParent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class ArcMap : public SubMapExtender<Adaptor,
 		      typename Parent::template ArcMap<_Value> > {
 		    public:
 		      typedef _Value Value;
 		      typedef SubMapExtender<Adaptor, typename Parent::
 		                             template ArcMap<Value> > 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=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        MapParent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class EdgeMap : public SubMapExtender<Adaptor,
 		      typename Parent::template EdgeMap<_Value> > {
 		    public:
 		      typedef _Value Value;
 		      typedef SubMapExtender<Adaptor, typename Parent::
 		                             template EdgeMap<Value> > 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=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        MapParent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  ///\ingroup graph_adaptors
 		  ///
-		  ///\brief An adaptor for hiding nodes from a digraph.
+		  /// \brief A graph adaptor for hiding nodes and edges in an
 		  /// undirected graph.
 		  ///
 		  ///An adaptor for hiding nodes from a digraph.  This adaptor
 		  ///specializes SubDigraphAdaptor in the way that only the node-set
 		  ///can be filtered. In usual case the checked parameter is true, we
 		  ///get the induced subgraph. But if the checked parameter is false
 		  ///then we can filter only isolated nodes.
 		  template<typename _Digraph,
 			   typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
 			   bool checked = true>
 		  class NodeSubDigraphAdaptor :
 		    public SubDigraphAdaptor<_Digraph, _NodeFilterMap,
-					     ConstMap<typename _Digraph::Arc, bool>, checked> {
+		  /// 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<typename _Graph, typename NodeFilterMap,
 		           typename EdgeFilterMap, bool _checked = true>
 		  class SubGraph
 		    : public GraphAdaptorExtender<
 		      SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, _checked> > {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef _NodeFilterMap NodeFilterMap;
 		    typedef SubDigraphAdaptor<Digraph, NodeFilterMap,
 					      ConstMap<typename Digraph::Arc, bool>, checked>
-		    Parent;
+		    typedef _Graph Graph;
 		    typedef GraphAdaptorExtender<
 		      SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Edge Edge;
 		  protected:
 		    ConstMap<typename Digraph::Arc, bool> const_true_map;
 		    NodeSubDigraphAdaptor() : const_true_map(true) {
 		      Parent::setArcFilterMap(const_true_map);
+		    }
 		    SubGraph() { }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a node-sub-digraph-adaptor for the given digraph with
 		    /// given node map filter.
 		    NodeSubDigraphAdaptor(Digraph& _digraph, NodeFilterMap& node_filter) :
 		      Parent(), const_true_map(true) {
 		      Parent::setDigraph(_digraph);
 		      Parent::setNodeFilterMap(node_filter);
-		      Parent::setArcFilterMap(const_true_map);
+		    /// 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 digraph, i.e. the iteration
+		    /// 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
@@ -772,168 +1302,219 @@
 		    /// 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  node-sub-digraph adaptor
 		  /// \brief Just gives back a subgraph
 		  ///
-		  /// Just gives back a node-sub-digraph adaptor
+		  /// Just gives back a subgraph
 		  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
 		  SubGraph<const Graph, NodeFilterMap, ArcFilterMap>
 		  subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) {
 		    return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm);
+		  }
 		  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
 		  SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
 		  subGraph(const Graph& graph,
 		           const NodeFilterMap& nfm, ArcFilterMap& efm) {
 		    return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
 		      (graph, nfm, efm);
+		  }
 		  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
 		  SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
 		  subGraph(const Graph& graph,
 		           NodeFilterMap& nfm, const ArcFilterMap& efm) {
 		    return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
 		      (graph, nfm, efm);
+		  }
 		  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
 		  SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
 		  subGraph(const Graph& graph,
 		           const NodeFilterMap& nfm, const ArcFilterMap& efm) {
 		    return SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
 		      (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<typename _Digraph,
 		           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
 		           bool _checked = true>
 		#else
 		  template<typename _Digraph,
 		           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
 		           bool _checked = true,
 		           typename Enable = void>
 		#endif
 		  class FilterNodes
 		    : public SubDigraph<_Digraph, _NodeFilterMap,
 		                        ConstMap<typename _Digraph::Arc, bool>, _checked> {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef _NodeFilterMap NodeFilterMap;
 		    typedef SubDigraph<Digraph, NodeFilterMap,
 		                       ConstMap<typename Digraph::Arc, bool>, _checked>
 		    Parent;
 		    typedef typename Parent::Node Node;
 		  protected:
 		    ConstMap<typename Digraph::Arc, bool> 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<typename _Graph, typename _NodeFilterMap, bool _checked>
 		  class FilterNodes<_Graph, _NodeFilterMap, _checked,
 		                    typename enable_if<UndirectedTagIndicator<_Graph> >::type>
 		    : public SubGraph<_Graph, _NodeFilterMap,
 		                      ConstMap<typename _Graph::Edge, bool>, _checked> {
 		  public:
 		    typedef _Graph Graph;
 		    typedef _NodeFilterMap NodeFilterMap;
 		    typedef SubGraph<Graph, NodeFilterMap,
 		                     ConstMap<typename Graph::Edge, bool> > Parent;
 		    typedef typename Parent::Node Node;
 		  protected:
 		    ConstMap<typename Graph::Edge, bool> 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<typename Digraph, typename NodeFilterMap>
 		  NodeSubDigraphAdaptor<const Digraph, NodeFilterMap>
 		  nodeSubDigraphAdaptor(const Digraph& digraph, NodeFilterMap& nfm) {
-		    return NodeSubDigraphAdaptor<const Digraph, NodeFilterMap>(digraph, nfm);
+		  FilterNodes<const Digraph, NodeFilterMap>
 		  filterNodes(const Digraph& digraph, NodeFilterMap& nfm) {
 		    return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm);
+		  }
 		  template<typename Digraph, typename NodeFilterMap>
 		  NodeSubDigraphAdaptor<const Digraph, const NodeFilterMap>
 		  nodeSubDigraphAdaptor(const Digraph& digraph, const NodeFilterMap& nfm) {
 		    return NodeSubDigraphAdaptor<const Digraph, const NodeFilterMap>
 		      (digraph, nfm);
 		  FilterNodes<const Digraph, const NodeFilterMap>
 		  filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) {
 		    return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm);
+		  }
 		  ///\ingroup graph_adaptors
 		  ///
 		  ///\brief An adaptor for hiding arcs from a digraph.
 		  ///
 		  ///An adaptor for hiding arcs from a digraph. This adaptor
 		  ///specializes SubDigraphAdaptor in the way that only the arc-set
 		  ///can be filtered. The usefulness of this adaptor is demonstrated
 		  ///in the problem of searching a maximum number of arc-disjoint
 		  ///shortest paths between two nodes \c s and \c t. Shortest here
 		  ///means being shortest with respect to non-negative
 		  ///arc-lengths. Note that the comprehension of the presented
 		  ///solution need's some elementary knowledge from combinatorial
-		  ///optimization.
+		  /// 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".
 		  ///
 		  ///If a single shortest path is to be searched between \c s and \c
 		  ///t, then this can be done easily by applying the Dijkstra
 		  ///algorithm. What happens, if a maximum number of arc-disjoint
 		  ///shortest paths is to be computed. It can be proved that an arc
 		  ///can be in a shortest path if and only if it is tight with respect
 		  ///to the potential function computed by Dijkstra.  Moreover, any
 		  ///path containing only such arcs is a shortest one.  Thus we have
 		  ///to compute a maximum number of arc-disjoint paths between \c s
 		  ///and \c t in the digraph which has arc-set all the tight arcs. The
 		  ///computation will be demonstrated on the following digraph, which
 		  ///is read from the dimacs file \c sub_digraph_adaptor_demo.dim.
 		  ///The full source code is available in \ref
 		  ///sub_digraph_adaptor_demo.cc.  If you are interested in more demo
 		  ///programs, you can use \ref dim_to_dot.cc to generate .dot files
 		  ///from dimacs files.  The .dot file of the following figure was
 		  ///generated by the demo program \ref dim_to_dot.cc.
 		  ///
 		  ///\dot
 		  ///digraph lemon_dot_example {
 		  ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
 		  ///n0 [ label="0 (s)" ];
 		  ///n1 [ label="1" ];
 		  ///n2 [ label="2" ];
 		  ///n3 [ label="3" ];
 		  ///n4 [ label="4" ];
 		  ///n5 [ label="5" ];
 		  ///n6 [ label="6 (t)" ];
 		  ///arc [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
 		  ///n5 ->  n6 [ label="9, length:4" ];
 		  ///n4 ->  n6 [ label="8, length:2" ];
 		  ///n3 ->  n5 [ label="7, length:1" ];
 		  ///n2 ->  n5 [ label="6, length:3" ];
 		  ///n2 ->  n6 [ label="5, length:5" ];
 		  ///n2 ->  n4 [ label="4, length:2" ];
 		  ///n1 ->  n4 [ label="3, length:3" ];
 		  ///n0 ->  n3 [ label="2, length:1" ];
 		  ///n0 ->  n2 [ label="1, length:2" ];
 		  ///n0 ->  n1 [ label="0, length:3" ];
 		  ///}
 		  ///\enddot
 		  ///
 		  ///\code
 		  ///Digraph g;
 		  ///Node s, t;
 		  ///LengthMap length(g);
 		  ///
 		  ///readDimacs(std::cin, g, length, s, t);
 		  ///
 		  ///cout << "arcs with lengths (of form id, source--length->target): " << endl;
 		  ///for(ArcIt e(g); e!=INVALID; ++e)
 		  ///  cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
 		  ///       << length[e] << "->" << g.id(g.target(e)) << endl;
 		  ///
 		  ///cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
 		  ///\endcode
 		  ///Next, the potential function is computed with Dijkstra.
 		  ///\code
 		  ///typedef Dijkstra<Digraph, LengthMap> Dijkstra;
 		  ///Dijkstra dijkstra(g, length);
 		  ///dijkstra.run(s);
 		  ///\endcode
 		  ///Next, we consrtruct a map which filters the arc-set to the tight arcs.
 		  ///\code
 		  ///typedef TightArcFilterMap<Digraph, const Dijkstra::DistMap, LengthMap>
 		  ///  TightArcFilter;
 		  ///TightArcFilter tight_arc_filter(g, dijkstra.distMap(), length);
 		  ///
 		  ///typedef ArcSubDigraphAdaptor<Digraph, TightArcFilter> SubGA;
 		  ///SubGA ga(g, tight_arc_filter);
 		  ///\endcode
 		  ///Then, the maximum nimber of arc-disjoint \c s-\c t paths are computed
 		  ///with a max flow algorithm Preflow.
 		  ///\code
 		  ///ConstMap<Arc, int> const_1_map(1);
 		  ///Digraph::ArcMap<int> flow(g, 0);
 		  ///
 		  ///Preflow<SubGA, ConstMap<Arc, int>, Digraph::ArcMap<int> >
 		  ///  preflow(ga, const_1_map, s, t);
 		  ///preflow.run();
 		  ///\endcode
 		  ///Last, the output is:
 		  ///\code
 		  ///cout << "maximum number of arc-disjoint shortest path: "
 		  ///     << preflow.flowValue() << endl;
 		  ///cout << "arcs of the maximum number of arc-disjoint shortest s-t paths: "
 		  ///     << endl;
 		  ///for(ArcIt e(g); e!=INVALID; ++e)
 		  ///  if (preflow.flow(e))
 		  ///    cout << " " << g.id(g.source(e)) << "--"
 		  ///         << length[e] << "->" << g.id(g.target(e)) << endl;
 		  ///\endcode
 		  ///The program has the following (expected :-)) output:
 		  ///\code
 		  ///arcs with lengths (of form id, source--length->target):
 		  /// 9, 5--4->6
 		  /// 8, 4--2->6
 		  /// 7, 3--1->5
 		  /// 6, 2--3->5
 		  /// 5, 2--5->6
 		  /// 4, 2--2->4
 		  /// 3, 1--3->4
 		  /// 2, 0--1->3
 		  /// 1, 0--2->2
 		  /// 0, 0--3->1
 		  ///s: 0 t: 6
 		  ///maximum number of arc-disjoint shortest path: 2
 		  ///arcs of the maximum number of arc-disjoint shortest s-t paths:
 		  /// 9, 5--4->6
 		  /// 8, 4--2->6
 		  /// 7, 3--1->5
 		  /// 4, 2--2->4
 		  /// 2, 0--1->3
 		  /// 1, 0--2->2
 		  ///\endcode
 		  /// \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<typename _Digraph, typename _ArcFilterMap>
 		  class ArcSubDigraphAdaptor :
 		    public SubDigraphAdaptor<_Digraph, ConstMap<typename _Digraph::Node, bool>,
 		  class FilterArcs :
 		    public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>,
 					     _ArcFilterMap, false> {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef _ArcFilterMap ArcFilterMap;
-		    typedef SubDigraphAdaptor<Digraph, ConstMap<typename Digraph::Node, bool>,
+		    typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>,
 					      ArcFilterMap, false> Parent;
 		    typedef typename Parent::Arc Arc;
@@ -941,7 +1522,7 @@
 		  protected:
 		    ConstMap<typename Digraph::Node, bool> const_true_map;
-		    ArcSubDigraphAdaptor() : const_true_map(true) {
+		    FilterArcs() : const_true_map(true) {
 		      Parent::setNodeFilterMap(const_true_map);
+		    }
@@ -949,9 +1530,9 @@
 		    /// \brief Constructor
 		    ///
-		    /// Creates a arc-sub-digraph-adaptor for the given digraph with
+		    /// Creates a FilterArcs adaptor for the given graph with
 		    /// given arc map filter.
-		    ArcSubDigraphAdaptor(Digraph& digraph, ArcFilterMap& arc_filter)
+		    FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
 		      : Parent(), const_true_map(true) {
 		      Parent::setDigraph(digraph);
 		      Parent::setNodeFilterMap(const_true_map);
@@ -960,9 +1541,9 @@
 		    /// \brief Hides the arc of the graph
 		    ///
-		    /// This function hides \c a in the digraph, i.e. the iteration
+		    /// 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.
+		    /// to be false in the corresponding arc map.
 		    void hide(const Arc& a) const { Parent::hide(a); }
 		    /// \brief Unhides the arc of the graph
@@ -980,27 +1561,106 @@
 		  };
-		  /// \brief Just gives back an arc-sub-digraph adaptor
+		  /// \brief Just gives back an FilterArcs adaptor
 		  ///
-		  /// Just gives back an arc-sub-digraph adaptor
+		  /// Just gives back an FilterArcs adaptor
 		  template<typename Digraph, typename ArcFilterMap>
 		  ArcSubDigraphAdaptor<const Digraph, ArcFilterMap>
 		  arcSubDigraphAdaptor(const Digraph& digraph, ArcFilterMap& afm) {
-		    return ArcSubDigraphAdaptor<const Digraph, ArcFilterMap>(digraph, afm);
+		  FilterArcs<const Digraph, ArcFilterMap>
 		  filterArcs(const Digraph& digraph, ArcFilterMap& afm) {
 		    return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm);
+		  }
 		  template<typename Digraph, typename ArcFilterMap>
 		  ArcSubDigraphAdaptor<const Digraph, const ArcFilterMap>
 		  arcSubDigraphAdaptor(const Digraph& digraph, const ArcFilterMap& afm) {
 		    return ArcSubDigraphAdaptor<const Digraph, const ArcFilterMap>
 		      (digraph, afm);
 		  FilterArcs<const Digraph, const ArcFilterMap>
 		  filterArcs(const Digraph& digraph, const ArcFilterMap& afm) {
 		    return FilterArcs<const Digraph, const ArcFilterMap>(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<typename _Graph, typename _EdgeFilterMap>
 		  class FilterEdges :
 		    public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>,
 		                    _EdgeFilterMap, false> {
 		  public:
 		    typedef _Graph Graph;
 		    typedef _EdgeFilterMap EdgeFilterMap;
 		    typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>,
 		                     EdgeFilterMap, false> Parent;
 		    typedef typename Parent::Edge Edge;
 		  protected:
 		    ConstMap<typename Graph::Node, bool> 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<typename Graph, typename EdgeFilterMap>
 		  FilterEdges<const Graph, EdgeFilterMap>
 		  filterEdges(const Graph& graph, EdgeFilterMap& efm) {
 		    return FilterEdges<const Graph, EdgeFilterMap>(graph, efm);
+		  }
 		  template<typename Graph, typename EdgeFilterMap>
 		  FilterEdges<const Graph, const EdgeFilterMap>
 		  filterEdges(const Graph& graph, const EdgeFilterMap& efm) {
 		    return FilterEdges<const Graph, const EdgeFilterMap>(graph, efm);
+		  }
 		  template <typename _Digraph>
-		  class UndirDigraphAdaptorBase {
+		  class UndirectorBase {
 		  public:
 		    typedef _Digraph Digraph;
-		    typedef UndirDigraphAdaptorBase Adaptor;
+		    typedef UndirectorBase Adaptor;
 		    typedef True UndirectedTag;
@@ -1008,7 +1668,7 @@
 		    typedef typename Digraph::Node Node;
 		    class Arc : public Edge {
-		      friend class UndirDigraphAdaptorBase;
+		      friend class UndirectorBase;
 		    protected:
 		      bool _forward;
@@ -1369,7 +2029,7 @@
 		  protected:
-		    UndirDigraphAdaptorBase() : _digraph(0) {}
+		    UndirectorBase() : _digraph(0) {}
 		    Digraph* _digraph;
@@ -1381,69 +2041,37 @@
 		  ///\ingroup graph_adaptors
 		  ///
-		  /// \brief A graph is made from a directed digraph by an adaptor
+		  /// \brief Undirect the graph
 		  ///
 		  /// This adaptor makes an undirected graph from a directed
 		  /// graph. All arc of the underlying digraph will be showed in the
 		  /// adaptor as an edge. Let's see an informal example about using
-		  /// this adaptor.
+		  /// 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".
 		  ///
 		  /// There is a network of the streets of a town. Of course there are
 		  /// some one-way street in the town hence the network is a directed
 		  /// one. There is a crazy driver who go oppositely in the one-way
 		  /// street without moral sense. Of course he can pass this streets
 		  /// slower than the regular way, in fact his speed is half of the
 		  /// normal speed. How long should he drive to get from a source
 		  /// point to the target? Let see the example code which calculate it:
 		  ///
 		  /// \todo BadCode, SimpleMap does no exists
 		  ///\code
 		  /// typedef UndirDigraphAdaptor<Digraph> Graph;
 		  /// Graph graph(digraph);
 		  ///
 		  /// typedef SimpleMap<LengthMap> FLengthMap;
 		  /// FLengthMap flength(length);
 		  ///
 		  /// typedef ScaleMap<LengthMap> RLengthMap;
 		  /// RLengthMap rlength(length, 2.0);
 		  ///
 		  /// typedef Graph::CombinedArcMap<FLengthMap, RLengthMap > ULengthMap;
 		  /// ULengthMap ulength(flength, rlength);
 		  ///
 		  /// Dijkstra<Graph, ULengthMap> dijkstra(graph, ulength);
 		  /// std::cout << "Driving time : " << dijkstra.run(src, trg) << std::endl;
 		  ///\endcode
 		  ///
 		  /// The combined arc map makes the length map for the undirected
 		  /// graph. It is created from a forward and reverse map. The forward
 		  /// map is created from the original length map with a SimpleMap
 		  /// adaptor which just makes a read-write map from the reference map
 		  /// i.e. it forgets that it can be return reference to values. The
 		  /// reverse map is just the scaled original map with the ScaleMap
 		  /// adaptor. The combination solves that passing the reverse way
 		  /// takes double time than the original. To get the driving time we
-		  /// run the dijkstra algorithm on the graph.
+		  /// \tparam _Digraph It must be conform to the \ref
 		  /// concepts::Digraph "Digraph concept". The type can be specified
 		  /// to const.
 		  template<typename _Digraph>
 		  class UndirDigraphAdaptor
 		    : public GraphAdaptorExtender<UndirDigraphAdaptorBase<_Digraph> > {
 		  class Undirector
 		    : public GraphAdaptorExtender<UndirectorBase<_Digraph> > {
 		  public:
 		    typedef _Digraph Digraph;
-		    typedef GraphAdaptorExtender<UndirDigraphAdaptorBase<Digraph> > Parent;
+		    typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent;
 		  protected:
-		    UndirDigraphAdaptor() { }
+		    Undirector() { }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Constructor
 		    UndirDigraphAdaptor(_Digraph& _digraph) {
-		      setDigraph(_digraph);
+		    /// 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 adaptor.
+		    /// get an arc map on the undirected graph.
 		    template <typename _ForwardMap, typename _BackwardMap>
 		    class CombinedArcMap {
 		    public:
@@ -1459,11 +2087,6 @@
 		      /// \brief Constructor
 		      ///
 		      /// Constructor
 		      CombinedArcMap() : _forward(0), _backward(0) {}
 		      /// \brief Constructor
 		      ///
 		      /// Constructor
 		      CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
 		        : _forward(&forward), _backward(&backward) {}
@@ -1503,20 +2126,6 @@
+		        }
+		      }
 		      /// \brief Sets the forward map
 		      ///
 		      /// Sets the forward map
 		      void setForwardMap(ForwardMap& forward) {
 		        _forward = &forward;
+		      }
 		      /// \brief Sets the backward map
 		      ///
 		      /// Sets the backward map
 		      void setBackwardMap(BackwardMap& backward) {
 		        _backward = &backward;
+		      }
 		    protected:
 		      ForwardMap* _forward;
@@ -1524,16 +2133,275 @@
 		    };
 		    /// \brief Just gives back a combined arc map
 		    ///
 		    /// Just gives back a combined arc map
 		    template <typename ForwardMap, typename BackwardMap>
 		    static CombinedArcMap<ForwardMap, BackwardMap>
 		    combinedArcMap(ForwardMap& forward, BackwardMap& backward) {
 		      return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward);
+		    }
 		    template <typename ForwardMap, typename BackwardMap>
 		    static CombinedArcMap<const ForwardMap, BackwardMap>
 		    combinedArcMap(const ForwardMap& forward, BackwardMap& backward) {
 		      return CombinedArcMap<const ForwardMap,
 		        BackwardMap>(forward, backward);
+		    }
 		    template <typename ForwardMap, typename BackwardMap>
 		    static CombinedArcMap<ForwardMap, const BackwardMap>
 		    combinedArcMap(ForwardMap& forward, const BackwardMap& backward) {
 		      return CombinedArcMap<ForwardMap,
 		        const BackwardMap>(forward, backward);
+		    }
 		    template <typename ForwardMap, typename BackwardMap>
 		    static CombinedArcMap<const ForwardMap, const BackwardMap>
 		    combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) {
 		      return CombinedArcMap<const ForwardMap,
 		        const BackwardMap>(forward, backward);
+		    }
 		  };
-		  /// \brief Just gives back an undir digraph adaptor
+		  /// \brief Just gives back an undirected view of the given digraph
 		  ///
-		  /// Just gives back an undir digraph adaptor
+		  /// Just gives back an undirected view of the given digraph
 		  template<typename Digraph>
 		  UndirDigraphAdaptor<const Digraph>
 		  undirDigraphAdaptor(const Digraph& digraph) {
 		    return UndirDigraphAdaptor<const Digraph>(digraph);
+		  }
 		  Undirector<const Digraph>
 		  undirector(const Digraph& digraph) {
 		    return Undirector<const Digraph>(digraph);
+		  }
 		  template <typename _Graph, typename _DirectionMap>
 		  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<Graph> NodeNumTag;
 		    int nodeNum() const { return _graph->nodeNum(); }
 		    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
 		    int arcNum() const { return _graph->edgeNum(); }
 		    typedef FindEdgeTagIndicator<Graph> 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<Graph, Node>::ItemNotifier NodeNotifier;
 		    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
 		    typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
 		    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
 		    template <typename _Value>
 		    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=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    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=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      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<typename _Graph,
 		           typename DirectionMap = typename _Graph::template EdgeMap<bool> >
 		  class Orienter :
 		    public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > {
 		  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<typename Graph, typename DirectionMap>
 		  Orienter<const Graph, DirectionMap>
 		  orienter(const Graph& graph, DirectionMap& dm) {
 		    return Orienter<const Graph, DirectionMap>(graph, dm);
+		  }
 		  template<typename Graph, typename DirectionMap>
 		  Orienter<const Graph, const DirectionMap>
 		  orienter(const Graph& graph, const DirectionMap& dm) {
 		    return Orienter<const Graph, const DirectionMap>(graph, dm);
+		  }
 		  namespace _adaptor_bits {
 		  template<typename _Digraph,
 			   typename _CapacityMap = typename _Digraph::template ArcMap<int>,
@@ -1561,12 +2429,6 @@
 		                     const Tolerance& tolerance = Tolerance())
 		      : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
 		    ResForwardFilter(const Tolerance& tolerance = Tolerance())
 		      : _capacity(0), _flow(0), _tolerance(tolerance)  { }
 		    void setCapacity(const CapacityMap& capacity) { _capacity = &capacity; }
 		    void setFlow(const FlowMap& flow) { _flow = &flow; }
 		    bool operator[](const typename Digraph::Arc& a) const {
 		      return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
+		    }
@@ -1598,17 +2460,13 @@
 		    ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,
 		                      const Tolerance& tolerance = Tolerance())
 		      : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
 		    ResBackwardFilter(const Tolerance& tolerance = Tolerance())
 		      : _capacity(0), _flow(0), _tolerance(tolerance) { }
 		    void setCapacity(const CapacityMap& capacity) { _capacity = &capacity; }
 		    void setFlow(const FlowMap& flow) { _flow = &flow; }
 		    bool operator[](const typename Digraph::Arc& a) const {
 		      return _tolerance.positive((*_flow)[a]);
+		    }
 		  };
+		  }
 		  ///\ingroup graph_adaptors
 		  ///
@@ -1616,43 +2474,40 @@
 		  ///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 digraph
 		  ///and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F
-		  ///\f$, be functions on the arc-set.
+		  /// 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.
 		  ///
 		  ///In the appications of ResDigraphAdaptor, \f$ f \f$ usually stands
 		  ///for a flow and \f$ c \f$ for a capacity function.  Suppose that a
-		  ///graph instance \c g of type \c ListDigraph implements \f$ G \f$.
+		  /// 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)<c(uv)\} \f$ and
 		  /// \f$ A_{backward}=\{vu : 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.
 		  ///
 		  ///\code
 		  ///  ListDigraph g;
 		  ///\endcode
 		  ///
 		  ///Then ResDigraphAdaptor 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)<c(uv)\} \f$ and
 		  /// \f$ A_{backward}=\{vu : 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$, multilicities 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 twice. The
 		  /// following code shows how such an instance can be constructed.
 		  ///
 		  ///\code
 		  ///  typedef ListDigraph Digraph;
 		  ///  IntArcMap f(g), c(g);
 		  ///  ResDigraphAdaptor<Digraph, int, IntArcMap, IntArcMap> ga(g);
-		  ///\endcode
+		  /// \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 _Digraph,
 			   typename _CapacityMap = typename _Digraph::template ArcMap<int>,
 			   typename _FlowMap = _CapacityMap,
 		           typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
 		  class ResDigraphAdaptor :
 		    public ArcSubDigraphAdaptor<
 		    UndirDigraphAdaptor<const _Digraph>,
 		    typename UndirDigraphAdaptor<const _Digraph>::template CombinedArcMap<
 		      ResForwardFilter<const _Digraph, _CapacityMap, _FlowMap>,
 		      ResBackwardFilter<const _Digraph, _CapacityMap, _FlowMap> > > {
 		  class Residual :
 		    public FilterArcs<
 		    Undirector<const _Digraph>,
 		    typename Undirector<const _Digraph>::template CombinedArcMap<
 		      _adaptor_bits::ResForwardFilter<const _Digraph, _CapacityMap,
 		                                      _FlowMap, _Tolerance>,
 		      _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap,
 		                                       _FlowMap, _Tolerance> > >
+		  {
 		  public:
 		    typedef _Digraph Digraph;
@@ -1661,50 +2516,38 @@
 		    typedef _Tolerance Tolerance;
 		    typedef typename CapacityMap::Value Value;
-		    typedef ResDigraphAdaptor Adaptor;
+		    typedef Residual Adaptor;
 		  protected:
 		    typedef UndirDigraphAdaptor<const Digraph> UndirDigraph;
 		    typedef ResForwardFilter<const Digraph, CapacityMap, FlowMap>
 		    ForwardFilter;
 		    typedef ResBackwardFilter<const Digraph, CapacityMap, FlowMap>
 		    BackwardFilter;
-		    typedef typename UndirDigraph::
+		    typedef Undirector<const Digraph> Undirected;
 		    typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap,
 		                                            FlowMap, Tolerance> ForwardFilter;
 		    typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap,
 		                                             FlowMap, Tolerance> BackwardFilter;
 		    typedef typename Undirected::
 		    template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
-		    typedef ArcSubDigraphAdaptor<UndirDigraph, ArcFilter> Parent;
+		    typedef FilterArcs<Undirected, ArcFilter> Parent;
 		    const CapacityMap* _capacity;
 		    FlowMap* _flow;
-		    UndirDigraph _graph;
+		    Undirected _graph;
 		    ForwardFilter _forward_filter;
 		    BackwardFilter _backward_filter;
 		    ArcFilter _arc_filter;
 		    void setCapacityMap(const CapacityMap& capacity) {
 		      _capacity = &capacity;
 		      _forward_filter.setCapacity(capacity);
 		      _backward_filter.setCapacity(capacity);
+		    }
 		    void setFlowMap(FlowMap& flow) {
 		      _flow = &flow;
 		      _forward_filter.setFlow(flow);
 		      _backward_filter.setFlow(flow);
+		    }
 		  public:
 		    /// \brief Constructor of the residual digraph.
 		    ///
-		    /// Constructor of the residual graph. The parameters are the digraph type,
 		    /// Constructor of the residual graph. The parameters are the digraph,
 		    /// the flow map, the capacity map and a tolerance object.
-		    ResDigraphAdaptor(const Digraph& digraph, const CapacityMap& capacity,
+		    Residual(const Digraph& digraph, const CapacityMap& capacity,
 		                    FlowMap& flow, const Tolerance& tolerance = Tolerance())
 		      : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
 		        _forward_filter(capacity, flow, tolerance),
@@ -1720,70 +2563,74 @@
 		    /// \brief Gives back the residual capacity of the arc.
 		    ///
 		    /// Gives back the residual capacity of the arc.
 		    Value rescap(const Arc& arc) const {
 		      if (UndirDigraph::direction(arc)) {
-		        return (*_capacity)[arc] - (*_flow)[arc];
+		    Value residualCapacity(const Arc& a) const {
 		      if (Undirected::direction(a)) {
 		        return (*_capacity)[a] - (*_flow)[a];
 		      } else {
 		        return (*_flow)[arc];
+		      }
+		    }
-		    /// \brief Augment on the given arc in the residual digraph.
+		        return (*_flow)[a];
+		      }
+		    }
 		    /// \brief Augment on the given arc in the residual graph.
 		    ///
-		    /// Augment on the given arc in the residual digraph. It increase
+		    /// Augment on the given arc in the residual graph. It increase
 		    /// or decrease the flow on the original arc depend on the direction
 		    /// of the residual arc.
 		    void augment(const Arc& e, const Value& a) const {
 		      if (UndirDigraph::direction(e)) {
-		        _flow->set(e, (*_flow)[e] + a);
+		    void augment(const Arc& a, const Value& v) const {
 		      if (Undirected::direction(a)) {
 		        _flow->set(a, (*_flow)[a] + v);
 		      } else {
-		        _flow->set(e, (*_flow)[e] - a);
+		        _flow->set(a, (*_flow)[a] - v);
+		      }
+		    }
 		    /// \brief Returns the direction of the arc.
 		    ///
 		    /// Returns true when the arc is same oriented as the original arc.
 		    static bool forward(const Arc& e) {
 		      return UndirDigraph::direction(e);
 		    static bool forward(const Arc& a) {
 		      return Undirected::direction(a);
+		    }
 		    /// \brief Returns the direction of the arc.
 		    ///
 		    /// Returns true when the arc is opposite oriented as the original arc.
 		    static bool backward(const Arc& e) {
 		      return !UndirDigraph::direction(e);
 		    static bool backward(const Arc& a) {
 		      return !Undirected::direction(a);
+		    }
 		    /// \brief Gives back the forward oriented residual arc.
 		    ///
 		    /// Gives back the forward oriented residual arc.
 		    static Arc forward(const typename Digraph::Arc& e) {
 		      return UndirDigraph::direct(e, true);
 		    static Arc forward(const typename Digraph::Arc& a) {
 		      return Undirected::direct(a, true);
+		    }
 		    /// \brief Gives back the backward oriented residual arc.
 		    ///
 		    /// Gives back the backward oriented residual arc.
 		    static Arc backward(const typename Digraph::Arc& e) {
 		      return UndirDigraph::direct(e, false);
 		    static Arc backward(const typename Digraph::Arc& a) {
 		      return Undirected::direct(a, false);
+		    }
 		    /// \brief Residual capacity map.
 		    ///
-		    /// In generic residual digraphs the residual capacity can be obtained
+		    /// In generic residual graph the residual capacity can be obtained
 		    /// as a map.
-		    class ResCap {
+		    class ResidualCapacity {
 		    protected:
 		      const Adaptor* _adaptor;
 		    public:
 		      /// The Key type
 		      typedef Arc Key;
 		      /// The Value type
 		      typedef typename _CapacityMap::Value Value;
 		      ResCap(const Adaptor& adaptor) : _adaptor(&adaptor) {}
 		      Value operator[](const Arc& e) const {
 		        return _adaptor->rescap(e);
 		      /// Constructor
 		      ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}
 		      /// \e
 		      Value operator[](const Arc& a) const {
 		        return _adaptor->residualCapacity(a);
+		      }
 		    };
@@ -1791,12 +2638,12 @@
 		  };
 		  template <typename _Digraph>
-		  class SplitDigraphAdaptorBase {
+		  class SplitNodesBase {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef DigraphAdaptorBase<const _Digraph> Parent;
-		    typedef SplitDigraphAdaptorBase Adaptor;
+		    typedef SplitNodesBase Adaptor;
 		    typedef typename Digraph::Node DigraphNode;
 		    typedef typename Digraph::Arc DigraphArc;
@@ -1812,7 +2659,7 @@
 		  public:
 		    class Node : public DigraphNode {
-		      friend class SplitDigraphAdaptorBase;
+		      friend class SplitNodesBase;
 		      template <typename T> friend class NodeMapBase;
 		    private:
@@ -1840,7 +2687,7 @@
 		    };
 		    class Arc {
-		      friend class SplitDigraphAdaptorBase;
+		      friend class SplitNodesBase;
 		      template <typename T> friend class ArcMapBase;
 		    private:
 		      typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;
@@ -2204,7 +3051,7 @@
 		  protected:
-		    SplitDigraphAdaptorBase() : _digraph(0) {}
+		    SplitNodesBase() : _digraph(0) {}
 		    Digraph* _digraph;
@@ -2216,77 +3063,31 @@
 		  /// \ingroup graph_adaptors
 		  ///
-		  /// \brief Split digraph adaptor class
+		  /// \brief Split the nodes of a directed graph
 		  ///
 		  /// This is an digraph adaptor which splits all node into an in-node
 		  /// and an out-node. Formaly, the adaptor replaces each \f$ u \f$
 		  /// node in the digraph with two node, \f$ u_{in} \f$ node and
 		  /// \f$ u_{out} \f$ node. If there is an \f$ (v, u) \f$ arc in the
 		  /// original digraph the new target of the arc will be \f$ u_{in} \f$ and
 		  /// similarly the source of the original \f$ (u, v) \f$ arc will be
 		  /// \f$ u_{out} \f$.  The adaptor will add for each node in the
 		  /// original digraph an additional arc which will connect
 		  /// The SplitNodes adaptor splits each node into an in-node and an
 		  /// out-node. Formaly, the adaptor replaces each \f$ u \f$ node in
 		  /// the digraph with two nodes(namely node \f$ u_{in} \f$ and node
 		  /// \f$ u_{out} \f$). If there is a \f$ (v, u) \f$ arc in the
 		  /// original digraph the new target of the arc will be \f$ u_{in} \f$
 		  /// and similarly the source of the original \f$ (u, v) \f$ arc
 		  /// will be \f$ u_{out} \f$.  The adaptor will add for each node in
 		  /// the original digraph an additional arc which connects
 		  /// \f$ (u_{in}, u_{out}) \f$.
 		  ///
 		  /// The aim of this class is to run algorithm with node costs if the
 		  /// algorithm can use directly just arc costs. In this case we should use
 		  /// a \c SplitDigraphAdaptor and set the node cost of the digraph to the
 		  /// bind arc in the adapted digraph.
 		  /// a \c SplitNodes and set the node cost of the graph to the
 		  /// bind arc in the adapted graph.
 		  ///
 		  /// For example a maximum flow algorithm can compute how many arc
 		  /// disjoint paths are in the digraph. But we would like to know how
 		  /// many node disjoint paths are in the digraph. First we have to
 		  /// adapt the digraph with the \c SplitDigraphAdaptor. Then run the flow
 		  /// algorithm on the adapted digraph. The bottleneck of the flow will
 		  /// be the bind arcs which bounds the flow with the count of the
 		  /// node disjoint paths.
 		  ///
 		  ///\code
 		  ///
 		  /// typedef SplitDigraphAdaptor<SmartDigraph> SDigraph;
 		  ///
 		  /// SDigraph sdigraph(digraph);
 		  ///
 		  /// typedef ConstMap<SDigraph::Arc, int> SCapacity;
 		  /// SCapacity scapacity(1);
 		  ///
 		  /// SDigraph::ArcMap<int> sflow(sdigraph);
 		  ///
 		  /// Preflow<SDigraph, SCapacity>
 		  ///   spreflow(sdigraph, scapacity,
 		  ///            SDigraph::outNode(source), SDigraph::inNode(target));
 		  ///
 		  /// spreflow.run();
 		  ///
 		  ///\endcode
 		  ///
 		  /// The result of the mamixum flow on the original digraph
 		  /// shows the next figure:
 		  ///
 		  /// \image html arc_disjoint.png
 		  /// \image latex arc_disjoint.eps "Arc disjoint paths" width=\textwidth
 		  ///
 		  /// And the maximum flow on the adapted digraph:
 		  ///
 		  /// \image html node_disjoint.png
 		  /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth
 		  ///
 		  /// The second solution contains just 3 disjoint paths while the first 4.
 		  /// The full code can be found in the \ref disjoint_paths_demo.cc demo file.
 		  ///
 		  /// This digraph adaptor is fully conform to the
 		  /// \ref concepts::Digraph "Digraph" concept and
 		  /// contains some additional member functions and types. The
 		  /// documentation of some member functions may be found just in the
 		  /// SplitDigraphAdaptorBase class.
 		  ///
 		  /// \sa SplitDigraphAdaptorBase
 		  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
 		  /// "Digraph concept". The type can be specified to be const.
 		  template <typename _Digraph>
 		  class SplitDigraphAdaptor
 		    : public DigraphAdaptorExtender<SplitDigraphAdaptorBase<_Digraph> > {
 		  class SplitNodes
 		    : public DigraphAdaptorExtender<SplitNodesBase<_Digraph> > {
 		  public:
 		    typedef _Digraph Digraph;
-		    typedef DigraphAdaptorExtender<SplitDigraphAdaptorBase<Digraph> > Parent;
+		    typedef DigraphAdaptorExtender<SplitNodesBase<Digraph> > Parent;
 		    typedef typename Digraph::Node DigraphNode;
 		    typedef typename Digraph::Arc DigraphArc;
@@ -2297,7 +3098,7 @@
 		    /// \brief Constructor of the adaptor.
 		    ///
 		    /// Constructor of the adaptor.
-		    SplitDigraphAdaptor(Digraph& g) {
+		    SplitNodes(Digraph& g) {
 		      Parent::setDigraph(g);
+		    }
@@ -2415,9 +3216,9 @@
 		    };
-		    /// \brief Just gives back a combined node map.
 		    /// \brief Just gives back a combined node map
 		    ///
-		    /// Just gives back a combined node map.
 		    /// Just gives back a combined node map
 		    template <typename InNodeMap, typename OutNodeMap>
 		    static CombinedNodeMap<InNodeMap, OutNodeMap>
 		    combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
@@ -2443,10 +3244,10 @@
 		        const OutNodeMap>(in_map, out_map);
+		    }
 		    /// \brief ArcMap combined from an original ArcMap and NodeMap
+		    /// \brief ArcMap combined from an original ArcMap and a NodeMap
 		    ///
 		    /// This class adapt an original digraph ArcMap and NodeMap to
 		    /// get an arc map on the adapted digraph.
 		    /// This class adapt an original ArcMap and a NodeMap to get an
 		    /// arc map on the adapted digraph
 		    template <typename DigraphArcMap, typename DigraphNodeMap>
 		    class CombinedArcMap {
 		    public:
@@ -2498,9 +3299,9 @@
 		      DigraphNodeMap& _node_map;
 		    };
-		    /// \brief Just gives back a combined arc map.
 		    /// \brief Just gives back a combined arc map
 		    ///
-		    /// Just gives back a combined arc map.
 		    /// Just gives back a combined arc map
 		    template <typename DigraphArcMap, typename DigraphNodeMap>
 		    static CombinedArcMap<DigraphArcMap, DigraphNodeMap>
 		    combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
@@ -2531,17 +3332,16 @@
 		  };
-		  /// \brief Just gives back a split digraph adaptor
+		  /// \brief Just gives back a node splitter
 		  ///
-		  /// Just gives back a split digraph adaptor
+		  /// Just gives back a node splitter
 		  template<typename Digraph>
 		  SplitDigraphAdaptor<Digraph>
 		  splitDigraphAdaptor(const Digraph& digraph) {
-		    return SplitDigraphAdaptor<Digraph>(digraph);
+		  SplitNodes<Digraph>
 		  splitNodes(const Digraph& digraph) {
 		    return SplitNodes<Digraph>(digraph);
+		  }
 		} //namespace lemon
 		#endif //LEMON_DIGRAPH_ADAPTOR_H
 		#endif //LEMON_ADAPTORS_H

lemon/bits/graph_adaptor_extender.h

Show inline comments

 		/* -*- C++ -*-
+		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
@@ -24,15 +24,8 @@
 		#include <lemon/bits/default_map.h>
 		///\ingroup digraphbits
 		///\file
 		///\brief Extenders for the digraph adaptor types
 		namespace lemon {
 		  /// \ingroup digraphbits
 		  ///
 		  /// \brief Extender for the DigraphAdaptors
 		  template <typename _Digraph>
 		  class DigraphAdaptorExtender : public _Digraph {
 		  public:
@@ -164,30 +157,16 @@
 		    };
 		    /// \brief Base node of the iterator
 		    ///
 		    /// Returns the base node (ie. the source in this case) of the iterator
 		    Node baseNode(const OutArcIt &e) const {
 		      return Parent::source(e);
+		    }
 		    /// \brief Running node of the iterator
 		    ///
 		    /// Returns the running node (ie. the target in this case) of the
 		    /// iterator
 		    Node runningNode(const OutArcIt &e) const {
 		      return Parent::target(e);
+		    }
 		    /// \brief Base node of the iterator
 		    ///
 		    /// Returns the base node (ie. the target in this case) of the iterator
 		    Node baseNode(const InArcIt &e) const {
 		      return Parent::target(e);
+		    }
 		    /// \brief Running node of the iterator
 		    ///
 		    /// Returns the running node (ie. the source in this case) of the
 		    /// iterator
 		    Node runningNode(const InArcIt &e) const {
 		      return Parent::source(e);
+		    }
@@ -395,43 +374,23 @@
+		      }
 		    };
 		    /// \brief Base node of the iterator
 		    ///
 		    /// Returns the base node (ie. the source in this case) of the iterator
 		    Node baseNode(const OutArcIt &a) const {
 		      return Parent::source(a);
+		    }
 		    /// \brief Running node of the iterator
 		    ///
 		    /// Returns the running node (ie. the target in this case) of the
 		    /// iterator
 		    Node runningNode(const OutArcIt &a) const {
 		      return Parent::target(a);
+		    }
 		    /// \brief Base node of the iterator
 		    ///
 		    /// Returns the base node (ie. the target in this case) of the iterator
 		    Node baseNode(const InArcIt &a) const {
 		      return Parent::target(a);
+		    }
 		    /// \brief Running node of the iterator
 		    ///
 		    /// Returns the running node (ie. the source in this case) of the
 		    /// iterator
 		    Node runningNode(const InArcIt &a) const {
 		      return Parent::source(a);
+		    }
 		    /// Base node of the iterator
 		    ///
 		    /// Returns the base node of the iterator
 		    Node baseNode(const IncEdgeIt &e) const {
 		      return e.direction ? Parent::u(e) : Parent::v(e);
+		    }
 		    /// Running node of the iterator
 		    ///
 		    /// Returns the running node of the iterator
 		    Node runningNode(const IncEdgeIt &e) const {
 		      return e.direction ? Parent::v(e) : Parent::u(e);
+		    }

lemon/bits/variant.h

Show inline comments

/* -*- C++ -*-
/* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 * This file is a part of LEMON, a generic C++ optimization library.
 *
 * Copyright (C) 2003-2008
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

test/graph_adaptor_test.cc

Show inline comments

 		/* -*- C++ -*-
+		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
@@ -25,8 +25,7 @@
 		#include<lemon/concepts/digraph.h>
 		#include<lemon/concepts/graph.h>
 		#include<lemon/digraph_adaptor.h>
 		#include<lemon/graph_adaptor.h>
 		#include<lemon/adaptors.h>
 		#include <limits>
 		#include <lemon/bfs.h>
@@ -37,11 +36,11 @@
 		using namespace lemon;
 		void checkRevDigraphAdaptor() {
 		  checkConcept<concepts::Digraph, RevDigraphAdaptor<concepts::Digraph> >();
 		void checkReverseDigraph() {
 		  checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();
 		  typedef ListDigraph Digraph;
-		  typedef RevDigraphAdaptor<Digraph> Adaptor;
+		  typedef ReverseDigraph<Digraph> Adaptor;
 		  Digraph digraph;
 		  Adaptor adaptor(digraph);
@@ -78,16 +77,16 @@
+		  }
+		}
-		void checkSubDigraphAdaptor() {
+		void checkSubDigraph() {
 		  checkConcept<concepts::Digraph,
-		    SubDigraphAdaptor<concepts::Digraph,
+		    SubDigraph<concepts::Digraph,
 		    concepts::Digraph::NodeMap<bool>,
 		    concepts::Digraph::ArcMap<bool> > >();
 		  typedef ListDigraph Digraph;
 		  typedef Digraph::NodeMap<bool> NodeFilter;
 		  typedef Digraph::ArcMap<bool> ArcFilter;
-		  typedef SubDigraphAdaptor<Digraph, NodeFilter, ArcFilter> Adaptor;
+		  typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor;
 		  Digraph digraph;
 		  NodeFilter node_filter(digraph);
@@ -175,14 +174,14 @@
 		  checkGraphArcMap(adaptor);
+		}
-		void checkNodeSubDigraphAdaptor() {
+		void checkFilterNodes1() {
 		  checkConcept<concepts::Digraph,
-		    NodeSubDigraphAdaptor<concepts::Digraph,
+		    FilterNodes<concepts::Digraph,
 		      concepts::Digraph::NodeMap<bool> > >();
 		  typedef ListDigraph Digraph;
 		  typedef Digraph::NodeMap<bool> NodeFilter;
-		  typedef NodeSubDigraphAdaptor<Digraph, NodeFilter> Adaptor;
+		  typedef FilterNodes<Digraph, NodeFilter> Adaptor;
 		  Digraph digraph;
 		  NodeFilter node_filter(digraph);
@@ -247,14 +246,14 @@
 		  checkGraphArcMap(adaptor);
+		}
-		void checkArcSubDigraphAdaptor() {
+		void checkFilterArcs() {
 		  checkConcept<concepts::Digraph,
-		    ArcSubDigraphAdaptor<concepts::Digraph,
+		    FilterArcs<concepts::Digraph,
 		    concepts::Digraph::ArcMap<bool> > >();
 		  typedef ListDigraph Digraph;
 		  typedef Digraph::ArcMap<bool> ArcFilter;
-		  typedef ArcSubDigraphAdaptor<Digraph, ArcFilter> Adaptor;
+		  typedef FilterArcs<Digraph, ArcFilter> Adaptor;
 		  Digraph digraph;
 		  ArcFilter arc_filter(digraph);
@@ -321,11 +320,11 @@
 		  checkGraphArcMap(adaptor);
+		}
 		void checkUndirDigraphAdaptor() {
 		  checkConcept<concepts::Graph, UndirDigraphAdaptor<concepts::Digraph> >();
 		void checkUndirector() {
 		  checkConcept<concepts::Graph, Undirector<concepts::Digraph> >();
 		  typedef ListDigraph Digraph;
-		  typedef UndirDigraphAdaptor<Digraph> Adaptor;
+		  typedef Undirector<Digraph> Adaptor;
 		  Digraph digraph;
 		  Adaptor adaptor(digraph);
@@ -371,15 +370,15 @@
+		}
-		void checkResDigraphAdaptor() {
+		void checkResidual() {
 		  checkConcept<concepts::Digraph,
-		    ResDigraphAdaptor<concepts::Digraph,
+		    Residual<concepts::Digraph,
 		    concepts::Digraph::ArcMap<int>,
 		    concepts::Digraph::ArcMap<int> > >();
 		  typedef ListDigraph Digraph;
 		  typedef Digraph::ArcMap<int> IntArcMap;
-		  typedef ResDigraphAdaptor<Digraph, IntArcMap> Adaptor;
+		  typedef Residual<Digraph, IntArcMap> Adaptor;
 		  Digraph digraph;
 		  IntArcMap capacity(digraph), flow(digraph);
@@ -480,7 +479,8 @@
 		    int min = std::numeric_limits<int>::max();
 		    for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
-		      if (adaptor.rescap(a) < min) min = adaptor.rescap(a);
+		      if (adaptor.residualCapacity(a) < min)
 		        min = adaptor.residualCapacity(a);
+		    }
 		    for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
@@ -493,11 +493,11 @@
+		}
 		void checkSplitDigraphAdaptor() {
 		  checkConcept<concepts::Digraph, SplitDigraphAdaptor<concepts::Digraph> >();
 		void checkSplitNodes() {
 		  checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();
 		  typedef ListDigraph Digraph;
-		  typedef SplitDigraphAdaptor<Digraph> Adaptor;
+		  typedef SplitNodes<Digraph> Adaptor;
 		  Digraph digraph;
 		  Adaptor adaptor(digraph);
@@ -549,16 +549,16 @@
+		  }
+		}
-		void checkSubGraphAdaptor() {
+		void checkSubGraph() {
 		  checkConcept<concepts::Graph,
-		    SubGraphAdaptor<concepts::Graph,
+		    SubGraph<concepts::Graph,
 		    concepts::Graph::NodeMap<bool>,
 		    concepts::Graph::EdgeMap<bool> > >();
 		  typedef ListGraph Graph;
 		  typedef Graph::NodeMap<bool> NodeFilter;
 		  typedef Graph::EdgeMap<bool> EdgeFilter;
-		  typedef SubGraphAdaptor<Graph, NodeFilter, EdgeFilter> Adaptor;
+		  typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor;
 		  Graph graph;
 		  NodeFilter node_filter(graph);
@@ -684,14 +684,14 @@
 		  checkGraphEdgeMap(adaptor);
+		}
-		void checkNodeSubGraphAdaptor() {
+		void checkFilterNodes2() {
 		  checkConcept<concepts::Graph,
-		    NodeSubGraphAdaptor<concepts::Graph,
+		    FilterNodes<concepts::Graph,
 		      concepts::Graph::NodeMap<bool> > >();
 		  typedef ListGraph Graph;
 		  typedef Graph::NodeMap<bool> NodeFilter;
-		  typedef NodeSubGraphAdaptor<Graph, NodeFilter> Adaptor;
+		  typedef FilterNodes<Graph, NodeFilter> Adaptor;
 		  Graph graph;
 		  NodeFilter node_filter(graph);
@@ -783,14 +783,14 @@
 		  checkGraphEdgeMap(adaptor);
+		}
-		void checkEdgeSubGraphAdaptor() {
+		void checkFilterEdges() {
 		  checkConcept<concepts::Graph,
-		    EdgeSubGraphAdaptor<concepts::Graph,
+		    FilterEdges<concepts::Graph,
 		    concepts::Graph::EdgeMap<bool> > >();
 		  typedef ListGraph Graph;
 		  typedef Graph::EdgeMap<bool> EdgeFilter;
-		  typedef EdgeSubGraphAdaptor<Graph, EdgeFilter> Adaptor;
+		  typedef FilterEdges<Graph, EdgeFilter> Adaptor;
 		  Graph graph;
 		  EdgeFilter edge_filter(graph);
@@ -885,13 +885,13 @@
 		  checkGraphEdgeMap(adaptor);
+		}
-		void checkDirGraphAdaptor() {
+		void checkOrienter() {
 		  checkConcept<concepts::Digraph,
-		    DirGraphAdaptor<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();
+		    Orienter<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();
 		  typedef ListGraph Graph;
 		  typedef ListGraph::EdgeMap<bool> DirMap;
-		  typedef DirGraphAdaptor<Graph> Adaptor;
+		  typedef Orienter<Graph> Adaptor;
 		  Graph graph;
 		  DirMap dir(graph, true);
@@ -967,18 +967,18 @@
 		int main(int, const char **) {
 		  checkRevDigraphAdaptor();
 		  checkSubDigraphAdaptor();
 		  checkNodeSubDigraphAdaptor();
 		  checkArcSubDigraphAdaptor();
 		  checkUndirDigraphAdaptor();
 		  checkResDigraphAdaptor();
-		  checkSplitDigraphAdaptor();
+		  checkReverseDigraph();
 		  checkSubDigraph();
 		  checkFilterNodes1();
 		  checkFilterArcs();
 		  checkUndirector();
 		  checkResidual();
 		  checkSplitNodes();
 		  checkSubGraphAdaptor();
 		  checkNodeSubGraphAdaptor();
 		  checkEdgeSubGraphAdaptor();
 		  checkDirGraphAdaptor();
 		  checkSubGraph();
 		  checkFilterNodes2();
 		  checkFilterEdges();
 		  checkOrienter();
 		  return 0;
+		}

lemon/graph_adaptor.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * 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_GRAPH_ADAPTOR_H
 		#define LEMON_GRAPH_ADAPTOR_H
 		///\ingroup graph_adaptors
 		///\file
 		///\brief Several graph adaptors.
 		///
 		///This file contains several useful undirected graph adaptor classes.
 		#include <lemon/core.h>
 		#include <lemon/maps.h>
 		#include <lemon/bits/graph_adaptor_extender.h>
 		namespace lemon {
 		  template<typename _Graph>
 		  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<Graph> NodeNumTag;
 		    int nodeNum() const { return _graph->nodeNum(); }
 		    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
 		    int arcNum() const { return _graph->arcNum(); }
 		    int edgeNum() const { return _graph->edgeNum(); }
 		    typedef FindEdgeTagIndicator<Graph> 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<Graph, Node>::ItemNotifier NodeNotifier;
 		    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
 		    typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
 		    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
 		    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
 		    EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
 		    template <typename _Value>
 		    class NodeMap : public Graph::template NodeMap<_Value> {
 		    public:
 		      typedef typename Graph::template NodeMap<_Value> Parent;
 		      explicit NodeMap(const GraphAdaptorBase<Graph>& adapter)
 			: Parent(*adapter._graph) {}
 		      NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
 			: Parent(*adapter._graph, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 			return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class ArcMap : public Graph::template ArcMap<_Value> {
 		    public:
 		      typedef typename Graph::template ArcMap<_Value> Parent;
 		      explicit ArcMap(const GraphAdaptorBase<Graph>& adapter)
 			: Parent(*adapter._graph) {}
 		      ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
 			: Parent(*adapter._graph, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 			return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 			return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class EdgeMap : public Graph::template EdgeMap<_Value> {
 		    public:
 		      typedef typename Graph::template EdgeMap<_Value> Parent;
 		      explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)
 			: Parent(*adapter._graph) {}
 		      EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
 			: Parent(*adapter._graph, value) {}
 		    private:
 		      EdgeMap& operator=(const EdgeMap& cmap) {
 			return operator=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  template <typename _Graph, typename NodeFilterMap,
 			    typename EdgeFilterMap, bool checked = true>
 		  class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
 		  public:
 		    typedef _Graph Graph;
 		    typedef SubGraphAdaptorBase Adaptor;
 		    typedef GraphAdaptorBase<_Graph> Parent;
 		  protected:
 		    NodeFilterMap* _node_filter_map;
 		    EdgeFilterMap* _edge_filter_map;
 		    SubGraphAdaptorBase()
 		      : 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<Graph> 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 <typename _Value>
 		    class NodeMap : public SubMapExtender<Adaptor,
 		        typename Parent::template NodeMap<_Value> > {
 		    public:
 		      typedef _Value Value;
 		      typedef SubMapExtender<Adaptor, typename Parent::
 		                             template NodeMap<Value> > 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=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        MapParent::operator=(cmap);
 			return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class ArcMap : public SubMapExtender<Adaptor,
 			typename Parent::template ArcMap<_Value> > {
 		    public:
 		      typedef _Value Value;
 		      typedef SubMapExtender<Adaptor, typename Parent::
 		                             template ArcMap<Value> > 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=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        MapParent::operator=(cmap);
 			return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class EdgeMap : public SubMapExtender<Adaptor,
 		        typename Parent::template EdgeMap<_Value> > {
 		    public:
 		      typedef _Value Value;
 		      typedef SubMapExtender<Adaptor, typename Parent::
 		                             template EdgeMap<Value> > 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=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        MapParent::operator=(cmap);
 			return *this;
+		      }
 		    };
 		  };
 		  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
 		  class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
 		    : public GraphAdaptorBase<_Graph> {
 		  public:
 		    typedef _Graph Graph;
 		    typedef SubGraphAdaptorBase Adaptor;
 		    typedef GraphAdaptorBase<_Graph> Parent;
 		  protected:
 		    NodeFilterMap* _node_filter_map;
 		    EdgeFilterMap* _edge_filter_map;
 		    SubGraphAdaptorBase() : 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<Graph> 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 <typename _Value>
 		    class NodeMap : public SubMapExtender<Adaptor,
 		        typename Parent::template NodeMap<_Value> > {
 		    public:
 		      typedef _Value Value;
 		      typedef SubMapExtender<Adaptor, typename Parent::
 		                             template NodeMap<Value> > 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=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        MapParent::operator=(cmap);
 			return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class ArcMap : public SubMapExtender<Adaptor,
 			typename Parent::template ArcMap<_Value> > {
 		    public:
 		      typedef _Value Value;
 		      typedef SubMapExtender<Adaptor, typename Parent::
 		                             template ArcMap<Value> > 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=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        MapParent::operator=(cmap);
 			return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class EdgeMap : public SubMapExtender<Adaptor,
 		        typename Parent::template EdgeMap<_Value> > {
 		    public:
 		      typedef _Value Value;
 		      typedef SubMapExtender<Adaptor, typename Parent::
 		                             template EdgeMap<Value> > 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=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        MapParent::operator=(cmap);
 			return *this;
+		      }
 		    };
 		  };
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief A graph adaptor for hiding nodes and edges from an
 		  /// undirected graph.
 		  ///
 		  /// SubGraphAdaptor shows the graph with filtered node-set and
 		  /// edge-set. If the \c checked parameter is true then it filters
 		  /// the edge-set to do not get invalid edges which incident node is
 		  /// filtered.
 		  ///
 		  /// If the \c checked template parameter is false then we have to
 		  /// note that the node-iterator cares only the filter on the
 		  /// node-set, and the edge-iterator cares only the filter on the
 		  /// edge-set.  This way the edge-map should filter all arcs which
 		  /// has filtered end node.
 		  template<typename _Graph, typename NodeFilterMap,
 			   typename EdgeFilterMap, bool checked = true>
 		  class SubGraphAdaptor :
 		    public GraphAdaptorExtender<
 		    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
 		  public:
 		    typedef _Graph Graph;
 		    typedef GraphAdaptorExtender<
 		      SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Edge Edge;
 		  protected:
 		    SubGraphAdaptor() { }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a sub-graph-adaptor for the given graph with
 		    /// given node and edge map filters.
 		    SubGraphAdaptor(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 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 edge of the graph
 		    ///
 		    /// This function hides \c e in the digraph, 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 sub-graph adaptor
 		  ///
 		  /// Just gives back a sub-graph adaptor
 		  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
 		  SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap>
 		  subGraphAdaptor(const Graph& graph,
 		                   NodeFilterMap& nfm, ArcFilterMap& efm) {
 		    return SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap>
 		      (graph, nfm, efm);
+		  }
 		  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
 		  SubGraphAdaptor<const Graph, const NodeFilterMap, ArcFilterMap>
 		  subGraphAdaptor(const Graph& graph,
 		                   NodeFilterMap& nfm, ArcFilterMap& efm) {
 		    return SubGraphAdaptor<const Graph, const NodeFilterMap, ArcFilterMap>
 		      (graph, nfm, efm);
+		  }
 		  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
 		  SubGraphAdaptor<const Graph, NodeFilterMap, const ArcFilterMap>
 		  subGraphAdaptor(const Graph& graph,
 		                   NodeFilterMap& nfm, ArcFilterMap& efm) {
 		    return SubGraphAdaptor<const Graph, NodeFilterMap, const ArcFilterMap>
 		      (graph, nfm, efm);
+		  }
 		  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
 		  SubGraphAdaptor<const Graph, const NodeFilterMap, const ArcFilterMap>
 		  subGraphAdaptor(const Graph& graph,
 		                   NodeFilterMap& nfm, ArcFilterMap& efm) {
 		    return SubGraphAdaptor<const Graph, const NodeFilterMap,
 		      const ArcFilterMap>(graph, nfm, efm);
+		  }
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief An adaptor for hiding nodes from an graph.
 		  ///
 		  /// An adaptor for hiding nodes from an graph.  This
 		  /// adaptor specializes SubGraphAdaptor in the way that only the
 		  /// node-set can be filtered. In usual case the checked parameter is
 		  /// true, we get the induced subgraph. But if the checked parameter
 		  /// is false then we can filter only isolated nodes.
 		  template<typename _Graph, typename _NodeFilterMap, bool checked = true>
 		  class NodeSubGraphAdaptor :
 		    public SubGraphAdaptor<_Graph, _NodeFilterMap,
 					   ConstMap<typename _Graph::Edge, bool>, checked> {
 		  public:
 		    typedef _Graph Graph;
 		    typedef _NodeFilterMap NodeFilterMap;
 		    typedef SubGraphAdaptor<Graph, NodeFilterMap,
 					    ConstMap<typename Graph::Edge, bool> > Parent;
 		    typedef typename Parent::Node Node;
 		  protected:
 		    ConstMap<typename Graph::Edge, bool> const_true_map;
 		    NodeSubGraphAdaptor() : const_true_map(true) {
 		      Parent::setEdgeFilterMap(const_true_map);
+		    }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a node-sub-graph-adaptor for the given graph with
 		    /// given node map filters.
 		    NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map) :
 		      Parent(), const_true_map(true) {
 		      Parent::setGraph(_graph);
 		      Parent::setNodeFilterMap(node_filter_map);
 		      Parent::setEdgeFilterMap(const_true_map);
+		    }
 		    /// \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 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); }
 		  };
 		  /// \brief Just gives back a node-sub-graph adaptor
 		  ///
 		  /// Just gives back a node-sub-graph adaptor
 		  template<typename Graph, typename NodeFilterMap>
 		  NodeSubGraphAdaptor<const Graph, NodeFilterMap>
 		  nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) {
 		    return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm);
+		  }
 		  template<typename Graph, typename NodeFilterMap>
 		  NodeSubGraphAdaptor<const Graph, const NodeFilterMap>
 		  nodeSubGraphAdaptor(const Graph& graph, const NodeFilterMap& nfm) {
 		    return NodeSubGraphAdaptor<const Graph, const NodeFilterMap>(graph, nfm);
+		  }
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief An adaptor for hiding edges from an graph.
 		  ///
 		  /// \warning Graph adaptors are in even more experimental state
 		  /// than the other parts of the lib. Use them at you own risk.
 		  ///
 		  /// An adaptor for hiding edges from an graph.
 		  /// This adaptor specializes SubGraphAdaptor in the way that
 		  /// only the arc-set
 		  /// can be filtered.
 		  template<typename _Graph, typename _EdgeFilterMap>
 		  class EdgeSubGraphAdaptor :
 		    public SubGraphAdaptor<_Graph, ConstMap<typename _Graph::Node,bool>,
 		                           _EdgeFilterMap, false> {
 		  public:
 		    typedef _Graph Graph;
 		    typedef _EdgeFilterMap EdgeFilterMap;
 		    typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
 					    EdgeFilterMap, false> Parent;
 		    typedef typename Parent::Edge Edge;
 		  protected:
 		    ConstMap<typename Graph::Node, bool> const_true_map;
 		    EdgeSubGraphAdaptor() : const_true_map(true) {
 		      Parent::setNodeFilterMap(const_true_map);
+		    }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a edge-sub-graph-adaptor for the given graph with
 		    /// given node map filters.
 		    EdgeSubGraphAdaptor(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 digraph, 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 an edge-sub-graph adaptor
 		  ///
 		  /// Just gives back an edge-sub-graph adaptor
 		  template<typename Graph, typename EdgeFilterMap>
 		  EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>
 		  edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) {
 		    return EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>(graph, efm);
+		  }
 		  template<typename Graph, typename EdgeFilterMap>
 		  EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>
 		  edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) {
 		    return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm);
+		  }
 		  template <typename _Graph, typename _DirectionMap>
 		  class DirGraphAdaptorBase {
 		  public:
 		    typedef _Graph Graph;
 		    typedef _DirectionMap DirectionMap;
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::Edge Arc;
 		    /// \brief Reverse arc
 		    ///
 		    /// It reverse the given arc. It simply negate the direction in the map.
 		    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<Graph> NodeNumTag;
 		    int nodeNum() const { return _graph->nodeNum(); }
 		    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
 		    int arcNum() const { return _graph->edgeNum(); }
 		    typedef FindEdgeTagIndicator<Graph> 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<Graph, Node>::ItemNotifier NodeNotifier;
 		    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
 		    typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
 		    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
 		    template <typename _Value>
 		    class NodeMap : public _Graph::template NodeMap<_Value> {
 		    public:
 		      typedef typename _Graph::template NodeMap<_Value> Parent;
 		      explicit NodeMap(const DirGraphAdaptorBase& adapter)
 			: Parent(*adapter._graph) {}
 		      NodeMap(const DirGraphAdaptorBase& adapter, const _Value& value)
 			: Parent(*adapter._graph, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class ArcMap : public _Graph::template EdgeMap<_Value> {
 		    public:
 		      typedef typename Graph::template EdgeMap<_Value> Parent;
 		      explicit ArcMap(const DirGraphAdaptorBase& adapter)
 			: Parent(*adapter._graph) { }
 		      ArcMap(const DirGraphAdaptorBase& adapter, const _Value& value)
 			: Parent(*adapter._graph, value) { }
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      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 A directed graph is made from an graph by an adaptor
 		  ///
 		  /// This adaptor gives a direction for each edge in the undirected
 		  /// graph. The direction of the arcs stored in the
 		  /// DirectionMap. This map is a bool map on the edges. If
 		  /// the edge is mapped to true then the direction of the directed
 		  /// arc will be the same as the default direction of the edge. The
 		  /// arcs can be easily reverted by the \ref
 		  /// DirGraphAdaptorBase::reverseArc "reverseArc()" member in the
 		  /// adaptor.
 		  ///
 		  /// It can be used to solve orientation problems on directed graphs.
 		  /// For example how can we orient an graph to get the minimum
 		  /// number of strongly connected components. If we orient the arcs with
 		  /// the dfs algorithm out from the source then we will get such an
 		  /// orientation.
 		  ///
 		  /// We use the \ref DfsVisitor "visitor" interface of the
 		  /// \ref DfsVisit "dfs" algorithm:
 		  ///\code
 		  /// template <typename DirMap>
 		  /// class OrientVisitor : public DfsVisitor<Graph> {
 		  /// public:
 		  ///
 		  ///   OrientVisitor(const Graph& graph, DirMap& dirMap)
 		  ///     : _graph(graph), _dirMap(dirMap), _processed(graph, false) {}
 		  ///
 		  ///   void discover(const Arc& arc) {
 		  ///     _processed.set(arc, true);
 		  ///     _dirMap.set(arc, _graph.direction(arc));
 		  ///   }
 		  ///
 		  ///   void examine(const Arc& arc) {
 		  ///     if (_processed[arc]) return;
 		  ///     _processed.set(arc, true);
 		  ///     _dirMap.set(arc, _graph.direction(arc));
 		  ///   }
 		  ///
 		  /// private:
 		  ///   const Graph& _graph;
 		  ///   DirMap& _dirMap;
 		  ///   Graph::EdgeMap<bool> _processed;
 		  /// };
 		  ///\endcode
 		  ///
 		  /// And now we can use the orientation:
 		  ///\code
 		  /// Graph::EdgeMap<bool> dmap(graph);
 		  ///
 		  /// typedef OrientVisitor<Graph::EdgeMap<bool> > Visitor;
 		  /// Visitor visitor(graph, dmap);
 		  ///
 		  /// DfsVisit<Graph, Visitor> dfs(graph, visitor);
 		  ///
 		  /// dfs.run();
 		  ///
 		  /// typedef DirGraphAdaptor<Graph> DGraph;
 		  /// DGraph dgraph(graph, dmap);
 		  ///
 		  /// LEMON_ASSERT(countStronglyConnectedComponents(dgraph) ==
 		  ///              countBiArcConnectedComponents(graph), "Wrong Orientation");
 		  ///\endcode
 		  ///
 		  /// The number of the bi-connected components is a lower bound for
 		  /// the number of the strongly connected components in the directed
 		  /// graph because if we contract the bi-connected components to
 		  /// nodes we will get a tree therefore we cannot orient arcs in
 		  /// both direction between bi-connected components. In the other way
 		  /// the algorithm will orient one component to be strongly
 		  /// connected. The two relations proof that the assertion will
 		  /// be always true and the found solution is optimal.
 		  ///
 		  /// \sa DirGraphAdaptorBase
 		  /// \sa dirGraphAdaptor
 		  template<typename _Graph,
 		           typename DirectionMap = typename _Graph::template EdgeMap<bool> >
 		  class DirGraphAdaptor :
 		    public DigraphAdaptorExtender<DirGraphAdaptorBase<_Graph, DirectionMap> > {
 		  public:
 		    typedef _Graph Graph;
 		    typedef DigraphAdaptorExtender<
 		      DirGraphAdaptorBase<_Graph, DirectionMap> > Parent;
 		    typedef typename Parent::Arc Arc;
 		  protected:
 		    DirGraphAdaptor() { }
 		  public:
 		    /// \brief Constructor of the adaptor
 		    ///
 		    /// Constructor of the adaptor
 		    DirGraphAdaptor(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 DirGraphAdaptor
 		  ///
 		  /// Just gives back a DirGraphAdaptor
 		  template<typename Graph, typename DirectionMap>
 		  DirGraphAdaptor<const Graph, DirectionMap>
 		  dirGraphAdaptor(const Graph& graph, DirectionMap& dm) {
 		    return DirGraphAdaptor<const Graph, DirectionMap>(graph, dm);
+		  }
 		  template<typename Graph, typename DirectionMap>
 		  DirGraphAdaptor<const Graph, const DirectionMap>
 		  dirGraphAdaptor(const Graph& graph, const DirectionMap& dm) {
 		    return DirGraphAdaptor<const Graph, const DirectionMap>(graph, dm);
+		  }
+		}
 		#endif

0 comments (0 inline)

RhodeCode

Login to your account

1		/* -- C++ --
	1	/* -- mode: C++; indent-tabs-mode: nil; --
2	2	*
3		* This file is a part of LEMON, a generic C++ optimization library
	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5	5	* Copyright (C) 2003-2008
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport