LEMON/LEMON-official Changeset - r434:ad483acf1654

Repositories » LEMON » LEMON-official

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

Changeset - r434:ad483acf1654

« 433:6ff53a
« 429:d8b87e

522:7f8560 »
469:d369e8 »
451:09e416 »
437:6a2a33 »
435:9afe81 »

r434:ad483acf1654

Tue, 02 Dec 2008 16:33:22

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Merge

0 3 5

merge default

3 files changed with 6878 insertions and 0 deletions:

lemon/adaptors.h

3347

lemon/bits/graph_adaptor_extender.h

403

lemon/bits/variant.h

494

lemon/connectivity.h

1572

test/graph_adaptor_test.cc

984

doc/groups.dox

lemon/Makefile.am

test/Makefile.am

↑ Collapse diff ↑

lemon/adaptors.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_ADAPTORS_H
 		#define LEMON_ADAPTORS_H
 		/// \ingroup graph_adaptors
 		/// \file
 		/// \brief Several graph adaptors
 		///
 		/// This file contains several useful adaptors for digraphs and graphs.
 		#include <lemon/core.h>
 		#include <lemon/maps.h>
 		#include <lemon/bits/variant.h>
 		#include <lemon/bits/graph_adaptor_extender.h>
 		#include <lemon/tolerance.h>
 		#include <algorithm>
 		namespace lemon {
 		  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); }
 		    void next(Arc& i) const { _digraph->next(i); }
 		    void nextIn(Arc& i) const { _digraph->nextIn(i); }
 		    void nextOut(Arc& i) const { _digraph->nextOut(i); }
 		    Node source(const Arc& a) const { return _digraph->source(a); }
 		    Node target(const Arc& a) const { return _digraph->target(a); }
 		    typedef NodeNumTagIndicator<Digraph> NodeNumTag;
 		    int nodeNum() const { return _digraph->nodeNum(); }
 		    typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
 		    int arcNum() const { return _digraph->arcNum(); }
 		    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
 		    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
 		      return _digraph->findArc(u, v, prev);
+		    }
 		    Node addNode() { return _digraph->addNode(); }
 		    Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); }
 		    void erase(const Node& n) const { _digraph->erase(n); }
 		    void erase(const Arc& a) const { _digraph->erase(a); }
 		    void clear() const { _digraph->clear(); }
 		    int id(const Node& n) const { return _digraph->id(n); }
 		    int id(const Arc& a) const { return _digraph->id(a); }
 		    Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
 		    Arc arcFromId(int ix) const { return _digraph->arcFromId(ix); }
 		    int maxNodeId() const { return _digraph->maxNodeId(); }
 		    int maxArcId() const { return _digraph->maxArcId(); }
 		    typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
 		    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
 		    typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier;
 		    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
 		    template <typename _Value>
 		    class NodeMap : public Digraph::template NodeMap<_Value> {
 		    public:
 		      typedef typename Digraph::template NodeMap<_Value> Parent;
 		      explicit NodeMap(const Adaptor& adaptor)
 		        : Parent(*adaptor._digraph) {}
 		      NodeMap(const Adaptor& adaptor, const _Value& value)
 		        : Parent(*adaptor._digraph, value) { }
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class ArcMap : public Digraph::template ArcMap<_Value> {
 		    public:
 		      typedef typename Digraph::template ArcMap<_Value> Parent;
 		      explicit ArcMap(const Adaptor& adaptor)
 		        : Parent(*adaptor._digraph) {}
 		      ArcMap(const Adaptor& adaptor, const _Value& value)
 		        : Parent(*adaptor._digraph, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  template<typename _Graph>
 		  class GraphAdaptorBase {
 		  public:
 		    typedef _Graph Graph;
 		    typedef Graph ParentGraph;
 		  protected:
 		    Graph* _graph;
 		    GraphAdaptorBase() : _graph(0) {}
 		    void setGraph(Graph& graph) { _graph = &graph; }
 		  public:
 		    GraphAdaptorBase(Graph& graph) : _graph(&graph) {}
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::Arc Arc;
 		    typedef typename Graph::Edge Edge;
 		    void first(Node& i) const { _graph->first(i); }
 		    void first(Arc& i) const { _graph->first(i); }
 		    void first(Edge& i) const { _graph->first(i); }
 		    void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); }
 		    void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); }
 		    void firstInc(Edge &i, bool &d, const Node &n) const {
 		      _graph->firstInc(i, d, n);
+		    }
 		    void next(Node& i) const { _graph->next(i); }
 		    void next(Arc& i) const { _graph->next(i); }
 		    void next(Edge& i) const { _graph->next(i); }
 		    void nextIn(Arc& i) const { _graph->nextIn(i); }
 		    void nextOut(Arc& i) const { _graph->nextOut(i); }
 		    void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); }
 		    Node u(const Edge& e) const { return _graph->u(e); }
 		    Node v(const Edge& e) const { return _graph->v(e); }
 		    Node source(const Arc& a) const { return _graph->source(a); }
 		    Node target(const Arc& a) const { return _graph->target(a); }
 		    typedef NodeNumTagIndicator<Graph> NodeNumTag;
 		    int nodeNum() const { return _graph->nodeNum(); }
 		    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
 		    int arcNum() const { return _graph->arcNum(); }
 		    int edgeNum() const { return _graph->edgeNum(); }
 		    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
 		    Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
 		      return _graph->findArc(u, v, prev);
+		    }
 		    Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) {
 		      return _graph->findEdge(u, v, prev);
+		    }
 		    Node addNode() { return _graph->addNode(); }
 		    Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }
 		    void erase(const Node& i) { _graph->erase(i); }
 		    void erase(const Edge& i) { _graph->erase(i); }
 		    void clear() { _graph->clear(); }
 		    bool direction(const Arc& a) const { return _graph->direction(a); }
 		    Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); }
 		    int id(const Node& v) const { return _graph->id(v); }
 		    int id(const Arc& a) const { return _graph->id(a); }
 		    int id(const Edge& e) const { return _graph->id(e); }
 		    Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
 		    Arc arcFromId(int ix) const { return _graph->arcFromId(ix); }
 		    Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); }
 		    int maxNodeId() const { return _graph->maxNodeId(); }
 		    int maxArcId() const { return _graph->maxArcId(); }
 		    int maxEdgeId() const { return _graph->maxEdgeId(); }
 		    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
 		    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
 		    typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
 		    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
 		    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
 		    EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
 		    template <typename _Value>
 		    class NodeMap : public Graph::template NodeMap<_Value> {
 		    public:
 		      typedef typename Graph::template NodeMap<_Value> Parent;
 		      explicit NodeMap(const GraphAdaptorBase<Graph>& adapter)
 		        : Parent(*adapter._graph) {}
 		      NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
 		        : Parent(*adapter._graph, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class ArcMap : public Graph::template ArcMap<_Value> {
 		    public:
 		      typedef typename Graph::template ArcMap<_Value> Parent;
 		      explicit ArcMap(const GraphAdaptorBase<Graph>& adapter)
 		        : Parent(*adapter._graph) {}
 		      ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
 		        : Parent(*adapter._graph, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class EdgeMap : public Graph::template EdgeMap<_Value> {
 		    public:
 		      typedef typename Graph::template EdgeMap<_Value> Parent;
 		      explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)
 		        : Parent(*adapter._graph) {}
 		      EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
 		        : Parent(*adapter._graph, value) {}
 		    private:
 		      EdgeMap& operator=(const EdgeMap& cmap) {
 		        return operator=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  template <typename _Digraph>
 		  class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef DigraphAdaptorBase<_Digraph> Parent;
 		  protected:
 		    ReverseDigraphBase() : Parent() { }
 		  public:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    void firstIn(Arc& a, const Node& n) const { Parent::firstOut(a, n); }
 		    void firstOut(Arc& a, const Node& n ) const { Parent::firstIn(a, n); }
 		    void nextIn(Arc& a) const { Parent::nextOut(a); }
 		    void nextOut(Arc& a) const { Parent::nextIn(a); }
 		    Node source(const Arc& a) const { return Parent::target(a); }
 		    Node target(const Arc& a) const { return Parent::source(a); }
 		    Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); }
 		    typedef FindEdgeTagIndicator<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.
 		  ///
 		  /// ReverseDigraph reverses the arcs in the adapted digraph. The
 		  /// SubDigraph is conform to the \ref concepts::Digraph
 		  /// "Digraph concept".
 		  ///
 		  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
 		  /// "Digraph concept". The type can be specified to be const.
 		  template<typename _Digraph>
 		  class ReverseDigraph :
 		    public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef DigraphAdaptorExtender<
 		      ReverseDigraphBase<_Digraph> > Parent;
 		  protected:
 		    ReverseDigraph() { }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a reverse digraph adaptor for the given digraph
 		    explicit ReverseDigraph(Digraph& digraph) {
 		      Parent::setDigraph(digraph);
+		    }
 		  };
 		  /// \brief Just gives back a reverse digraph adaptor
 		  ///
 		  /// Just gives back a reverse digraph adaptor
 		  template<typename Digraph>
 		  ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) {
 		    return ReverseDigraph<const Digraph>(digraph);
+		  }
 		  template <typename _Digraph, typename _NodeFilterMap,
 		            typename _ArcFilterMap, bool _checked = true>
 		  class SubDigraphBase : public DigraphAdaptorBase<_Digraph> {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef _NodeFilterMap NodeFilterMap;
 		    typedef _ArcFilterMap ArcFilterMap;
 		    typedef SubDigraphBase Adaptor;
 		    typedef DigraphAdaptorBase<_Digraph> Parent;
 		  protected:
 		    NodeFilterMap* _node_filter;
 		    ArcFilterMap* _arc_filter;
 		    SubDigraphBase()
 		      : Parent(), _node_filter(0), _arc_filter(0) { }
 		    void setNodeFilterMap(NodeFilterMap& node_filter) {
 		      _node_filter = &node_filter;
+		    }
 		    void setArcFilterMap(ArcFilterMap& arc_filter) {
 		      _arc_filter = &arc_filter;
+		    }
 		  public:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    void first(Node& i) const {
 		      Parent::first(i);
 		      while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
+		    }
 		    void first(Arc& i) const {
 		      Parent::first(i);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 		                              || !(*_node_filter)[Parent::source(i)]
 		                              || !(*_node_filter)[Parent::target(i)]))
 		        Parent::next(i);
+		    }
 		    void firstIn(Arc& i, const Node& n) const {
 		      Parent::firstIn(i, n);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 		                              || !(*_node_filter)[Parent::source(i)]))
 		        Parent::nextIn(i);
+		    }
 		    void firstOut(Arc& i, const Node& n) const {
 		      Parent::firstOut(i, n);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 		                              || !(*_node_filter)[Parent::target(i)]))
 		        Parent::nextOut(i);
+		    }
 		    void next(Node& i) const {
 		      Parent::next(i);
 		      while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
+		    }
 		    void next(Arc& i) const {
 		      Parent::next(i);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 		                              || !(*_node_filter)[Parent::source(i)]
 		                              || !(*_node_filter)[Parent::target(i)]))
 		        Parent::next(i);
+		    }
 		    void nextIn(Arc& i) const {
 		      Parent::nextIn(i);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 		                              || !(*_node_filter)[Parent::source(i)]))
 		        Parent::nextIn(i);
+		    }
 		    void nextOut(Arc& i) const {
 		      Parent::nextOut(i);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 		                              || !(*_node_filter)[Parent::target(i)]))
 		        Parent::nextOut(i);
+		    }
 		    void hide(const Node& n) const { _node_filter->set(n, false); }
 		    void hide(const Arc& a) const { _arc_filter->set(a, false); }
 		    void unHide(const Node& n) const { _node_filter->set(n, true); }
 		    void unHide(const Arc& a) const { _arc_filter->set(a, true); }
 		    bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
 		    bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }
 		    typedef False NodeNumTag;
 		    typedef False EdgeNumTag;
 		    typedef FindEdgeTagIndicator<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::
 		                             template NodeMap<Value> > MapParent;
 		      NodeMap(const Adaptor& adaptor)
 		        : MapParent(adaptor) {}
 		      NodeMap(const Adaptor& adaptor, const Value& value)
 		        : MapParent(adaptor, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        MapParent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class ArcMap : public SubMapExtender<Adaptor,
 		      typename Parent::template ArcMap<_Value> > {
 		    public:
 		      typedef _Value Value;
 		      typedef SubMapExtender<Adaptor, typename Parent::
 		                             template ArcMap<Value> > MapParent;
 		      ArcMap(const Adaptor& adaptor)
 		        : MapParent(adaptor) {}
 		      ArcMap(const Adaptor& adaptor, const Value& value)
 		        : MapParent(adaptor, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        MapParent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>
 		  class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>
 		    : public DigraphAdaptorBase<_Digraph> {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef _NodeFilterMap NodeFilterMap;
 		    typedef _ArcFilterMap ArcFilterMap;
 		    typedef SubDigraphBase Adaptor;
 		    typedef DigraphAdaptorBase<Digraph> Parent;
 		  protected:
 		    NodeFilterMap* _node_filter;
 		    ArcFilterMap* _arc_filter;
 		    SubDigraphBase()
 		      : Parent(), _node_filter(0), _arc_filter(0) { }
 		    void setNodeFilterMap(NodeFilterMap& node_filter) {
 		      _node_filter = &node_filter;
+		    }
 		    void setArcFilterMap(ArcFilterMap& arc_filter) {
 		      _arc_filter = &arc_filter;
+		    }
 		  public:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    void first(Node& i) const {
 		      Parent::first(i);
 		      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
+		    }
 		    void first(Arc& i) const {
 		      Parent::first(i);
 		      while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
+		    }
 		    void firstIn(Arc& i, const Node& n) const {
 		      Parent::firstIn(i, n);
 		      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
+		    }
 		    void firstOut(Arc& i, const Node& n) const {
 		      Parent::firstOut(i, n);
 		      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
+		    }
 		    void next(Node& i) const {
 		      Parent::next(i);
 		      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
+		    }
 		    void next(Arc& i) const {
 		      Parent::next(i);
 		      while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
+		    }
 		    void nextIn(Arc& i) const {
 		      Parent::nextIn(i);
 		      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
+		    }
 		    void nextOut(Arc& i) const {
 		      Parent::nextOut(i);
 		      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i);
+		    }
 		    void hide(const Node& n) const { _node_filter->set(n, false); }
 		    void hide(const Arc& e) const { _arc_filter->set(e, false); }
 		    void unHide(const Node& n) const { _node_filter->set(n, true); }
 		    void unHide(const Arc& e) const { _arc_filter->set(e, true); }
 		    bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
 		    bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }
 		    typedef False NodeNumTag;
 		    typedef False EdgeNumTag;
 		    typedef FindEdgeTagIndicator<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::
 		                             template NodeMap<Value> > MapParent;
 		      NodeMap(const Adaptor& adaptor)
 		        : MapParent(adaptor) {}
 		      NodeMap(const Adaptor& adaptor, const Value& value)
 		        : MapParent(adaptor, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        MapParent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class ArcMap : public SubMapExtender<Adaptor,
 		      typename Parent::template ArcMap<_Value> > {
 		    public:
 		      typedef _Value Value;
 		      typedef SubMapExtender<Adaptor, typename Parent::
 		                             template ArcMap<Value> > MapParent;
 		      ArcMap(const Adaptor& adaptor)
 		        : MapParent(adaptor) {}
 		      ArcMap(const Adaptor& adaptor, const Value& value)
 		        : MapParent(adaptor, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        MapParent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief An adaptor for hiding nodes and arcs in a digraph
 		  ///
 		  /// SubDigraph hides nodes and arcs in a digraph. A bool node map
 		  /// and a bool arc map must be specified, which define the filters
 		  /// for nodes and arcs. Just the nodes and arcs with true value are
 		  /// shown in the subdigraph. The SubDigraph is conform to the \ref
 		  /// concepts::Digraph "Digraph concept". If the \c _checked parameter
 		  /// is true, then the arcs incident to filtered nodes are also
 		  /// filtered out.
 		  ///
 		  /// \tparam _Digraph It must be conform to the \ref
 		  /// concepts::Digraph "Digraph concept". The type can be specified
 		  /// to const.
 		  /// \tparam _NodeFilterMap A bool valued node map of the the adapted digraph.
 		  /// \tparam _ArcFilterMap A bool valued arc map of the the adapted digraph.
 		  /// \tparam _checked If the parameter is false then the arc filtering
 		  /// is not checked with respect to node filter. Otherwise, each arc
 		  /// is automatically filtered, which is incident to a filtered node.
 		  ///
 		  /// \see FilterNodes
 		  /// \see FilterArcs
 		  template<typename _Digraph,
 		           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
 		           typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>,
 		           bool _checked = true>
 		  class SubDigraph
 		    : public DigraphAdaptorExtender<
 		      SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef _NodeFilterMap NodeFilterMap;
 		    typedef _ArcFilterMap ArcFilterMap;
 		    typedef DigraphAdaptorExtender<
 		      SubDigraphBase<Digraph, NodeFilterMap, ArcFilterMap, _checked> >
 		    Parent;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		  protected:
 		    SubDigraph() { }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a subdigraph for the given digraph with
 		    /// given node and arc map filters.
 		    SubDigraph(Digraph& digraph, NodeFilterMap& node_filter,
 		               ArcFilterMap& arc_filter) {
 		      setDigraph(digraph);
 		      setNodeFilterMap(node_filter);
 		      setArcFilterMap(arc_filter);
+		    }
 		    /// \brief Hides the node of the graph
 		    ///
 		    /// This function hides \c n in the digraph, i.e. the iteration
 		    /// jumps over it. This is done by simply setting the value of \c n
 		    /// to be false in the corresponding node-map.
 		    void hide(const Node& n) const { Parent::hide(n); }
 		    /// \brief Hides the arc of the graph
 		    ///
 		    /// This function hides \c a in the digraph, i.e. the iteration
 		    /// jumps over it. This is done by simply setting the value of \c a
 		    /// to be false in the corresponding arc-map.
 		    void hide(const Arc& a) const { Parent::hide(a); }
 		    /// \brief Unhides the node of the graph
 		    ///
 		    /// The value of \c n is set to be true in the node-map which stores
 		    /// hide information. If \c n was hidden previuosly, then it is shown
 		    /// again
 		    void unHide(const Node& n) const { Parent::unHide(n); }
 		    /// \brief Unhides the arc of the graph
 		    ///
 		    /// The value of \c a is set to be true in the arc-map which stores
 		    /// hide information. If \c a was hidden previuosly, then it is shown
 		    /// again
 		    void unHide(const Arc& a) const { Parent::unHide(a); }
 		    /// \brief Returns true if \c n is hidden.
 		    ///
 		    /// Returns true if \c n is hidden.
 		    ///
 		    bool hidden(const Node& n) const { return Parent::hidden(n); }
 		    /// \brief Returns true if \c a is hidden.
 		    ///
 		    /// Returns true if \c a is hidden.
 		    ///
 		    bool hidden(const Arc& a) const { return Parent::hidden(a); }
 		  };
 		  /// \brief Just gives back a subdigraph
 		  ///
 		  /// Just gives back a subdigraph
 		  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
 		  SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
 		  subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) {
 		    return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap>
 		      (digraph, nfm, afm);
+		  }
 		  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
 		  SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
 		  subDigraph(const Digraph& digraph,
 		             const NodeFilterMap& nfm, ArcFilterMap& afm) {
 		    return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap>
 		      (digraph, nfm, afm);
+		  }
 		  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
 		  SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
 		  subDigraph(const Digraph& digraph,
 		             NodeFilterMap& nfm, const ArcFilterMap& afm) {
 		    return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap>
 		      (digraph, nfm, afm);
+		  }
 		  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
 		  SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap>
 		  subDigraph(const Digraph& digraph,
 		             const NodeFilterMap& nfm, const ArcFilterMap& afm) {
 		    return SubDigraph<const Digraph, const NodeFilterMap,
 		      const ArcFilterMap>(digraph, nfm, afm);
+		  }
 		  template <typename _Graph, typename NodeFilterMap,
 		            typename EdgeFilterMap, bool _checked = true>
 		  class SubGraphBase : public GraphAdaptorBase<_Graph> {
 		  public:
 		    typedef _Graph Graph;
 		    typedef SubGraphBase Adaptor;
 		    typedef GraphAdaptorBase<_Graph> Parent;
 		  protected:
 		    NodeFilterMap* _node_filter_map;
 		    EdgeFilterMap* _edge_filter_map;
 		    SubGraphBase()
 		      : Parent(), _node_filter_map(0), _edge_filter_map(0) { }
 		    void setNodeFilterMap(NodeFilterMap& node_filter_map) {
 		      _node_filter_map=&node_filter_map;
+		    }
 		    void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
 		      _edge_filter_map=&edge_filter_map;
+		    }
 		  public:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    typedef typename Parent::Edge Edge;
 		    void first(Node& i) const {
 		      Parent::first(i);
 		      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
+		    }
 		    void first(Arc& i) const {
 		      Parent::first(i);
 		      while (i!=INVALID && (!(*_edge_filter_map)[i]
 		                            || !(*_node_filter_map)[Parent::source(i)]
 		                            || !(*_node_filter_map)[Parent::target(i)]))
 		        Parent::next(i);
+		    }
 		    void first(Edge& i) const {
 		      Parent::first(i);
 		      while (i!=INVALID && (!(*_edge_filter_map)[i]
 		                            || !(*_node_filter_map)[Parent::u(i)]
 		                            || !(*_node_filter_map)[Parent::v(i)]))
 		        Parent::next(i);
+		    }
 		    void firstIn(Arc& i, const Node& n) const {
 		      Parent::firstIn(i, n);
 		      while (i!=INVALID && (!(*_edge_filter_map)[i]
 		                            || !(*_node_filter_map)[Parent::source(i)]))
 		        Parent::nextIn(i);
+		    }
 		    void firstOut(Arc& i, const Node& n) const {
 		      Parent::firstOut(i, n);
 		      while (i!=INVALID && (!(*_edge_filter_map)[i]
 		                            || !(*_node_filter_map)[Parent::target(i)]))
 		        Parent::nextOut(i);
+		    }
 		    void firstInc(Edge& i, bool& d, const Node& n) const {
 		      Parent::firstInc(i, d, n);
 		      while (i!=INVALID && (!(*_edge_filter_map)[i]
 		                            || !(*_node_filter_map)[Parent::u(i)]
 		                            || !(*_node_filter_map)[Parent::v(i)]))
 		        Parent::nextInc(i, d);
+		    }
 		    void next(Node& i) const {
 		      Parent::next(i);
 		      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
+		    }
 		    void next(Arc& i) const {
 		      Parent::next(i);
 		      while (i!=INVALID && (!(*_edge_filter_map)[i]
 		                            || !(*_node_filter_map)[Parent::source(i)]
 		                            || !(*_node_filter_map)[Parent::target(i)]))
 		        Parent::next(i);
+		    }
 		    void next(Edge& i) const {
 		      Parent::next(i);
 		      while (i!=INVALID && (!(*_edge_filter_map)[i]
 		                            || !(*_node_filter_map)[Parent::u(i)]
 		                            || !(*_node_filter_map)[Parent::v(i)]))
 		        Parent::next(i);
+		    }
 		    void nextIn(Arc& i) const {
 		      Parent::nextIn(i);
 		      while (i!=INVALID && (!(*_edge_filter_map)[i]
 		                            || !(*_node_filter_map)[Parent::source(i)]))
 		        Parent::nextIn(i);
+		    }
 		    void nextOut(Arc& i) const {
 		      Parent::nextOut(i);
 		      while (i!=INVALID && (!(*_edge_filter_map)[i]
 		                            || !(*_node_filter_map)[Parent::target(i)]))
 		        Parent::nextOut(i);
+		    }
 		    void nextInc(Edge& i, bool& d) const {
 		      Parent::nextInc(i, d);
 		      while (i!=INVALID && (!(*_edge_filter_map)[i]
 		                            || !(*_node_filter_map)[Parent::u(i)]
 		                            || !(*_node_filter_map)[Parent::v(i)]))
 		        Parent::nextInc(i, d);
+		    }
 		    void hide(const Node& n) const { _node_filter_map->set(n, false); }
 		    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
 		    void unHide(const Node& n) const { _node_filter_map->set(n, true); }
 		    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
 		    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
 		    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
 		    typedef False NodeNumTag;
 		    typedef False EdgeNumTag;
 		    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
 		    Arc findArc(const Node& u, const Node& v,
 		                const Arc& prev = INVALID) {
 		      if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
 		        return INVALID;
+		      }
 		      Arc arc = Parent::findArc(u, v, prev);
 		      while (arc != INVALID && !(*_edge_filter_map)[arc]) {
 		        arc = Parent::findArc(u, v, arc);
+		      }
 		      return arc;
+		    }
 		    Edge findEdge(const Node& u, const Node& v,
 		                  const Edge& prev = INVALID) {
 		      if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
 		        return INVALID;
+		      }
 		      Edge edge = Parent::findEdge(u, v, prev);
 		      while (edge != INVALID && !(*_edge_filter_map)[edge]) {
 		        edge = Parent::findEdge(u, v, edge);
+		      }
 		      return edge;
+		    }
 		    template <typename _Value>
 		    class NodeMap : public SubMapExtender<Adaptor,
 		      typename Parent::template NodeMap<_Value> > {
 		    public:
 		      typedef _Value Value;
 		      typedef SubMapExtender<Adaptor, typename Parent::
 		                             template NodeMap<Value> > MapParent;
 		      NodeMap(const Adaptor& adaptor)
 		        : MapParent(adaptor) {}
 		      NodeMap(const Adaptor& adaptor, const Value& value)
 		        : MapParent(adaptor, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        MapParent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class ArcMap : public SubMapExtender<Adaptor,
 		      typename Parent::template ArcMap<_Value> > {
 		    public:
 		      typedef _Value Value;
 		      typedef SubMapExtender<Adaptor, typename Parent::
 		                             template ArcMap<Value> > MapParent;
 		      ArcMap(const Adaptor& adaptor)
 		        : MapParent(adaptor) {}
 		      ArcMap(const Adaptor& adaptor, const Value& value)
 		        : MapParent(adaptor, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        MapParent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class EdgeMap : public SubMapExtender<Adaptor,
 		      typename Parent::template EdgeMap<_Value> > {
 		    public:
 		      typedef _Value Value;
 		      typedef SubMapExtender<Adaptor, typename Parent::
 		                             template EdgeMap<Value> > MapParent;
 		      EdgeMap(const Adaptor& adaptor)
 		        : MapParent(adaptor) {}
 		      EdgeMap(const Adaptor& adaptor, const Value& value)
 		        : MapParent(adaptor, value) {}
 		    private:
 		      EdgeMap& operator=(const EdgeMap& cmap) {
 		        return operator=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        MapParent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
 		  class SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
 		    : public GraphAdaptorBase<_Graph> {
 		  public:
 		    typedef _Graph Graph;
 		    typedef SubGraphBase Adaptor;
 		    typedef GraphAdaptorBase<_Graph> Parent;
 		  protected:
 		    NodeFilterMap* _node_filter_map;
 		    EdgeFilterMap* _edge_filter_map;
 		    SubGraphBase() : Parent(),
 		                     _node_filter_map(0), _edge_filter_map(0) { }
 		    void setNodeFilterMap(NodeFilterMap& node_filter_map) {
 		      _node_filter_map=&node_filter_map;
+		    }
 		    void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
 		      _edge_filter_map=&edge_filter_map;
+		    }
 		  public:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    typedef typename Parent::Edge Edge;
 		    void first(Node& i) const {
 		      Parent::first(i);
 		      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
+		    }
 		    void first(Arc& i) const {
 		      Parent::first(i);
 		      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
+		    }
 		    void first(Edge& i) const {
 		      Parent::first(i);
 		      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
+		    }
 		    void firstIn(Arc& i, const Node& n) const {
 		      Parent::firstIn(i, n);
 		      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
+		    }
 		    void firstOut(Arc& i, const Node& n) const {
 		      Parent::firstOut(i, n);
 		      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
+		    }
 		    void firstInc(Edge& i, bool& d, const Node& n) const {
 		      Parent::firstInc(i, d, n);
 		      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
+		    }
 		    void next(Node& i) const {
 		      Parent::next(i);
 		      while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
+		    }
 		    void next(Arc& i) const {
 		      Parent::next(i);
 		      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
+		    }
 		    void next(Edge& i) const {
 		      Parent::next(i);
 		      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
+		    }
 		    void nextIn(Arc& i) const {
 		      Parent::nextIn(i);
 		      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
+		    }
 		    void nextOut(Arc& i) const {
 		      Parent::nextOut(i);
 		      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
+		    }
 		    void nextInc(Edge& i, bool& d) const {
 		      Parent::nextInc(i, d);
 		      while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
+		    }
 		    void hide(const Node& n) const { _node_filter_map->set(n, false); }
 		    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
 		    void unHide(const Node& n) const { _node_filter_map->set(n, true); }
 		    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
 		    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
 		    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
 		    typedef False NodeNumTag;
 		    typedef False EdgeNumTag;
 		    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
 		    Arc findArc(const Node& u, const Node& v,
 		                const Arc& prev = INVALID) {
 		      Arc arc = Parent::findArc(u, v, prev);
 		      while (arc != INVALID && !(*_edge_filter_map)[arc]) {
 		        arc = Parent::findArc(u, v, arc);
+		      }
 		      return arc;
+		    }
 		    Edge findEdge(const Node& u, const Node& v,
 		                  const Edge& prev = INVALID) {
 		      Edge edge = Parent::findEdge(u, v, prev);
 		      while (edge != INVALID && !(*_edge_filter_map)[edge]) {
 		        edge = Parent::findEdge(u, v, edge);
+		      }
 		      return edge;
+		    }
 		    template <typename _Value>
 		    class NodeMap : public SubMapExtender<Adaptor,
 		      typename Parent::template NodeMap<_Value> > {
 		    public:
 		      typedef _Value Value;
 		      typedef SubMapExtender<Adaptor, typename Parent::
 		                             template NodeMap<Value> > MapParent;
 		      NodeMap(const Adaptor& adaptor)
 		        : MapParent(adaptor) {}
 		      NodeMap(const Adaptor& adaptor, const Value& value)
 		        : MapParent(adaptor, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        MapParent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class ArcMap : public SubMapExtender<Adaptor,
 		      typename Parent::template ArcMap<_Value> > {
 		    public:
 		      typedef _Value Value;
 		      typedef SubMapExtender<Adaptor, typename Parent::
 		                             template ArcMap<Value> > MapParent;
 		      ArcMap(const Adaptor& adaptor)
 		        : MapParent(adaptor) {}
 		      ArcMap(const Adaptor& adaptor, const Value& value)
 		        : MapParent(adaptor, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        MapParent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class EdgeMap : public SubMapExtender<Adaptor,
 		      typename Parent::template EdgeMap<_Value> > {
 		    public:
 		      typedef _Value Value;
 		      typedef SubMapExtender<Adaptor, typename Parent::
 		                             template EdgeMap<Value> > MapParent;
 		      EdgeMap(const Adaptor& adaptor)
 		        : MapParent(adaptor) {}
 		      EdgeMap(const Adaptor& adaptor, const _Value& value)
 		        : MapParent(adaptor, value) {}
 		    private:
 		      EdgeMap& operator=(const EdgeMap& cmap) {
 		        return operator=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        MapParent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief A graph adaptor for hiding nodes and edges in an
 		  /// undirected graph.
 		  ///
 		  /// SubGraph hides nodes and edges in a graph. A bool node map and a
 		  /// bool edge map must be specified, which define the filters for
 		  /// nodes and edges. Just the nodes and edges with true value are
 		  /// shown in the subgraph. The SubGraph is conform to the \ref
 		  /// concepts::Graph "Graph concept". If the \c _checked parameter is
 		  /// true, then the edges incident to filtered nodes are also
 		  /// filtered out.
 		  ///
 		  /// \tparam _Graph It must be conform to the \ref
 		  /// concepts::Graph "Graph concept". The type can be specified
 		  /// to const.
 		  /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
 		  /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted graph.
 		  /// \tparam _checked If the parameter is false then the edge filtering
 		  /// is not checked with respect to node filter. Otherwise, each edge
 		  /// is automatically filtered, which is incident to a filtered node.
 		  ///
 		  /// \see FilterNodes
 		  /// \see FilterEdges
 		  template<typename _Graph, typename NodeFilterMap,
 		           typename EdgeFilterMap, bool _checked = true>
 		  class SubGraph
 		    : public GraphAdaptorExtender<
 		      SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, _checked> > {
 		  public:
 		    typedef _Graph Graph;
 		    typedef GraphAdaptorExtender<
 		      SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Edge Edge;
 		  protected:
 		    SubGraph() { }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a subgraph for the given graph with given node and
 		    /// edge map filters.
 		    SubGraph(Graph& _graph, NodeFilterMap& node_filter_map,
 		             EdgeFilterMap& edge_filter_map) {
 		      setGraph(_graph);
 		      setNodeFilterMap(node_filter_map);
 		      setEdgeFilterMap(edge_filter_map);
+		    }
 		    /// \brief Hides the node of the graph
 		    ///
 		    /// This function hides \c n in the graph, i.e. the iteration
 		    /// jumps over it. This is done by simply setting the value of \c n
 		    /// to be false in the corresponding node-map.
 		    void hide(const Node& n) const { Parent::hide(n); }
 		    /// \brief Hides the edge of the graph
 		    ///
 		    /// This function hides \c e in the graph, i.e. the iteration
 		    /// jumps over it. This is done by simply setting the value of \c e
 		    /// to be false in the corresponding edge-map.
 		    void hide(const Edge& e) const { Parent::hide(e); }
 		    /// \brief Unhides the node of the graph
 		    ///
 		    /// The value of \c n is set to be true in the node-map which stores
 		    /// hide information. If \c n was hidden previuosly, then it is shown
 		    /// again
 		    void unHide(const Node& n) const { Parent::unHide(n); }
 		    /// \brief Unhides the edge of the graph
 		    ///
 		    /// The value of \c e is set to be true in the edge-map which stores
 		    /// hide information. If \c e was hidden previuosly, then it is shown
 		    /// again
 		    void unHide(const Edge& e) const { Parent::unHide(e); }
 		    /// \brief Returns true if \c n is hidden.
 		    ///
 		    /// Returns true if \c n is hidden.
 		    ///
 		    bool hidden(const Node& n) const { return Parent::hidden(n); }
 		    /// \brief Returns true if \c e is hidden.
 		    ///
 		    /// Returns true if \c e is hidden.
 		    ///
 		    bool hidden(const Edge& e) const { return Parent::hidden(e); }
 		  };
 		  /// \brief Just gives back a subgraph
 		  ///
 		  /// Just gives back a subgraph
 		  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
 		  SubGraph<const Graph, NodeFilterMap, ArcFilterMap>
 		  subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) {
 		    return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm);
+		  }
 		  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
 		  SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
 		  subGraph(const Graph& graph,
 		           const NodeFilterMap& nfm, ArcFilterMap& efm) {
 		    return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap>
 		      (graph, nfm, efm);
+		  }
 		  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
 		  SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
 		  subGraph(const Graph& graph,
 		           NodeFilterMap& nfm, const ArcFilterMap& efm) {
 		    return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap>
 		      (graph, nfm, efm);
+		  }
 		  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
 		  SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
 		  subGraph(const Graph& graph,
 		           const NodeFilterMap& nfm, const ArcFilterMap& efm) {
 		    return SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap>
 		      (graph, nfm, efm);
+		  }
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief An adaptor for hiding nodes from a digraph or a graph.
 		  ///
 		  /// FilterNodes adaptor hides nodes in a graph or a digraph. A bool
 		  /// node map must be specified, which defines the filters for
 		  /// nodes. Just the unfiltered nodes and the arcs or edges incident
 		  /// to unfiltered nodes are shown in the subdigraph or subgraph. The
 		  /// FilterNodes is conform to the \ref concepts::Digraph
 		  /// "Digraph concept" or \ref concepts::Graph "Graph concept" depending
 		  /// on the \c _Digraph template parameter. If the \c _checked
 		  /// parameter is true, then the arc or edges incident to filtered nodes
 		  /// are also filtered out.
 		  ///
 		  /// \tparam _Digraph It must be conform to the \ref
 		  /// concepts::Digraph "Digraph concept" or \ref concepts::Graph
 		  /// "Graph concept". The type can be specified to be const.
 		  /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph.
 		  /// \tparam _checked If the parameter is false then the arc or edge
 		  /// filtering is not checked with respect to node filter. In this
 		  /// case just isolated nodes can be filtered out from the
 		  /// graph.
 		#ifdef DOXYGEN
 		  template<typename _Digraph,
 		           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
 		           bool _checked = true>
 		#else
 		  template<typename _Digraph,
 		           typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,
 		           bool _checked = true,
 		           typename Enable = void>
 		#endif
 		  class FilterNodes
 		    : public SubDigraph<_Digraph, _NodeFilterMap,
 		                        ConstMap<typename _Digraph::Arc, bool>, _checked> {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef _NodeFilterMap NodeFilterMap;
 		    typedef SubDigraph<Digraph, NodeFilterMap,
 		                       ConstMap<typename Digraph::Arc, bool>, _checked>
 		    Parent;
 		    typedef typename Parent::Node Node;
 		  protected:
 		    ConstMap<typename Digraph::Arc, bool> const_true_map;
 		    FilterNodes() : const_true_map(true) {
 		      Parent::setArcFilterMap(const_true_map);
+		    }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates an adaptor for the given digraph or graph with
 		    /// given node filter map.
 		    FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) :
 		      Parent(), const_true_map(true) {
 		      Parent::setDigraph(_digraph);
 		      Parent::setNodeFilterMap(node_filter);
 		      Parent::setArcFilterMap(const_true_map);
+		    }
 		    /// \brief Hides the node of the graph
 		    ///
 		    /// This function hides \c n in the digraph or graph, i.e. the iteration
 		    /// jumps over it. This is done by simply setting the value of \c n
 		    /// to be false in the corresponding node map.
 		    void hide(const Node& n) const { Parent::hide(n); }
 		    /// \brief Unhides the node of the graph
 		    ///
 		    /// The value of \c n is set to be true in the node-map which stores
 		    /// hide information. If \c n was hidden previuosly, then it is shown
 		    /// again
 		    void unHide(const Node& n) const { Parent::unHide(n); }
 		    /// \brief Returns true if \c n is hidden.
 		    ///
 		    /// Returns true if \c n is hidden.
 		    ///
 		    bool hidden(const Node& n) const { return Parent::hidden(n); }
 		  };
 		  template<typename _Graph, typename _NodeFilterMap, bool _checked>
 		  class FilterNodes<_Graph, _NodeFilterMap, _checked,
 		                    typename enable_if<UndirectedTagIndicator<_Graph> >::type>
 		    : public SubGraph<_Graph, _NodeFilterMap,
 		                      ConstMap<typename _Graph::Edge, bool>, _checked> {
 		  public:
 		    typedef _Graph Graph;
 		    typedef _NodeFilterMap NodeFilterMap;
 		    typedef SubGraph<Graph, NodeFilterMap,
 		                     ConstMap<typename Graph::Edge, bool> > Parent;
 		    typedef typename Parent::Node Node;
 		  protected:
 		    ConstMap<typename Graph::Edge, bool> const_true_map;
 		    FilterNodes() : const_true_map(true) {
 		      Parent::setEdgeFilterMap(const_true_map);
+		    }
 		  public:
 		    FilterNodes(Graph& _graph, NodeFilterMap& node_filter_map) :
 		      Parent(), const_true_map(true) {
 		      Parent::setGraph(_graph);
 		      Parent::setNodeFilterMap(node_filter_map);
 		      Parent::setEdgeFilterMap(const_true_map);
+		    }
 		    void hide(const Node& n) const { Parent::hide(n); }
 		    void unHide(const Node& n) const { Parent::unHide(n); }
 		    bool hidden(const Node& n) const { return Parent::hidden(n); }
 		  };
 		  /// \brief Just gives back a FilterNodes adaptor
 		  ///
 		  /// Just gives back a FilterNodes adaptor
 		  template<typename Digraph, typename NodeFilterMap>
 		  FilterNodes<const Digraph, NodeFilterMap>
 		  filterNodes(const Digraph& digraph, NodeFilterMap& nfm) {
 		    return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm);
+		  }
 		  template<typename Digraph, typename NodeFilterMap>
 		  FilterNodes<const Digraph, const NodeFilterMap>
 		  filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) {
 		    return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm);
+		  }
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief An adaptor for hiding arcs from a digraph.
 		  ///
 		  /// FilterArcs adaptor hides arcs in a digraph. A bool arc map must
 		  /// be specified, which defines the filters for arcs. Just the
 		  /// unfiltered arcs are shown in the subdigraph. The FilterArcs is
 		  /// conform to the \ref concepts::Digraph "Digraph concept".
 		  ///
 		  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
 		  /// "Digraph concept". The type can be specified to be const.
 		  /// \tparam _ArcFilterMap A bool valued arc map of the the adapted
 		  /// graph.
 		  template<typename _Digraph, typename _ArcFilterMap>
 		  class FilterArcs :
 		    public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>,
 		                      _ArcFilterMap, false> {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef _ArcFilterMap ArcFilterMap;
 		    typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>,
 		                       ArcFilterMap, false> Parent;
 		    typedef typename Parent::Arc Arc;
 		  protected:
 		    ConstMap<typename Digraph::Node, bool> const_true_map;
 		    FilterArcs() : const_true_map(true) {
 		      Parent::setNodeFilterMap(const_true_map);
+		    }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a FilterArcs adaptor for the given graph with
 		    /// given arc map filter.
 		    FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter)
 		      : Parent(), const_true_map(true) {
 		      Parent::setDigraph(digraph);
 		      Parent::setNodeFilterMap(const_true_map);
 		      Parent::setArcFilterMap(arc_filter);
+		    }
 		    /// \brief Hides the arc of the graph
 		    ///
 		    /// This function hides \c a in the graph, i.e. the iteration
 		    /// jumps over it. This is done by simply setting the value of \c a
 		    /// to be false in the corresponding arc map.
 		    void hide(const Arc& a) const { Parent::hide(a); }
 		    /// \brief Unhides the arc of the graph
 		    ///
 		    /// The value of \c a is set to be true in the arc-map which stores
 		    /// hide information. If \c a was hidden previuosly, then it is shown
 		    /// again
 		    void unHide(const Arc& a) const { Parent::unHide(a); }
 		    /// \brief Returns true if \c a is hidden.
 		    ///
 		    /// Returns true if \c a is hidden.
 		    ///
 		    bool hidden(const Arc& a) const { return Parent::hidden(a); }
 		  };
 		  /// \brief Just gives back an FilterArcs adaptor
 		  ///
 		  /// Just gives back an FilterArcs adaptor
 		  template<typename Digraph, typename ArcFilterMap>
 		  FilterArcs<const Digraph, ArcFilterMap>
 		  filterArcs(const Digraph& digraph, ArcFilterMap& afm) {
 		    return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm);
+		  }
 		  template<typename Digraph, typename ArcFilterMap>
 		  FilterArcs<const Digraph, const ArcFilterMap>
 		  filterArcs(const Digraph& digraph, const ArcFilterMap& afm) {
 		    return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm);
+		  }
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief An adaptor for hiding edges from a graph.
 		  ///
 		  /// FilterEdges adaptor hides edges in a digraph. A bool edge map must
 		  /// be specified, which defines the filters for edges. Just the
 		  /// unfiltered edges are shown in the subdigraph. The FilterEdges is
 		  /// conform to the \ref concepts::Graph "Graph concept".
 		  ///
 		  /// \tparam _Graph It must be conform to the \ref concepts::Graph
 		  /// "Graph concept". The type can be specified to be const.
 		  /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted
 		  /// graph.
 		  template<typename _Graph, typename _EdgeFilterMap>
 		  class FilterEdges :
 		    public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>,
 		                    _EdgeFilterMap, false> {
 		  public:
 		    typedef _Graph Graph;
 		    typedef _EdgeFilterMap EdgeFilterMap;
 		    typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>,
 		                     EdgeFilterMap, false> Parent;
 		    typedef typename Parent::Edge Edge;
 		  protected:
 		    ConstMap<typename Graph::Node, bool> const_true_map;
 		    FilterEdges() : const_true_map(true) {
 		      Parent::setNodeFilterMap(const_true_map);
+		    }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a FilterEdges adaptor for the given graph with
 		    /// given edge map filters.
 		    FilterEdges(Graph& _graph, EdgeFilterMap& edge_filter_map) :
 		      Parent(), const_true_map(true) {
 		      Parent::setGraph(_graph);
 		      Parent::setNodeFilterMap(const_true_map);
 		      Parent::setEdgeFilterMap(edge_filter_map);
+		    }
 		    /// \brief Hides the edge of the graph
 		    ///
 		    /// This function hides \c e in the graph, i.e. the iteration
 		    /// jumps over it. This is done by simply setting the value of \c e
 		    /// to be false in the corresponding edge-map.
 		    void hide(const Edge& e) const { Parent::hide(e); }
 		    /// \brief Unhides the edge of the graph
 		    ///
 		    /// The value of \c e is set to be true in the edge-map which stores
 		    /// hide information. If \c e was hidden previuosly, then it is shown
 		    /// again
 		    void unHide(const Edge& e) const { Parent::unHide(e); }
 		    /// \brief Returns true if \c e is hidden.
 		    ///
 		    /// Returns true if \c e is hidden.
 		    ///
 		    bool hidden(const Edge& e) const { return Parent::hidden(e); }
 		  };
 		  /// \brief Just gives back a FilterEdges adaptor
 		  ///
 		  /// Just gives back a FilterEdges adaptor
 		  template<typename Graph, typename EdgeFilterMap>
 		  FilterEdges<const Graph, EdgeFilterMap>
 		  filterEdges(const Graph& graph, EdgeFilterMap& efm) {
 		    return FilterEdges<const Graph, EdgeFilterMap>(graph, efm);
+		  }
 		  template<typename Graph, typename EdgeFilterMap>
 		  FilterEdges<const Graph, const EdgeFilterMap>
 		  filterEdges(const Graph& graph, const EdgeFilterMap& efm) {
 		    return FilterEdges<const Graph, const EdgeFilterMap>(graph, efm);
+		  }
 		  template <typename _Digraph>
 		  class UndirectorBase {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef UndirectorBase Adaptor;
 		    typedef True UndirectedTag;
 		    typedef typename Digraph::Arc Edge;
 		    typedef typename Digraph::Node Node;
 		    class Arc : public Edge {
 		      friend class UndirectorBase;
 		    protected:
 		      bool _forward;
 		      Arc(const Edge& edge, bool forward) :
 		        Edge(edge), _forward(forward) {}
 		    public:
 		      Arc() {}
 		      Arc(Invalid) : Edge(INVALID), _forward(true) {}
 		      bool operator==(const Arc &other) const {
 		        return _forward == other._forward &&
 		          static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
+		      }
 		      bool operator!=(const Arc &other) const {
 		        return _forward != other._forward ||
 		          static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
+		      }
 		      bool operator<(const Arc &other) const {
 		        return _forward < other._forward ||
 		          (_forward == other._forward &&
 		           static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
+		      }
 		    };
 		    void first(Node& n) const {
 		      _digraph->first(n);
+		    }
 		    void next(Node& n) const {
 		      _digraph->next(n);
+		    }
 		    void first(Arc& a) const {
 		      _digraph->first(a);
 		      a._forward = true;
+		    }
 		    void next(Arc& a) const {
 		      if (a._forward) {
 		        a._forward = false;
 		      } else {
 		        _digraph->next(a);
 		        a._forward = true;
+		      }
+		    }
 		    void first(Edge& e) const {
 		      _digraph->first(e);
+		    }
 		    void next(Edge& e) const {
 		      _digraph->next(e);
+		    }
 		    void firstOut(Arc& a, const Node& n) const {
 		      _digraph->firstIn(a, n);
 		      if( static_cast<const Edge&>(a) != INVALID ) {
 		        a._forward = false;
 		      } else {
 		        _digraph->firstOut(a, n);
 		        a._forward = true;
+		      }
+		    }
 		    void nextOut(Arc &a) const {
 		      if (!a._forward) {
 		        Node n = _digraph->target(a);
 		        _digraph->nextIn(a);
 		        if (static_cast<const Edge&>(a) == INVALID ) {
 		          _digraph->firstOut(a, n);
 		          a._forward = true;
+		        }
+		      }
 		      else {
 		        _digraph->nextOut(a);
+		      }
+		    }
 		    void firstIn(Arc &a, const Node &n) const {
 		      _digraph->firstOut(a, n);
 		      if (static_cast<const Edge&>(a) != INVALID ) {
 		        a._forward = false;
 		      } else {
 		        _digraph->firstIn(a, n);
 		        a._forward = true;
+		      }
+		    }
 		    void nextIn(Arc &a) const {
 		      if (!a._forward) {
 		        Node n = _digraph->source(a);
 		        _digraph->nextOut(a);
 		        if( static_cast<const Edge&>(a) == INVALID ) {
 		          _digraph->firstIn(a, n);
 		          a._forward = true;
+		        }
+		      }
 		      else {
 		        _digraph->nextIn(a);
+		      }
+		    }
 		    void firstInc(Edge &e, bool &d, const Node &n) const {
 		      d = true;
 		      _digraph->firstOut(e, n);
 		      if (e != INVALID) return;
 		      d = false;
 		      _digraph->firstIn(e, n);
+		    }
 		    void nextInc(Edge &e, bool &d) const {
 		      if (d) {
 		        Node s = _digraph->source(e);
 		        _digraph->nextOut(e);
 		        if (e != INVALID) return;
 		        d = false;
 		        _digraph->firstIn(e, s);
 		      } else {
 		        _digraph->nextIn(e);
+		      }
+		    }
 		    Node u(const Edge& e) const {
 		      return _digraph->source(e);
+		    }
 		    Node v(const Edge& e) const {
 		      return _digraph->target(e);
+		    }
 		    Node source(const Arc &a) const {
 		      return a._forward ? _digraph->source(a) : _digraph->target(a);
+		    }
 		    Node target(const Arc &a) const {
 		      return a._forward ? _digraph->target(a) : _digraph->source(a);
+		    }
 		    static Arc direct(const Edge &e, bool d) {
 		      return Arc(e, d);
+		    }
 		    Arc direct(const Edge &e, const Node& n) const {
 		      return Arc(e, _digraph->source(e) == n);
+		    }
 		    static bool direction(const Arc &a) { return a._forward; }
 		    Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
 		    Arc arcFromId(int ix) const {
 		      return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1));
+		    }
 		    Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); }
 		    int id(const Node &n) const { return _digraph->id(n); }
 		    int id(const Arc &a) const {
 		      return  (_digraph->id(a) << 1) | (a._forward ? 1 : 0);
+		    }
 		    int id(const Edge &e) const { return _digraph->id(e); }
 		    int maxNodeId() const { return _digraph->maxNodeId(); }
 		    int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; }
 		    int maxEdgeId() const { return _digraph->maxArcId(); }
 		    Node addNode() { return _digraph->addNode(); }
 		    Edge addEdge(const Node& u, const Node& v) {
 		      return _digraph->addArc(u, v);
+		    }
 		    void erase(const Node& i) { _digraph->erase(i); }
 		    void erase(const Edge& i) { _digraph->erase(i); }
 		    void clear() { _digraph->clear(); }
 		    typedef NodeNumTagIndicator<Digraph> NodeNumTag;
 		    int nodeNum() const { return 2 * _digraph->arcNum(); }
 		    typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;
 		    int arcNum() const { return 2 * _digraph->arcNum(); }
 		    int edgeNum() const { return _digraph->arcNum(); }
 		    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;
 		    Arc findArc(Node s, Node t, Arc p = INVALID) const {
 		      if (p == INVALID) {
 		        Edge arc = _digraph->findArc(s, t);
 		        if (arc != INVALID) return direct(arc, true);
 		        arc = _digraph->findArc(t, s);
 		        if (arc != INVALID) return direct(arc, false);
 		      } else if (direction(p)) {
 		        Edge arc = _digraph->findArc(s, t, p);
 		        if (arc != INVALID) return direct(arc, true);
 		        arc = _digraph->findArc(t, s);
 		        if (arc != INVALID) return direct(arc, false);
 		      } else {
 		        Edge arc = _digraph->findArc(t, s, p);
 		        if (arc != INVALID) return direct(arc, false);
+		      }
 		      return INVALID;
+		    }
 		    Edge findEdge(Node s, Node t, Edge p = INVALID) const {
 		      if (s != t) {
 		        if (p == INVALID) {
 		          Edge arc = _digraph->findArc(s, t);
 		          if (arc != INVALID) return arc;
 		          arc = _digraph->findArc(t, s);
 		          if (arc != INVALID) return arc;
 		        } else if (_digraph->s(p) == s) {
 		          Edge arc = _digraph->findArc(s, t, p);
 		          if (arc != INVALID) return arc;
 		          arc = _digraph->findArc(t, s);
 		          if (arc != INVALID) return arc;
 		        } else {
 		          Edge arc = _digraph->findArc(t, s, p);
 		          if (arc != INVALID) return arc;
+		        }
 		      } else {
 		        return _digraph->findArc(s, t, p);
+		      }
 		      return INVALID;
+		    }
 		  private:
 		    template <typename _Value>
 		    class ArcMapBase {
 		    private:
 		      typedef typename Digraph::template ArcMap<_Value> MapImpl;
 		    public:
 		      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
 		      typedef _Value Value;
 		      typedef Arc Key;
 		      ArcMapBase(const Adaptor& adaptor) :
 		        _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
 		      ArcMapBase(const Adaptor& adaptor, const Value& v)
 		        : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {}
 		      void set(const Arc& a, const Value& v) {
 		        if (direction(a)) {
 		          _forward.set(a, v);
 		        } else {
 		          _backward.set(a, v);
+		        }
+		      }
 		      typename MapTraits<MapImpl>::ConstReturnValue
 		      operator[](const Arc& a) const {
 		        if (direction(a)) {
 		          return _forward[a];
 		        } else {
 		          return _backward[a];
+		        }
+		      }
 		      typename MapTraits<MapImpl>::ReturnValue
 		      operator[](const Arc& a) {
 		        if (direction(a)) {
 		          return _forward[a];
 		        } else {
 		          return _backward[a];
+		        }
+		      }
 		    protected:
 		      MapImpl _forward, _backward;
 		    };
 		  public:
 		    template <typename _Value>
 		    class NodeMap : public Digraph::template NodeMap<_Value> {
 		    public:
 		      typedef _Value Value;
 		      typedef typename Digraph::template NodeMap<Value> Parent;
 		      explicit NodeMap(const Adaptor& adaptor)
 		        : Parent(*adaptor._digraph) {}
 		      NodeMap(const Adaptor& adaptor, const _Value& value)
 		        : Parent(*adaptor._digraph, value) { }
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class ArcMap
 		      : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
+		    {
 		    public:
 		      typedef _Value Value;
 		      typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
 		      ArcMap(const Adaptor& adaptor)
 		        : Parent(adaptor) {}
 		      ArcMap(const Adaptor& adaptor, const Value& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class EdgeMap : public Digraph::template ArcMap<_Value> {
 		    public:
 		      typedef _Value Value;
 		      typedef typename Digraph::template ArcMap<Value> Parent;
 		      explicit EdgeMap(const Adaptor& adaptor)
 		        : Parent(*adaptor._digraph) {}
 		      EdgeMap(const Adaptor& adaptor, const Value& value)
 		        : Parent(*adaptor._digraph, value) {}
 		    private:
 		      EdgeMap& operator=(const EdgeMap& cmap) {
 		        return operator=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      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:
 		    UndirectorBase() : _digraph(0) {}
 		    Digraph* _digraph;
 		    void setDigraph(Digraph& digraph) {
 		      _digraph = &digraph;
+		    }
 		  };
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Undirect the graph
 		  ///
 		  /// This adaptor makes an undirected graph from a directed
 		  /// graph. All arcs of the underlying digraph will be showed in the
 		  /// adaptor as an edge. The Orienter adaptor is conform to the \ref
 		  /// concepts::Graph "Graph concept".
 		  ///
 		  /// \tparam _Digraph It must be conform to the \ref
 		  /// concepts::Digraph "Digraph concept". The type can be specified
 		  /// to const.
 		  template<typename _Digraph>
 		  class Undirector
 		    : public GraphAdaptorExtender<UndirectorBase<_Digraph> > {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent;
 		  protected:
 		    Undirector() { }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a undirected graph from the given digraph
 		    Undirector(_Digraph& digraph) {
 		      setDigraph(digraph);
+		    }
 		    /// \brief ArcMap combined from two original ArcMap
 		    ///
 		    /// This class adapts two original digraph ArcMap to
 		    /// get an arc map on the undirected graph.
 		    template <typename _ForwardMap, typename _BackwardMap>
 		    class CombinedArcMap {
 		    public:
 		      typedef _ForwardMap ForwardMap;
 		      typedef _BackwardMap BackwardMap;
 		      typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
 		      typedef typename ForwardMap::Value Value;
 		      typedef typename Parent::Arc Key;
 		      /// \brief Constructor
 		      ///
 		      /// Constructor
 		      CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
 		        : _forward(&forward), _backward(&backward) {}
 		      /// \brief Sets the value associated with a key.
 		      ///
 		      /// Sets the value associated with a key.
 		      void set(const Key& e, const Value& a) {
 		        if (Parent::direction(e)) {
 		          _forward->set(e, a);
 		        } else {
 		          _backward->set(e, a);
+		        }
+		      }
 		      /// \brief Returns the value associated with a key.
 		      ///
 		      /// Returns the value associated with a key.
 		      typename MapTraits<ForwardMap>::ConstReturnValue
 		      operator[](const Key& e) const {
 		        if (Parent::direction(e)) {
 		          return (*_forward)[e];
 		        } else {
 		          return (*_backward)[e];
+		        }
+		      }
 		      /// \brief Returns the value associated with a key.
 		      ///
 		      /// Returns the value associated with a key.
 		      typename MapTraits<ForwardMap>::ReturnValue
 		      operator[](const Key& e) {
 		        if (Parent::direction(e)) {
 		          return (*_forward)[e];
 		        } else {
 		          return (*_backward)[e];
+		        }
+		      }
 		    protected:
 		      ForwardMap* _forward;
 		      BackwardMap* _backward;
 		    };
 		    /// \brief Just gives back a combined arc map
 		    ///
 		    /// Just gives back a combined arc map
 		    template <typename ForwardMap, typename BackwardMap>
 		    static CombinedArcMap<ForwardMap, BackwardMap>
 		    combinedArcMap(ForwardMap& forward, BackwardMap& backward) {
 		      return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward);
+		    }
 		    template <typename ForwardMap, typename BackwardMap>
 		    static CombinedArcMap<const ForwardMap, BackwardMap>
 		    combinedArcMap(const ForwardMap& forward, BackwardMap& backward) {
 		      return CombinedArcMap<const ForwardMap,
 		        BackwardMap>(forward, backward);
+		    }
 		    template <typename ForwardMap, typename BackwardMap>
 		    static CombinedArcMap<ForwardMap, const BackwardMap>
 		    combinedArcMap(ForwardMap& forward, const BackwardMap& backward) {
 		      return CombinedArcMap<ForwardMap,
 		        const BackwardMap>(forward, backward);
+		    }
 		    template <typename ForwardMap, typename BackwardMap>
 		    static CombinedArcMap<const ForwardMap, const BackwardMap>
 		    combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) {
 		      return CombinedArcMap<const ForwardMap,
 		        const BackwardMap>(forward, backward);
+		    }
 		  };
 		  /// \brief Just gives back an undirected view of the given digraph
 		  ///
 		  /// Just gives back an undirected view of the given digraph
 		  template<typename Digraph>
 		  Undirector<const Digraph>
 		  undirector(const Digraph& digraph) {
 		    return Undirector<const Digraph>(digraph);
+		  }
 		  template <typename _Graph, typename _DirectionMap>
 		  class OrienterBase {
 		  public:
 		    typedef _Graph Graph;
 		    typedef _DirectionMap DirectionMap;
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::Edge Arc;
 		    void reverseArc(const Arc& arc) {
 		      _direction->set(arc, !(*_direction)[arc]);
+		    }
 		    void first(Node& i) const { _graph->first(i); }
 		    void first(Arc& i) const { _graph->first(i); }
 		    void firstIn(Arc& i, const Node& n) const {
 		      bool d;
 		      _graph->firstInc(i, d, n);
 		      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
+		    }
 		    void firstOut(Arc& i, const Node& n ) const {
 		      bool d;
 		      _graph->firstInc(i, d, n);
 		      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
+		    }
 		    void next(Node& i) const { _graph->next(i); }
 		    void next(Arc& i) const { _graph->next(i); }
 		    void nextIn(Arc& i) const {
 		      bool d = !(*_direction)[i];
 		      _graph->nextInc(i, d);
 		      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
+		    }
 		    void nextOut(Arc& i) const {
 		      bool d = (*_direction)[i];
 		      _graph->nextInc(i, d);
 		      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
+		    }
 		    Node source(const Arc& e) const {
 		      return (*_direction)[e] ? _graph->u(e) : _graph->v(e);
+		    }
 		    Node target(const Arc& e) const {
 		      return (*_direction)[e] ? _graph->v(e) : _graph->u(e);
+		    }
 		    typedef NodeNumTagIndicator<Graph> NodeNumTag;
 		    int nodeNum() const { return _graph->nodeNum(); }
 		    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
 		    int arcNum() const { return _graph->edgeNum(); }
 		    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
 		    Arc findArc(const Node& u, const Node& v,
 		                const Arc& prev = INVALID) {
 		      Arc arc = prev;
 		      bool d = arc == INVALID ? true : (*_direction)[arc];
 		      if (d) {
 		        arc = _graph->findEdge(u, v, arc);
 		        while (arc != INVALID && !(*_direction)[arc]) {
 		          _graph->findEdge(u, v, arc);
+		        }
 		        if (arc != INVALID) return arc;
+		      }
 		      _graph->findEdge(v, u, arc);
 		      while (arc != INVALID && (*_direction)[arc]) {
 		        _graph->findEdge(u, v, arc);
+		      }
 		      return arc;
+		    }
 		    Node addNode() {
 		      return Node(_graph->addNode());
+		    }
 		    Arc addArc(const Node& u, const Node& v) {
 		      Arc arc = _graph->addArc(u, v);
 		      _direction->set(arc, _graph->source(arc) == u);
 		      return arc;
+		    }
 		    void erase(const Node& i) { _graph->erase(i); }
 		    void erase(const Arc& i) { _graph->erase(i); }
 		    void clear() { _graph->clear(); }
 		    int id(const Node& v) const { return _graph->id(v); }
 		    int id(const Arc& e) const { return _graph->id(e); }
 		    Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
 		    Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
 		    int maxNodeId() const { return _graph->maxNodeId(); }
 		    int maxArcId() const { return _graph->maxEdgeId(); }
 		    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
 		    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
 		    typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
 		    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
 		    template <typename _Value>
 		    class NodeMap : public _Graph::template NodeMap<_Value> {
 		    public:
 		      typedef typename _Graph::template NodeMap<_Value> Parent;
 		      explicit NodeMap(const OrienterBase& adapter)
 		        : Parent(*adapter._graph) {}
 		      NodeMap(const OrienterBase& adapter, const _Value& value)
 		        : Parent(*adapter._graph, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class ArcMap : public _Graph::template EdgeMap<_Value> {
 		    public:
 		      typedef typename Graph::template EdgeMap<_Value> Parent;
 		      explicit ArcMap(const OrienterBase& adapter)
 		        : Parent(*adapter._graph) { }
 		      ArcMap(const OrienterBase& adapter, const _Value& value)
 		        : Parent(*adapter._graph, value) { }
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  protected:
 		    Graph* _graph;
 		    DirectionMap* _direction;
 		    void setDirectionMap(DirectionMap& direction) {
 		      _direction = &direction;
+		    }
 		    void setGraph(Graph& graph) {
 		      _graph = &graph;
+		    }
 		  };
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Orients the edges of the graph to get a digraph
 		  ///
 		  /// This adaptor orients each edge in the undirected graph. The
 		  /// direction of the arcs stored in an edge node map.  The arcs can
 		  /// be easily reverted by the \c reverseArc() member function in the
 		  /// adaptor. The Orienter adaptor is conform to the \ref
 		  /// concepts::Digraph "Digraph concept".
 		  ///
 		  /// \tparam _Graph It must be conform to the \ref concepts::Graph
 		  /// "Graph concept". The type can be specified to be const.
 		  /// \tparam _DirectionMap A bool valued edge map of the the adapted
 		  /// graph.
 		  ///
 		  /// \sa orienter
 		  template<typename _Graph,
 		           typename DirectionMap = typename _Graph::template EdgeMap<bool> >
 		  class Orienter :
 		    public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > {
 		  public:
 		    typedef _Graph Graph;
 		    typedef DigraphAdaptorExtender<
 		      OrienterBase<_Graph, DirectionMap> > Parent;
 		    typedef typename Parent::Arc Arc;
 		  protected:
 		    Orienter() { }
 		  public:
 		    /// \brief Constructor of the adaptor
 		    ///
 		    /// Constructor of the adaptor
 		    Orienter(Graph& graph, DirectionMap& direction) {
 		      setGraph(graph);
 		      setDirectionMap(direction);
+		    }
 		    /// \brief Reverse arc
 		    ///
 		    /// It reverse the given arc. It simply negate the direction in the map.
 		    void reverseArc(const Arc& a) {
 		      Parent::reverseArc(a);
+		    }
 		  };
 		  /// \brief Just gives back a Orienter
 		  ///
 		  /// Just gives back a Orienter
 		  template<typename Graph, typename DirectionMap>
 		  Orienter<const Graph, DirectionMap>
 		  orienter(const Graph& graph, DirectionMap& dm) {
 		    return Orienter<const Graph, DirectionMap>(graph, dm);
+		  }
 		  template<typename Graph, typename DirectionMap>
 		  Orienter<const Graph, const DirectionMap>
 		  orienter(const Graph& graph, const DirectionMap& dm) {
 		    return Orienter<const Graph, const DirectionMap>(graph, dm);
+		  }
 		  namespace _adaptor_bits {
 		    template<typename _Digraph,
 		             typename _CapacityMap = typename _Digraph::template ArcMap<int>,
 		             typename _FlowMap = _CapacityMap,
 		             typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
 		    class ResForwardFilter {
 		    public:
 		      typedef _Digraph Digraph;
 		      typedef _CapacityMap CapacityMap;
 		      typedef _FlowMap FlowMap;
 		      typedef _Tolerance Tolerance;
 		      typedef typename Digraph::Arc Key;
 		      typedef bool Value;
 		    private:
 		      const CapacityMap* _capacity;
 		      const FlowMap* _flow;
 		      Tolerance _tolerance;
 		    public:
 		      ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,
 		                       const Tolerance& tolerance = Tolerance())
 		        : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
 		      bool operator[](const typename Digraph::Arc& a) const {
 		        return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);
+		      }
 		    };
 		    template<typename _Digraph,
 		             typename _CapacityMap = typename _Digraph::template ArcMap<int>,
 		             typename _FlowMap = _CapacityMap,
 		             typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
 		    class ResBackwardFilter {
 		    public:
 		      typedef _Digraph Digraph;
 		      typedef _CapacityMap CapacityMap;
 		      typedef _FlowMap FlowMap;
 		      typedef _Tolerance Tolerance;
 		      typedef typename Digraph::Arc Key;
 		      typedef bool Value;
 		    private:
 		      const CapacityMap* _capacity;
 		      const FlowMap* _flow;
 		      Tolerance _tolerance;
 		    public:
 		      ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,
 		                        const Tolerance& tolerance = Tolerance())
 		        : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }
 		      bool operator[](const typename Digraph::Arc& a) const {
 		        return _tolerance.positive((*_flow)[a]);
+		      }
 		    };
+		  }
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief An adaptor for composing the residual graph for directed
 		  /// flow and circulation problems.
 		  ///
 		  /// An adaptor for composing the residual graph for directed flow and
 		  /// circulation problems.  Let \f$ G=(V, A) \f$ be a directed graph
 		  /// and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
 		  /// be functions on the arc-set.
 		  ///
 		  /// Then Residual implements the digraph structure with
 		  /// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward} \f$,
 		  /// where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
 		  /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so
 		  /// called residual graph.  When we take the union
 		  /// \f$ A_{forward}\cup A_{backward} \f$, multiplicities are counted,
 		  /// i.e.  if an arc is in both \f$ A_{forward} \f$ and
 		  /// \f$ A_{backward} \f$, then in the adaptor it appears in both
 		  /// orientation.
 		  ///
 		  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
 		  /// "Digraph concept". The type is implicitly const.
 		  /// \tparam _CapacityMap An arc map of some numeric type, it defines
 		  /// the capacities in the flow problem. The map is implicitly const.
 		  /// \tparam _FlowMap An arc map of some numeric type, it defines
 		  /// the capacities in the flow problem.
 		  /// \tparam _Tolerance Handler for inexact computation.
 		  template<typename _Digraph,
 		           typename _CapacityMap = typename _Digraph::template ArcMap<int>,
 		           typename _FlowMap = _CapacityMap,
 		           typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
 		  class Residual :
 		    public FilterArcs<
 		    Undirector<const _Digraph>,
 		    typename Undirector<const _Digraph>::template CombinedArcMap<
 		      _adaptor_bits::ResForwardFilter<const _Digraph, _CapacityMap,
 		                                      _FlowMap, _Tolerance>,
 		      _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap,
 		                                       _FlowMap, _Tolerance> > >
+		  {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef _CapacityMap CapacityMap;
 		    typedef _FlowMap FlowMap;
 		    typedef _Tolerance Tolerance;
 		    typedef typename CapacityMap::Value Value;
 		    typedef Residual Adaptor;
 		  protected:
 		    typedef Undirector<const Digraph> Undirected;
 		    typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap,
 		                                            FlowMap, Tolerance> ForwardFilter;
 		    typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap,
 		                                             FlowMap, Tolerance> BackwardFilter;
 		    typedef typename Undirected::
 		    template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
 		    typedef FilterArcs<Undirected, ArcFilter> Parent;
 		    const CapacityMap* _capacity;
 		    FlowMap* _flow;
 		    Undirected _graph;
 		    ForwardFilter _forward_filter;
 		    BackwardFilter _backward_filter;
 		    ArcFilter _arc_filter;
 		  public:
 		    /// \brief Constructor of the residual digraph.
 		    ///
 		    /// Constructor of the residual graph. The parameters are the digraph,
 		    /// the flow map, the capacity map and a tolerance object.
 		    Residual(const Digraph& digraph, const CapacityMap& capacity,
 		             FlowMap& flow, const Tolerance& tolerance = Tolerance())
 		      : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
 		        _forward_filter(capacity, flow, tolerance),
 		        _backward_filter(capacity, flow, tolerance),
 		        _arc_filter(_forward_filter, _backward_filter)
+		    {
 		      Parent::setDigraph(_graph);
 		      Parent::setArcFilterMap(_arc_filter);
+		    }
 		    typedef typename Parent::Arc Arc;
 		    /// \brief Gives back the residual capacity of the arc.
 		    ///
 		    /// Gives back the residual capacity of the arc.
 		    Value residualCapacity(const Arc& a) const {
 		      if (Undirected::direction(a)) {
 		        return (*_capacity)[a] - (*_flow)[a];
 		      } else {
 		        return (*_flow)[a];
+		      }
+		    }
 		    /// \brief Augment on the given arc in the residual graph.
 		    ///
 		    /// Augment on the given arc in the residual graph. It increase
 		    /// or decrease the flow on the original arc depend on the direction
 		    /// of the residual arc.
 		    void augment(const Arc& a, const Value& v) const {
 		      if (Undirected::direction(a)) {
 		        _flow->set(a, (*_flow)[a] + v);
 		      } else {
 		        _flow->set(a, (*_flow)[a] - v);
+		      }
+		    }
 		    /// \brief Returns the direction of the arc.
 		    ///
 		    /// Returns true when the arc is same oriented as the original arc.
 		    static bool forward(const Arc& a) {
 		      return Undirected::direction(a);
+		    }
 		    /// \brief Returns the direction of the arc.
 		    ///
 		    /// Returns true when the arc is opposite oriented as the original arc.
 		    static bool backward(const Arc& a) {
 		      return !Undirected::direction(a);
+		    }
 		    /// \brief Gives back the forward oriented residual arc.
 		    ///
 		    /// Gives back the forward oriented residual arc.
 		    static Arc forward(const typename Digraph::Arc& a) {
 		      return Undirected::direct(a, true);
+		    }
 		    /// \brief Gives back the backward oriented residual arc.
 		    ///
 		    /// Gives back the backward oriented residual arc.
 		    static Arc backward(const typename Digraph::Arc& a) {
 		      return Undirected::direct(a, false);
+		    }
 		    /// \brief Residual capacity map.
 		    ///
 		    /// In generic residual graph the residual capacity can be obtained
 		    /// as a map.
 		    class ResidualCapacity {
 		    protected:
 		      const Adaptor* _adaptor;
 		    public:
 		      /// The Key type
 		      typedef Arc Key;
 		      /// The Value type
 		      typedef typename _CapacityMap::Value Value;
 		      /// Constructor
 		      ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {}
 		      /// \e
 		      Value operator[](const Arc& a) const {
 		        return _adaptor->residualCapacity(a);
+		      }
 		    };
 		  };
 		  template <typename _Digraph>
 		  class SplitNodesBase {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef DigraphAdaptorBase<const _Digraph> Parent;
 		    typedef SplitNodesBase 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 SplitNodesBase;
 		      template <typename T> friend class NodeMapBase;
 		    private:
 		      bool _in;
 		      Node(DigraphNode node, bool in)
 		        : DigraphNode(node), _in(in) {}
 		    public:
 		      Node() {}
 		      Node(Invalid) : DigraphNode(INVALID), _in(true) {}
 		      bool operator==(const Node& node) const {
 		        return DigraphNode::operator==(node) && _in == node._in;
+		      }
 		      bool operator!=(const Node& node) const {
 		        return !(*this == node);
+		      }
 		      bool operator<(const Node& node) const {
 		        return DigraphNode::operator<(node) ||
 		          (DigraphNode::operator==(node) && _in < node._in);
+		      }
 		    };
 		    class Arc {
 		      friend class SplitNodesBase;
 		      template <typename T> friend class ArcMapBase;
 		    private:
 		      typedef BiVariant<DigraphArc, DigraphNode> ArcImpl;
 		      explicit Arc(const DigraphArc& arc) : _item(arc) {}
 		      explicit Arc(const DigraphNode& node) : _item(node) {}
 		      ArcImpl _item;
 		    public:
 		      Arc() {}
 		      Arc(Invalid) : _item(DigraphArc(INVALID)) {}
 		      bool operator==(const Arc& arc) const {
 		        if (_item.firstState()) {
 		          if (arc._item.firstState()) {
 		            return _item.first() == arc._item.first();
+		          }
 		        } else {
 		          if (arc._item.secondState()) {
 		            return _item.second() == arc._item.second();
+		          }
+		        }
 		        return false;
+		      }
 		      bool operator!=(const Arc& arc) const {
 		        return !(*this == arc);
+		      }
 		      bool operator<(const Arc& arc) const {
 		        if (_item.firstState()) {
 		          if (arc._item.firstState()) {
 		            return _item.first() < arc._item.first();
+		          }
 		          return false;
 		        } else {
 		          if (arc._item.secondState()) {
 		            return _item.second() < arc._item.second();
+		          }
 		          return true;
+		        }
+		      }
 		      operator DigraphArc() const { return _item.first(); }
 		      operator DigraphNode() const { return _item.second(); }
 		    };
 		    void first(Node& n) const {
 		      _digraph->first(n);
 		      n._in = true;
+		    }
 		    void next(Node& n) const {
 		      if (n._in) {
 		        n._in = false;
 		      } else {
 		        n._in = true;
 		        _digraph->next(n);
+		      }
+		    }
 		    void first(Arc& e) const {
 		      e._item.setSecond();
 		      _digraph->first(e._item.second());
 		      if (e._item.second() == INVALID) {
 		        e._item.setFirst();
 		        _digraph->first(e._item.first());
+		      }
+		    }
 		    void next(Arc& e) const {
 		      if (e._item.secondState()) {
 		        _digraph->next(e._item.second());
 		        if (e._item.second() == INVALID) {
 		          e._item.setFirst();
 		          _digraph->first(e._item.first());
+		        }
 		      } else {
 		        _digraph->next(e._item.first());
+		      }
+		    }
 		    void firstOut(Arc& e, const Node& n) const {
 		      if (n._in) {
 		        e._item.setSecond(n);
 		      } else {
 		        e._item.setFirst();
 		        _digraph->firstOut(e._item.first(), n);
+		      }
+		    }
 		    void nextOut(Arc& e) const {
 		      if (!e._item.firstState()) {
 		        e._item.setFirst(INVALID);
 		      } else {
 		        _digraph->nextOut(e._item.first());
+		      }
+		    }
 		    void firstIn(Arc& e, const Node& n) const {
 		      if (!n._in) {
 		        e._item.setSecond(n);
 		      } else {
 		        e._item.setFirst();
 		        _digraph->firstIn(e._item.first(), n);
+		      }
+		    }
 		    void nextIn(Arc& e) const {
 		      if (!e._item.firstState()) {
 		        e._item.setFirst(INVALID);
 		      } else {
 		        _digraph->nextIn(e._item.first());
+		      }
+		    }
 		    Node source(const Arc& e) const {
 		      if (e._item.firstState()) {
 		        return Node(_digraph->source(e._item.first()), false);
 		      } else {
 		        return Node(e._item.second(), true);
+		      }
+		    }
 		    Node target(const Arc& e) const {
 		      if (e._item.firstState()) {
 		        return Node(_digraph->target(e._item.first()), true);
 		      } else {
 		        return Node(e._item.second(), false);
+		      }
+		    }
 		    int id(const Node& n) const {
 		      return (_digraph->id(n) << 1) | (n._in ? 0 : 1);
+		    }
 		    Node nodeFromId(int ix) const {
 		      return Node(_digraph->nodeFromId(ix >> 1), (ix & 1) == 0);
+		    }
 		    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);
+		    }
 		    static bool inNode(const Node& n) {
 		      return n._in;
+		    }
 		    static bool outNode(const Node& n) {
 		      return !n._in;
+		    }
 		    static bool origArc(const Arc& e) {
 		      return e._item.firstState();
+		    }
 		    static bool bindArc(const Arc& e) {
 		      return e._item.secondState();
+		    }
 		    static Node inNode(const DigraphNode& n) {
 		      return Node(n, true);
+		    }
 		    static Node outNode(const DigraphNode& n) {
 		      return Node(n, false);
+		    }
 		    static Arc arc(const DigraphNode& n) {
 		      return Arc(n);
+		    }
 		    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);
+		          }
+		        }
 		      } else {
 		        if (inNode(v)) {
 		          return Arc(::lemon::findArc(*_digraph, u, v, prev));
+		        }
+		      }
 		      return INVALID;
+		    }
 		  private:
 		    template <typename _Value>
 		    class NodeMapBase
 		      : public MapTraits<typename Parent::template NodeMap<_Value> > {
 		      typedef typename Parent::template NodeMap<_Value> NodeImpl;
 		    public:
 		      typedef Node Key;
 		      typedef _Value Value;
 		      NodeMapBase(const Adaptor& adaptor)
 		        : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
 		      NodeMapBase(const Adaptor& adaptor, const Value& value)
 		        : _in_map(*adaptor._digraph, value),
 		          _out_map(*adaptor._digraph, value) {}
 		      void set(const Node& key, const Value& val) {
 		        if (Adaptor::inNode(key)) { _in_map.set(key, val); }
 		        else {_out_map.set(key, val); }
+		      }
 		      typename MapTraits<NodeImpl>::ReturnValue
 		      operator[](const Node& key) {
 		        if (Adaptor::inNode(key)) { return _in_map[key]; }
 		        else { return _out_map[key]; }
+		      }
 		      typename MapTraits<NodeImpl>::ConstReturnValue
 		      operator[](const Node& key) const {
 		        if (Adaptor::inNode(key)) { return _in_map[key]; }
 		        else { return _out_map[key]; }
+		      }
 		    private:
 		      NodeImpl _in_map, _out_map;
 		    };
 		    template <typename _Value>
 		    class ArcMapBase
 		      : public MapTraits<typename Parent::template ArcMap<_Value> > {
 		      typedef typename Parent::template ArcMap<_Value> ArcImpl;
 		      typedef typename Parent::template NodeMap<_Value> NodeImpl;
 		    public:
 		      typedef Arc Key;
 		      typedef _Value Value;
 		      ArcMapBase(const Adaptor& adaptor)
 		        : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
 		      ArcMapBase(const Adaptor& adaptor, const Value& value)
 		        : _arc_map(*adaptor._digraph, value),
 		          _node_map(*adaptor._digraph, value) {}
 		      void set(const Arc& key, const Value& val) {
 		        if (Adaptor::origArc(key)) {
 		          _arc_map.set(key._item.first(), val);
 		        } else {
 		          _node_map.set(key._item.second(), val);
+		        }
+		      }
 		      typename MapTraits<ArcImpl>::ReturnValue
 		      operator[](const Arc& key) {
 		        if (Adaptor::origArc(key)) {
 		          return _arc_map[key._item.first()];
 		        } else {
 		          return _node_map[key._item.second()];
+		        }
+		      }
 		      typename MapTraits<ArcImpl>::ConstReturnValue
 		      operator[](const Arc& key) const {
 		        if (Adaptor::origArc(key)) {
 		          return _arc_map[key._item.first()];
 		        } else {
 		          return _node_map[key._item.second()];
+		        }
+		      }
 		    private:
 		      ArcImpl _arc_map;
 		      NodeImpl _node_map;
 		    };
 		  public:
 		    template <typename _Value>
 		    class NodeMap
 		      : public SubMapExtender<Adaptor, NodeMapBase<_Value> >
+		    {
 		    public:
 		      typedef _Value Value;
 		      typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent;
 		      NodeMap(const Adaptor& adaptor)
 		        : Parent(adaptor) {}
 		      NodeMap(const Adaptor& adaptor, const Value& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class ArcMap
 		      : public SubMapExtender<Adaptor, ArcMapBase<_Value> >
+		    {
 		    public:
 		      typedef _Value Value;
 		      typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
 		      ArcMap(const Adaptor& adaptor)
 		        : Parent(adaptor) {}
 		      ArcMap(const Adaptor& adaptor, const Value& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  protected:
 		    SplitNodesBase() : _digraph(0) {}
 		    Digraph* _digraph;
 		    void setDigraph(Digraph& digraph) {
 		      _digraph = &digraph;
+		    }
 		  };
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Split the nodes of a directed graph
 		  ///
 		  /// The SplitNodes adaptor splits each node into an in-node and an
 		  /// out-node. Formaly, the adaptor replaces each \f$ u \f$ node in
 		  /// the digraph with two nodes(namely node \f$ u_{in} \f$ and node
 		  /// \f$ u_{out} \f$). If there is a \f$ (v, u) \f$ arc in the
 		  /// original digraph the new target of the arc will be \f$ u_{in} \f$
 		  /// and similarly the source of the original \f$ (u, v) \f$ arc
 		  /// will be \f$ u_{out} \f$.  The adaptor will add for each node in
 		  /// the original digraph an additional arc which connects
 		  /// \f$ (u_{in}, u_{out}) \f$.
 		  ///
 		  /// The aim of this class is to run algorithm with node costs if the
 		  /// algorithm can use directly just arc costs. In this case we should use
 		  /// a \c SplitNodes and set the node cost of the graph to the
 		  /// bind arc in the adapted graph.
 		  ///
 		  /// \tparam _Digraph It must be conform to the \ref concepts::Digraph
 		  /// "Digraph concept". The type can be specified to be const.
 		  template <typename _Digraph>
 		  class SplitNodes
 		    : public DigraphAdaptorExtender<SplitNodesBase<_Digraph> > {
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef DigraphAdaptorExtender<SplitNodesBase<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.
 		    SplitNodes(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 {
 		          return _out_map[key];
+		        }
+		      }
 		      /// \brief The const subscript operator.
 		      ///
 		      /// The const subscript operator.
 		      Value operator[](const Key& key) const {
 		        if (Parent::inNode(key)) {
 		          return _in_map[key];
 		        } else {
 		          return _out_map[key];
+		        }
+		      }
 		      /// \brief The setter function of the map.
 		      ///
 		      /// The setter function of the map.
 		      void set(const Key& key, const Value& value) {
 		        if (Parent::inNode(key)) {
 		          _in_map.set(key, value);
 		        } else {
 		          _out_map.set(key, value);
+		        }
+		      }
 		    private:
 		      InNodeMap& _in_map;
 		      OutNodeMap& _out_map;
 		    };
 		    /// \brief Just gives back a combined node map
 		    ///
 		    /// Just gives back a combined node map
 		    template <typename InNodeMap, typename OutNodeMap>
 		    static CombinedNodeMap<InNodeMap, OutNodeMap>
 		    combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
 		      return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
+		    }
 		    template <typename InNodeMap, typename OutNodeMap>
 		    static CombinedNodeMap<const InNodeMap, OutNodeMap>
 		    combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
 		      return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
+		    }
 		    template <typename InNodeMap, typename OutNodeMap>
 		    static CombinedNodeMap<InNodeMap, const OutNodeMap>
 		    combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
 		      return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
+		    }
 		    template <typename InNodeMap, typename OutNodeMap>
 		    static CombinedNodeMap<const InNodeMap, const OutNodeMap>
 		    combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
 		      return CombinedNodeMap<const InNodeMap,
 		        const OutNodeMap>(in_map, out_map);
+		    }
 		    /// \brief ArcMap combined from an original ArcMap and a NodeMap
 		    ///
 		    /// This class adapt an original ArcMap and a NodeMap to get an
 		    /// arc map on the adapted digraph
 		    template <typename DigraphArcMap, typename DigraphNodeMap>
 		    class CombinedArcMap {
 		    public:
 		      typedef Arc Key;
 		      typedef typename DigraphArcMap::Value Value;
 		      /// \brief Constructor
 		      ///
 		      /// Constructor.
 		      CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map)
 		        : _arc_map(arc_map), _node_map(node_map) {}
 		      /// \brief The subscript operator.
 		      ///
 		      /// The subscript operator.
 		      void set(const Arc& arc, const Value& val) {
 		        if (Parent::origArc(arc)) {
 		          _arc_map.set(arc, val);
 		        } else {
 		          _node_map.set(arc, val);
+		        }
+		      }
 		      /// \brief The const subscript operator.
 		      ///
 		      /// The const subscript operator.
 		      Value operator[](const Key& arc) const {
 		        if (Parent::origArc(arc)) {
 		          return _arc_map[arc];
 		        } else {
 		          return _node_map[arc];
+		        }
+		      }
 		      /// \brief The const subscript operator.
 		      ///
 		      /// The const subscript operator.
 		      Value& operator[](const Key& arc) {
 		        if (Parent::origArc(arc)) {
 		          return _arc_map[arc];
 		        } else {
 		          return _node_map[arc];
+		        }
+		      }
 		    private:
 		      DigraphArcMap& _arc_map;
 		      DigraphNodeMap& _node_map;
 		    };
 		    /// \brief Just gives back a combined arc map
 		    ///
 		    /// Just gives back a combined arc map
 		    template <typename DigraphArcMap, typename DigraphNodeMap>
 		    static CombinedArcMap<DigraphArcMap, DigraphNodeMap>
 		    combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
 		      return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map);
+		    }
 		    template <typename DigraphArcMap, typename DigraphNodeMap>
 		    static CombinedArcMap<const DigraphArcMap, DigraphNodeMap>
 		    combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) {
 		      return CombinedArcMap<const DigraphArcMap,
 		        DigraphNodeMap>(arc_map, node_map);
+		    }
 		    template <typename DigraphArcMap, typename DigraphNodeMap>
 		    static CombinedArcMap<DigraphArcMap, const DigraphNodeMap>
 		    combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) {
 		      return CombinedArcMap<DigraphArcMap,
 		        const DigraphNodeMap>(arc_map, node_map);
+		    }
 		    template <typename DigraphArcMap, typename DigraphNodeMap>
 		    static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap>
 		    combinedArcMap(const DigraphArcMap& arc_map,
 		                   const DigraphNodeMap& node_map) {
 		      return CombinedArcMap<const DigraphArcMap,
 		        const DigraphNodeMap>(arc_map, node_map);
+		    }
 		  };
 		  /// \brief Just gives back a node splitter
 		  ///
 		  /// Just gives back a node splitter
 		  template<typename Digraph>
 		  SplitNodes<Digraph>
 		  splitNodes(const Digraph& digraph) {
 		    return SplitNodes<Digraph>(digraph);
+		  }
 		} //namespace lemon
 		#endif //LEMON_ADAPTORS_H

lemon/bits/graph_adaptor_extender.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H
 		#define LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/bits/default_map.h>
 		namespace lemon {
 		  template <typename _Digraph>
 		  class DigraphAdaptorExtender : public _Digraph {
 		  public:
 		    typedef _Digraph Parent;
 		    typedef _Digraph Digraph;
 		    typedef DigraphAdaptorExtender Adaptor;
 		    // Base extensions
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    int maxId(Node) const {
 		      return Parent::maxNodeId();
+		    }
 		    int maxId(Arc) const {
 		      return Parent::maxArcId();
+		    }
 		    Node fromId(int id, Node) const {
 		      return Parent::nodeFromId(id);
+		    }
 		    Arc fromId(int id, Arc) const {
 		      return Parent::arcFromId(id);
+		    }
 		    Node oppositeNode(const Node &n, const Arc &e) const {
 		      if (n == Parent::source(e))
 		        return Parent::target(e);
 		      else if(n==Parent::target(e))
 		        return Parent::source(e);
 		      else
 		        return INVALID;
+		    }
 		    class NodeIt : public Node {
 		      const Adaptor* _adaptor;
 		    public:
 		      NodeIt() {}
 		      NodeIt(Invalid i) : Node(i) { }
 		      explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
 		        _adaptor->first(static_cast<Node&>(*this));
+		      }
 		      NodeIt(const Adaptor& adaptor, const Node& node)
 		        : Node(node), _adaptor(&adaptor) {}
 		      NodeIt& operator++() {
 		        _adaptor->next(*this);
 		        return *this;
+		      }
 		    };
 		    class ArcIt : public Arc {
 		      const Adaptor* _adaptor;
 		    public:
 		      ArcIt() { }
 		      ArcIt(Invalid i) : Arc(i) { }
 		      explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
 		        _adaptor->first(static_cast<Arc&>(*this));
+		      }
 		      ArcIt(const Adaptor& adaptor, const Arc& e) :
 		        Arc(e), _adaptor(&adaptor) { }
 		      ArcIt& operator++() {
 		        _adaptor->next(*this);
 		        return *this;
+		      }
 		    };
 		    class OutArcIt : public Arc {
 		      const Adaptor* _adaptor;
 		    public:
 		      OutArcIt() { }
 		      OutArcIt(Invalid i) : Arc(i) { }
 		      OutArcIt(const Adaptor& adaptor, const Node& node)
 		        : _adaptor(&adaptor) {
 		        _adaptor->firstOut(*this, node);
+		      }
 		      OutArcIt(const Adaptor& adaptor, const Arc& arc)
 		        : Arc(arc), _adaptor(&adaptor) {}
 		      OutArcIt& operator++() {
 		        _adaptor->nextOut(*this);
 		        return *this;
+		      }
 		    };
 		    class InArcIt : public Arc {
 		      const Adaptor* _adaptor;
 		    public:
 		      InArcIt() { }
 		      InArcIt(Invalid i) : Arc(i) { }
 		      InArcIt(const Adaptor& adaptor, const Node& node)
 		        : _adaptor(&adaptor) {
 		        _adaptor->firstIn(*this, node);
+		      }
 		      InArcIt(const Adaptor& adaptor, const Arc& arc) :
 		        Arc(arc), _adaptor(&adaptor) {}
 		      InArcIt& operator++() {
 		        _adaptor->nextIn(*this);
 		        return *this;
+		      }
 		    };
 		    Node baseNode(const OutArcIt &e) const {
 		      return Parent::source(e);
+		    }
 		    Node runningNode(const OutArcIt &e) const {
 		      return Parent::target(e);
+		    }
 		    Node baseNode(const InArcIt &e) const {
 		      return Parent::target(e);
+		    }
 		    Node runningNode(const InArcIt &e) const {
 		      return Parent::source(e);
+		    }
 		  };
 		  /// \ingroup digraphbits
 		  ///
 		  /// \brief Extender for the GraphAdaptors
 		  template <typename _Graph>
 		  class GraphAdaptorExtender : public _Graph {
 		  public:
 		    typedef _Graph Parent;
 		    typedef _Graph Graph;
 		    typedef GraphAdaptorExtender Adaptor;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    typedef typename Parent::Edge Edge;
 		    // Graph extension
 		    int maxId(Node) const {
 		      return Parent::maxNodeId();
+		    }
 		    int maxId(Arc) const {
 		      return Parent::maxArcId();
+		    }
 		    int maxId(Edge) const {
 		      return Parent::maxEdgeId();
+		    }
 		    Node fromId(int id, Node) const {
 		      return Parent::nodeFromId(id);
+		    }
 		    Arc fromId(int id, Arc) const {
 		      return Parent::arcFromId(id);
+		    }
 		    Edge fromId(int id, Edge) const {
 		      return Parent::edgeFromId(id);
+		    }
 		    Node oppositeNode(const Node &n, const Edge &e) const {
 		      if( n == Parent::u(e))
 		        return Parent::v(e);
 		      else if( n == Parent::v(e))
 		        return Parent::u(e);
 		      else
 		        return INVALID;
+		    }
 		    Arc oppositeArc(const Arc &a) const {
 		      return Parent::direct(a, !Parent::direction(a));
+		    }
 		    using Parent::direct;
 		    Arc direct(const Edge &e, const Node &s) const {
 		      return Parent::direct(e, Parent::u(e) == s);
+		    }
 		    class NodeIt : public Node {
 		      const Adaptor* _adaptor;
 		    public:
 		      NodeIt() {}
 		      NodeIt(Invalid i) : Node(i) { }
 		      explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
 		        _adaptor->first(static_cast<Node&>(*this));
+		      }
 		      NodeIt(const Adaptor& adaptor, const Node& node)
 		        : Node(node), _adaptor(&adaptor) {}
 		      NodeIt& operator++() {
 		        _adaptor->next(*this);
 		        return *this;
+		      }
 		    };
 		    class ArcIt : public Arc {
 		      const Adaptor* _adaptor;
 		    public:
 		      ArcIt() { }
 		      ArcIt(Invalid i) : Arc(i) { }
 		      explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
 		        _adaptor->first(static_cast<Arc&>(*this));
+		      }
 		      ArcIt(const Adaptor& adaptor, const Arc& e) :
 		        Arc(e), _adaptor(&adaptor) { }
 		      ArcIt& operator++() {
 		        _adaptor->next(*this);
 		        return *this;
+		      }
 		    };
 		    class OutArcIt : public Arc {
 		      const Adaptor* _adaptor;
 		    public:
 		      OutArcIt() { }
 		      OutArcIt(Invalid i) : Arc(i) { }
 		      OutArcIt(const Adaptor& adaptor, const Node& node)
 		        : _adaptor(&adaptor) {
 		        _adaptor->firstOut(*this, node);
+		      }
 		      OutArcIt(const Adaptor& adaptor, const Arc& arc)
 		        : Arc(arc), _adaptor(&adaptor) {}
 		      OutArcIt& operator++() {
 		        _adaptor->nextOut(*this);
 		        return *this;
+		      }
 		    };
 		    class InArcIt : public Arc {
 		      const Adaptor* _adaptor;
 		    public:
 		      InArcIt() { }
 		      InArcIt(Invalid i) : Arc(i) { }
 		      InArcIt(const Adaptor& adaptor, const Node& node)
 		        : _adaptor(&adaptor) {
 		        _adaptor->firstIn(*this, node);
+		      }
 		      InArcIt(const Adaptor& adaptor, const Arc& arc) :
 		        Arc(arc), _adaptor(&adaptor) {}
 		      InArcIt& operator++() {
 		        _adaptor->nextIn(*this);
 		        return *this;
+		      }
 		    };
 		    class EdgeIt : public Parent::Edge {
 		      const Adaptor* _adaptor;
 		    public:
 		      EdgeIt() { }
 		      EdgeIt(Invalid i) : Edge(i) { }
 		      explicit EdgeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
 		        _adaptor->first(static_cast<Edge&>(*this));
+		      }
 		      EdgeIt(const Adaptor& adaptor, const Edge& e) :
 		        Edge(e), _adaptor(&adaptor) { }
 		      EdgeIt& operator++() {
 		        _adaptor->next(*this);
 		        return *this;
+		      }
 		    };
 		    class IncEdgeIt : public Edge {
 		      friend class GraphAdaptorExtender;
 		      const Adaptor* _adaptor;
 		      bool direction;
 		    public:
 		      IncEdgeIt() { }
 		      IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
 		      IncEdgeIt(const Adaptor& adaptor, const Node &n) : _adaptor(&adaptor) {
 		        _adaptor->firstInc(static_cast<Edge&>(*this), direction, n);
+		      }
 		      IncEdgeIt(const Adaptor& adaptor, const Edge &e, const Node &n)
 		        : _adaptor(&adaptor), Edge(e) {
 		        direction = (_adaptor->u(e) == n);
+		      }
 		      IncEdgeIt& operator++() {
 		        _adaptor->nextInc(*this, direction);
 		        return *this;
+		      }
 		    };
 		    Node baseNode(const OutArcIt &a) const {
 		      return Parent::source(a);
+		    }
 		    Node runningNode(const OutArcIt &a) const {
 		      return Parent::target(a);
+		    }
 		    Node baseNode(const InArcIt &a) const {
 		      return Parent::target(a);
+		    }
 		    Node runningNode(const InArcIt &a) const {
 		      return Parent::source(a);
+		    }
 		    Node baseNode(const IncEdgeIt &e) const {
 		      return e.direction ? Parent::u(e) : Parent::v(e);
+		    }
 		    Node runningNode(const IncEdgeIt &e) const {
 		      return e.direction ? Parent::v(e) : Parent::u(e);
+		    }
 		  };
+		}
 		#endif

lemon/bits/variant.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BITS_VARIANT_H
 		#define LEMON_BITS_VARIANT_H
 		#include <lemon/assert.h>
 		/// \file
 		/// \brief Variant types
 		namespace lemon {
 		  namespace _variant_bits {
 		    template <int left, int right>
 		    struct CTMax {
 		      static const int value = left < right ? right : left;
 		    };
+		  }
 		  /// \brief Simple Variant type for two types
 		  ///
 		  /// Simple Variant type for two types. The Variant type is a type
 		  /// safe union. The C++ has strong limitations for using unions, by
 		  /// example we can not store type with non default constructor or
 		  /// destructor in an union. This class always knowns the current
 		  /// state of the variant and it cares for the proper construction
 		  /// and destruction.
 		  template <typename _First, typename _Second>
 		  class BiVariant {
 		  public:
 		    /// \brief The \c First type.
 		    typedef _First First;
 		    /// \brief The \c Second type.
 		    typedef _Second Second;
 		    /// \brief Constructor
 		    ///
 		    /// This constructor initalizes to the default value of the \c First
 		    /// type.
 		    BiVariant() {
 		      flag = true;
 		      new(reinterpret_cast<First*>(data)) First();
+		    }
 		    /// \brief Constructor
 		    ///
 		    /// This constructor initalizes to the given value of the \c First
 		    /// type.
 		    BiVariant(const First& f) {
 		      flag = true;
 		      new(reinterpret_cast<First*>(data)) First(f);
+		    }
 		    /// \brief Constructor
 		    ///
 		    /// This constructor initalizes to the given value of the \c
 		    /// Second type.
 		    BiVariant(const Second& s) {
 		      flag = false;
 		      new(reinterpret_cast<Second*>(data)) Second(s);
+		    }
 		    /// \brief Copy constructor
 		    ///
 		    /// Copy constructor
 		    BiVariant(const BiVariant& bivariant) {
 		      flag = bivariant.flag;
 		      if (flag) {
 		        new(reinterpret_cast<First*>(data)) First(bivariant.first());
 		      } else {
 		        new(reinterpret_cast<Second*>(data)) Second(bivariant.second());
+		      }
+		    }
 		    /// \brief Destrcutor
 		    ///
 		    /// Destructor
 		    ~BiVariant() {
 		      destroy();
+		    }
 		    /// \brief Set to the default value of the \c First type.
 		    ///
 		    /// This function sets the variant to the default value of the \c
 		    /// First type.
 		    BiVariant& setFirst() {
 		      destroy();
 		      flag = true;
 		      new(reinterpret_cast<First*>(data)) First();
 		      return *this;
+		    }
 		    /// \brief Set to the given value of the \c First type.
 		    ///
 		    /// This function sets the variant to the given value of the \c
 		    /// First type.
 		    BiVariant& setFirst(const First& f) {
 		      destroy();
 		      flag = true;
 		      new(reinterpret_cast<First*>(data)) First(f);
 		      return *this;
+		    }
 		    /// \brief Set to the default value of the \c Second type.
 		    ///
 		    /// This function sets the variant to the default value of the \c
 		    /// Second type.
 		    BiVariant& setSecond() {
 		      destroy();
 		      flag = false;
 		      new(reinterpret_cast<Second*>(data)) Second();
 		      return *this;
+		    }
 		    /// \brief Set to the given value of the \c Second type.
 		    ///
 		    /// This function sets the variant to the given value of the \c
 		    /// Second type.
 		    BiVariant& setSecond(const Second& s) {
 		      destroy();
 		      flag = false;
 		      new(reinterpret_cast<Second*>(data)) Second(s);
 		      return *this;
+		    }
 		    /// \brief Operator form of the \c setFirst()
 		    BiVariant& operator=(const First& f) {
 		      return setFirst(f);
+		    }
 		    /// \brief Operator form of the \c setSecond()
 		    BiVariant& operator=(const Second& s) {
 		      return setSecond(s);
+		    }
 		    /// \brief Assign operator
 		    BiVariant& operator=(const BiVariant& bivariant) {
 		      if (this == &bivariant) return *this;
 		      destroy();
 		      flag = bivariant.flag;
 		      if (flag) {
 		        new(reinterpret_cast<First*>(data)) First(bivariant.first());
 		      } else {
 		        new(reinterpret_cast<Second*>(data)) Second(bivariant.second());
+		      }
 		      return *this;
+		    }
 		    /// \brief Reference to the value
 		    ///
 		    /// Reference to the value of the \c First type.
 		    /// \pre The BiVariant should store value of \c First type.
 		    First& first() {
 		      LEMON_DEBUG(flag, "Variant wrong state");
 		      return *reinterpret_cast<First*>(data);
+		    }
 		    /// \brief Const reference to the value
 		    ///
 		    /// Const reference to the value of the \c First type.
 		    /// \pre The BiVariant should store value of \c First type.
 		    const First& first() const {
 		      LEMON_DEBUG(flag, "Variant wrong state");
 		      return *reinterpret_cast<const First*>(data);
+		    }
 		    /// \brief Operator form of the \c first()
 		    operator First&() { return first(); }
 		    /// \brief Operator form of the const \c first()
 		    operator const First&() const { return first(); }
 		    /// \brief Reference to the value
 		    ///
 		    /// Reference to the value of the \c Second type.
 		    /// \pre The BiVariant should store value of \c Second type.
 		    Second& second() {
 		      LEMON_DEBUG(!flag, "Variant wrong state");
 		      return *reinterpret_cast<Second*>(data);
+		    }
 		    /// \brief Const reference to the value
 		    ///
 		    /// Const reference to the value of the \c Second type.
 		    /// \pre The BiVariant should store value of \c Second type.
 		    const Second& second() const {
 		      LEMON_DEBUG(!flag, "Variant wrong state");
 		      return *reinterpret_cast<const Second*>(data);
+		    }
 		    /// \brief Operator form of the \c second()
 		    operator Second&() { return second(); }
 		    /// \brief Operator form of the const \c second()
 		    operator const Second&() const { return second(); }
 		    /// \brief %True when the variant is in the first state
 		    ///
 		    /// %True when the variant stores value of the \c First type.
 		    bool firstState() const { return flag; }
 		    /// \brief %True when the variant is in the second state
 		    ///
 		    /// %True when the variant stores value of the \c Second type.
 		    bool secondState() const { return !flag; }
 		  private:
 		    void destroy() {
 		      if (flag) {
 		        reinterpret_cast<First*>(data)->~First();
 		      } else {
 		        reinterpret_cast<Second*>(data)->~Second();
+		      }
+		    }
 		    char data[_variant_bits::CTMax<sizeof(First), sizeof(Second)>::value];
 		    bool flag;
 		  };
 		  namespace _variant_bits {
 		    template <int _idx, typename _TypeMap>
 		    struct Memory {
 		      typedef typename _TypeMap::template Map<_idx>::Type Current;
 		      static void destroy(int index, char* place) {
 		        if (index == _idx) {
 		          reinterpret_cast<Current*>(place)->~Current();
 		        } else {
 		          Memory<_idx - 1, _TypeMap>::destroy(index, place);
+		        }
+		      }
 		      static void copy(int index, char* to, const char* from) {
 		        if (index == _idx) {
 		          new (reinterpret_cast<Current*>(to))
 		            Current(reinterpret_cast<const Current*>(from));
 		        } else {
 		          Memory<_idx - 1, _TypeMap>::copy(index, to, from);
+		        }
+		      }
 		    };
 		    template <typename _TypeMap>
 		    struct Memory<-1, _TypeMap> {
 		      static void destroy(int, char*) {
 		        LEMON_DEBUG(false, "Variant wrong index.");
+		      }
 		      static void copy(int, char*, const char*) {
 		        LEMON_DEBUG(false, "Variant wrong index.");
+		      }
 		    };
 		    template <int _idx, typename _TypeMap>
 		    struct Size {
 		      static const int value =
 		      CTMax<sizeof(typename _TypeMap::template Map<_idx>::Type),
 		            Size<_idx - 1, _TypeMap>::value>::value;
 		    };
 		    template <typename _TypeMap>
 		    struct Size<0, _TypeMap> {
 		      static const int value =
 		      sizeof(typename _TypeMap::template Map<0>::Type);
 		    };
+		  }
 		  /// \brief Variant type
 		  ///
 		  /// Simple Variant type. The Variant type is a type safe union. The
 		  /// C++ has strong limitations for using unions, for example we
 		  /// cannot store type with non default constructor or destructor in
 		  /// a union. This class always knowns the current state of the
 		  /// variant and it cares for the proper construction and
 		  /// destruction.
 		  ///
 		  /// \param _num The number of the types which can be stored in the
 		  /// variant type.
 		  /// \param _TypeMap This class describes the types of the Variant. The
 		  /// _TypeMap::Map<index>::Type should be a valid type for each index
 		  /// in the range {0, 1, ..., _num - 1}. The \c VariantTypeMap is helper
 		  /// class to define such type mappings up to 10 types.
 		  ///
 		  /// And the usage of the class:
 		  ///\code
 		  /// typedef Variant<3, VariantTypeMap<int, std::string, double> > MyVariant;
 		  /// MyVariant var;
 		  /// var.set<0>(12);
 		  /// std::cout << var.get<0>() << std::endl;
 		  /// var.set<1>("alpha");
 		  /// std::cout << var.get<1>() << std::endl;
 		  /// var.set<2>(0.75);
 		  /// std::cout << var.get<2>() << std::endl;
 		  ///\endcode
 		  ///
 		  /// The result of course:
 		  ///\code
 		  /// 12
 		  /// alpha
 		  /// 0.75
 		  ///\endcode
 		  template <int _num, typename _TypeMap>
 		  class Variant {
 		  public:
 		    static const int num = _num;
 		    typedef _TypeMap TypeMap;
 		    /// \brief Constructor
 		    ///
 		    /// This constructor initalizes to the default value of the \c type
 		    /// with 0 index.
 		    Variant() {
 		      flag = 0;
 		      new(reinterpret_cast<typename TypeMap::template Map<0>::Type*>(data))
 		        typename TypeMap::template Map<0>::Type();
+		    }
 		    /// \brief Copy constructor
 		    ///
 		    /// Copy constructor
 		    Variant(const Variant& variant) {
 		      flag = variant.flag;
 		      _variant_bits::Memory<num - 1, TypeMap>::copy(flag, data, variant.data);
+		    }
 		    /// \brief Assign operator
 		    ///
 		    /// Assign operator
 		    Variant& operator=(const Variant& variant) {
 		      if (this == &variant) return *this;
 		      _variant_bits::Memory<num - 1, TypeMap>::
 		        destroy(flag, data);
 		      flag = variant.flag;
 		      _variant_bits::Memory<num - 1, TypeMap>::
 		        copy(flag, data, variant.data);
 		      return *this;
+		    }
 		    /// \brief Destrcutor
 		    ///
 		    /// Destructor
 		    ~Variant() {
 		      _variant_bits::Memory<num - 1, TypeMap>::destroy(flag, data);
+		    }
 		    /// \brief Set to the default value of the type with \c _idx index.
 		    ///
 		    /// This function sets the variant to the default value of the
 		    /// type with \c _idx index.
 		    template <int _idx>
 		    Variant& set() {
 		      _variant_bits::Memory<num - 1, TypeMap>::destroy(flag, data);
 		      flag = _idx;
 		      new(reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>(data))
 		        typename TypeMap::template Map<_idx>::Type();
 		      return *this;
+		    }
 		    /// \brief Set to the given value of the type with \c _idx index.
 		    ///
 		    /// This function sets the variant to the given value of the type
 		    /// with \c _idx index.
 		    template <int _idx>
 		    Variant& set(const typename _TypeMap::template Map<_idx>::Type& init) {
 		      _variant_bits::Memory<num - 1, TypeMap>::destroy(flag, data);
 		      flag = _idx;
 		      new(reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>(data))
 		        typename TypeMap::template Map<_idx>::Type(init);
 		      return *this;
+		    }
 		    /// \brief Gets the current value of the type with \c _idx index.
 		    ///
 		    /// Gets the current value of the type with \c _idx index.
 		    template <int _idx>
 		    const typename TypeMap::template Map<_idx>::Type& get() const {
 		      LEMON_DEBUG(_idx == flag, "Variant wrong index");
 		      return *reinterpret_cast<const typename TypeMap::
 		        template Map<_idx>::Type*>(data);
+		    }
 		    /// \brief Gets the current value of the type with \c _idx index.
 		    ///
 		    /// Gets the current value of the type with \c _idx index.
 		    template <int _idx>
 		    typename _TypeMap::template Map<_idx>::Type& get() {
 		      LEMON_DEBUG(_idx == flag, "Variant wrong index");
 		      return *reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>
 		        (data);
+		    }
 		    /// \brief Returns the current state of the variant.
 		    ///
 		    /// Returns the current state of the variant.
 		    int state() const {
 		      return flag;
+		    }
 		  private:
 		    char data[_variant_bits::Size<num - 1, TypeMap>::value];
 		    int flag;
 		  };
 		  namespace _variant_bits {
 		    template <int _index, typename _List>
 		    struct Get {
 		      typedef typename Get<_index - 1, typename _List::Next>::Type Type;
 		    };
 		    template <typename _List>
 		    struct Get<0, _List> {
 		      typedef typename _List::Type Type;
 		    };
 		    struct List {};
 		    template <typename _Type, typename _List>
 		    struct Insert {
 		      typedef _List Next;
 		      typedef _Type Type;
 		    };
 		    template <int _idx, typename _T0, typename _T1, typename _T2,
 		              typename _T3, typename _T5, typename _T4, typename _T6,
 		              typename _T7, typename _T8, typename _T9>
 		    struct Mapper {
 		      typedef List L10;
 		      typedef Insert<_T9, L10> L9;
 		      typedef Insert<_T8, L9> L8;
 		      typedef Insert<_T7, L8> L7;
 		      typedef Insert<_T6, L7> L6;
 		      typedef Insert<_T5, L6> L5;
 		      typedef Insert<_T4, L5> L4;
 		      typedef Insert<_T3, L4> L3;
 		      typedef Insert<_T2, L3> L2;
 		      typedef Insert<_T1, L2> L1;
 		      typedef Insert<_T0, L1> L0;
 		      typedef typename Get<_idx, L0>::Type Type;
 		    };
+		  }
 		  /// \brief Helper class for Variant
 		  ///
 		  /// Helper class to define type mappings for Variant. This class
 		  /// converts the template parameters to be mappable by integer.
 		  /// \see Variant
 		  template <
 		    typename _T0,
 		    typename _T1 = void, typename _T2 = void, typename _T3 = void,
 		    typename _T5 = void, typename _T4 = void, typename _T6 = void,
 		    typename _T7 = void, typename _T8 = void, typename _T9 = void>
 		  struct VariantTypeMap {
 		    template <int _idx>
 		    struct Map {
 		      typedef typename _variant_bits::
 		      Mapper<_idx, _T0, _T1, _T2, _T3, _T4, _T5, _T6, _T7, _T8, _T9>::Type
 		      Type;
 		    };
 		  };
+		}
 		#endif

lemon/connectivity.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_TOPOLOGY_H
 		#define LEMON_TOPOLOGY_H
 		#include <lemon/dfs.h>
 		#include <lemon/bfs.h>
 		#include <lemon/core.h>
 		#include <lemon/maps.h>
 		#include <lemon/adaptors.h>
 		#include <lemon/concepts/digraph.h>
 		#include <lemon/concepts/graph.h>
 		#include <lemon/concept_check.h>
 		#include <stack>
 		#include <functional>
 		/// \ingroup connectivity
 		/// \file
 		/// \brief Connectivity algorithms
 		///
 		/// Connectivity algorithms
 		namespace lemon {
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Check whether the given undirected graph is connected.
 		  ///
 		  /// Check whether the given undirected graph is connected.
 		  /// \param graph The undirected graph.
 		  /// \return %True when there is path between any two nodes in the graph.
 		  /// \note By definition, the empty graph is connected.
 		  template <typename Graph>
 		  bool connected(const Graph& graph) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::NodeIt NodeIt;
 		    if (NodeIt(graph) == INVALID) return true;
 		    Dfs<Graph> dfs(graph);
 		    dfs.run(NodeIt(graph));
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        return false;
+		      }
+		    }
 		    return true;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Count the number of connected components of an undirected graph
 		  ///
 		  /// Count the number of connected components of an undirected graph
 		  ///
 		  /// \param graph The graph. It must be undirected.
 		  /// \return The number of components
 		  /// \note By definition, the empty graph consists
 		  /// of zero connected components.
 		  template <typename Graph>
 		  int countConnectedComponents(const Graph &graph) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::Arc Arc;
 		    typedef NullMap<Node, Arc> PredMap;
 		    typedef NullMap<Node, int> DistMap;
 		    int compNum = 0;
 		    typename Bfs<Graph>::
 		      template SetPredMap<PredMap>::
 		      template SetDistMap<DistMap>::
 		      Create bfs(graph);
 		    PredMap predMap;
 		    bfs.predMap(predMap);
 		    DistMap distMap;
 		    bfs.distMap(distMap);
 		    bfs.init();
 		    for(typename Graph::NodeIt n(graph); n != INVALID; ++n) {
 		      if (!bfs.reached(n)) {
 		        bfs.addSource(n);
 		        bfs.start();
 		        ++compNum;
+		      }
+		    }
 		    return compNum;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Find the connected components of an undirected graph
 		  ///
 		  /// Find the connected components of an undirected graph.
 		  ///
 		  /// \param graph The graph. It must be undirected.
 		  /// \retval compMap A writable node map. The values will be set from 0 to
 		  /// the number of the connected components minus one. Each values of the map
 		  /// will be set exactly once, the values of a certain component will be
 		  /// set continuously.
 		  /// \return The number of components
 		  ///
 		  template <class Graph, class NodeMap>
 		  int connectedComponents(const Graph &graph, NodeMap &compMap) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::Arc Arc;
 		    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
 		    typedef NullMap<Node, Arc> PredMap;
 		    typedef NullMap<Node, int> DistMap;
 		    int compNum = 0;
 		    typename Bfs<Graph>::
 		      template SetPredMap<PredMap>::
 		      template SetDistMap<DistMap>::
 		      Create bfs(graph);
 		    PredMap predMap;
 		    bfs.predMap(predMap);
 		    DistMap distMap;
 		    bfs.distMap(distMap);
 		    bfs.init();
 		    for(typename Graph::NodeIt n(graph); n != INVALID; ++n) {
 		      if(!bfs.reached(n)) {
 		        bfs.addSource(n);
 		        while (!bfs.emptyQueue()) {
 		          compMap.set(bfs.nextNode(), compNum);
 		          bfs.processNextNode();
+		        }
 		        ++compNum;
+		      }
+		    }
 		    return compNum;
+		  }
 		  namespace _topology_bits {
 		    template <typename Digraph, typename Iterator >
 		    struct LeaveOrderVisitor : public DfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Node Node;
 		      LeaveOrderVisitor(Iterator it) : _it(it) {}
 		      void leave(const Node& node) {
 		        *(_it++) = node;
+		      }
 		    private:
 		      Iterator _it;
 		    };
 		    template <typename Digraph, typename Map>
 		    struct FillMapVisitor : public DfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Node Node;
 		      typedef typename Map::Value Value;
 		      FillMapVisitor(Map& map, Value& value)
 		        : _map(map), _value(value) {}
 		      void reach(const Node& node) {
 		        _map.set(node, _value);
+		      }
 		    private:
 		      Map& _map;
 		      Value& _value;
 		    };
 		    template <typename Digraph, typename ArcMap>
 		    struct StronglyConnectedCutEdgesVisitor : public DfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Node Node;
 		      typedef typename Digraph::Arc Arc;
 		      StronglyConnectedCutEdgesVisitor(const Digraph& digraph,
 		                                       ArcMap& cutMap,
 		                                       int& cutNum)
 		        : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum),
 		          _compMap(digraph), _num(0) {
+		      }
 		      void stop(const Node&) {
 		        ++_num;
+		      }
 		      void reach(const Node& node) {
 		        _compMap.set(node, _num);
+		      }
 		      void examine(const Arc& arc) {
 		         if (_compMap[_digraph.source(arc)] !=
 		             _compMap[_digraph.target(arc)]) {
 		           _cutMap.set(arc, true);
 		           ++_cutNum;
+		         }
+		      }
 		    private:
 		      const Digraph& _digraph;
 		      ArcMap& _cutMap;
 		      int& _cutNum;
 		      typename Digraph::template NodeMap<int> _compMap;
 		      int _num;
 		    };
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Check whether the given directed graph is strongly connected.
 		  ///
 		  /// Check whether the given directed graph is strongly connected. The
 		  /// graph is strongly connected when any two nodes of the graph are
 		  /// connected with directed paths in both direction.
 		  /// \return %False when the graph is not strongly connected.
 		  /// \see connected
 		  ///
 		  /// \note By definition, the empty graph is strongly connected.
 		  template <typename Digraph>
 		  bool stronglyConnected(const Digraph& digraph) {
 		    checkConcept<concepts::Digraph, Digraph>();
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typename Digraph::Node source = NodeIt(digraph);
 		    if (source == INVALID) return true;
 		    using namespace _topology_bits;
 		    typedef DfsVisitor<Digraph> Visitor;
 		    Visitor visitor;
 		    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
 		    dfs.init();
 		    dfs.addSource(source);
 		    dfs.start();
 		    for (NodeIt it(digraph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        return false;
+		      }
+		    }
 		    typedef ReverseDigraph<const Digraph> RDigraph;
 		    RDigraph rdigraph(digraph);
 		    typedef DfsVisitor<Digraph> RVisitor;
 		    RVisitor rvisitor;
 		    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
 		    rdfs.init();
 		    rdfs.addSource(source);
 		    rdfs.start();
 		    for (NodeIt it(rdigraph); it != INVALID; ++it) {
 		      if (!rdfs.reached(it)) {
 		        return false;
+		      }
+		    }
 		    return true;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Count the strongly connected components of a directed graph
 		  ///
 		  /// Count the strongly connected components of a directed graph.
 		  /// The strongly connected components are the classes of an
 		  /// equivalence relation on the nodes of the graph. Two nodes are in
 		  /// the same class if they are connected with directed paths in both
 		  /// direction.
 		  ///
 		  /// \param graph The graph.
 		  /// \return The number of components
 		  /// \note By definition, the empty graph has zero
 		  /// strongly connected components.
 		  template <typename Digraph>
 		  int countStronglyConnectedComponents(const Digraph& digraph) {
 		    checkConcept<concepts::Digraph, Digraph>();
 		    using namespace _topology_bits;
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::ArcIt ArcIt;
 		    typedef std::vector<Node> Container;
 		    typedef typename Container::iterator Iterator;
 		    Container nodes(countNodes(digraph));
 		    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
 		    Visitor visitor(nodes.begin());
 		    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
 		    dfs.init();
 		    for (NodeIt it(digraph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    typedef typename Container::reverse_iterator RIterator;
 		    typedef ReverseDigraph<const Digraph> RDigraph;
 		    RDigraph rdigraph(digraph);
 		    typedef DfsVisitor<Digraph> RVisitor;
 		    RVisitor rvisitor;
 		    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
 		    int compNum = 0;
 		    rdfs.init();
 		    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
 		      if (!rdfs.reached(*it)) {
 		        rdfs.addSource(*it);
 		        rdfs.start();
 		        ++compNum;
+		      }
+		    }
 		    return compNum;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Find the strongly connected components of a directed graph
 		  ///
 		  /// Find the strongly connected components of a directed graph.  The
 		  /// strongly connected components are the classes of an equivalence
 		  /// relation on the nodes of the graph. Two nodes are in
 		  /// relationship when there are directed paths between them in both
 		  /// direction. In addition, the numbering of components will satisfy
 		  /// that there is no arc going from a higher numbered component to
 		  /// a lower.
 		  ///
 		  /// \param digraph The digraph.
 		  /// \retval compMap A writable node map. The values will be set from 0 to
 		  /// the number of the strongly connected components minus one. Each value
 		  /// of the map will be set exactly once, the values of a certain component
 		  /// will be set continuously.
 		  /// \return The number of components
 		  ///
 		  template <typename Digraph, typename NodeMap>
 		  int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
 		    checkConcept<concepts::Digraph, Digraph>();
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
 		    using namespace _topology_bits;
 		    typedef std::vector<Node> Container;
 		    typedef typename Container::iterator Iterator;
 		    Container nodes(countNodes(digraph));
 		    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
 		    Visitor visitor(nodes.begin());
 		    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
 		    dfs.init();
 		    for (NodeIt it(digraph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    typedef typename Container::reverse_iterator RIterator;
 		    typedef ReverseDigraph<const Digraph> RDigraph;
 		    RDigraph rdigraph(digraph);
 		    int compNum = 0;
 		    typedef FillMapVisitor<RDigraph, NodeMap> RVisitor;
 		    RVisitor rvisitor(compMap, compNum);
 		    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
 		    rdfs.init();
 		    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
 		      if (!rdfs.reached(*it)) {
 		        rdfs.addSource(*it);
 		        rdfs.start();
 		        ++compNum;
+		      }
+		    }
 		    return compNum;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Find the cut arcs of the strongly connected components.
 		  ///
 		  /// Find the cut arcs of the strongly connected components.
 		  /// The strongly connected components are the classes of an equivalence
 		  /// relation on the nodes of the graph. Two nodes are in relationship
 		  /// when there are directed paths between them in both direction.
 		  /// The strongly connected components are separated by the cut arcs.
 		  ///
 		  /// \param graph The graph.
 		  /// \retval cutMap A writable node map. The values will be set true when the
 		  /// arc is a cut arc.
 		  ///
 		  /// \return The number of cut arcs
 		  template <typename Digraph, typename ArcMap>
 		  int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) {
 		    checkConcept<concepts::Digraph, Digraph>();
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>();
 		    using namespace _topology_bits;
 		    typedef std::vector<Node> Container;
 		    typedef typename Container::iterator Iterator;
 		    Container nodes(countNodes(graph));
 		    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
 		    Visitor visitor(nodes.begin());
 		    DfsVisit<Digraph, Visitor> dfs(graph, visitor);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    typedef typename Container::reverse_iterator RIterator;
 		    typedef ReverseDigraph<const Digraph> RDigraph;
 		    RDigraph rgraph(graph);
 		    int cutNum = 0;
 		    typedef StronglyConnectedCutEdgesVisitor<RDigraph, ArcMap> RVisitor;
 		    RVisitor rvisitor(rgraph, cutMap, cutNum);
 		    DfsVisit<RDigraph, RVisitor> rdfs(rgraph, rvisitor);
 		    rdfs.init();
 		    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
 		      if (!rdfs.reached(*it)) {
 		        rdfs.addSource(*it);
 		        rdfs.start();
+		      }
+		    }
 		    return cutNum;
+		  }
 		  namespace _topology_bits {
 		    template <typename Digraph>
 		    class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Node Node;
 		      typedef typename Digraph::Arc Arc;
 		      typedef typename Digraph::Edge Edge;
 		      CountBiNodeConnectedComponentsVisitor(const Digraph& graph, int &compNum)
 		        : _graph(graph), _compNum(compNum),
 		          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
 		      void start(const Node& node) {
 		        _predMap.set(node, INVALID);
+		      }
 		      void reach(const Node& node) {
 		        _numMap.set(node, _num);
 		        _retMap.set(node, _num);
 		        ++_num;
+		      }
 		      void discover(const Arc& edge) {
 		        _predMap.set(_graph.target(edge), _graph.source(edge));
+		      }
 		      void examine(const Arc& edge) {
 		        if (_graph.source(edge) == _graph.target(edge) &&
 		            _graph.direction(edge)) {
 		          ++_compNum;
 		          return;
+		        }
 		        if (_predMap[_graph.source(edge)] == _graph.target(edge)) {
 		          return;
+		        }
 		        if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
 		          _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
+		        }
+		      }
 		      void backtrack(const Arc& edge) {
 		        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
 		          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
+		        }
 		        if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
 		          ++_compNum;
+		        }
+		      }
 		    private:
 		      const Digraph& _graph;
 		      int& _compNum;
 		      typename Digraph::template NodeMap<int> _numMap;
 		      typename Digraph::template NodeMap<int> _retMap;
 		      typename Digraph::template NodeMap<Node> _predMap;
 		      int _num;
 		    };
 		    template <typename Digraph, typename ArcMap>
 		    class BiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Node Node;
 		      typedef typename Digraph::Arc Arc;
 		      typedef typename Digraph::Edge Edge;
 		      BiNodeConnectedComponentsVisitor(const Digraph& graph,
 		                                       ArcMap& compMap, int &compNum)
 		        : _graph(graph), _compMap(compMap), _compNum(compNum),
 		          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
 		      void start(const Node& node) {
 		        _predMap.set(node, INVALID);
+		      }
 		      void reach(const Node& node) {
 		        _numMap.set(node, _num);
 		        _retMap.set(node, _num);
 		        ++_num;
+		      }
 		      void discover(const Arc& edge) {
 		        Node target = _graph.target(edge);
 		        _predMap.set(target, edge);
 		        _edgeStack.push(edge);
+		      }
 		      void examine(const Arc& edge) {
 		        Node source = _graph.source(edge);
 		        Node target = _graph.target(edge);
 		        if (source == target && _graph.direction(edge)) {
 		          _compMap.set(edge, _compNum);
 		          ++_compNum;
 		          return;
+		        }
 		        if (_numMap[target] < _numMap[source]) {
 		          if (_predMap[source] != _graph.oppositeArc(edge)) {
 		            _edgeStack.push(edge);
+		          }
+		        }
 		        if (_predMap[source] != INVALID &&
 		            target == _graph.source(_predMap[source])) {
 		          return;
+		        }
 		        if (_retMap[source] > _numMap[target]) {
 		          _retMap.set(source, _numMap[target]);
+		        }
+		      }
 		      void backtrack(const Arc& edge) {
 		        Node source = _graph.source(edge);
 		        Node target = _graph.target(edge);
 		        if (_retMap[source] > _retMap[target]) {
 		          _retMap.set(source, _retMap[target]);
+		        }
 		        if (_numMap[source] <= _retMap[target]) {
 		          while (_edgeStack.top() != edge) {
 		            _compMap.set(_edgeStack.top(), _compNum);
 		            _edgeStack.pop();
+		          }
 		          _compMap.set(edge, _compNum);
 		          _edgeStack.pop();
 		          ++_compNum;
+		        }
+		      }
 		    private:
 		      const Digraph& _graph;
 		      ArcMap& _compMap;
 		      int& _compNum;
 		      typename Digraph::template NodeMap<int> _numMap;
 		      typename Digraph::template NodeMap<int> _retMap;
 		      typename Digraph::template NodeMap<Arc> _predMap;
 		      std::stack<Edge> _edgeStack;
 		      int _num;
 		    };
 		    template <typename Digraph, typename NodeMap>
 		    class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Node Node;
 		      typedef typename Digraph::Arc Arc;
 		      typedef typename Digraph::Edge Edge;
 		      BiNodeConnectedCutNodesVisitor(const Digraph& graph, NodeMap& cutMap,
 		                                     int& cutNum)
 		        : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
 		          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
 		      void start(const Node& node) {
 		        _predMap.set(node, INVALID);
 		        rootCut = false;
+		      }
 		      void reach(const Node& node) {
 		        _numMap.set(node, _num);
 		        _retMap.set(node, _num);
 		        ++_num;
+		      }
 		      void discover(const Arc& edge) {
 		        _predMap.set(_graph.target(edge), _graph.source(edge));
+		      }
 		      void examine(const Arc& edge) {
 		        if (_graph.source(edge) == _graph.target(edge) &&
 		            _graph.direction(edge)) {
 		          if (!_cutMap[_graph.source(edge)]) {
 		            _cutMap.set(_graph.source(edge), true);
 		            ++_cutNum;
+		          }
 		          return;
+		        }
 		        if (_predMap[_graph.source(edge)] == _graph.target(edge)) return;
 		        if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
 		          _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
+		        }
+		      }
 		      void backtrack(const Arc& edge) {
 		        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
 		          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
+		        }
 		        if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
 		          if (_predMap[_graph.source(edge)] != INVALID) {
 		            if (!_cutMap[_graph.source(edge)]) {
 		              _cutMap.set(_graph.source(edge), true);
 		              ++_cutNum;
+		            }
 		          } else if (rootCut) {
 		            if (!_cutMap[_graph.source(edge)]) {
 		              _cutMap.set(_graph.source(edge), true);
 		              ++_cutNum;
+		            }
 		          } else {
 		            rootCut = true;
+		          }
+		        }
+		      }
 		    private:
 		      const Digraph& _graph;
 		      NodeMap& _cutMap;
 		      int& _cutNum;
 		      typename Digraph::template NodeMap<int> _numMap;
 		      typename Digraph::template NodeMap<int> _retMap;
 		      typename Digraph::template NodeMap<Node> _predMap;
 		      std::stack<Edge> _edgeStack;
 		      int _num;
 		      bool rootCut;
 		    };
+		  }
 		  template <typename Graph>
 		  int countBiNodeConnectedComponents(const Graph& graph);
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Checks the graph is bi-node-connected.
 		  ///
 		  /// This function checks that the undirected graph is bi-node-connected
 		  /// graph. The graph is bi-node-connected if any two undirected edge is
 		  /// on same circle.
 		  ///
 		  /// \param graph The graph.
 		  /// \return %True when the graph bi-node-connected.
 		  template <typename Graph>
 		  bool biNodeConnected(const Graph& graph) {
 		    return countBiNodeConnectedComponents(graph) <= 1;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Count the biconnected components.
 		  ///
 		  /// This function finds the bi-node-connected components in an undirected
 		  /// graph. The biconnected components are the classes of an equivalence
 		  /// relation on the undirected edges. Two undirected edge is in relationship
 		  /// when they are on same circle.
 		  ///
 		  /// \param graph The graph.
 		  /// \return The number of components.
 		  template <typename Graph>
 		  int countBiNodeConnectedComponents(const Graph& graph) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::NodeIt NodeIt;
 		    using namespace _topology_bits;
 		    typedef CountBiNodeConnectedComponentsVisitor<Graph> Visitor;
 		    int compNum = 0;
 		    Visitor visitor(graph, compNum);
 		    DfsVisit<Graph, Visitor> dfs(graph, visitor);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    return compNum;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Find the bi-node-connected components.
 		  ///
 		  /// This function finds the bi-node-connected components in an undirected
 		  /// graph. The bi-node-connected components are the classes of an equivalence
 		  /// relation on the undirected edges. Two undirected edge are in relationship
 		  /// when they are on same circle.
 		  ///
 		  /// \param graph The graph.
 		  /// \retval compMap A writable uedge map. The values will be set from 0
 		  /// to the number of the biconnected components minus one. Each values
 		  /// of the map will be set exactly once, the values of a certain component
 		  /// will be set continuously.
 		  /// \return The number of components.
 		  ///
 		  template <typename Graph, typename EdgeMap>
 		  int biNodeConnectedComponents(const Graph& graph,
 		                                EdgeMap& compMap) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::NodeIt NodeIt;
 		    typedef typename Graph::Edge Edge;
 		    checkConcept<concepts::WriteMap<Edge, int>, EdgeMap>();
 		    using namespace _topology_bits;
 		    typedef BiNodeConnectedComponentsVisitor<Graph, EdgeMap> Visitor;
 		    int compNum = 0;
 		    Visitor visitor(graph, compMap, compNum);
 		    DfsVisit<Graph, Visitor> dfs(graph, visitor);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    return compNum;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Find the bi-node-connected cut nodes.
 		  ///
 		  /// This function finds the bi-node-connected cut nodes in an undirected
 		  /// graph. The bi-node-connected components are the classes of an equivalence
 		  /// relation on the undirected edges. Two undirected edges are in
 		  /// relationship when they are on same circle. The biconnected components
 		  /// are separted by nodes which are the cut nodes of the components.
 		  ///
 		  /// \param graph The graph.
 		  /// \retval cutMap A writable edge map. The values will be set true when
 		  /// the node separate two or more components.
 		  /// \return The number of the cut nodes.
 		  template <typename Graph, typename NodeMap>
 		  int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::NodeIt NodeIt;
 		    checkConcept<concepts::WriteMap<Node, bool>, NodeMap>();
 		    using namespace _topology_bits;
 		    typedef BiNodeConnectedCutNodesVisitor<Graph, NodeMap> Visitor;
 		    int cutNum = 0;
 		    Visitor visitor(graph, cutMap, cutNum);
 		    DfsVisit<Graph, Visitor> dfs(graph, visitor);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    return cutNum;
+		  }
 		  namespace _topology_bits {
 		    template <typename Digraph>
 		    class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Node Node;
 		      typedef typename Digraph::Arc Arc;
 		      typedef typename Digraph::Edge Edge;
 		      CountBiEdgeConnectedComponentsVisitor(const Digraph& graph, int &compNum)
 		        : _graph(graph), _compNum(compNum),
 		          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
 		      void start(const Node& node) {
 		        _predMap.set(node, INVALID);
+		      }
 		      void reach(const Node& node) {
 		        _numMap.set(node, _num);
 		        _retMap.set(node, _num);
 		        ++_num;
+		      }
 		      void leave(const Node& node) {
 		        if (_numMap[node] <= _retMap[node]) {
 		          ++_compNum;
+		        }
+		      }
 		      void discover(const Arc& edge) {
 		        _predMap.set(_graph.target(edge), edge);
+		      }
 		      void examine(const Arc& edge) {
 		        if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
 		          return;
+		        }
 		        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
 		          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
+		        }
+		      }
 		      void backtrack(const Arc& edge) {
 		        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
 		          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
+		        }
+		      }
 		    private:
 		      const Digraph& _graph;
 		      int& _compNum;
 		      typename Digraph::template NodeMap<int> _numMap;
 		      typename Digraph::template NodeMap<int> _retMap;
 		      typename Digraph::template NodeMap<Arc> _predMap;
 		      int _num;
 		    };
 		    template <typename Digraph, typename NodeMap>
 		    class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Node Node;
 		      typedef typename Digraph::Arc Arc;
 		      typedef typename Digraph::Edge Edge;
 		      BiEdgeConnectedComponentsVisitor(const Digraph& graph,
 		                                       NodeMap& compMap, int &compNum)
 		        : _graph(graph), _compMap(compMap), _compNum(compNum),
 		          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
 		      void start(const Node& node) {
 		        _predMap.set(node, INVALID);
+		      }
 		      void reach(const Node& node) {
 		        _numMap.set(node, _num);
 		        _retMap.set(node, _num);
 		        _nodeStack.push(node);
 		        ++_num;
+		      }
 		      void leave(const Node& node) {
 		        if (_numMap[node] <= _retMap[node]) {
 		          while (_nodeStack.top() != node) {
 		            _compMap.set(_nodeStack.top(), _compNum);
 		            _nodeStack.pop();
+		          }
 		          _compMap.set(node, _compNum);
 		          _nodeStack.pop();
 		          ++_compNum;
+		        }
+		      }
 		      void discover(const Arc& edge) {
 		        _predMap.set(_graph.target(edge), edge);
+		      }
 		      void examine(const Arc& edge) {
 		        if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
 		          return;
+		        }
 		        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
 		          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
+		        }
+		      }
 		      void backtrack(const Arc& edge) {
 		        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
 		          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
+		        }
+		      }
 		    private:
 		      const Digraph& _graph;
 		      NodeMap& _compMap;
 		      int& _compNum;
 		      typename Digraph::template NodeMap<int> _numMap;
 		      typename Digraph::template NodeMap<int> _retMap;
 		      typename Digraph::template NodeMap<Arc> _predMap;
 		      std::stack<Node> _nodeStack;
 		      int _num;
 		    };
 		    template <typename Digraph, typename ArcMap>
 		    class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Node Node;
 		      typedef typename Digraph::Arc Arc;
 		      typedef typename Digraph::Edge Edge;
 		      BiEdgeConnectedCutEdgesVisitor(const Digraph& graph,
 		                                     ArcMap& cutMap, int &cutNum)
 		        : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
 		          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
 		      void start(const Node& node) {
 		        _predMap[node] = INVALID;
+		      }
 		      void reach(const Node& node) {
 		        _numMap.set(node, _num);
 		        _retMap.set(node, _num);
 		        ++_num;
+		      }
 		      void leave(const Node& node) {
 		        if (_numMap[node] <= _retMap[node]) {
 		          if (_predMap[node] != INVALID) {
 		            _cutMap.set(_predMap[node], true);
 		            ++_cutNum;
+		          }
+		        }
+		      }
 		      void discover(const Arc& edge) {
 		        _predMap.set(_graph.target(edge), edge);
+		      }
 		      void examine(const Arc& edge) {
 		        if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
 		          return;
+		        }
 		        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
 		          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
+		        }
+		      }
 		      void backtrack(const Arc& edge) {
 		        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
 		          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
+		        }
+		      }
 		    private:
 		      const Digraph& _graph;
 		      ArcMap& _cutMap;
 		      int& _cutNum;
 		      typename Digraph::template NodeMap<int> _numMap;
 		      typename Digraph::template NodeMap<int> _retMap;
 		      typename Digraph::template NodeMap<Arc> _predMap;
 		      int _num;
 		    };
+		  }
 		  template <typename Graph>
 		  int countBiEdgeConnectedComponents(const Graph& graph);
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Checks that the graph is bi-edge-connected.
 		  ///
 		  /// This function checks that the graph is bi-edge-connected. The undirected
 		  /// graph is bi-edge-connected when any two nodes are connected with two
 		  /// edge-disjoint paths.
 		  ///
 		  /// \param graph The undirected graph.
 		  /// \return The number of components.
 		  template <typename Graph>
 		  bool biEdgeConnected(const Graph& graph) {
 		    return countBiEdgeConnectedComponents(graph) <= 1;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Count the bi-edge-connected components.
 		  ///
 		  /// This function count the bi-edge-connected components in an undirected
 		  /// graph. The bi-edge-connected components are the classes of an equivalence
 		  /// relation on the nodes. Two nodes are in relationship when they are
 		  /// connected with at least two edge-disjoint paths.
 		  ///
 		  /// \param graph The undirected graph.
 		  /// \return The number of components.
 		  template <typename Graph>
 		  int countBiEdgeConnectedComponents(const Graph& graph) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::NodeIt NodeIt;
 		    using namespace _topology_bits;
 		    typedef CountBiEdgeConnectedComponentsVisitor<Graph> Visitor;
 		    int compNum = 0;
 		    Visitor visitor(graph, compNum);
 		    DfsVisit<Graph, Visitor> dfs(graph, visitor);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    return compNum;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Find the bi-edge-connected components.
 		  ///
 		  /// This function finds the bi-edge-connected components in an undirected
 		  /// graph. The bi-edge-connected components are the classes of an equivalence
 		  /// relation on the nodes. Two nodes are in relationship when they are
 		  /// connected at least two edge-disjoint paths.
 		  ///
 		  /// \param graph The graph.
 		  /// \retval compMap A writable node map. The values will be set from 0 to
 		  /// the number of the biconnected components minus one. Each values
 		  /// of the map will be set exactly once, the values of a certain component
 		  /// will be set continuously.
 		  /// \return The number of components.
 		  ///
 		  template <typename Graph, typename NodeMap>
 		  int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::NodeIt NodeIt;
 		    typedef typename Graph::Node Node;
 		    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
 		    using namespace _topology_bits;
 		    typedef BiEdgeConnectedComponentsVisitor<Graph, NodeMap> Visitor;
 		    int compNum = 0;
 		    Visitor visitor(graph, compMap, compNum);
 		    DfsVisit<Graph, Visitor> dfs(graph, visitor);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    return compNum;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Find the bi-edge-connected cut edges.
 		  ///
 		  /// This function finds the bi-edge-connected components in an undirected
 		  /// graph. The bi-edge-connected components are the classes of an equivalence
 		  /// relation on the nodes. Two nodes are in relationship when they are
 		  /// connected with at least two edge-disjoint paths. The bi-edge-connected
 		  /// components are separted by edges which are the cut edges of the
 		  /// components.
 		  ///
 		  /// \param graph The graph.
 		  /// \retval cutMap A writable node map. The values will be set true when the
 		  /// edge is a cut edge.
 		  /// \return The number of cut edges.
 		  template <typename Graph, typename EdgeMap>
 		  int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::NodeIt NodeIt;
 		    typedef typename Graph::Edge Edge;
 		    checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>();
 		    using namespace _topology_bits;
 		    typedef BiEdgeConnectedCutEdgesVisitor<Graph, EdgeMap> Visitor;
 		    int cutNum = 0;
 		    Visitor visitor(graph, cutMap, cutNum);
 		    DfsVisit<Graph, Visitor> dfs(graph, visitor);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    return cutNum;
+		  }
 		  namespace _topology_bits {
 		    template <typename Digraph, typename IntNodeMap>
 		    class TopologicalSortVisitor : public DfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Node Node;
 		      typedef typename Digraph::Arc edge;
 		      TopologicalSortVisitor(IntNodeMap& order, int num)
 		        : _order(order), _num(num) {}
 		      void leave(const Node& node) {
 		        _order.set(node, --_num);
+		      }
 		    private:
 		      IntNodeMap& _order;
 		      int _num;
 		    };
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Sort the nodes of a DAG into topolgical order.
 		  ///
 		  /// Sort the nodes of a DAG into topolgical order.
 		  ///
 		  /// \param graph The graph. It must be directed and acyclic.
 		  /// \retval order A writable node map. The values will be set from 0 to
 		  /// the number of the nodes in the graph minus one. Each values of the map
 		  /// will be set exactly once, the values  will be set descending order.
 		  ///
 		  /// \see checkedTopologicalSort
 		  /// \see dag
 		  template <typename Digraph, typename NodeMap>
 		  void topologicalSort(const Digraph& graph, NodeMap& order) {
 		    using namespace _topology_bits;
 		    checkConcept<concepts::Digraph, Digraph>();
 		    checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    TopologicalSortVisitor<Digraph, NodeMap>
 		      visitor(order, countNodes(graph));
 		    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
 		      dfs(graph, visitor);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Sort the nodes of a DAG into topolgical order.
 		  ///
 		  /// Sort the nodes of a DAG into topolgical order. It also checks
 		  /// that the given graph is DAG.
 		  ///
 		  /// \param graph The graph. It must be directed and acyclic.
 		  /// \retval order A readable - writable node map. The values will be set
 		  /// from 0 to the number of the nodes in the graph minus one. Each values
 		  /// of the map will be set exactly once, the values will be set descending
 		  /// order.
 		  /// \return %False when the graph is not DAG.
 		  ///
 		  /// \see topologicalSort
 		  /// \see dag
 		  template <typename Digraph, typename NodeMap>
 		  bool checkedTopologicalSort(const Digraph& graph, NodeMap& order) {
 		    using namespace _topology_bits;
 		    checkConcept<concepts::Digraph, Digraph>();
 		    checkConcept<concepts::ReadWriteMap<typename Digraph::Node, int>,
 		      NodeMap>();
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    order = constMap<Node, int, -1>();
 		    TopologicalSortVisitor<Digraph, NodeMap>
 		      visitor(order, countNodes(graph));
 		    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
 		      dfs(graph, visitor);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        while (!dfs.emptyQueue()) {
 		           Arc edge = dfs.nextArc();
 		           Node target = graph.target(edge);
 		           if (dfs.reached(target) && order[target] == -1) {
 		             return false;
+		           }
 		           dfs.processNextArc();
+		         }
+		      }
+		    }
 		    return true;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Check that the given directed graph is a DAG.
 		  ///
 		  /// Check that the given directed graph is a DAG. The DAG is
 		  /// an Directed Acyclic Digraph.
 		  /// \return %False when the graph is not DAG.
 		  /// \see acyclic
 		  template <typename Digraph>
 		  bool dag(const Digraph& graph) {
 		    checkConcept<concepts::Digraph, Digraph>();
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::template NodeMap<bool> ProcessedMap;
 		    typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
 		      Create dfs(graph);
 		    ProcessedMap processed(graph);
 		    dfs.processedMap(processed);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        while (!dfs.emptyQueue()) {
 		          Arc edge = dfs.nextArc();
 		          Node target = graph.target(edge);
 		          if (dfs.reached(target) && !processed[target]) {
 		            return false;
+		          }
 		          dfs.processNextArc();
+		        }
+		      }
+		    }
 		    return true;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Check that the given undirected graph is acyclic.
 		  ///
 		  /// Check that the given undirected graph acyclic.
 		  /// \param graph The undirected graph.
 		  /// \return %True when there is no circle in the graph.
 		  /// \see dag
 		  template <typename Graph>
 		  bool acyclic(const Graph& graph) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::NodeIt NodeIt;
 		    typedef typename Graph::Arc Arc;
 		    Dfs<Graph> dfs(graph);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        while (!dfs.emptyQueue()) {
 		          Arc edge = dfs.nextArc();
 		          Node source = graph.source(edge);
 		          Node target = graph.target(edge);
 		          if (dfs.reached(target) &&
 		              dfs.predArc(source) != graph.oppositeArc(edge)) {
 		            return false;
+		          }
 		          dfs.processNextArc();
+		        }
+		      }
+		    }
 		    return true;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Check that the given undirected graph is tree.
 		  ///
 		  /// Check that the given undirected graph is tree.
 		  /// \param graph The undirected graph.
 		  /// \return %True when the graph is acyclic and connected.
 		  template <typename Graph>
 		  bool tree(const Graph& graph) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::NodeIt NodeIt;
 		    typedef typename Graph::Arc Arc;
 		    Dfs<Graph> dfs(graph);
 		    dfs.init();
 		    dfs.addSource(NodeIt(graph));
 		    while (!dfs.emptyQueue()) {
 		      Arc edge = dfs.nextArc();
 		      Node source = graph.source(edge);
 		      Node target = graph.target(edge);
 		      if (dfs.reached(target) &&
 		          dfs.predArc(source) != graph.oppositeArc(edge)) {
 		        return false;
+		      }
 		      dfs.processNextArc();
+		    }
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        return false;
+		      }
+		    }
 		    return true;
+		  }
 		  namespace _topology_bits {
 		    template <typename Digraph>
 		    class BipartiteVisitor : public BfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Arc Arc;
 		      typedef typename Digraph::Node Node;
 		      BipartiteVisitor(const Digraph& graph, bool& bipartite)
 		        : _graph(graph), _part(graph), _bipartite(bipartite) {}
 		      void start(const Node& node) {
 		        _part[node] = true;
+		      }
 		      void discover(const Arc& edge) {
 		        _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
+		      }
 		      void examine(const Arc& edge) {
 		        _bipartite = _bipartite &&
 		          _part[_graph.target(edge)] != _part[_graph.source(edge)];
+		      }
 		    private:
 		      const Digraph& _graph;
 		      typename Digraph::template NodeMap<bool> _part;
 		      bool& _bipartite;
 		    };
 		    template <typename Digraph, typename PartMap>
 		    class BipartitePartitionsVisitor : public BfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Arc Arc;
 		      typedef typename Digraph::Node Node;
 		      BipartitePartitionsVisitor(const Digraph& graph,
 		                                 PartMap& part, bool& bipartite)
 		        : _graph(graph), _part(part), _bipartite(bipartite) {}
 		      void start(const Node& node) {
 		        _part.set(node, true);
+		      }
 		      void discover(const Arc& edge) {
 		        _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
+		      }
 		      void examine(const Arc& edge) {
 		        _bipartite = _bipartite &&
 		          _part[_graph.target(edge)] != _part[_graph.source(edge)];
+		      }
 		    private:
 		      const Digraph& _graph;
 		      PartMap& _part;
 		      bool& _bipartite;
 		    };
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Check if the given undirected graph is bipartite or not
 		  ///
 		  /// The function checks if the given undirected \c graph graph is bipartite
 		  /// or not. The \ref Bfs algorithm is used to calculate the result.
 		  /// \param graph The undirected graph.
 		  /// \return %True if \c graph is bipartite, %false otherwise.
 		  /// \sa bipartitePartitions
 		  template<typename Graph>
 		  inline bool bipartite(const Graph &graph){
 		    using namespace _topology_bits;
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::NodeIt NodeIt;
 		    typedef typename Graph::ArcIt ArcIt;
 		    bool bipartite = true;
 		    BipartiteVisitor<Graph>
 		      visitor(graph, bipartite);
 		    BfsVisit<Graph, BipartiteVisitor<Graph> >
 		      bfs(graph, visitor);
 		    bfs.init();
 		    for(NodeIt it(graph); it != INVALID; ++it) {
 		      if(!bfs.reached(it)){
 		        bfs.addSource(it);
 		        while (!bfs.emptyQueue()) {
 		          bfs.processNextNode();
 		          if (!bipartite) return false;
+		        }
+		      }
+		    }
 		    return true;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Check if the given undirected graph is bipartite or not
 		  ///
 		  /// The function checks if the given undirected graph is bipartite
 		  /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result.
 		  /// During the execution, the \c partMap will be set as the two
 		  /// partitions of the graph.
 		  /// \param graph The undirected graph.
 		  /// \retval partMap A writable bool map of nodes. It will be set as the
 		  /// two partitions of the graph.
 		  /// \return %True if \c graph is bipartite, %false otherwise.
 		  template<typename Graph, typename NodeMap>
 		  inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
 		    using namespace _topology_bits;
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::NodeIt NodeIt;
 		    typedef typename Graph::ArcIt ArcIt;
 		    bool bipartite = true;
 		    BipartitePartitionsVisitor<Graph, NodeMap>
 		      visitor(graph, partMap, bipartite);
 		    BfsVisit<Graph, BipartitePartitionsVisitor<Graph, NodeMap> >
 		      bfs(graph, visitor);
 		    bfs.init();
 		    for(NodeIt it(graph); it != INVALID; ++it) {
 		      if(!bfs.reached(it)){
 		        bfs.addSource(it);
 		        while (!bfs.emptyQueue()) {
 		          bfs.processNextNode();
 		          if (!bipartite) return false;
+		        }
+		      }
+		    }
 		    return true;
+		  }
 		  /// \brief Returns true when there are not loop edges in the graph.
 		  ///
 		  /// Returns true when there are not loop edges in the graph.
 		  template <typename Digraph>
 		  bool loopFree(const Digraph& graph) {
 		    for (typename Digraph::ArcIt it(graph); it != INVALID; ++it) {
 		      if (graph.source(it) == graph.target(it)) return false;
+		    }
 		    return true;
+		  }
 		  /// \brief Returns true when there are not parallel edges in the graph.
 		  ///
 		  /// Returns true when there are not parallel edges in the graph.
 		  template <typename Digraph>
 		  bool parallelFree(const Digraph& graph) {
 		    typename Digraph::template NodeMap<bool> reached(graph, false);
 		    for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) {
 		      for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
 		        if (reached[graph.target(e)]) return false;
 		        reached.set(graph.target(e), true);
+		      }
 		      for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
 		        reached.set(graph.target(e), false);
+		      }
+		    }
 		    return true;
+		  }
 		  /// \brief Returns true when there are not loop edges and parallel
 		  /// edges in the graph.
 		  ///
 		  /// Returns true when there are not loop edges and parallel edges in
 		  /// the graph.
 		  template <typename Digraph>
 		  bool simpleDigraph(const Digraph& graph) {
 		    typename Digraph::template NodeMap<bool> reached(graph, false);
 		    for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) {
 		      reached.set(n, true);
 		      for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
 		        if (reached[graph.target(e)]) return false;
 		        reached.set(graph.target(e), true);
+		      }
 		      for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
 		        reached.set(graph.target(e), false);
+		      }
 		      reached.set(n, false);
+		    }
 		    return true;
+		  }
 		} //namespace lemon
 		#endif //LEMON_TOPOLOGY_H

test/graph_adaptor_test.cc

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#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/adaptors.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 checkReverseDigraph() {
 		  checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();
 		  typedef ListDigraph Digraph;
 		  typedef ReverseDigraph<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);
 		  checkGraphInArcList(adaptor, n1, 2);
 		  checkGraphInArcList(adaptor, n2, 1);
 		  checkGraphInArcList(adaptor, n3, 0);
 		  checkNodeIds(adaptor);
 		  checkArcIds(adaptor);
 		  checkGraphNodeMap(adaptor);
 		  checkGraphArcMap(adaptor);
 		  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
 		    check(adaptor.source(a) == digraph.target(a), "Wrong reverse");
 		    check(adaptor.target(a) == digraph.source(a), "Wrong reverse");
+		  }
+		}
 		void checkSubDigraph() {
 		  checkConcept<concepts::Digraph,
 		    SubDigraph<concepts::Digraph,
 		    concepts::Digraph::NodeMap<bool>,
 		    concepts::Digraph::ArcMap<bool> > >();
 		  typedef ListDigraph Digraph;
 		  typedef Digraph::NodeMap<bool> NodeFilter;
 		  typedef Digraph::ArcMap<bool> ArcFilter;
 		  typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor;
 		  Digraph digraph;
 		  NodeFilter node_filter(digraph);
 		  ArcFilter arc_filter(digraph);
 		  Adaptor adaptor(digraph, node_filter, arc_filter);
 		  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);
 		  node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
 		  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
 		  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);
 		  arc_filter[a2] = false;
 		  checkGraphNodeList(adaptor, 3);
 		  checkGraphArcList(adaptor, 2);
 		  checkGraphConArcList(adaptor, 2);
 		  checkGraphOutArcList(adaptor, n1, 1);
 		  checkGraphOutArcList(adaptor, n2, 1);
 		  checkGraphOutArcList(adaptor, n3, 0);
 		  checkGraphInArcList(adaptor, n1, 0);
 		  checkGraphInArcList(adaptor, n2, 1);
 		  checkGraphInArcList(adaptor, n3, 1);
 		  checkNodeIds(adaptor);
 		  checkArcIds(adaptor);
 		  checkGraphNodeMap(adaptor);
 		  checkGraphArcMap(adaptor);
 		  node_filter[n1] = false;
 		  checkGraphNodeList(adaptor, 2);
 		  checkGraphArcList(adaptor, 1);
 		  checkGraphConArcList(adaptor, 1);
 		  checkGraphOutArcList(adaptor, n2, 1);
 		  checkGraphOutArcList(adaptor, n3, 0);
 		  checkGraphInArcList(adaptor, n2, 0);
 		  checkGraphInArcList(adaptor, n3, 1);
 		  checkNodeIds(adaptor);
 		  checkArcIds(adaptor);
 		  checkGraphNodeMap(adaptor);
 		  checkGraphArcMap(adaptor);
 		  node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
 		  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
 		  checkGraphNodeList(adaptor, 0);
 		  checkGraphArcList(adaptor, 0);
 		  checkGraphConArcList(adaptor, 0);
 		  checkNodeIds(adaptor);
 		  checkArcIds(adaptor);
 		  checkGraphNodeMap(adaptor);
 		  checkGraphArcMap(adaptor);
+		}
 		void checkFilterNodes1() {
 		  checkConcept<concepts::Digraph,
 		    FilterNodes<concepts::Digraph,
 		      concepts::Digraph::NodeMap<bool> > >();
 		  typedef ListDigraph Digraph;
 		  typedef Digraph::NodeMap<bool> NodeFilter;
 		  typedef FilterNodes<Digraph, NodeFilter> Adaptor;
 		  Digraph digraph;
 		  NodeFilter node_filter(digraph);
 		  Adaptor adaptor(digraph, node_filter);
 		  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);
 		  node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
 		  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);
 		  node_filter[n1] = false;
 		  checkGraphNodeList(adaptor, 2);
 		  checkGraphArcList(adaptor, 1);
 		  checkGraphConArcList(adaptor, 1);
 		  checkGraphOutArcList(adaptor, n2, 1);
 		  checkGraphOutArcList(adaptor, n3, 0);
 		  checkGraphInArcList(adaptor, n2, 0);
 		  checkGraphInArcList(adaptor, n3, 1);
 		  checkNodeIds(adaptor);
 		  checkArcIds(adaptor);
 		  checkGraphNodeMap(adaptor);
 		  checkGraphArcMap(adaptor);
 		  node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
 		  checkGraphNodeList(adaptor, 0);
 		  checkGraphArcList(adaptor, 0);
 		  checkGraphConArcList(adaptor, 0);
 		  checkNodeIds(adaptor);
 		  checkArcIds(adaptor);
 		  checkGraphNodeMap(adaptor);
 		  checkGraphArcMap(adaptor);
+		}
 		void checkFilterArcs() {
 		  checkConcept<concepts::Digraph,
 		    FilterArcs<concepts::Digraph,
 		    concepts::Digraph::ArcMap<bool> > >();
 		  typedef ListDigraph Digraph;
 		  typedef Digraph::ArcMap<bool> ArcFilter;
 		  typedef FilterArcs<Digraph, ArcFilter> Adaptor;
 		  Digraph digraph;
 		  ArcFilter arc_filter(digraph);
 		  Adaptor adaptor(digraph, arc_filter);
 		  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);
 		  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
 		  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);
 		  arc_filter[a2] = false;
 		  checkGraphNodeList(adaptor, 3);
 		  checkGraphArcList(adaptor, 2);
 		  checkGraphConArcList(adaptor, 2);
 		  checkGraphOutArcList(adaptor, n1, 1);
 		  checkGraphOutArcList(adaptor, n2, 1);
 		  checkGraphOutArcList(adaptor, n3, 0);
 		  checkGraphInArcList(adaptor, n1, 0);
 		  checkGraphInArcList(adaptor, n2, 1);
 		  checkGraphInArcList(adaptor, n3, 1);
 		  checkNodeIds(adaptor);
 		  checkArcIds(adaptor);
 		  checkGraphNodeMap(adaptor);
 		  checkGraphArcMap(adaptor);
 		  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
 		  checkGraphNodeList(adaptor, 3);
 		  checkGraphArcList(adaptor, 0);
 		  checkGraphConArcList(adaptor, 0);
 		  checkNodeIds(adaptor);
 		  checkArcIds(adaptor);
 		  checkGraphNodeMap(adaptor);
 		  checkGraphArcMap(adaptor);
+		}
 		void checkUndirector() {
 		  checkConcept<concepts::Graph, Undirector<concepts::Digraph> >();
 		  typedef ListDigraph Digraph;
 		  typedef Undirector<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, 6);
 		  checkGraphEdgeList(adaptor, 3);
 		  checkGraphConArcList(adaptor, 6);
 		  checkGraphConEdgeList(adaptor, 3);
 		  checkGraphOutArcList(adaptor, n1, 2);
 		  checkGraphOutArcList(adaptor, n2, 2);
 		  checkGraphOutArcList(adaptor, n3, 2);
 		  checkGraphInArcList(adaptor, n1, 2);
 		  checkGraphInArcList(adaptor, n2, 2);
 		  checkGraphInArcList(adaptor, n3, 2);
 		  checkGraphIncEdgeList(adaptor, n1, 2);
 		  checkGraphIncEdgeList(adaptor, n2, 2);
 		  checkGraphIncEdgeList(adaptor, n3, 2);
 		  checkNodeIds(adaptor);
 		  checkArcIds(adaptor);
 		  checkEdgeIds(adaptor);
 		  checkGraphNodeMap(adaptor);
 		  checkGraphArcMap(adaptor);
 		  checkGraphEdgeMap(adaptor);
 		  for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) {
 		    check(adaptor.u(e) == digraph.source(e), "Wrong undir");
 		    check(adaptor.v(e) == digraph.target(e), "Wrong undir");
+		  }
+		}
 		void checkResidual() {
 		  checkConcept<concepts::Digraph,
 		    Residual<concepts::Digraph,
 		    concepts::Digraph::ArcMap<int>,
 		    concepts::Digraph::ArcMap<int> > >();
 		  typedef ListDigraph Digraph;
 		  typedef Digraph::ArcMap<int> IntArcMap;
 		  typedef Residual<Digraph, IntArcMap> Adaptor;
 		  Digraph digraph;
 		  IntArcMap capacity(digraph), flow(digraph);
 		  Adaptor adaptor(digraph, capacity, flow);
 		  Digraph::Node n1 = digraph.addNode();
 		  Digraph::Node n2 = digraph.addNode();
 		  Digraph::Node n3 = digraph.addNode();
 		  Digraph::Node n4 = digraph.addNode();
 		  Digraph::Arc a1 = digraph.addArc(n1, n2);
 		  Digraph::Arc a2 = digraph.addArc(n1, n3);
 		  Digraph::Arc a3 = digraph.addArc(n1, n4);
 		  Digraph::Arc a4 = digraph.addArc(n2, n3);
 		  Digraph::Arc a5 = digraph.addArc(n2, n4);
 		  Digraph::Arc a6 = digraph.addArc(n3, n4);
 		  capacity[a1] = 8;
 		  capacity[a2] = 6;
 		  capacity[a3] = 4;
 		  capacity[a4] = 4;
 		  capacity[a5] = 6;
 		  capacity[a6] = 10;
 		  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
 		    flow[a] = 0;
+		  }
 		  checkGraphNodeList(adaptor, 4);
 		  checkGraphArcList(adaptor, 6);
 		  checkGraphConArcList(adaptor, 6);
 		  checkGraphOutArcList(adaptor, n1, 3);
 		  checkGraphOutArcList(adaptor, n2, 2);
 		  checkGraphOutArcList(adaptor, n3, 1);
 		  checkGraphOutArcList(adaptor, n4, 0);
 		  checkGraphInArcList(adaptor, n1, 0);
 		  checkGraphInArcList(adaptor, n2, 1);
 		  checkGraphInArcList(adaptor, n3, 2);
 		  checkGraphInArcList(adaptor, n4, 3);
 		  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
 		    flow[a] = capacity[a] / 2;
+		  }
 		  checkGraphNodeList(adaptor, 4);
 		  checkGraphArcList(adaptor, 12);
 		  checkGraphConArcList(adaptor, 12);
 		  checkGraphOutArcList(adaptor, n1, 3);
 		  checkGraphOutArcList(adaptor, n2, 3);
 		  checkGraphOutArcList(adaptor, n3, 3);
 		  checkGraphOutArcList(adaptor, n4, 3);
 		  checkGraphInArcList(adaptor, n1, 3);
 		  checkGraphInArcList(adaptor, n2, 3);
 		  checkGraphInArcList(adaptor, n3, 3);
 		  checkGraphInArcList(adaptor, n4, 3);
 		  checkNodeIds(adaptor);
 		  checkArcIds(adaptor);
 		  checkGraphNodeMap(adaptor);
 		  checkGraphArcMap(adaptor);
 		  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
 		    flow[a] = capacity[a];
+		  }
 		  checkGraphNodeList(adaptor, 4);
 		  checkGraphArcList(adaptor, 6);
 		  checkGraphConArcList(adaptor, 6);
 		  checkGraphOutArcList(adaptor, n1, 0);
 		  checkGraphOutArcList(adaptor, n2, 1);
 		  checkGraphOutArcList(adaptor, n3, 2);
 		  checkGraphOutArcList(adaptor, n4, 3);
 		  checkGraphInArcList(adaptor, n1, 3);
 		  checkGraphInArcList(adaptor, n2, 2);
 		  checkGraphInArcList(adaptor, n3, 1);
 		  checkGraphInArcList(adaptor, n4, 0);
 		  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
 		    flow[a] = 0;
+		  }
 		  int flow_value = 0;
 		  while (true) {
 		    Bfs<Adaptor> bfs(adaptor);
 		    bfs.run(n1, n4);
 		    if (!bfs.reached(n4)) break;
 		    Path<Adaptor> p = bfs.path(n4);
 		    int min = std::numeric_limits<int>::max();
 		    for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
 		      if (adaptor.residualCapacity(a) < min)
 		        min = adaptor.residualCapacity(a);
+		    }
 		    for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
 		      adaptor.augment(a, min);
+		    }
 		    flow_value += min;
+		  }
 		  check(flow_value == 18, "Wrong flow with res graph adaptor");
+		}
 		void checkSplitNodes() {
 		  checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();
 		  typedef ListDigraph Digraph;
 		  typedef SplitNodes<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, 6);
 		  checkGraphArcList(adaptor, 6);
 		  checkGraphConArcList(adaptor, 6);
 		  checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);
 		  checkGraphOutArcList(adaptor, adaptor.outNode(n1), 2);
 		  checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);
 		  checkGraphOutArcList(adaptor, adaptor.outNode(n2), 1);
 		  checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);
 		  checkGraphOutArcList(adaptor, adaptor.outNode(n3), 0);
 		  checkGraphInArcList(adaptor, adaptor.inNode(n1), 0);
 		  checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);
 		  checkGraphInArcList(adaptor, adaptor.inNode(n2), 1);
 		  checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);
 		  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 checkSubGraph() {
 		  checkConcept<concepts::Graph,
 		    SubGraph<concepts::Graph,
 		    concepts::Graph::NodeMap<bool>,
 		    concepts::Graph::EdgeMap<bool> > >();
 		  typedef ListGraph Graph;
 		  typedef Graph::NodeMap<bool> NodeFilter;
 		  typedef Graph::EdgeMap<bool> EdgeFilter;
 		  typedef SubGraph<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);
 		  Graph::Edge e4 = graph.addEdge(n3, n4);
 		  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
 		  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
 		  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);
 		  edge_filter[e2] = false;
 		  checkGraphNodeList(adaptor, 4);
 		  checkGraphArcList(adaptor, 6);
 		  checkGraphEdgeList(adaptor, 3);
 		  checkGraphConArcList(adaptor, 6);
 		  checkGraphConEdgeList(adaptor, 3);
 		  checkGraphOutArcList(adaptor, n1, 1);
 		  checkGraphOutArcList(adaptor, n2, 2);
 		  checkGraphOutArcList(adaptor, n3, 2);
 		  checkGraphOutArcList(adaptor, n4, 1);
 		  checkGraphInArcList(adaptor, n1, 1);
 		  checkGraphInArcList(adaptor, n2, 2);
 		  checkGraphInArcList(adaptor, n3, 2);
 		  checkGraphInArcList(adaptor, n4, 1);
 		  checkGraphIncEdgeList(adaptor, n1, 1);
 		  checkGraphIncEdgeList(adaptor, n2, 2);
 		  checkGraphIncEdgeList(adaptor, n3, 2);
 		  checkGraphIncEdgeList(adaptor, n4, 1);
 		  checkNodeIds(adaptor);
 		  checkArcIds(adaptor);
 		  checkEdgeIds(adaptor);
 		  checkGraphNodeMap(adaptor);
 		  checkGraphArcMap(adaptor);
 		  checkGraphEdgeMap(adaptor);
 		  node_filter[n1] = false;
 		  checkGraphNodeList(adaptor, 3);
 		  checkGraphArcList(adaptor, 4);
 		  checkGraphEdgeList(adaptor, 2);
 		  checkGraphConArcList(adaptor, 4);
 		  checkGraphConEdgeList(adaptor, 2);
 		  checkGraphOutArcList(adaptor, n2, 1);
 		  checkGraphOutArcList(adaptor, n3, 2);
 		  checkGraphOutArcList(adaptor, n4, 1);
 		  checkGraphInArcList(adaptor, n2, 1);
 		  checkGraphInArcList(adaptor, n3, 2);
 		  checkGraphInArcList(adaptor, n4, 1);
 		  checkGraphIncEdgeList(adaptor, n2, 1);
 		  checkGraphIncEdgeList(adaptor, n3, 2);
 		  checkGraphIncEdgeList(adaptor, n4, 1);
 		  checkNodeIds(adaptor);
 		  checkArcIds(adaptor);
 		  checkEdgeIds(adaptor);
 		  checkGraphNodeMap(adaptor);
 		  checkGraphArcMap(adaptor);
 		  checkGraphEdgeMap(adaptor);
 		  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
 		  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
 		  checkGraphNodeList(adaptor, 0);
 		  checkGraphArcList(adaptor, 0);
 		  checkGraphEdgeList(adaptor, 0);
 		  checkGraphConArcList(adaptor, 0);
 		  checkGraphConEdgeList(adaptor, 0);
 		  checkNodeIds(adaptor);
 		  checkArcIds(adaptor);
 		  checkEdgeIds(adaptor);
 		  checkGraphNodeMap(adaptor);
 		  checkGraphArcMap(adaptor);
 		  checkGraphEdgeMap(adaptor);
+		}
 		void checkFilterNodes2() {
 		  checkConcept<concepts::Graph,
 		    FilterNodes<concepts::Graph,
 		      concepts::Graph::NodeMap<bool> > >();
 		  typedef ListGraph Graph;
 		  typedef Graph::NodeMap<bool> NodeFilter;
 		  typedef FilterNodes<Graph, NodeFilter> Adaptor;
 		  Graph graph;
 		  NodeFilter node_filter(graph);
 		  Adaptor adaptor(graph, node_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);
 		  Graph::Edge e4 = graph.addEdge(n3, n4);
 		  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
 		  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);
 		  node_filter[n1] = false;
 		  checkGraphNodeList(adaptor, 3);
 		  checkGraphArcList(adaptor, 4);
 		  checkGraphEdgeList(adaptor, 2);
 		  checkGraphConArcList(adaptor, 4);
 		  checkGraphConEdgeList(adaptor, 2);
 		  checkGraphOutArcList(adaptor, n2, 1);
 		  checkGraphOutArcList(adaptor, n3, 2);
 		  checkGraphOutArcList(adaptor, n4, 1);
 		  checkGraphInArcList(adaptor, n2, 1);
 		  checkGraphInArcList(adaptor, n3, 2);
 		  checkGraphInArcList(adaptor, n4, 1);
 		  checkGraphIncEdgeList(adaptor, n2, 1);
 		  checkGraphIncEdgeList(adaptor, n3, 2);
 		  checkGraphIncEdgeList(adaptor, n4, 1);
 		  checkNodeIds(adaptor);
 		  checkArcIds(adaptor);
 		  checkEdgeIds(adaptor);
 		  checkGraphNodeMap(adaptor);
 		  checkGraphArcMap(adaptor);
 		  checkGraphEdgeMap(adaptor);
 		  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
 		  checkGraphNodeList(adaptor, 0);
 		  checkGraphArcList(adaptor, 0);
 		  checkGraphEdgeList(adaptor, 0);
 		  checkGraphConArcList(adaptor, 0);
 		  checkGraphConEdgeList(adaptor, 0);
 		  checkNodeIds(adaptor);
 		  checkArcIds(adaptor);
 		  checkEdgeIds(adaptor);
 		  checkGraphNodeMap(adaptor);
 		  checkGraphArcMap(adaptor);
 		  checkGraphEdgeMap(adaptor);
+		}
 		void checkFilterEdges() {
 		  checkConcept<concepts::Graph,
 		    FilterEdges<concepts::Graph,
 		    concepts::Graph::EdgeMap<bool> > >();
 		  typedef ListGraph Graph;
 		  typedef Graph::EdgeMap<bool> EdgeFilter;
 		  typedef FilterEdges<Graph, EdgeFilter> Adaptor;
 		  Graph graph;
 		  EdgeFilter edge_filter(graph);
 		  Adaptor adaptor(graph, 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);
 		  Graph::Edge e4 = graph.addEdge(n3, n4);
 		  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
 		  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);
 		  edge_filter[e2] = false;
 		  checkGraphNodeList(adaptor, 4);
 		  checkGraphArcList(adaptor, 6);
 		  checkGraphEdgeList(adaptor, 3);
 		  checkGraphConArcList(adaptor, 6);
 		  checkGraphConEdgeList(adaptor, 3);
 		  checkGraphOutArcList(adaptor, n1, 1);
 		  checkGraphOutArcList(adaptor, n2, 2);
 		  checkGraphOutArcList(adaptor, n3, 2);
 		  checkGraphOutArcList(adaptor, n4, 1);
 		  checkGraphInArcList(adaptor, n1, 1);
 		  checkGraphInArcList(adaptor, n2, 2);
 		  checkGraphInArcList(adaptor, n3, 2);
 		  checkGraphInArcList(adaptor, n4, 1);
 		  checkGraphIncEdgeList(adaptor, n1, 1);
 		  checkGraphIncEdgeList(adaptor, n2, 2);
 		  checkGraphIncEdgeList(adaptor, n3, 2);
 		  checkGraphIncEdgeList(adaptor, n4, 1);
 		  checkNodeIds(adaptor);
 		  checkArcIds(adaptor);
 		  checkEdgeIds(adaptor);
 		  checkGraphNodeMap(adaptor);
 		  checkGraphArcMap(adaptor);
 		  checkGraphEdgeMap(adaptor);
 		  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
 		  checkGraphNodeList(adaptor, 4);
 		  checkGraphArcList(adaptor, 0);
 		  checkGraphEdgeList(adaptor, 0);
 		  checkGraphConArcList(adaptor, 0);
 		  checkGraphConEdgeList(adaptor, 0);
 		  checkNodeIds(adaptor);
 		  checkArcIds(adaptor);
 		  checkEdgeIds(adaptor);
 		  checkGraphNodeMap(adaptor);
 		  checkGraphArcMap(adaptor);
 		  checkGraphEdgeMap(adaptor);
+		}
 		void checkOrienter() {
 		  checkConcept<concepts::Digraph,
 		    Orienter<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();
 		  typedef ListGraph Graph;
 		  typedef ListGraph::EdgeMap<bool> DirMap;
 		  typedef Orienter<Graph> Adaptor;
 		  Graph graph;
 		  DirMap dir(graph, true);
 		  Adaptor adaptor(graph, dir);
 		  Graph::Node n1 = graph.addNode();
 		  Graph::Node n2 = graph.addNode();
 		  Graph::Node n3 = graph.addNode();
 		  Graph::Edge e1 = graph.addEdge(n1, n2);
 		  Graph::Edge e2 = graph.addEdge(n1, n3);
 		  Graph::Edge e3 = graph.addEdge(n2, n3);
 		  checkGraphNodeList(adaptor, 3);
 		  checkGraphArcList(adaptor, 3);
 		  checkGraphConArcList(adaptor, 3);
+		  {
 		    dir[e1] = true;
 		    Adaptor::Node u = adaptor.source(e1);
 		    Adaptor::Node v = adaptor.target(e1);
 		    dir[e1] = false;
 		    check (u == adaptor.target(e1), "Wrong dir");
 		    check (v == adaptor.source(e1), "Wrong dir");
 		    check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir");
 		    dir[e1] = n1 == u;
+		  }
+		  {
 		    dir[e2] = true;
 		    Adaptor::Node u = adaptor.source(e2);
 		    Adaptor::Node v = adaptor.target(e2);
 		    dir[e2] = false;
 		    check (u == adaptor.target(e2), "Wrong dir");
 		    check (v == adaptor.source(e2), "Wrong dir");
 		    check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir");
 		    dir[e2] = n3 == u;
+		  }
+		  {
 		    dir[e3] = true;
 		    Adaptor::Node u = adaptor.source(e3);
 		    Adaptor::Node v = adaptor.target(e3);
 		    dir[e3] = false;
 		    check (u == adaptor.target(e3), "Wrong dir");
 		    check (v == adaptor.source(e3), "Wrong dir");
 		    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 **) {
 		  checkReverseDigraph();
 		  checkSubDigraph();
 		  checkFilterNodes1();
 		  checkFilterArcs();
 		  checkUndirector();
 		  checkResidual();
 		  checkSplitNodes();
 		  checkSubGraph();
 		  checkFilterNodes2();
 		  checkFilterEdges();
 		  checkOrienter();
 		  return 0;
+		}

doc/groups.dox

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		namespace lemon {
 		/**
 		@defgroup datas Data Structures
 		This group describes the several data structures implemented in LEMON.
 		*/
 		/**
 		@defgroup graphs Graph Structures
 		@ingroup datas
 		\brief Graph structures implemented in LEMON.
 		The implementation of combinatorial algorithms heavily relies on
 		efficient graph implementations. LEMON offers data structures which are
 		planned to be easily used in an experimental phase of implementation studies,
 		and thereafter the program code can be made efficient by small modifications.
 		The most efficient implementation of diverse applications require the
 		usage of different physical graph implementations. These differences
 		appear in the size of graph we require to handle, memory or time usage
 		limitations or in the set of operations through which the graph can be
 		accessed.  LEMON provides several physical graph structures to meet
 		the diverging requirements of the possible users.  In order to save on
 		running time or on memory usage, some structures may fail to provide
 		some graph features like arc/edge or node deletion.
 		Alteration of standard containers need a very limited number of
 		operations, these together satisfy the everyday requirements.
 		In the case of graph structures, different operations are needed which do
 		not alter the physical graph, but gives another view. If some nodes or
 		arcs have to be hidden or the reverse oriented graph have to be used, then
 		this is the case. It also may happen that in a flow implementation
 		the residual graph can be accessed by another algorithm, or a node-set
 		is to be shrunk for another algorithm.
 		LEMON also provides a variety of graphs for these requirements called
 		\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
 		in conjunction with other graph representations.
 		You are free to use the graph structure that fit your requirements
 		the best, most graph algorithms and auxiliary data structures can be used
 		with any graph structure.
 		<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
 		*/
 		/**
 		@defgroup graph_adaptors Adaptor Classes for graphs
 		@ingroup graphs
 		\brief This group contains several adaptor classes for digraphs and graphs
 		The main parts of LEMON are the different graph structures, generic
 		graph algorithms, graph concepts which couple these, and graph
 		adaptors. While the previous notions are more or less clear, the
 		latter one needs further explanation. Graph adaptors are graph classes
 		which serve for considering graph structures in different ways.
 		A short example makes this much clearer.  Suppose that we have an
 		instance \c g of a directed graph type say ListDigraph and an algorithm
 		\code
 		template <typename Digraph>
 		int algorithm(const Digraph&);
 		\endcode
 		is needed to run on the reverse oriented graph.  It may be expensive
 		(in time or in memory usage) to copy \c g with the reversed
 		arcs.  In this case, an adaptor class is used, which (according
 		to LEMON digraph concepts) works as a digraph.  The adaptor uses the
 		original digraph structure and digraph operations when methods of the
 		reversed oriented graph are called.  This means that the adaptor have
 		minor memory usage, and do not perform sophisticated algorithmic
 		actions.  The purpose of it is to give a tool for the cases when a
 		graph have to be used in a specific alteration.  If this alteration is
 		obtained by a usual construction like filtering the arc-set or
 		considering a new orientation, then an adaptor is worthwhile to use.
 		To come back to the reverse oriented graph, in this situation
 		\code
 		template<typename Digraph> class ReverseDigraph;
 		\endcode
 		template class can be used. The code looks as follows
 		\code
 		ListDigraph g;
 		ReverseDigraph<ListGraph> rg(g);
 		int result = algorithm(rg);
 		\endcode
 		After running the algorithm, the original graph \c g is untouched.
 		This techniques gives rise to an elegant code, and based on stable
 		graph adaptors, complex algorithms can be implemented easily.
 		In flow, circulation and bipartite matching problems, the residual
 		graph is of particular importance. Combining an adaptor implementing
 		this, shortest path algorithms and minimum mean cycle algorithms,
 		a range of weighted and cardinality optimization algorithms can be
 		obtained. For other examples, the interested user is referred to the
 		detailed documentation of particular adaptors.
 		The behavior of graph adaptors can be very different. Some of them keep
 		capabilities of the original graph while in other cases this would be
 		meaningless. This means that the concepts that they are models of depend
 		on the graph adaptor, and the wrapped graph(s).
 		If an arc of \c rg is deleted, this is carried out by deleting the
 		corresponding arc of \c g, thus the adaptor modifies the original graph.
 		But for a residual graph, this operation has no sense.
 		Let us stand one more example here to simplify your work.
 		RevGraphAdaptor has constructor
 		\code
 		ReverseDigraph(Digraph& digraph);
 		\endcode
 		This means that in a situation, when a <tt>const ListDigraph&</tt>
 		reference to a graph is given, then it have to be instantiated with
 		<tt>Digraph=const ListDigraph</tt>.
 		\code
 		int algorithm1(const ListDigraph& g) {
 		  RevGraphAdaptor<const ListDigraph> rg(g);
 		  return algorithm2(rg);
+		}
 		\endcode
 		*/
 		/**
 		@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
 		@ingroup graphs
 		\brief Graph types between real graphs and graph adaptors.
 		This group describes some graph types between real graphs and graph adaptors.
 		These classes wrap graphs to give new functionality as the adaptors do it.
 		On the other hand they are not light-weight structures as the adaptors.
 		*/
 		/**
 		@defgroup maps Maps
 		@ingroup datas
 		\brief Map structures implemented in LEMON.
 		This group describes the map structures implemented in LEMON.
 		LEMON provides several special purpose maps and map adaptors that e.g. combine
 		new maps from existing ones.
 		<b>See also:</b> \ref map_concepts "Map Concepts".
 		*/
 		/**
 		@defgroup graph_maps Graph Maps
 		@ingroup maps
 		\brief Special graph-related maps.
 		This group describes maps that are specifically designed to assign
 		values to the nodes and arcs/edges of graphs.
 		If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
 		\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
 		*/
 		/**
 		\defgroup map_adaptors Map Adaptors
 		\ingroup maps
 		\brief Tools to create new maps from existing ones
 		This group describes map adaptors that are used to create "implicit"
 		maps from other maps.
 		Most of them are \ref concepts::ReadMap "read-only maps".
 		They can make arithmetic and logical operations between one or two maps
 		(negation, shifting, addition, multiplication, logical 'and', 'or',
 		'not' etc.) or e.g. convert a map to another one of different Value type.
 		The typical usage of this classes is passing implicit maps to
 		algorithms.  If a function type algorithm is called then the function
 		type map adaptors can be used comfortable. For example let's see the
 		usage of map adaptors with the \c graphToEps() function.
 		\code
 		  Color nodeColor(int deg) {
 		    if (deg >= 2) {
 		      return Color(0.5, 0.0, 0.5);
 		    } else if (deg == 1) {
 		      return Color(1.0, 0.5, 1.0);
 		    } else {
 		      return Color(0.0, 0.0, 0.0);
+		    }
+		  }
 		  Digraph::NodeMap<int> degree_map(graph);
 		  graphToEps(graph, "graph.eps")
 		    .coords(coords).scaleToA4().undirected()
 		    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
 		    .run();
 		\endcode
 		The \c functorToMap() function makes an \c int to \c Color map from the
 		\c nodeColor() function. The \c composeMap() compose the \c degree_map
 		and the previously created map. The composed map is a proper function to
 		get the color of each node.
 		The usage with class type algorithms is little bit harder. In this
 		case the function type map adaptors can not be used, because the
 		function map adaptors give back temporary objects.
 		\code
 		  Digraph graph;
 		  typedef Digraph::ArcMap<double> DoubleArcMap;
 		  DoubleArcMap length(graph);
 		  DoubleArcMap speed(graph);
 		  typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
 		  TimeMap time(length, speed);
 		  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
 		  dijkstra.run(source, target);
 		\endcode
 		We have a length map and a maximum speed map on the arcs of a digraph.
 		The minimum time to pass the arc can be calculated as the division of
 		the two maps which can be done implicitly with the \c DivMap template
 		class. We use the implicit minimum time map as the length map of the
 		\c Dijkstra algorithm.
 		*/
 		/**
 		@defgroup matrices Matrices
 		@ingroup datas
 		\brief Two dimensional data storages implemented in LEMON.
 		This group describes two dimensional data storages implemented in LEMON.
 		*/
 		/**
 		@defgroup paths Path Structures
 		@ingroup datas
 		\brief %Path structures implemented in LEMON.
 		This group describes the path structures implemented in LEMON.
 		LEMON provides flexible data structures to work with paths.
 		All of them have similar interfaces and they can be copied easily with
 		assignment operators and copy constructors. This makes it easy and
 		efficient to have e.g. the Dijkstra algorithm to store its result in
 		any kind of path structure.
 		\sa lemon::concepts::Path
 		*/
 		/**
 		@defgroup auxdat Auxiliary Data Structures
 		@ingroup datas
 		\brief Auxiliary data structures implemented in LEMON.
 		This group describes some data structures implemented in LEMON in
 		order to make it easier to implement combinatorial algorithms.

lemon/Makefile.am

Show inline comments

 		EXTRA_DIST += \
 			lemon/lemon.pc.in \
 			lemon/CMakeLists.txt
 		pkgconfig_DATA += lemon/lemon.pc
 		lib_LTLIBRARIES += lemon/libemon.la
 		lemon_libemon_la_SOURCES = \
 		        lemon/arg_parser.cc \
 		        lemon/base.cc \
 		        lemon/color.cc \
 		        lemon/random.cc
 		#lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS) $(AM_CXXFLAGS)
 		#lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
 		lemon_HEADERS += \
 			lemon/adaptors.h \
 		        lemon/arg_parser.h \
 			lemon/assert.h \
 		        lemon/bfs.h \
 		        lemon/bin_heap.h \
 		        lemon/circulation.h \
 		        lemon/color.h \
 			lemon/concept_check.h \
 		        lemon/counter.h \
 			lemon/core.h \
 		        lemon/dfs.h \
 		        lemon/dijkstra.h \
 		        lemon/dim2.h \
 		        lemon/dimacs.h \
 			lemon/elevator.h \
 			lemon/error.h \
 			lemon/full_graph.h \
 		        lemon/graph_to_eps.h \
 		        lemon/grid_graph.h \
 			lemon/hypercube_graph.h \
 			lemon/kruskal.h \
 			lemon/hao_orlin.h \
 			lemon/lgf_reader.h \
 			lemon/lgf_writer.h \
 			lemon/list_graph.h \
 			lemon/maps.h \
 			lemon/math.h \
 			lemon/max_matching.h \
 			lemon/nauty_reader.h \
 			lemon/path.h \
 			lemon/preflow.h \
 		        lemon/random.h \
 			lemon/smart_graph.h \
 			lemon/suurballe.h \
 		        lemon/time_measure.h \
 		        lemon/tolerance.h \
 			lemon/unionfind.h
 		bits_HEADERS += \
 			lemon/bits/alteration_notifier.h \
 			lemon/bits/array_map.h \
 			lemon/bits/base_extender.h \
 		        lemon/bits/bezier.h \
 			lemon/bits/default_map.h \
 		        lemon/bits/enable_if.h \
 			lemon/bits/graph_adaptor_extender.h \
 			lemon/bits/graph_extender.h \
 			lemon/bits/map_extender.h \
 			lemon/bits/path_dump.h \
 			lemon/bits/traits.h \
 			lemon/bits/variant.h \
 			lemon/bits/vector_map.h
 		concept_HEADERS += \
 			lemon/concepts/digraph.h \
 			lemon/concepts/graph.h \
 			lemon/concepts/graph_components.h \
 			lemon/concepts/heap.h \
 			lemon/concepts/maps.h \
 			lemon/concepts/path.h

test/Makefile.am

Show inline comments

 		EXTRA_DIST += \
 			test/CMakeLists.txt \
 		        test/min_cost_flow_test.lgf \
 		        test/preflow_graph.lgf
 		noinst_HEADERS += \
 			test/graph_test.h \
 		        test/test_tools.h
 		check_PROGRAMS += \
 			test/bfs_test \
 		        test/circulation_test \
 		        test/counter_test \
 			test/dfs_test \
 			test/digraph_test \
 			test/dijkstra_test \
 		        test/dim_test \
 			test/error_test \
 			test/graph_adaptor_test \
 			test/graph_copy_test \
 			test/graph_test \
 			test/graph_utils_test \
 			test/heap_test \
 			test/kruskal_test \
 			test/hao_orlin_test \
 		        test/maps_test \
 			test/max_matching_test \
 		        test/random_test \
 		        test/path_test \
 		        test/preflow_test \
 		        test/suurballe_test \
 		        test/test_tools_fail \
 		        test/test_tools_pass \
 		        test/time_measure_test \
 			test/unionfind_test
 		TESTS += $(check_PROGRAMS)
 		XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
 		test_bfs_test_SOURCES = test/bfs_test.cc
 		test_circulation_test_SOURCES = test/circulation_test.cc
 		test_counter_test_SOURCES = test/counter_test.cc
 		test_dfs_test_SOURCES = test/dfs_test.cc
 		test_digraph_test_SOURCES = test/digraph_test.cc
 		test_dijkstra_test_SOURCES = test/dijkstra_test.cc
 		test_dim_test_SOURCES = test/dim_test.cc
 		test_error_test_SOURCES = test/error_test.cc
 		test_graph_adaptor_test_SOURCES = test/graph_adaptor_test.cc
 		test_graph_copy_test_SOURCES = test/graph_copy_test.cc
 		test_graph_test_SOURCES = test/graph_test.cc
 		test_graph_utils_test_SOURCES = test/graph_utils_test.cc
 		test_heap_test_SOURCES = test/heap_test.cc
 		test_kruskal_test_SOURCES = test/kruskal_test.cc
 		test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
 		test_maps_test_SOURCES = test/maps_test.cc
 		test_max_matching_test_SOURCES = test/max_matching_test.cc
 		test_path_test_SOURCES = test/path_test.cc
 		test_preflow_test_SOURCES = test/preflow_test.cc
 		test_suurballe_test_SOURCES = test/suurballe_test.cc
 		test_random_test_SOURCES = test/random_test.cc
 		test_test_tools_fail_SOURCES = test/test_tools_fail.cc
 		test_test_tools_pass_SOURCES = test/test_tools_pass.cc
 		test_time_measure_test_SOURCES = test/time_measure_test.cc
 		test_unionfind_test_SOURCES = test/unionfind_test.cc

0 comments (0 inline)

RhodeCode

Login to your account