LEMON/LEMON-official Changeset - r431:4b6112235fad

Repositories » LEMON » LEMON-official

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

Changeset - r431:4b6112235fad

« 430:05357d

432:76287c »

r431: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

@@ -14,50 +14,39 @@
 		 * 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; }
@@ -157,53 +146,24 @@
+		      }
 		      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;
@@ -222,45 +182,43 @@
 		      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);
@@ -275,24 +233,28 @@
 		  /// }
 		  ///\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);
@@ -365,62 +327,31 @@
 		    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);
@@ -539,62 +470,31 @@
 		      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);
@@ -652,107 +552,140 @@
 		        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) {
@@ -765,24 +698,25 @@
 		  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
@@ -793,91 +727,118 @@
 		  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" ];
@@ -965,45 +926,72 @@
 		  /// 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);
+		  }
@@ -1384,30 +1372,30 @@
 		    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;
@@ -1793,30 +1781,24 @@
 		      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;
@@ -2013,76 +1995,52 @@
 		    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 {
@@ -2266,25 +2224,25 @@
 		  /// \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);
@@ -2321,34 +2279,93 @@
 		  /// 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

lemon/graph_adaptor.h

Show inline comments

@@ -22,33 +22,24 @@
 		///\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; }
@@ -186,43 +177,24 @@
 			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;
@@ -309,60 +281,31 @@
 		      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);
@@ -534,60 +477,31 @@
 		      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);
+		      }
@@ -673,57 +587,109 @@
 		      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) {
@@ -756,40 +722,71 @@
 		  /// 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);
+		  }
@@ -804,59 +801,82 @@
 		  /// 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
 		    ///
@@ -1094,35 +1114,43 @@
 		  /// 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>

test/graph_adaptor_test.cc

Show inline comments

@@ -28,60 +28,24 @@
 		#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();
@@ -576,74 +540,24 @@
 		      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;
@@ -1044,29 +958,27 @@
 		  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