LEMON/LEMON-main Changeset - r415:4b6112235fad

Repositories » LEMON » LEMON-main

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

Changeset - r415:4b6112235fad

« 414:05357d

416:76287c »

r415:4b6112235fad

Sun, 30 Nov 2008 19:00:30

[Not Reviewed]

0 comments (0 inline)

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

Improvements in graph adaptors (#67) Remove DigraphAdaptor and GraphAdaptor Remove docs of base classes Move the member documentations to real adaptors Minor improvements in documentation

0 3 0

default

3 files changed with 325 insertions and 368 deletions:

lemon/digraph_adaptor.h

205

188

lemon/graph_adaptor.h

120

test/graph_adaptor_test.cc

↑ Collapse diff ↑

lemon/digraph_adaptor.h

Show inline comments

@@ -2,74 +2,63 @@
+		 *
 		 * 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_DIGRAPH_ADAPTOR_H
 		#define LEMON_DIGRAPH_ADAPTOR_H
 		///\ingroup graph_adaptors
 		///\file
 		///\brief Several digraph adaptors.
 		///
-		///This file contains several useful digraph adaptor functions.
+		///This file contains several useful digraph adaptor classes.
 		#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>
 		namespace lemon {
 		  ///\brief Base type for the Digraph Adaptors
 		  ///
 		  ///Base type for the Digraph Adaptors
 		  ///
 		  ///This is the base type for most of LEMON digraph adaptors. This
 		  ///class implements a trivial digraph adaptor i.e. it only wraps the
 		  ///functions and types of the digraph. The purpose of this class is
 		  ///to make easier implementing digraph adaptors. E.g. if an adaptor
 		  ///is considered which differs from the wrapped digraph only in some
 		  ///of its functions or types, then it can be derived from
 		  ///DigraphAdaptor, and only the differences should be implemented.
 		  template<typename _Digraph>
 		  class DigraphAdaptorBase {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef DigraphAdaptorBase Adaptor;
 		    typedef Digraph ParentDigraph;
 		  protected:
 		    Digraph* _digraph;
 		    DigraphAdaptorBase() : _digraph(0) { }
 		    void setDigraph(Digraph& digraph) { _digraph = &digraph; }
 		  public:
 		    DigraphAdaptorBase(Digraph& digraph) : _digraph(&digraph) { }
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::Arc Arc;
 		    void first(Node& i) const { _digraph->first(i); }
 		    void first(Arc& i) const { _digraph->first(i); }
 		    void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); }
 		    void firstOut(Arc& i, const Node& n ) const { _digraph->firstOut(i, n); }
 		    void next(Node& i) const { _digraph->next(i); }
@@ -145,166 +134,139 @@
 		      typedef typename Digraph::template ArcMap<_Value> Parent;
 		      explicit ArcMap(const Adaptor& adaptor)
 			: Parent(*adaptor._digraph) {}
 		      ArcMap(const Adaptor& adaptor, const _Value& value)
 			: Parent(*adaptor._digraph, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  ///\ingroup graph_adaptors
 		  ///
 		  ///\brief Trivial Digraph Adaptor
 		  ///
 		  /// This class is an adaptor which does not change the adapted
 		  /// digraph.  It can be used only to test the digraph adaptors.
 		  template <typename _Digraph>
 		  class DigraphAdaptor :
 		    public DigraphAdaptorExtender<DigraphAdaptorBase<_Digraph> > {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef DigraphAdaptorExtender<DigraphAdaptorBase<_Digraph> > Parent;
 		  protected:
 		    DigraphAdaptor() : Parent() { }
 		  public:
 		    explicit DigraphAdaptor(Digraph& digraph) { setDigraph(digraph); }
 		  };
 		  /// \brief Just gives back a digraph adaptor
 		  ///
 		  /// Just gives back a digraph adaptor which
 		  /// should be provide original digraph
 		  template<typename Digraph>
 		  DigraphAdaptor<const Digraph>
 		  digraphAdaptor(const Digraph& digraph) {
 		    return DigraphAdaptor<const Digraph>(digraph);
+		  }
 		  template <typename _Digraph>
 		  class RevDigraphAdaptorBase : public DigraphAdaptorBase<_Digraph> {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef DigraphAdaptorBase<_Digraph> Parent;
 		  protected:
 		    RevDigraphAdaptorBase() : Parent() { }
 		  public:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }
 		    void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); }
 		    void nextIn(Arc& a) const { Parent::nextOut(a); }
 		    void nextOut(Arc& a) const { Parent::nextIn(a); }
 		    Node source(const Arc& a) const { return Parent::target(a); }
 		    Node target(const Arc& a) const { return Parent::source(a); }
 		    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
 		    Arc findArc(const Node& u, const Node& v,
 				const Arc& prev = INVALID) {
 		      return Parent::findArc(v, u, prev);
+		    }
 		  };
 		  ///\ingroup graph_adaptors
 		  ///
 		  ///\brief A digraph adaptor which reverses the orientation of the arcs.
 		  ///
 		  /// If \c g is defined as
 		  ///\code
-		  /// ListDigraph g;
+		  /// ListDigraph dg;
 		  ///\endcode
 		  /// then
 		  ///\code
-		  /// RevDigraphAdaptor<ListDigraph> ga(g);
+		  /// RevDigraphAdaptor<ListDigraph> dga(dg);
 		  ///\endcode
-		  /// implements the digraph obtained from \c g by
+		  /// implements the digraph obtained from \c dg by
 		  /// reversing the orientation of its arcs.
 		  ///
 		  /// A good example of using RevDigraphAdaptor is to decide that the
 		  /// directed graph is wheter strongly connected or not. If from one
 		  /// node each node is reachable and from each node is reachable this
 		  /// node then and just then the digraph is strongly
 		  /// connected. Instead of this condition we use a little bit
 		  /// different. From one node each node ahould be reachable in the
 		  /// digraph and in the reversed digraph. Now this condition can be
 		  /// checked with the Dfs algorithm class and the RevDigraphAdaptor
-		  /// algorithm class.
+		  /// 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.
 		  ///
 		  /// And look at the code:
 		  ///
 		  /// 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
 		  template<typename _Digraph>
 		  class RevDigraphAdaptor :
 		    public DigraphAdaptorExtender<RevDigraphAdaptorBase<_Digraph> > {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef DigraphAdaptorExtender<
 		      RevDigraphAdaptorBase<_Digraph> > Parent;
 		  protected:
 		    RevDigraphAdaptor() { }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a reverse graph adaptor for the given digraph
 		    explicit RevDigraphAdaptor(Digraph& digraph) {
 		      Parent::setDigraph(digraph);
+		    }
 		  };
 		  /// \brief Just gives back a reverse digraph adaptor
 		  ///
 		  /// Just gives back a reverse digraph adaptor
 		  template<typename Digraph>
 		  RevDigraphAdaptor<const Digraph>
 		  revDigraphAdaptor(const Digraph& digraph) {
 		    return RevDigraphAdaptor<const Digraph>(digraph);
+		  }
 		  template <typename _Digraph, typename _NodeFilterMap,
 			    typename _ArcFilterMap, bool checked = true>
 		  class SubDigraphAdaptorBase : public DigraphAdaptorBase<_Digraph> {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef _NodeFilterMap NodeFilterMap;
 		    typedef _ArcFilterMap ArcFilterMap;
 		    typedef SubDigraphAdaptorBase Adaptor;
 		    typedef DigraphAdaptorBase<_Digraph> Parent;
@@ -353,86 +315,55 @@
 		    void next(Node& i) const {
 		      Parent::next(i);
 		      while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
+		    }
 		    void next(Arc& i) const {
 		      Parent::next(i);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 			     || !(*_node_filter)[Parent::source(i)]
 			     || !(*_node_filter)[Parent::target(i)])) Parent::next(i);
+		    }
 		    void nextIn(Arc& i) const {
 		      Parent::nextIn(i);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 			     || !(*_node_filter)[Parent::source(i)])) Parent::nextIn(i);
+		    }
 		    void nextOut(Arc& i) const {
 		      Parent::nextOut(i);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 			     || !(*_node_filter)[Parent::target(i)])) Parent::nextOut(i);
+		    }
 		    ///\e
 		    /// 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 { _node_filter->set(n, false); }
 		    ///\e
 		    /// This function hides \c a in the digraph, i.e. the iteration
 		    /// jumps over it. This is done by simply setting the value of \c a
 		    /// to be false in the corresponding arc-map.
 		    void hide(const Arc& a) const { _arc_filter->set(a, false); }
 		    ///\e
 		    /// 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 { _node_filter->set(n, true); }
 		    ///\e
 		    /// The value of \c a is set to be true in the arc-map which stores
 		    /// hide information. If \c a was hidden previuosly, then it is shown
 		    /// again
 		    void unHide(const Arc& a) const { _arc_filter->set(a, true); }
 		    /// Returns true if \c n is hidden.
 		    ///\e
 		    ///
 		    bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
 		    /// Returns true if \c a is hidden.
 		    ///\e
 		    ///
 		    bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }
 		    typedef False NodeNumTag;
 		    typedef False EdgeNumTag;
 		    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
 		    Arc findArc(const Node& source, const Node& target,
 				const Arc& prev = INVALID) {
 		      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
 		        return INVALID;
+		      }
 		      Arc arc = Parent::findArc(source, target, prev);
 		      while (arc != INVALID && !(*_arc_filter)[arc]) {
 		        arc = Parent::findArc(source, target, arc);
+		      }
 		      return arc;
+		    }
 		    template <typename _Value>
 		    class NodeMap : public SubMapExtender<Adaptor,
 		        typename Parent::template NodeMap<_Value> > {
 		    public:
 		      typedef _Value Value;
 		      typedef SubMapExtender<Adaptor, typename Parent::
@@ -527,86 +458,55 @@
 		    void firstOut(Arc& i, const Node& n) const {
 		      Parent::firstOut(i, n);
 		      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
+		    }
 		    void next(Node& i) const {
 		      Parent::next(i);
 		      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
+		    }
 		    void next(Arc& i) const {
 		      Parent::next(i);
 		      while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
+		    }
 		    void nextIn(Arc& i) const {
 		      Parent::nextIn(i);
 		      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
+		    }
 		    void nextOut(Arc& i) const {
 		      Parent::nextOut(i);
 		      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
+		    }
 		    ///\e
 		    /// 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 { _node_filter->set(n, false); }
 		    ///\e
 		    /// 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 arc-map.
 		    void hide(const Arc& e) const { _arc_filter->set(e, false); }
 		    ///\e
 		    /// 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 { _node_filter->set(n, true); }
 		    ///\e
 		    /// The value of \c e is set to be true in the arc-map which stores
 		    /// hide information. If \c e was hidden previuosly, then it is shown
 		    /// again
 		    void unHide(const Arc& e) const { _arc_filter->set(e, true); }
 		    /// Returns true if \c n is hidden.
 		    ///\e
 		    ///
 		    bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
 		    /// Returns true if \c n is hidden.
 		    ///\e
 		    ///
 		    bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }
 		    typedef False NodeNumTag;
 		    typedef False EdgeNumTag;
 		    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
 		    Arc findArc(const Node& source, const Node& target,
 				  const Arc& prev = INVALID) {
 		      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
 		        return INVALID;
+		      }
 		      Arc arc = Parent::findArc(source, target, prev);
 		      while (arc != INVALID && !(*_arc_filter)[arc]) {
 		        arc = Parent::findArc(source, target, arc);
+		      }
 		      return arc;
+		    }
 		    template <typename _Value>
 		    class NodeMap : public SubMapExtender<Adaptor,
 		        typename Parent::template NodeMap<_Value> > {
 		    public:
 		      typedef _Value Value;
 		      typedef SubMapExtender<Adaptor, typename Parent::
@@ -640,256 +540,317 @@
 		      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;
+		      }
 		    };
 		  };
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief A digraph adaptor for hiding nodes and arcs from a digraph.
 		  ///
 		  /// SubDigraphAdaptor shows the digraph with filtered node-set and
 		  /// arc-set. If the \c checked parameter is true then it filters the arcset
 		  /// to do not get invalid arcs without source or target.
 		  /// Let \f$ G=(V, A) \f$ be a directed digraph
 		  /// and suppose that the digraph instance \c g of type ListDigraph
 		  /// implements \f$ G \f$.
 		  /// Let moreover \f$ b_V \f$ and \f$ b_A \f$ be bool-valued functions resp.
 		  /// on the node-set and arc-set.
 		  /// SubDigraphAdaptor<...>::NodeIt iterates
 		  /// on the node-set \f$ \{v\in V : b_V(v)=true\} \f$ and
 		  /// SubDigraphAdaptor<...>::ArcIt iterates
 		  /// on the arc-set \f$ \{e\in A : b_A(e)=true\} \f$. Similarly,
 		  /// SubDigraphAdaptor<...>::OutArcIt and
 		  /// SubDigraphAdaptor<...>::InArcIt iterates
 		  /// only on arcs leaving and entering a specific node which have true value.
 		  /// arc-set. If the \c checked parameter is true then it filters the arc-set
 		  /// respect to the source and target.
 		  ///
 		  /// 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 arc-iterator cares only the filter on the
 		  /// arc-set.  This way the arc-map should filter all arcs which's
-		  /// source or target is filtered by the node-filter.
+		  /// 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> SubGA;
 		  /// SubGA ga(g, nm, am);
-		  /// for (SubGA::NodeIt n(ga); n!=INVALID; ++n)
+		  /// 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;
 		  /// std::cout << ":-)" << std::endl;
 		  /// for (SubGA::ArcIt a(ga); a!=INVALID; ++a)
 		  /// 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 SubGA::NodeIt, but it can be converted to
+		  /// 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.
 		  ///
 		  /// For other examples see also the documentation of
 		  /// NodeSubDigraphAdaptor and ArcSubDigraphAdaptor.
 		  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> > {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef _NodeFilterMap NodeFilterMap;
 		    typedef _ArcFilterMap ArcFilterMap;
 		    typedef DigraphAdaptorExtender<
 		      SubDigraphAdaptorBase<Digraph, NodeFilterMap, ArcFilterMap, checked> >
 		    Parent;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		  protected:
 		    SubDigraphAdaptor() { }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a sub-digraph-adaptor for the given digraph with
 		    /// given node and arc map filters.
 		    SubDigraphAdaptor(Digraph& digraph, NodeFilterMap& node_filter,
 				      ArcFilterMap& arc_filter) {
 		      setDigraph(digraph);
 		      setNodeFilterMap(node_filter);
 		      setArcFilterMap(arc_filter);
+		    }
 		    /// \brief Hides the node of the graph
 		    ///
 		    /// This function hides \c n in the digraph, i.e. the iteration
 		    /// jumps over it. This is done by simply setting the value of \c n
 		    /// to be false in the corresponding node-map.
 		    void hide(const Node& n) const { Parent::hide(n); }
 		    /// \brief Hides the arc of the graph
 		    ///
 		    /// This function hides \c a in the digraph, i.e. the iteration
 		    /// jumps over it. This is done by simply setting the value of \c a
 		    /// to be false in the corresponding arc-map.
 		    void hide(const Arc& a) const { Parent::hide(a); }
 		    /// \brief Unhides the node of the graph
 		    ///
 		    /// The value of \c n is set to be true in the node-map which stores
 		    /// hide information. If \c n was hidden previuosly, then it is shown
 		    /// again
 		    void unHide(const Node& n) const { Parent::unHide(n); }
 		    /// \brief Unhides the arc of the graph
 		    ///
 		    /// The value of \c a is set to be true in the arc-map which stores
 		    /// hide information. If \c a was hidden previuosly, then it is shown
 		    /// again
 		    void unHide(const Arc& a) const { Parent::unHide(a); }
 		    /// \brief Returns true if \c n is hidden.
 		    ///
 		    /// Returns true if \c n is hidden.
 		    ///
 		    bool hidden(const Node& n) const { return Parent::hidden(n); }
 		    /// \brief Returns true if \c a is hidden.
 		    ///
 		    /// Returns true if \c a is hidden.
 		    ///
 		    bool hidden(const Arc& a) const { return Parent::hidden(a); }
 		  };
-		  /// \brief Just gives back a sub digraph adaptor
+		  /// \brief Just gives back a sub-digraph-adaptor
 		  ///
-		  /// Just gives back a sub digraph adaptor
+		  /// Just gives back a sub-digraph-adaptor
 		  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>
 		      (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>
 		      (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>
 		      (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,
 		      const ArcFilterMap>(digraph, nfm, afm);
+		  }
 		  ///\ingroup graph_adaptors
 		  ///
 		  ///\brief An adaptor for hiding nodes from a digraph.
 		  ///
 		  ///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> {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef _NodeFilterMap NodeFilterMap;
 		    typedef SubDigraphAdaptor<Digraph, NodeFilterMap,
 					      ConstMap<typename Digraph::Arc, bool>, checked>
 		    Parent;
 		    typedef typename Parent::Node Node;
 		  protected:
 		    ConstMap<typename Digraph::Arc, bool> const_true_map;
 		    NodeSubDigraphAdaptor() : const_true_map(true) {
 		      Parent::setArcFilterMap(const_true_map);
+		    }
 		  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);
+		    }
 		    /// \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 \c NodeSubDigraphAdaptor
+		  /// \brief Just gives back a  node-sub-digraph adaptor
 		  ///
-		  /// Just gives back a \c NodeSubDigraphAdaptor
+		  /// Just gives back a node-sub-digraph adaptor
 		  template<typename Digraph, typename NodeFilterMap>
 		  NodeSubDigraphAdaptor<const Digraph, NodeFilterMap>
 		  nodeSubDigraphAdaptor(const Digraph& digraph, NodeFilterMap& nfm) {
 		    return NodeSubDigraphAdaptor<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);
+		  }
 		  ///\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 w.r.t.  non-negative arc-lengths. Note that
 		  ///the comprehension of the presented solution need's some
-		  ///elementary knowlarc from combinatorial optimization.
+		  ///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.
 		  ///
 		  ///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
-		  ///didigraph lemon_dot_example {
+		  ///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;
@@ -953,69 +914,96 @@
 		  /// 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
 		  template<typename _Digraph, typename _ArcFilterMap>
 		  class ArcSubDigraphAdaptor :
 		    public SubDigraphAdaptor<_Digraph, ConstMap<typename _Digraph::Node, bool>,
 					     _ArcFilterMap, false> {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef _ArcFilterMap ArcFilterMap;
 		    typedef SubDigraphAdaptor<Digraph, ConstMap<typename Digraph::Node, bool>,
 					      ArcFilterMap, false> Parent;
 		    typedef typename Parent::Arc Arc;
 		  protected:
 		    ConstMap<typename Digraph::Node, bool> const_true_map;
 		    ArcSubDigraphAdaptor() : const_true_map(true) {
 		      Parent::setNodeFilterMap(const_true_map);
+		    }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a arc-sub-digraph-adaptor for the given digraph with
 		    /// given arc map filter.
 		    ArcSubDigraphAdaptor(Digraph& digraph, ArcFilterMap& arc_filter)
 		      : Parent(), const_true_map(true) {
 		      Parent::setDigraph(digraph);
 		      Parent::setNodeFilterMap(const_true_map);
 		      Parent::setArcFilterMap(arc_filter);
+		    }
 		    /// \brief Hides the arc of the graph
 		    ///
 		    /// This function hides \c a in the digraph, i.e. the iteration
 		    /// jumps over it. This is done by simply setting the value of \c a
 		    /// to be false in the corresponding arc-map.
 		    void hide(const Arc& a) const { Parent::hide(a); }
 		    /// \brief Unhides the arc of the graph
 		    ///
 		    /// The value of \c a is set to be true in the arc-map which stores
 		    /// hide information. If \c a was hidden previuosly, then it is shown
 		    /// again
 		    void unHide(const Arc& a) const { Parent::unHide(a); }
 		    /// \brief Returns true if \c a is hidden.
 		    ///
 		    /// Returns true if \c a is hidden.
 		    ///
 		    bool hidden(const Arc& a) const { return Parent::hidden(a); }
 		  };
-		  /// \brief Just gives back an arc sub digraph adaptor
+		  /// \brief Just gives back an arc-sub-digraph adaptor
 		  ///
-		  /// Just gives back an arc sub digraph adaptor
+		  /// Just gives back an arc-sub-digraph adaptor
 		  template<typename Digraph, typename ArcFilterMap>
 		  ArcSubDigraphAdaptor<const Digraph, ArcFilterMap>
 		  arcSubDigraphAdaptor(const Digraph& digraph, ArcFilterMap& afm) {
 		    return ArcSubDigraphAdaptor<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);
+		  }
 		  template <typename _Digraph>
 		  class UndirDigraphAdaptorBase {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef UndirDigraphAdaptorBase Adaptor;
 		    typedef True UndirectedTag;
 		    typedef typename Digraph::Arc Edge;
 		    typedef typename Digraph::Node Node;
@@ -1372,54 +1360,54 @@
 		      EdgeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
 		    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
 		  protected:
 		    UndirDigraphAdaptorBase() : _digraph(0) {}
 		    Digraph* _digraph;
 		    void setDigraph(Digraph& digraph) {
 		      _digraph = &digraph;
+		    }
 		  };
 		  ///\ingroup graph_adaptors
 		  ///
-		  /// \brief An graph is made from a directed digraph by an adaptor
+		  /// \brief A graph is made from a directed digraph by an adaptor
 		  ///
 		  /// This adaptor makes an undirected graph from a directed
 		  /// digraph. All arc of the underlying will be showed in the adaptor
 		  /// as an edge. Let's see an informal example about using
-		  /// this adaptor:
+		  /// 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.
 		  ///
 		  /// 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);
@@ -1781,54 +1769,48 @@
 		      return UndirDigraph::direct(e, false);
+		    }
 		    /// \brief Residual capacity map.
 		    ///
 		    /// In generic residual digraphs the residual capacity can be obtained
 		    /// as a map.
 		    class ResCap {
 		    protected:
 		      const Adaptor* _adaptor;
 		    public:
 		      typedef Arc Key;
 		      typedef typename _CapacityMap::Value Value;
 		      ResCap(const Adaptor& adaptor) : _adaptor(&adaptor) {}
 		      Value operator[](const Arc& e) const {
 		        return _adaptor->rescap(e);
+		      }
 		    };
 		  };
 		  /// \brief Base class for split digraph adaptor
 		  ///
 		  /// Base class of split digraph adaptor. In most case you do not need to
 		  /// use it directly but the documented member functions of this class can
 		  /// be used with the SplitDigraphAdaptor class.
 		  /// \sa SplitDigraphAdaptor
 		  template <typename _Digraph>
 		  class SplitDigraphAdaptorBase {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef DigraphAdaptorBase<const _Digraph> Parent;
 		    typedef SplitDigraphAdaptorBase Adaptor;
 		    typedef typename Digraph::Node DigraphNode;
 		    typedef typename Digraph::Arc DigraphArc;
 		    class Node;
 		    class Arc;
 		  private:
 		    template <typename T> class NodeMapBase;
 		    template <typename T> class ArcMapBase;
 		  public:
 		    class Node : public DigraphNode {
 		      friend class SplitDigraphAdaptorBase;
 		      template <typename T> friend class NodeMapBase;
@@ -2001,100 +1983,76 @@
+		    }
 		    int maxNodeId() const {
 		      return 2 * _digraph->maxNodeId() + 1;
+		    }
 		    int id(const Arc& e) const {
 		      if (e._item.firstState()) {
 		        return _digraph->id(e._item.first()) << 1;
 		      } else {
 		        return (_digraph->id(e._item.second()) << 1) | 1;
+		      }
+		    }
 		    Arc arcFromId(int ix) const {
 		      if ((ix & 1) == 0) {
 		        return Arc(_digraph->arcFromId(ix >> 1));
 		      } else {
 		        return Arc(_digraph->nodeFromId(ix >> 1));
+		      }
+		    }
 		    int maxArcId() const {
 		      return std::max(_digraph->maxNodeId() << 1,
 		                      (_digraph->maxArcId() << 1) | 1);
+		    }
 		    /// \brief Returns true when the node is in-node.
 		    ///
 		    /// Returns true when the node is in-node.
 		    static bool inNode(const Node& n) {
 		      return n._in;
+		    }
 		    /// \brief Returns true when the node is out-node.
 		    ///
 		    /// Returns true when the node is out-node.
 		    static bool outNode(const Node& n) {
 		      return !n._in;
+		    }
 		    /// \brief Returns true when the arc is arc in the original digraph.
 		    ///
 		    /// Returns true when the arc is arc in the original digraph.
 		    static bool origArc(const Arc& e) {
 		      return e._item.firstState();
+		    }
 		    /// \brief Returns true when the arc binds an in-node and an out-node.
 		    ///
 		    /// Returns true when the arc binds an in-node and an out-node.
 		    static bool bindArc(const Arc& e) {
 		      return e._item.secondState();
+		    }
 		    /// \brief Gives back the in-node created from the \c node.
 		    ///
 		    /// Gives back the in-node created from the \c node.
 		    static Node inNode(const DigraphNode& n) {
 		      return Node(n, true);
+		    }
 		    /// \brief Gives back the out-node created from the \c node.
 		    ///
 		    /// Gives back the out-node created from the \c node.
 		    static Node outNode(const DigraphNode& n) {
 		      return Node(n, false);
+		    }
 		    /// \brief Gives back the arc binds the two part of the node.
 		    ///
 		    /// Gives back the arc binds the two part of the node.
 		    static Arc arc(const DigraphNode& n) {
 		      return Arc(n);
+		    }
 		    /// \brief Gives back the arc of the original arc.
 		    ///
 		    /// Gives back the arc of the original arc.
 		    static Arc arc(const DigraphArc& e) {
 		      return Arc(e);
+		    }
 		    typedef True NodeNumTag;
 		    int nodeNum() const {
 		      return  2 * countNodes(*_digraph);
+		    }
 		    typedef True EdgeNumTag;
 		    int arcNum() const {
 		      return countArcs(*_digraph) + countNodes(*_digraph);
+		    }
 		    typedef True FindEdgeTag;
 		    Arc findArc(const Node& u, const Node& v,
 				const Arc& prev = INVALID) const {
 		      if (inNode(u)) {
 		        if (outNode(v)) {
 		          if (static_cast<const DigraphNode&>(u) ==
 		              static_cast<const DigraphNode&>(v) && prev == INVALID) {
 		            return Arc(u);
+		          }
@@ -2254,49 +2212,49 @@
 		      _digraph = &digraph;
+		    }
 		  };
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Split digraph adaptor class
 		  ///
 		  /// 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
 		  /// \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.
 		  ///
-		  /// By example a maximum flow algoritm can compute how many arc
+		  /// 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();
 		  ///
@@ -2309,58 +2267,117 @@
 		  /// \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
 		  template <typename _Digraph>
 		  class SplitDigraphAdaptor
 		    : public DigraphAdaptorExtender<SplitDigraphAdaptorBase<_Digraph> > {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef DigraphAdaptorExtender<SplitDigraphAdaptorBase<Digraph> > Parent;
 		    typedef typename Digraph::Node DigraphNode;
 		    typedef typename Digraph::Arc DigraphArc;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    /// \brief Constructor of the adaptor.
 		    ///
 		    /// Constructor of the adaptor.
 		    SplitDigraphAdaptor(Digraph& g) {
 		      Parent::setDigraph(g);
+		    }
 		    /// \brief Returns true when the node is in-node.
 		    ///
 		    /// Returns true when the node is in-node.
 		    static bool inNode(const Node& n) {
 		      return Parent::inNode(n);
+		    }
 		    /// \brief Returns true when the node is out-node.
 		    ///
 		    /// Returns true when the node is out-node.
 		    static bool outNode(const Node& n) {
 		      return Parent::outNode(n);
+		    }
 		    /// \brief Returns true when the arc is arc in the original digraph.
 		    ///
 		    /// Returns true when the arc is arc in the original digraph.
 		    static bool origArc(const Arc& a) {
 		      return Parent::origArc(a);
+		    }
 		    /// \brief Returns true when the arc binds an in-node and an out-node.
 		    ///
 		    /// Returns true when the arc binds an in-node and an out-node.
 		    static bool bindArc(const Arc& a) {
 		      return Parent::bindArc(a);
+		    }
 		    /// \brief Gives back the in-node created from the \c node.
 		    ///
 		    /// Gives back the in-node created from the \c node.
 		    static Node inNode(const DigraphNode& n) {
 		      return Parent::inNode(n);
+		    }
 		    /// \brief Gives back the out-node created from the \c node.
 		    ///
 		    /// Gives back the out-node created from the \c node.
 		    static Node outNode(const DigraphNode& n) {
 		      return Parent::outNode(n);
+		    }
 		    /// \brief Gives back the arc binds the two part of the node.
 		    ///
 		    /// Gives back the arc binds the two part of the node.
 		    static Arc arc(const DigraphNode& n) {
 		      return Parent::arc(n);
+		    }
 		    /// \brief Gives back the arc of the original arc.
 		    ///
 		    /// Gives back the arc of the original arc.
 		    static Arc arc(const DigraphArc& a) {
 		      return Parent::arc(a);
+		    }
 		    /// \brief NodeMap combined from two original NodeMap
 		    ///
 		    /// This class adapt two of the original digraph NodeMap to
 		    /// get a node map on the adapted digraph.
 		    template <typename InNodeMap, typename OutNodeMap>
 		    class CombinedNodeMap {
 		    public:
 		      typedef Node Key;
 		      typedef typename InNodeMap::Value Value;
 		      /// \brief Constructor
 		      ///
 		      /// Constructor.
 		      CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
 			: _in_map(in_map), _out_map(out_map) {}
 		      /// \brief The subscript operator.
 		      ///
 		      /// The subscript operator.
 		      Value& operator[](const Key& key) {
 			if (Parent::inNode(key)) {
 			  return _in_map[key];
 			} else {

lemon/graph_adaptor.h

Show inline comments

@@ -10,57 +10,48 @@
 		 * 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 {
 		  /// \brief Base type for the Graph Adaptors
 		  ///
 		  /// This is the base type for most of LEMON graph adaptors.
 		  /// This class implements a trivial graph adaptor i.e. it only wraps the
 		  /// functions and types of the graph. The purpose of this class is to
 		  /// make easier implementing graph adaptors. E.g. if an adaptor is
 		  /// considered which differs from the wrapped graph only in some of its
 		  /// functions or types, then it can be derived from GraphAdaptor, and only
 		  /// the differences should be implemented.
 		  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); }
@@ -174,67 +165,48 @@
 		    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;
+		      }
 		    };
 		  };
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Trivial graph adaptor
 		  ///
 		  /// This class is an adaptor which does not change the adapted undirected
 		  /// graph. It can be used only to test the graph adaptors.
 		  template <typename _Graph>
 		  class GraphAdaptor
 		    : public GraphAdaptorExtender< GraphAdaptorBase<_Graph> > {
 		  public:
 		    typedef _Graph Graph;
 		    typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent;
 		  protected:
 		    GraphAdaptor() : Parent() {}
 		  public:
 		    explicit GraphAdaptor(Graph& graph) { setGraph(graph); }
 		  };
 		  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:
@@ -297,84 +269,55 @@
 		      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);
+		    }
 		    /// \brief Hide the given node in the graph.
 		    ///
 		    /// This function hides \c n in the graph, i.e. the iteration
 		    /// jumps over it. This is done by simply setting the value of \c n
 		    /// to be false in the corresponding node-map.
 		    void hide(const Node& n) const { _node_filter_map->set(n, false); }
 		    /// \brief Hide the given edge in 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 { _edge_filter_map->set(e, false); }
 		    /// \brief Unhide the given node in 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 { _node_filter_map->set(n, true); }
 		    /// \brief Hide the given edge in 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 { _edge_filter_map->set(e, true); }
 		    /// \brief Returns true if \c n is hidden.
 		    ///
 		    /// Returns true if \c n is hidden.
 		    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
 		    /// \brief Returns true if \c e is hidden.
 		    ///
 		    /// Returns true if \c e is hidden.
 		    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]) {
@@ -522,84 +465,55 @@
 		      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);
+		    }
 		    /// \brief Hide the given node in the graph.
 		    ///
 		    /// This function hides \c n in the graph, i.e. the iteration
 		    /// jumps over it. This is done by simply setting the value of \c n
 		    /// to be false in the corresponding node-map.
 		    void hide(const Node& n) const { _node_filter_map->set(n, false); }
 		    /// \brief Hide the given edge in 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 { _edge_filter_map->set(e, false); }
 		    /// \brief Unhide the given node in 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 { _node_filter_map->set(n, true); }
 		    /// \brief Hide the given edge in 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 { _edge_filter_map->set(e, true); }
 		    /// \brief Returns true if \c n is hidden.
 		    ///
 		    /// Returns true if \c n is hidden.
 		    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
 		    /// \brief Returns true if \c e is hidden.
 		    ///
 		    /// Returns true if \c e is hidden.
 		    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>
@@ -661,81 +575,133 @@
 		                             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 arcs from an
+		  /// \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);
+		  }
@@ -744,131 +710,185 @@
 		  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);
+		  }
 		  /// \brief Base of direct graph adaptor
 		  ///
 		  /// Base class of the direct graph adaptor. All public member
 		  /// of this class can be used with the DirGraphAdaptor too.
 		  /// \sa DirGraphAdaptor
 		  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);
+		    }
@@ -1082,55 +1102,63 @@
 		  ///
 		  /// 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

test/graph_adaptor_test.cc

Show inline comments

@@ -16,84 +16,48 @@
+		 *
 		 */
 		#include<iostream>
 		#include<lemon/concept_check.h>
 		#include<lemon/list_graph.h>
 		#include<lemon/smart_graph.h>
 		#include<lemon/concepts/digraph.h>
 		#include<lemon/concepts/graph.h>
 		#include<lemon/digraph_adaptor.h>
 		#include<lemon/graph_adaptor.h>
 		#include <limits>
 		#include <lemon/bfs.h>
 		#include <lemon/path.h>
 		#include"test/test_tools.h"
 		#include"test/graph_test.h"
 		using namespace lemon;
 		void checkDigraphAdaptor() {
 		  checkConcept<concepts::Digraph, DigraphAdaptor<concepts::Digraph> >();
 		  typedef ListDigraph Digraph;
 		  typedef DigraphAdaptor<Digraph> Adaptor;
 		  Digraph digraph;
 		  Adaptor adaptor(digraph);
 		  Digraph::Node n1 = digraph.addNode();
 		  Digraph::Node n2 = digraph.addNode();
 		  Digraph::Node n3 = digraph.addNode();
 		  Digraph::Arc a1 = digraph.addArc(n1, n2);
 		  Digraph::Arc a2 = digraph.addArc(n1, n3);
 		  Digraph::Arc a3 = digraph.addArc(n2, n3);
 		  checkGraphNodeList(adaptor, 3);
 		  checkGraphArcList(adaptor, 3);
 		  checkGraphConArcList(adaptor, 3);
 		  checkGraphOutArcList(adaptor, n1, 2);
 		  checkGraphOutArcList(adaptor, n2, 1);
 		  checkGraphOutArcList(adaptor, n3, 0);
 		  checkGraphInArcList(adaptor, n1, 0);
 		  checkGraphInArcList(adaptor, n2, 1);
 		  checkGraphInArcList(adaptor, n3, 2);
 		  checkNodeIds(adaptor);
 		  checkArcIds(adaptor);
 		  checkGraphNodeMap(adaptor);
 		  checkGraphArcMap(adaptor);
+		}
 		void checkRevDigraphAdaptor() {
 		  checkConcept<concepts::Digraph, RevDigraphAdaptor<concepts::Digraph> >();
 		  typedef ListDigraph Digraph;
 		  typedef RevDigraphAdaptor<Digraph> Adaptor;
 		  Digraph digraph;
 		  Adaptor adaptor(digraph);
 		  Digraph::Node n1 = digraph.addNode();
 		  Digraph::Node n2 = digraph.addNode();
 		  Digraph::Node n3 = digraph.addNode();
 		  Digraph::Arc a1 = digraph.addArc(n1, n2);
 		  Digraph::Arc a2 = digraph.addArc(n1, n3);
 		  Digraph::Arc a3 = digraph.addArc(n2, n3);
 		  checkGraphNodeList(adaptor, 3);
 		  checkGraphArcList(adaptor, 3);
 		  checkGraphConArcList(adaptor, 3);
 		  checkGraphOutArcList(adaptor, n1, 0);
 		  checkGraphOutArcList(adaptor, n2, 1);
 		  checkGraphOutArcList(adaptor, n3, 2);
@@ -564,98 +528,48 @@
 		  checkGraphInArcList(adaptor, adaptor.inNode(n3), 2);
 		  checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);
 		  checkNodeIds(adaptor);
 		  checkArcIds(adaptor);
 		  checkGraphNodeMap(adaptor);
 		  checkGraphArcMap(adaptor);
 		  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
 		    if (adaptor.origArc(a)) {
 		      Digraph::Arc oa = a;
 		      check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)),
 			    "Wrong split");
 		      check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)),
 			    "Wrong split");
 		    } else {
 		      Digraph::Node on = a;
 		      check(adaptor.source(a) == adaptor.inNode(on), "Wrong split");
 		      check(adaptor.target(a) == adaptor.outNode(on), "Wrong split");
+		    }
+		  }
+		}
 		void checkGraphAdaptor() {
 		  checkConcept<concepts::Graph, GraphAdaptor<concepts::Graph> >();
 		  typedef ListGraph Graph;
 		  typedef GraphAdaptor<Graph> Adaptor;
 		  Graph graph;
 		  Adaptor adaptor(graph);
 		  Graph::Node n1 = graph.addNode();
 		  Graph::Node n2 = graph.addNode();
 		  Graph::Node n3 = graph.addNode();
 		  Graph::Node n4 = graph.addNode();
 		  Graph::Edge a1 = graph.addEdge(n1, n2);
 		  Graph::Edge a2 = graph.addEdge(n1, n3);
 		  Graph::Edge a3 = graph.addEdge(n2, n3);
 		  Graph::Edge a4 = graph.addEdge(n3, n4);
 		  checkGraphNodeList(adaptor, 4);
 		  checkGraphArcList(adaptor, 8);
 		  checkGraphEdgeList(adaptor, 4);
 		  checkGraphConArcList(adaptor, 8);
 		  checkGraphConEdgeList(adaptor, 4);
 		  checkGraphOutArcList(adaptor, n1, 2);
 		  checkGraphOutArcList(adaptor, n2, 2);
 		  checkGraphOutArcList(adaptor, n3, 3);
 		  checkGraphOutArcList(adaptor, n4, 1);
 		  checkGraphInArcList(adaptor, n1, 2);
 		  checkGraphInArcList(adaptor, n2, 2);
 		  checkGraphInArcList(adaptor, n3, 3);
 		  checkGraphInArcList(adaptor, n4, 1);
 		  checkGraphIncEdgeList(adaptor, n1, 2);
 		  checkGraphIncEdgeList(adaptor, n2, 2);
 		  checkGraphIncEdgeList(adaptor, n3, 3);
 		  checkGraphIncEdgeList(adaptor, n4, 1);
 		  checkNodeIds(adaptor);
 		  checkArcIds(adaptor);
 		  checkEdgeIds(adaptor);
 		  checkGraphNodeMap(adaptor);
 		  checkGraphArcMap(adaptor);
 		  checkGraphEdgeMap(adaptor);
+		}
 		void checkSubGraphAdaptor() {
 		  checkConcept<concepts::Graph,
 		    SubGraphAdaptor<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;
 		  Graph graph;
 		  NodeFilter node_filter(graph);
 		  EdgeFilter edge_filter(graph);
 		  Adaptor adaptor(graph, node_filter, edge_filter);
 		  Graph::Node n1 = graph.addNode();
 		  Graph::Node n2 = graph.addNode();
 		  Graph::Node n3 = graph.addNode();
 		  Graph::Node n4 = graph.addNode();
 		  Graph::Edge e1 = graph.addEdge(n1, n2);
 		  Graph::Edge e2 = graph.addEdge(n1, n3);
 		  Graph::Edge e3 = graph.addEdge(n2, n3);
@@ -1032,41 +946,39 @@
 		    check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir");
 		    dir[e3] = n2 == u;
+		  }
 		  checkGraphOutArcList(adaptor, n1, 1);
 		  checkGraphOutArcList(adaptor, n2, 1);
 		  checkGraphOutArcList(adaptor, n3, 1);
 		  checkGraphInArcList(adaptor, n1, 1);
 		  checkGraphInArcList(adaptor, n2, 1);
 		  checkGraphInArcList(adaptor, n3, 1);
 		  checkNodeIds(adaptor);
 		  checkArcIds(adaptor);
 		  checkGraphNodeMap(adaptor);
 		  checkGraphArcMap(adaptor);
+		}
 		int main(int, const char **) {
 		  checkDigraphAdaptor();
 		  checkRevDigraphAdaptor();
 		  checkSubDigraphAdaptor();
 		  checkNodeSubDigraphAdaptor();
 		  checkArcSubDigraphAdaptor();
 		  checkUndirDigraphAdaptor();
 		  checkResDigraphAdaptor();
 		  checkSplitDigraphAdaptor();
 		  checkGraphAdaptor();
 		  checkSubGraphAdaptor();
 		  checkNodeSubGraphAdaptor();
 		  checkEdgeSubGraphAdaptor();
 		  checkDirGraphAdaptor();
 		  return 0;
+		}

0 comments (0 inline)

RhodeCode

Login to your account