LEMON/LEMON-main Changeset - r648:4ff8041e9c2e

Repositories » LEMON » LEMON-main

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

Changeset - r648:4ff8041e9c2e

« 647:dcba64

649:76cbcb »

r648:4ff8041e9c2e

Wed, 06 May 2009 14:44:05

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

Doc improvements and fixes for connectivity tools (#285) And add loopFree(), parallelFree(), simpleGraph() to the module doc.

0 2 0

default

2 files changed with 305 insertions and 225 deletions:

lemon/connectivity.h

303

223

lemon/euler.h

↑ Collapse diff ↑

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-2009
 		 * 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_CONNECTIVITY_H
 		#define LEMON_CONNECTIVITY_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 graph_properties
 		/// \file
 		/// \brief Connectivity algorithms
 		///
 		/// Connectivity algorithms
 		namespace lemon {
 		  /// \ingroup graph_properties
 		  ///
-		  /// \brief Check whether the given undirected graph is connected.
+		  /// \brief Check whether an undirected graph is connected.
 		  ///
 		  /// Check whether the given undirected graph is connected.
 		  /// \param graph The undirected graph.
-		  /// \return \c true when there is path between any two nodes in the graph.
+		  /// This function checks whether the given undirected graph is connected,
 		  /// i.e. there is a path between any two nodes in the graph.
 		  ///
 		  /// \return \c true if the graph is connected.
 		  /// \note By definition, the empty graph is connected.
 		  ///
 		  /// \see countConnectedComponents(), connectedComponents()
 		  /// \see stronglyConnected()
 		  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 graph_properties
 		  ///
 		  /// \brief Count the number of connected components of an undirected graph
 		  ///
-		  /// Count the number of connected components of an undirected graph
+		  /// This function counts the number of connected components of the given
 		  /// undirected graph.
 		  ///
 		  /// \param graph The graph. It must be undirected.
 		  /// \return The number of components
 		  /// The connected components are the classes of an equivalence relation
 		  /// on the nodes of an undirected graph. Two nodes are in the same class
 		  /// if they are connected with a path.
 		  ///
 		  /// \return The number of connected components.
 		  /// \note By definition, the empty graph consists
 		  /// of zero connected components.
 		  ///
 		  /// \see connected(), connectedComponents()
 		  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 graph_properties
 		  ///
 		  /// \brief Find the connected components of an undirected graph
 		  ///
-		  /// Find the connected components of an undirected graph.
+		  /// This function finds the connected components of the given undirected
 		  /// graph.
 		  ///
 		  /// The connected components are the classes of an equivalence relation
 		  /// on the nodes of an undirected graph. Two nodes are in the same class
 		  /// if they are connected with a path.
 		  ///
 		  /// \image html connected_components.png
 		  /// \image latex connected_components.eps "Connected components" width=\textwidth
 		  ///
-		  /// \param graph The graph. It must be undirected.
+		  /// \param graph The undirected graph.
 		  /// \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
 		  /// the number of the connected components minus one. Each value of the map
 		  /// will be set exactly once, and the values of a certain component will be
 		  /// set continuously.
 		  /// \return The number of components
+		  /// \return The number of connected components.
 		  /// \note By definition, the empty graph consists
 		  /// of zero connected components.
 		  ///
 		  /// \see connected(), countConnectedComponents()
 		  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 _connectivity_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 StronglyConnectedCutArcsVisitor : public DfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Node Node;
 		      typedef typename Digraph::Arc Arc;
 		      StronglyConnectedCutArcsVisitor(const Digraph& digraph,
 		                                      ArcMap& cutMap,
 		                                      int& cutNum)
 		        : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum),
 		          _compMap(digraph, -1), _num(-1) {
+		      }
 		      void start(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 graph_properties
 		  ///
-		  /// \brief Check whether the given directed graph is strongly connected.
+		  /// \brief Check whether a 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
 		  /// This function checks whether the given directed graph is strongly
 		  /// connected, i.e. any two nodes of the digraph are
 		  /// connected with directed paths in both direction.
 		  /// \return \c false when the graph is not strongly connected.
 		  /// \see connected
 		  ///
-		  /// \note By definition, the empty graph is strongly connected.
+		  /// \return \c true if the digraph is strongly connected.
 		  /// \note By definition, the empty digraph is strongly connected.
 		  ///
 		  /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()
 		  /// \see 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 _connectivity_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;
 		    typedef typename RDigraph::NodeIt RNodeIt;
 		    RDigraph rdigraph(digraph);
-		    typedef DfsVisitor<Digraph> RVisitor;
+		    typedef DfsVisitor<RDigraph> RVisitor;
 		    RVisitor rvisitor;
 		    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
 		    rdfs.init();
 		    rdfs.addSource(source);
 		    rdfs.start();
 		    for (RNodeIt it(rdigraph); it != INVALID; ++it) {
 		      if (!rdfs.reached(it)) {
 		        return false;
+		      }
+		    }
 		    return true;
+		  }
 		  /// \ingroup graph_properties
 		  ///
-		  /// \brief Count the strongly connected components of a directed graph
+		  /// \brief Count the number of strongly connected components of a
 		  /// directed graph
 		  ///
-		  /// Count the strongly connected components of a directed graph.
+		  /// This function counts the number of strongly connected components of
 		  /// the given directed graph.
 		  ///
 		  /// The strongly connected components are the classes of an
-		  /// equivalence relation on the nodes of the graph. Two nodes are in
+		  /// equivalence relation on the nodes of a digraph. Two nodes are in
 		  /// the same class if they are connected with directed paths in both
 		  /// direction.
 		  ///
 		  /// \param digraph The graph.
 		  /// \return The number of components
-		  /// \note By definition, the empty graph has zero
+		  /// \return The number of strongly connected components.
 		  /// \note By definition, the empty digraph has zero
 		  /// strongly connected components.
 		  ///
 		  /// \see stronglyConnected(), stronglyConnectedComponents()
 		  template <typename Digraph>
 		  int countStronglyConnectedComponents(const Digraph& digraph) {
 		    checkConcept<concepts::Digraph, Digraph>();
 		    using namespace _connectivity_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 graph_properties
 		  ///
 		  /// \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.
+		  /// This function finds the strongly connected components of the given
 		  /// directed graph. In addition, the numbering of the components will
 		  /// satisfy that there is no arc going from a higher numbered component
 		  /// to a lower one (i.e. it provides a topological order of the components).
 		  ///
 		  /// The strongly connected components are the classes of an
 		  /// equivalence relation on the nodes of a digraph. Two nodes are in
 		  /// the same class if they are connected with directed paths in both
 		  /// direction.
 		  ///
 		  /// \image html strongly_connected_components.png
 		  /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
 		  ///
 		  /// \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
+		  /// of the map will be set exactly once, and the values of a certain
 		  /// component will be set continuously.
 		  /// \return The number of strongly connected components.
 		  /// \note By definition, the empty digraph has zero
 		  /// strongly connected components.
 		  ///
 		  /// \see stronglyConnected(), countStronglyConnectedComponents()
 		  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 _connectivity_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 graph_properties
 		  ///
 		  /// \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.
 		  /// This function finds the cut arcs of the strongly connected components
 		  /// of the given digraph.
 		  ///
 		  /// The strongly connected components are the classes of an
 		  /// equivalence relation on the nodes of a digraph. Two nodes are in
 		  /// the same class if they are connected with directed paths 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.
+		  /// \param digraph The digraph.
 		  /// \retval cutMap A writable arc map. The values will be set to \c true
 		  /// for the cut arcs (exactly once for each cut arc), and will not be
 		  /// changed for other arcs.
 		  /// \return The number of cut arcs.
 		  ///
-		  /// \return The number of cut arcs
+		  /// \see stronglyConnected(), stronglyConnectedComponents()
 		  template <typename Digraph, typename ArcMap>
-		  int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) {
+		  int stronglyConnectedCutArcs(const Digraph& digraph, 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 _connectivity_bits;
 		    typedef std::vector<Node> Container;
 		    typedef typename Container::iterator Iterator;
-		    Container nodes(countNodes(graph));
+		    Container nodes(countNodes(digraph));
 		    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
 		    Visitor visitor(nodes.begin());
-		    DfsVisit<Digraph, Visitor> dfs(graph, visitor);
+		    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
 		    dfs.init();
-		    for (NodeIt it(graph); it != INVALID; ++it) {
+		    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 rgraph(graph);
+		    RDigraph rdigraph(digraph);
 		    int cutNum = 0;
 		    typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
-		    RVisitor rvisitor(rgraph, cutMap, cutNum);
+		    RVisitor rvisitor(rdigraph, cutMap, cutNum);
-		    DfsVisit<RDigraph, RVisitor> rdfs(rgraph, rvisitor);
+		    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();
+		      }
+		    }
 		    return cutNum;
+		  }
 		  namespace _connectivity_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 graph_properties
 		  ///
-		  /// \brief Checks the graph is bi-node-connected.
+		  /// \brief Check whether an undirected 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.
+		  /// This function checks whether the given undirected graph is
 		  /// bi-node-connected, i.e. any two edges are on same circle.
 		  ///
 		  /// \param graph The graph.
 		  /// \return \c true when the graph bi-node-connected.
 		  /// \return \c true if the graph bi-node-connected.
 		  /// \note By definition, the empty graph is bi-node-connected.
 		  ///
 		  /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()
 		  template <typename Graph>
 		  bool biNodeConnected(const Graph& graph) {
 		    return countBiNodeConnectedComponents(graph) <= 1;
+		  }
 		  /// \ingroup graph_properties
 		  ///
-		  /// \brief Count the biconnected components.
+		  /// \brief Count the number of bi-node-connected components of an
 		  /// undirected graph.
 		  ///
 		  /// 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.
 		  /// This function counts the number of bi-node-connected components of
 		  /// the given undirected graph.
 		  ///
 		  /// \param graph The graph.
 		  /// \return The number of components.
 		  /// The bi-node-connected components are the classes of an equivalence
 		  /// relation on the edges of a undirected graph. Two edges are in the
 		  /// same class if they are on same circle.
 		  ///
 		  /// \return The number of bi-node-connected components.
 		  ///
 		  /// \see biNodeConnected(), biNodeConnectedComponents()
 		  template <typename Graph>
 		  int countBiNodeConnectedComponents(const Graph& graph) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::NodeIt NodeIt;
 		    using namespace _connectivity_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 graph_properties
 		  ///
 		  /// \brief Find the bi-node-connected components.
+		  /// \brief Find the bi-node-connected components of an undirected graph.
 		  ///
 		  /// 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.
 		  /// This function finds the bi-node-connected components of the given
 		  /// undirected graph.
 		  ///
 		  /// The bi-node-connected components are the classes of an equivalence
 		  /// relation on the edges of a undirected graph. Two edges are in the
 		  /// same class if they are on same circle.
 		  ///
 		  /// \image html node_biconnected_components.png
 		  /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
 		  ///
 		  /// \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.
 		  /// \param graph The undirected graph.
 		  /// \retval compMap A writable edge map. The values will be set from 0
 		  /// to the number of the bi-node-connected components minus one. Each
 		  /// value of the map will be set exactly once, and the values of a
 		  /// certain component will be set continuously.
 		  /// \return The number of bi-node-connected components.
 		  ///
 		  /// \see biNodeConnected(), countBiNodeConnectedComponents()
 		  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 _connectivity_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 graph_properties
 		  ///
 		  /// \brief Find the bi-node-connected cut nodes.
+		  /// \brief Find the bi-node-connected cut nodes in an undirected graph.
 		  ///
 		  /// 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.
+		  /// This function finds the bi-node-connected cut nodes in the given
 		  /// undirected graph.
 		  ///
 		  /// \param graph The graph.
 		  /// \retval cutMap A writable edge map. The values will be set true when
-		  /// the node separate two or more components.
+		  /// The bi-node-connected components are the classes of an equivalence
 		  /// relation on the edges of a undirected graph. Two edges are in the
 		  /// same class if they are on same circle.
 		  /// The bi-node-connected components are separted by the cut nodes of
 		  /// the components.
 		  ///
 		  /// \param graph The undirected graph.
 		  /// \retval cutMap A writable node map. The values will be set to
 		  /// \c true for the nodes that separate two or more components
 		  /// (exactly once for each cut node), and will not be changed for
 		  /// other nodes.
 		  /// \return The number of the cut nodes.
 		  ///
 		  /// \see biNodeConnected(), biNodeConnectedComponents()
 		  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 _connectivity_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 _connectivity_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 graph_properties
 		  ///
-		  /// \brief Checks that the graph is bi-edge-connected.
+		  /// \brief Check whether an undirected 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.
+		  /// This function checks whether the given undirected graph is
 		  /// bi-edge-connected, i.e. any two nodes are connected with at least
 		  /// two edge-disjoint paths.
 		  ///
 		  /// \param graph The undirected graph.
 		  /// \return The number of components.
 		  /// \return \c true if the graph is bi-edge-connected.
 		  /// \note By definition, the empty graph is bi-edge-connected.
 		  ///
 		  /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents()
 		  template <typename Graph>
 		  bool biEdgeConnected(const Graph& graph) {
 		    return countBiEdgeConnectedComponents(graph) <= 1;
+		  }
 		  /// \ingroup graph_properties
 		  ///
-		  /// \brief Count the bi-edge-connected components.
+		  /// \brief Count the number of bi-edge-connected components of an
 		  /// undirected graph.
 		  ///
 		  /// 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.
 		  /// This function counts the number of bi-edge-connected components of
 		  /// the given undirected graph.
 		  ///
 		  /// \param graph The undirected graph.
 		  /// \return The number of components.
 		  /// The bi-edge-connected components are the classes of an equivalence
 		  /// relation on the nodes of an undirected graph. Two nodes are in the
 		  /// same class if they are connected with at least two edge-disjoint
 		  /// paths.
 		  ///
 		  /// \return The number of bi-edge-connected components.
 		  ///
 		  /// \see biEdgeConnected(), biEdgeConnectedComponents()
 		  template <typename Graph>
 		  int countBiEdgeConnectedComponents(const Graph& graph) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::NodeIt NodeIt;
 		    using namespace _connectivity_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 graph_properties
 		  ///
 		  /// \brief Find the bi-edge-connected components.
+		  /// \brief Find the bi-edge-connected components of an undirected graph.
 		  ///
 		  /// 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.
 		  /// This function finds the bi-edge-connected components of the given
 		  /// undirected graph.
 		  ///
 		  /// The bi-edge-connected components are the classes of an equivalence
 		  /// relation on the nodes of an undirected graph. Two nodes are in the
 		  /// same class if they are connected with at least two edge-disjoint
 		  /// paths.
 		  ///
 		  /// \image html edge_biconnected_components.png
 		  /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
 		  ///
 		  /// \param graph The graph.
+		  /// \param graph The undirected 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.
 		  /// the number of the bi-edge-connected components minus one. Each value
 		  /// of the map will be set exactly once, and the values of a certain
 		  /// component will be set continuously.
 		  /// \return The number of bi-edge-connected components.
 		  ///
 		  /// \see biEdgeConnected(), countBiEdgeConnectedComponents()
 		  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 _connectivity_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 graph_properties
 		  ///
 		  /// \brief Find the bi-edge-connected cut edges.
+		  /// \brief Find the bi-edge-connected cut edges in an undirected graph.
 		  ///
 		  /// 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.
 		  /// This function finds the bi-edge-connected cut edges in the given
 		  /// undirected graph.
 		  ///
 		  /// \param graph The graph.
 		  /// \retval cutMap A writable node map. The values will be set true when the
-		  /// edge is a cut edge.
+		  /// The bi-edge-connected components are the classes of an equivalence
 		  /// relation on the nodes of an undirected graph. Two nodes are in the
 		  /// same class if they are connected with at least two edge-disjoint
 		  /// paths.
 		  /// The bi-edge-connected components are separted by the cut edges of
 		  /// the components.
 		  ///
 		  /// \param graph The undirected graph.
 		  /// \retval cutMap A writable edge map. The values will be set to \c true
 		  /// for the cut edges (exactly once for each cut edge), and will not be
 		  /// changed for other edges.
 		  /// \return The number of cut edges.
 		  ///
 		  /// \see biEdgeConnected(), biEdgeConnectedComponents()
 		  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 _connectivity_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 _connectivity_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 graph_properties
 		  ///
 		  /// \brief Check whether a digraph is DAG.
 		  ///
 		  /// This function checks whether the given digraph is DAG, i.e.
 		  /// \e Directed \e Acyclic \e Graph.
 		  /// \return \c true if there is no directed cycle in the digraph.
 		  /// \see acyclic()
 		  template <typename Digraph>
 		  bool dag(const Digraph& digraph) {
 		    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(digraph);
 		    ProcessedMap processed(digraph);
 		    dfs.processedMap(processed);
 		    dfs.init();
 		    for (NodeIt it(digraph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        while (!dfs.emptyQueue()) {
 		          Arc arc = dfs.nextArc();
 		          Node target = digraph.target(arc);
 		          if (dfs.reached(target) && !processed[target]) {
 		            return false;
+		          }
 		          dfs.processNextArc();
+		        }
+		      }
+		    }
 		    return true;
+		  }
 		  /// \ingroup graph_properties
 		  ///
 		  /// \brief Sort the nodes of a DAG into topolgical order.
 		  ///
-		  /// Sort the nodes of a DAG into topolgical order.
+		  /// This function sorts the nodes of the given acyclic digraph (DAG)
 		  /// into topolgical order.
 		  ///
-		  /// \param graph The graph. It must be directed and acyclic.
+		  /// \param digraph The digraph, which must be DAG.
 		  /// \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.
 		  /// the number of the nodes in the digraph minus one. Each value of the
 		  /// map will be set exactly once, and the values will be set descending
 		  /// order.
 		  ///
 		  /// \see checkedTopologicalSort
 		  /// \see dag
 		  /// \see dag(), checkedTopologicalSort()
 		  template <typename Digraph, typename NodeMap>
-		  void topologicalSort(const Digraph& graph, NodeMap& order) {
+		  void topologicalSort(const Digraph& digraph, NodeMap& order) {
 		    using namespace _connectivity_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));
+		      visitor(order, countNodes(digraph));
 		    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
-		      dfs(graph, visitor);
+		      dfs(digraph, visitor);
 		    dfs.init();
-		    for (NodeIt it(graph); it != INVALID; ++it) {
+		    for (NodeIt it(digraph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
+		  }
 		  /// \ingroup graph_properties
 		  ///
 		  /// \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.
 		  /// This function sorts the nodes of the given acyclic digraph (DAG)
 		  /// into topolgical order and also checks whether the given digraph
 		  /// is DAG.
 		  ///
 		  /// \param digraph 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 \c false when the graph is not DAG.
 		  /// \param digraph The digraph.
 		  /// \retval order A readable and writable node map. The values will be
 		  /// set from 0 to the number of the nodes in the digraph minus one.
 		  /// Each value of the map will be set exactly once, and the values will
 		  /// be set descending order.
 		  /// \return \c false if the digraph is not DAG.
 		  ///
 		  /// \see topologicalSort
 		  /// \see dag
 		  /// \see dag(), topologicalSort()
 		  template <typename Digraph, typename NodeMap>
 		  bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
 		    using namespace _connectivity_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;
 		    for (NodeIt it(digraph); it != INVALID; ++it) {
 		      order.set(it, -1);
+		    }
 		    TopologicalSortVisitor<Digraph, NodeMap>
 		      visitor(order, countNodes(digraph));
 		    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
 		      dfs(digraph, visitor);
 		    dfs.init();
 		    for (NodeIt it(digraph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        while (!dfs.emptyQueue()) {
 		           Arc arc = dfs.nextArc();
 		           Node target = digraph.target(arc);
 		           if (dfs.reached(target) && order[target] == -1) {
 		             return false;
+		           }
 		           dfs.processNextArc();
+		         }
+		      }
+		    }
 		    return true;
+		  }
 		  /// \ingroup graph_properties
 		  ///
-		  /// \brief Check that the given directed graph is a DAG.
+		  /// \brief Check whether an undirected graph is acyclic.
 		  ///
 		  /// Check that the given directed graph is a DAG. The DAG is
 		  /// an Directed Acyclic Digraph.
 		  /// \return \c false when the graph is not DAG.
 		  /// \see acyclic
 		  template <typename Digraph>
 		  bool dag(const Digraph& digraph) {
 		    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(digraph);
 		    ProcessedMap processed(digraph);
 		    dfs.processedMap(processed);
 		    dfs.init();
 		    for (NodeIt it(digraph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        while (!dfs.emptyQueue()) {
 		          Arc edge = dfs.nextArc();
 		          Node target = digraph.target(edge);
 		          if (dfs.reached(target) && !processed[target]) {
 		            return false;
+		          }
 		          dfs.processNextArc();
+		        }
+		      }
+		    }
 		    return true;
+		  }
 		  /// \ingroup graph_properties
 		  ///
 		  /// \brief Check that the given undirected graph is acyclic.
 		  ///
 		  /// Check that the given undirected graph acyclic.
 		  /// \param graph The undirected graph.
 		  /// \return \c true when there is no circle in the graph.
 		  /// \see dag
 		  /// This function checks whether the given undirected graph is acyclic.
 		  /// \return \c true if there is no cycle 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);
+		          Arc arc = dfs.nextArc();
 		          Node source = graph.source(arc);
 		          Node target = graph.target(arc);
 		          if (dfs.reached(target) &&
-		              dfs.predArc(source) != graph.oppositeArc(edge)) {
+		              dfs.predArc(source) != graph.oppositeArc(arc)) {
 		            return false;
+		          }
 		          dfs.processNextArc();
+		        }
+		      }
+		    }
 		    return true;
+		  }
 		  /// \ingroup graph_properties
 		  ///
-		  /// \brief Check that the given undirected graph is tree.
+		  /// \brief Check whether an undirected graph is tree.
 		  ///
 		  /// Check that the given undirected graph is tree.
 		  /// \param graph The undirected graph.
-		  /// \return \c true when the graph is acyclic and connected.
+		  /// This function checks whether the given undirected graph is tree.
 		  /// \return \c true if the graph is acyclic and connected.
 		  /// \see acyclic(), 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;
 		    if (NodeIt(graph) == INVALID) return true;
 		    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);
+		      Arc arc = dfs.nextArc();
 		      Node source = graph.source(arc);
 		      Node target = graph.target(arc);
 		      if (dfs.reached(target) &&
-		          dfs.predArc(source) != graph.oppositeArc(edge)) {
+		          dfs.predArc(source) != graph.oppositeArc(arc)) {
 		        return false;
+		      }
 		      dfs.processNextArc();
+		    }
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        return false;
+		      }
+		    }
 		    return true;
+		  }
 		  namespace _connectivity_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 graph_properties
 		  ///
-		  /// \brief Check if the given undirected graph is bipartite or not
+		  /// \brief Check whether an undirected graph is bipartite.
 		  ///
 		  /// 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 \c true if \c graph is bipartite, \c false otherwise.
-		  /// \sa bipartitePartitions
+		  /// The function checks whether the given undirected graph is bipartite.
 		  /// \return \c true if the graph is bipartite.
 		  ///
 		  /// \see bipartitePartitions()
 		  template<typename Graph>
-		  inline bool bipartite(const Graph &graph){
 		  bool bipartite(const Graph &graph){
 		    using namespace _connectivity_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 graph_properties
 		  ///
-		  /// \brief Check if the given undirected graph is bipartite or not
+		  /// \brief Find the bipartite partitions of an undirected graph.
 		  ///
 		  /// 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.
 		  /// This function checks whether the given undirected graph is bipartite
 		  /// and gives back the bipartite partitions.
 		  ///
 		  /// \image html bipartite_partitions.png
 		  /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
 		  ///
 		  /// \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 \c true if \c graph is bipartite, \c false otherwise.
+		  /// \retval partMap A writable node map of \c bool (or convertible) value
 		  /// type. The values will be set to \c true for one component and
 		  /// \c false for the other one.
 		  /// \return \c true if the graph is bipartite, \c false otherwise.
 		  ///
 		  /// \see bipartite()
 		  template<typename Graph, typename NodeMap>
-		  inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
 		  bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
 		    using namespace _connectivity_bits;
 		    checkConcept<concepts::Graph, Graph>();
 		    checkConcept<concepts::WriteMap<typename Graph::Node, bool>, NodeMap>();
 		    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.
+		  /// \ingroup graph_properties
 		  ///
 		  /// Returns true when there are not loop edges in the graph.
 		  template <typename Digraph>
 		  bool loopFree(const Digraph& digraph) {
 		    for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) {
-		      if (digraph.source(it) == digraph.target(it)) return false;
+		  /// \brief Check whether the given graph contains no loop arcs/edges.
 		  ///
 		  /// This function returns \c true if there are no loop arcs/edges in
 		  /// the given graph. It works for both directed and undirected graphs.
 		  template <typename Graph>
 		  bool loopFree(const Graph& graph) {
 		    for (typename Graph::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.
+		  /// \ingroup graph_properties
 		  ///
-		  /// Returns true when there are not parallel edges in the graph.
+		  /// \brief Check whether the given graph contains no parallel arcs/edges.
 		  ///
 		  /// This function returns \c true if there are no parallel arcs/edges in
 		  /// the given graph. It works for both directed and undirected graphs.
 		  template <typename Graph>
 		  bool parallelFree(const Graph& graph) {
 		    typename Graph::template NodeMap<int> reached(graph, 0);
 		    int cnt = 1;
 		    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
 		      for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
 		        if (reached[graph.target(a)] == cnt) return false;
 		        reached[graph.target(a)] = cnt;
+		      }
 		      ++cnt;
+		    }
 		    return true;
+		  }
 		  /// \brief Returns true when there are not loop edges and parallel
 		  /// edges in the graph.
 		  /// \ingroup graph_properties
 		  ///
 		  /// Returns true when there are not loop edges and parallel edges in
 		  /// the graph.
 		  /// \brief Check whether the given graph is simple.
 		  ///
 		  /// This function returns \c true if the given graph is simple, i.e.
 		  /// it contains no loop arcs/edges and no parallel arcs/edges.
 		  /// The function works for both directed and undirected graphs.
 		  /// \see loopFree(), parallelFree()
 		  template <typename Graph>
 		  bool simpleGraph(const Graph& graph) {
 		    typename Graph::template NodeMap<int> reached(graph, 0);
 		    int cnt = 1;
 		    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
 		      reached[n] = cnt;
 		      for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
 		        if (reached[graph.target(a)] == cnt) return false;
 		        reached[graph.target(a)] = cnt;
+		      }
 		      ++cnt;
+		    }
 		    return true;
+		  }
 		} //namespace lemon
 		#endif //LEMON_CONNECTIVITY_H

lemon/euler.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-2009
 		 * 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_EULER_H
 		#define LEMON_EULER_H
 		#include<lemon/core.h>
 		#include<lemon/adaptors.h>
 		#include<lemon/connectivity.h>
 		#include <list>
 		/// \ingroup graph_properties
 		/// \file
 		/// \brief Euler tour iterators and a function for checking the \e Eulerian
 		/// property.
 		///
 		///This file provides Euler tour iterators and a function to check
 		///if a (di)graph is \e Eulerian.
 		namespace lemon {
 		  ///Euler tour iterator for digraphs.
 		  /// \ingroup graph_prop
 		  ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed
 		  ///graph (if there exists) and it converts to the \c Arc type of the digraph.
 		  ///
 		  ///For example, if the given digraph has an Euler tour (i.e it has only one
 		  ///non-trivial component and the in-degree is equal to the out-degree
 		  ///for all nodes), then the following code will put the arcs of \c g
 		  ///to the vector \c et according to an Euler tour of \c g.
 		  ///\code
 		  ///  std::vector<ListDigraph::Arc> et;
 		  ///  for(DiEulerIt<ListDigraph> e(g); e!=INVALID; ++e)
 		  ///    et.push_back(e);
 		  ///\endcode
 		  ///If \c g has no Euler tour, then the resulted walk will not be closed
 		  ///or not contain all arcs.
 		  ///\sa EulerIt
 		  template<typename GR>
 		  class DiEulerIt
+		  {
 		    typedef typename GR::Node Node;
 		    typedef typename GR::NodeIt NodeIt;
 		    typedef typename GR::Arc Arc;
 		    typedef typename GR::ArcIt ArcIt;
 		    typedef typename GR::OutArcIt OutArcIt;
 		    typedef typename GR::InArcIt InArcIt;
 		    const GR &g;
 		    typename GR::template NodeMap<OutArcIt> narc;
 		    std::list<Arc> euler;
 		  public:
 		    ///Constructor
 		    ///Constructor.
 		    ///\param gr A digraph.
 		    ///\param start The starting point of the tour. If it is not given,
 		    ///the tour will start from the first node that has an outgoing arc.
 		    DiEulerIt(const GR &gr, typename GR::Node start = INVALID)
 		      : g(gr), narc(g)
+		    {
 		      if (start==INVALID) {
 		        NodeIt n(g);
 		        while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;
 		        start=n;
+		      }
 		      if (start!=INVALID) {
 		        for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n);
 		        while (narc[start]!=INVALID) {
 		          euler.push_back(narc[start]);
 		          Node next=g.target(narc[start]);
 		          ++narc[start];
 		          start=next;
+		        }
+		      }
+		    }
 		    ///Arc conversion
 		    operator Arc() { return euler.empty()?INVALID:euler.front(); }
 		    ///Compare with \c INVALID
 		    bool operator==(Invalid) { return euler.empty(); }
 		    ///Compare with \c INVALID
 		    bool operator!=(Invalid) { return !euler.empty(); }
 		    ///Next arc of the tour
 		    ///Next arc of the tour
 		    ///
 		    DiEulerIt &operator++() {
 		      Node s=g.target(euler.front());
 		      euler.pop_front();
 		      typename std::list<Arc>::iterator next=euler.begin();
 		      while(narc[s]!=INVALID) {
 		        euler.insert(next,narc[s]);
 		        Node n=g.target(narc[s]);
 		        ++narc[s];
 		        s=n;
+		      }
 		      return *this;
+		    }
 		    ///Postfix incrementation
 		    /// Postfix incrementation.
 		    ///
 		    ///\warning This incrementation
 		    ///returns an \c Arc, not a \ref DiEulerIt, as one may
 		    ///expect.
 		    Arc operator++(int)
+		    {
 		      Arc e=*this;
 		      ++(*this);
 		      return e;
+		    }
 		  };
 		  ///Euler tour iterator for graphs.
 		  /// \ingroup graph_properties
 		  ///This iterator provides an Euler tour (Eulerian circuit) of an
 		  ///\e undirected graph (if there exists) and it converts to the \c Arc
 		  ///and \c Edge types of the graph.
 		  ///
 		  ///For example, if the given graph has an Euler tour (i.e it has only one
 		  ///non-trivial component and the degree of each node is even),
 		  ///the following code will print the arc IDs according to an
 		  ///Euler tour of \c g.
 		  ///\code
 		  ///  for(EulerIt<ListGraph> e(g); e!=INVALID; ++e) {
 		  ///    std::cout << g.id(Edge(e)) << std::eol;
 		  ///  }
 		  ///\endcode
 		  ///Although this iterator is for undirected graphs, it still returns
 		  ///arcs in order to indicate the direction of the tour.
 		  ///(But arcs convert to edges, of course.)
 		  ///
 		  ///If \c g has no Euler tour, then the resulted walk will not be closed
 		  ///or not contain all edges.
 		  template<typename GR>
 		  class EulerIt
+		  {
 		    typedef typename GR::Node Node;
 		    typedef typename GR::NodeIt NodeIt;
 		    typedef typename GR::Arc Arc;
 		    typedef typename GR::Edge Edge;
 		    typedef typename GR::ArcIt ArcIt;
 		    typedef typename GR::OutArcIt OutArcIt;
 		    typedef typename GR::InArcIt InArcIt;
 		    const GR &g;
 		    typename GR::template NodeMap<OutArcIt> narc;
 		    typename GR::template EdgeMap<bool> visited;
 		    std::list<Arc> euler;
 		  public:
 		    ///Constructor
 		    ///Constructor.
 		    ///\param gr A graph.
 		    ///\param start The starting point of the tour. If it is not given,
 		    ///the tour will start from the first node that has an incident edge.
 		    EulerIt(const GR &gr, typename GR::Node start = INVALID)
 		      : g(gr), narc(g), visited(g, false)
+		    {
 		      if (start==INVALID) {
 		        NodeIt n(g);
 		        while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;
 		        start=n;
+		      }
 		      if (start!=INVALID) {
 		        for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n);
 		        while(narc[start]!=INVALID) {
 		          euler.push_back(narc[start]);
 		          visited[narc[start]]=true;
 		          Node next=g.target(narc[start]);
 		          ++narc[start];
 		          start=next;
 		          while(narc[start]!=INVALID && visited[narc[start]]) ++narc[start];
+		        }
+		      }
+		    }
 		    ///Arc conversion
 		    operator Arc() const { return euler.empty()?INVALID:euler.front(); }
 		    ///Edge conversion
 		    operator Edge() const { return euler.empty()?INVALID:euler.front(); }
 		    ///Compare with \c INVALID
 		    bool operator==(Invalid) const { return euler.empty(); }
 		    ///Compare with \c INVALID
 		    bool operator!=(Invalid) const { return !euler.empty(); }
 		    ///Next arc of the tour
 		    ///Next arc of the tour
 		    ///
 		    EulerIt &operator++() {
 		      Node s=g.target(euler.front());
 		      euler.pop_front();
 		      typename std::list<Arc>::iterator next=euler.begin();
 		      while(narc[s]!=INVALID) {
 		        while(narc[s]!=INVALID && visited[narc[s]]) ++narc[s];
 		        if(narc[s]==INVALID) break;
 		        else {
 		          euler.insert(next,narc[s]);
 		          visited[narc[s]]=true;
 		          Node n=g.target(narc[s]);
 		          ++narc[s];
 		          s=n;
+		        }
+		      }
 		      return *this;
+		    }
 		    ///Postfix incrementation
 		    /// Postfix incrementation.
 		    ///
 		    ///\warning This incrementation returns an \c Arc (which converts to
 		    ///an \c Edge), not an \ref EulerIt, as one may expect.
 		    Arc operator++(int)
+		    {
 		      Arc e=*this;
 		      ++(*this);
 		      return e;
+		    }
 		  };
-		  ///Check if the given graph is \e Eulerian
 		  ///Check if the given graph is Eulerian
 		  /// \ingroup graph_properties
-		  ///This function checks if the given graph is \e Eulerian.
 		  ///This function checks if the given graph is Eulerian.
 		  ///It works for both directed and undirected graphs.
 		  ///
 		  ///By definition, a digraph is called \e Eulerian if
 		  ///and only if it is connected and the number of incoming and outgoing
 		  ///arcs are the same for each node.
 		  ///Similarly, an undirected graph is called \e Eulerian if
 		  ///and only if it is connected and the number of incident edges is even
 		  ///for each node.
 		  ///
 		  ///\note There are (di)graphs that are not Eulerian, but still have an
 		  /// Euler tour, since they may contain isolated nodes.
 		  ///
 		  ///\sa DiEulerIt, EulerIt
 		  template<typename GR>
 		#ifdef DOXYGEN
 		  bool
 		#else
 		  typename enable_if<UndirectedTagIndicator<GR>,bool>::type
 		  eulerian(const GR &g)
+		  {
 		    for(typename GR::NodeIt n(g);n!=INVALID;++n)
 		      if(countIncEdges(g,n)%2) return false;
 		    return connected(g);
+		  }
 		  template<class GR>
 		  typename disable_if<UndirectedTagIndicator<GR>,bool>::type
 		#endif
 		  eulerian(const GR &g)
+		  {
 		    for(typename GR::NodeIt n(g);n!=INVALID;++n)
 		      if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
 		    return connected(undirector(g));
+		  }
+		}
 		#endif

0 comments (0 inline)

RhodeCode

Login to your account