LEMON/LEMON-official Changeset - r699:e2f99a473998

Repositories » LEMON » LEMON-official

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

Changeset - r699:e2f99a473998

« 696:76cbcb
« 698:3adf5e

700:682941 »

r699:e2f99a473998

Thu, 07 May 2009 13:19:41

[Not Reviewed]

0 comments (0 inline)

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

Merge

0 4 1

merge default

0 files changed with 625 insertions and 247 deletions:

test/connectivity_test.cc

297

lemon/connectivity.h

323

245

lemon/euler.h

test/CMakeLists.txt

test/Makefile.am

↑ Collapse diff ↑

test/connectivity_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-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.
+		 *
 		 */
 		#include <lemon/connectivity.h>
 		#include <lemon/list_graph.h>
 		#include <lemon/adaptors.h>
 		#include "test_tools.h"
 		using namespace lemon;
 		int main()
+		{
 		  typedef ListDigraph Digraph;
 		  typedef Undirector<Digraph> Graph;
+		  {
 		    Digraph d;
 		    Digraph::NodeMap<int> order(d);
 		    Graph g(d);
 		    check(stronglyConnected(d), "The empty digraph is strongly connected");
 		    check(countStronglyConnectedComponents(d) == 0,
 		          "The empty digraph has 0 strongly connected component");
 		    check(connected(g), "The empty graph is connected");
 		    check(countConnectedComponents(g) == 0,
 		          "The empty graph has 0 connected component");
 		    check(biNodeConnected(g), "The empty graph is bi-node-connected");
 		    check(countBiNodeConnectedComponents(g) == 0,
 		          "The empty graph has 0 bi-node-connected component");
 		    check(biEdgeConnected(g), "The empty graph is bi-edge-connected");
 		    check(countBiEdgeConnectedComponents(g) == 0,
 		          "The empty graph has 0 bi-edge-connected component");
 		    check(dag(d), "The empty digraph is DAG.");
 		    check(checkedTopologicalSort(d, order), "The empty digraph is DAG.");
 		    check(loopFree(d), "The empty digraph is loop-free.");
 		    check(parallelFree(d), "The empty digraph is parallel-free.");
 		    check(simpleGraph(d), "The empty digraph is simple.");
 		    check(acyclic(g), "The empty graph is acyclic.");
 		    check(tree(g), "The empty graph is tree.");
 		    check(bipartite(g), "The empty graph is bipartite.");
 		    check(loopFree(g), "The empty graph is loop-free.");
 		    check(parallelFree(g), "The empty graph is parallel-free.");
 		    check(simpleGraph(g), "The empty graph is simple.");
+		  }
+		  {
 		    Digraph d;
 		    Digraph::NodeMap<int> order(d);
 		    Graph g(d);
 		    Digraph::Node n = d.addNode();
 		    check(stronglyConnected(d), "This digraph is strongly connected");
 		    check(countStronglyConnectedComponents(d) == 1,
 		          "This digraph has 1 strongly connected component");
 		    check(connected(g), "This graph is connected");
 		    check(countConnectedComponents(g) == 1,
 		          "This graph has 1 connected component");
 		    check(biNodeConnected(g), "This graph is bi-node-connected");
 		    check(countBiNodeConnectedComponents(g) == 0,
 		          "This graph has 0 bi-node-connected component");
 		    check(biEdgeConnected(g), "This graph is bi-edge-connected");
 		    check(countBiEdgeConnectedComponents(g) == 1,
 		          "This graph has 1 bi-edge-connected component");
 		    check(dag(d), "This digraph is DAG.");
 		    check(checkedTopologicalSort(d, order), "This digraph is DAG.");
 		    check(loopFree(d), "This digraph is loop-free.");
 		    check(parallelFree(d), "This digraph is parallel-free.");
 		    check(simpleGraph(d), "This digraph is simple.");
 		    check(acyclic(g), "This graph is acyclic.");
 		    check(tree(g), "This graph is tree.");
 		    check(bipartite(g), "This graph is bipartite.");
 		    check(loopFree(g), "This graph is loop-free.");
 		    check(parallelFree(g), "This graph is parallel-free.");
 		    check(simpleGraph(g), "This graph is simple.");
+		  }
+		  {
 		    Digraph d;
 		    Digraph::NodeMap<int> order(d);
 		    Graph g(d);
 		    Digraph::Node n1 = d.addNode();
 		    Digraph::Node n2 = d.addNode();
 		    Digraph::Node n3 = d.addNode();
 		    Digraph::Node n4 = d.addNode();
 		    Digraph::Node n5 = d.addNode();
 		    Digraph::Node n6 = d.addNode();
 		    d.addArc(n1, n3);
 		    d.addArc(n3, n2);
 		    d.addArc(n2, n1);
 		    d.addArc(n4, n2);
 		    d.addArc(n4, n3);
 		    d.addArc(n5, n6);
 		    d.addArc(n6, n5);
 		    check(!stronglyConnected(d), "This digraph is not strongly connected");
 		    check(countStronglyConnectedComponents(d) == 3,
 		          "This digraph has 3 strongly connected components");
 		    check(!connected(g), "This graph is not connected");
 		    check(countConnectedComponents(g) == 2,
 		          "This graph has 2 connected components");
 		    check(!dag(d), "This digraph is not DAG.");
 		    check(!checkedTopologicalSort(d, order), "This digraph is not DAG.");
 		    check(loopFree(d), "This digraph is loop-free.");
 		    check(parallelFree(d), "This digraph is parallel-free.");
 		    check(simpleGraph(d), "This digraph is simple.");
 		    check(!acyclic(g), "This graph is not acyclic.");
 		    check(!tree(g), "This graph is not tree.");
 		    check(!bipartite(g), "This graph is not bipartite.");
 		    check(loopFree(g), "This graph is loop-free.");
 		    check(!parallelFree(g), "This graph is not parallel-free.");
 		    check(!simpleGraph(g), "This graph is not simple.");
 		    d.addArc(n3, n3);
 		    check(!loopFree(d), "This digraph is not loop-free.");
 		    check(!loopFree(g), "This graph is not loop-free.");
 		    check(!simpleGraph(d), "This digraph is not simple.");
 		    d.addArc(n3, n2);
 		    check(!parallelFree(d), "This digraph is not parallel-free.");
+		  }
+		  {
 		    Digraph d;
 		    Digraph::ArcMap<bool> cutarcs(d, false);
 		    Graph g(d);
 		    Digraph::Node n1 = d.addNode();
 		    Digraph::Node n2 = d.addNode();
 		    Digraph::Node n3 = d.addNode();
 		    Digraph::Node n4 = d.addNode();
 		    Digraph::Node n5 = d.addNode();
 		    Digraph::Node n6 = d.addNode();
 		    Digraph::Node n7 = d.addNode();
 		    Digraph::Node n8 = d.addNode();
 		    d.addArc(n1, n2);
 		    d.addArc(n5, n1);
 		    d.addArc(n2, n8);
 		    d.addArc(n8, n5);
 		    d.addArc(n6, n4);
 		    d.addArc(n4, n6);
 		    d.addArc(n2, n5);
 		    d.addArc(n1, n8);
 		    d.addArc(n6, n7);
 		    d.addArc(n7, n6);
 		    check(!stronglyConnected(d), "This digraph is not strongly connected");
 		    check(countStronglyConnectedComponents(d) == 3,
 		          "This digraph has 3 strongly connected components");
 		    Digraph::NodeMap<int> scomp1(d);
 		    check(stronglyConnectedComponents(d, scomp1) == 3,
 		          "This digraph has 3 strongly connected components");
 		    check(scomp1[n1] != scomp1[n3] && scomp1[n1] != scomp1[n4] &&
 		          scomp1[n3] != scomp1[n4], "Wrong stronglyConnectedComponents()");
 		    check(scomp1[n1] == scomp1[n2] && scomp1[n1] == scomp1[n5] &&
 		          scomp1[n1] == scomp1[n8], "Wrong stronglyConnectedComponents()");
 		    check(scomp1[n4] == scomp1[n6] && scomp1[n4] == scomp1[n7],
 		          "Wrong stronglyConnectedComponents()");
 		    Digraph::ArcMap<bool> scut1(d, false);
 		    check(stronglyConnectedCutArcs(d, scut1) == 0,
 		          "This digraph has 0 strongly connected cut arc.");
 		    for (Digraph::ArcIt a(d); a != INVALID; ++a) {
 		      check(!scut1[a], "Wrong stronglyConnectedCutArcs()");
+		    }
 		    check(!connected(g), "This graph is not connected");
 		    check(countConnectedComponents(g) == 3,
 		          "This graph has 3 connected components");
 		    Graph::NodeMap<int> comp(g);
 		    check(connectedComponents(g, comp) == 3,
 		          "This graph has 3 connected components");
 		    check(comp[n1] != comp[n3] && comp[n1] != comp[n4] &&
 		          comp[n3] != comp[n4], "Wrong connectedComponents()");
 		    check(comp[n1] == comp[n2] && comp[n1] == comp[n5] &&
 		          comp[n1] == comp[n8], "Wrong connectedComponents()");
 		    check(comp[n4] == comp[n6] && comp[n4] == comp[n7],
 		          "Wrong connectedComponents()");
 		    cutarcs[d.addArc(n3, n1)] = true;
 		    cutarcs[d.addArc(n3, n5)] = true;
 		    cutarcs[d.addArc(n3, n8)] = true;
 		    cutarcs[d.addArc(n8, n6)] = true;
 		    cutarcs[d.addArc(n8, n7)] = true;
 		    check(!stronglyConnected(d), "This digraph is not strongly connected");
 		    check(countStronglyConnectedComponents(d) == 3,
 		          "This digraph has 3 strongly connected components");
 		    Digraph::NodeMap<int> scomp2(d);
 		    check(stronglyConnectedComponents(d, scomp2) == 3,
 		          "This digraph has 3 strongly connected components");
 		    check(scomp2[n3] == 0, "Wrong stronglyConnectedComponents()");
 		    check(scomp2[n1] == 1 && scomp2[n2] == 1 && scomp2[n5] == 1 &&
 		          scomp2[n8] == 1, "Wrong stronglyConnectedComponents()");
 		    check(scomp2[n4] == 2 && scomp2[n6] == 2 && scomp2[n7] == 2,
 		          "Wrong stronglyConnectedComponents()");
 		    Digraph::ArcMap<bool> scut2(d, false);
 		    check(stronglyConnectedCutArcs(d, scut2) == 5,
 		          "This digraph has 5 strongly connected cut arcs.");
 		    for (Digraph::ArcIt a(d); a != INVALID; ++a) {
 		      check(scut2[a] == cutarcs[a], "Wrong stronglyConnectedCutArcs()");
+		    }
+		  }
+		  {
 		    // DAG example for topological sort from the book New Algorithms
 		    // (T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein)
 		    Digraph d;
 		    Digraph::NodeMap<int> order(d);
 		    Digraph::Node belt = d.addNode();
 		    Digraph::Node trousers = d.addNode();
 		    Digraph::Node necktie = d.addNode();
 		    Digraph::Node coat = d.addNode();
 		    Digraph::Node socks = d.addNode();
 		    Digraph::Node shirt = d.addNode();
 		    Digraph::Node shoe = d.addNode();
 		    Digraph::Node watch = d.addNode();
 		    Digraph::Node pants = d.addNode();
 		    d.addArc(socks, shoe);
 		    d.addArc(pants, shoe);
 		    d.addArc(pants, trousers);
 		    d.addArc(trousers, shoe);
 		    d.addArc(trousers, belt);
 		    d.addArc(belt, coat);
 		    d.addArc(shirt, belt);
 		    d.addArc(shirt, necktie);
 		    d.addArc(necktie, coat);
 		    check(dag(d), "This digraph is DAG.");
 		    topologicalSort(d, order);
 		    for (Digraph::ArcIt a(d); a != INVALID; ++a) {
 		      check(order[d.source(a)] < order[d.target(a)],
 		            "Wrong topologicalSort()");
+		    }
+		  }
+		  {
 		    ListGraph g;
 		    ListGraph::NodeMap<bool> map(g);
 		    ListGraph::Node n1 = g.addNode();
 		    ListGraph::Node n2 = g.addNode();
 		    ListGraph::Node n3 = g.addNode();
 		    ListGraph::Node n4 = g.addNode();
 		    ListGraph::Node n5 = g.addNode();
 		    ListGraph::Node n6 = g.addNode();
 		    ListGraph::Node n7 = g.addNode();
 		    g.addEdge(n1, n3);
 		    g.addEdge(n1, n4);
 		    g.addEdge(n2, n5);
 		    g.addEdge(n3, n6);
 		    g.addEdge(n4, n6);
 		    g.addEdge(n4, n7);
 		    g.addEdge(n5, n7);
 		    check(bipartite(g), "This graph is bipartite");
 		    check(bipartitePartitions(g, map), "This graph is bipartite");
 		    check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7],
 		          "Wrong bipartitePartitions()");
 		    check(map[n3] == map[n4] && map[n3] == map[n5],
 		          "Wrong bipartitePartitions()");
+		  }
 		  return 0;
+		}

lemon/connectivity.h

Show inline comments

@@ -33,55 +33,65 @@
 		#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>::
@@ -100,35 +110,44 @@
 		        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>::
@@ -222,33 +241,35 @@
 		      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;
@@ -261,55 +282,59 @@
 		    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;
@@ -346,41 +371,47 @@
 		        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;
@@ -415,72 +446,77 @@
 		        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 {
@@ -697,48 +733,53 @@
 		      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);
@@ -747,40 +788,44 @@
 		    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;
@@ -792,36 +837,43 @@
 		    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;
@@ -1022,48 +1074,55 @@
 		      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);
@@ -1072,40 +1131,45 @@
 		    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;
@@ -1116,37 +1180,43 @@
 		    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;
@@ -1180,77 +1250,120 @@
 		        _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;
@@ -1274,120 +1387,78 @@
 		           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;
+		  }
@@ -1442,33 +1513,32 @@
+		      }
 		    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> >
@@ -1479,109 +1549,117 @@
 		        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.
 		  template <typename Digraph>
 		  bool parallelFree(const Digraph& digraph) {
 		    typename Digraph::template NodeMap<bool> reached(digraph, false);
 		    for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
 		      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
 		        if (reached[digraph.target(a)]) return false;
 		        reached.set(digraph.target(a), true);
 		  /// \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;
+		      }
 		      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
 		        reached.set(digraph.target(a), false);
+		      }
+		      ++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.
 		  template <typename Digraph>
 		  bool simpleDigraph(const Digraph& digraph) {
 		    typename Digraph::template NodeMap<bool> reached(digraph, false);
 		    for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
 		      reached.set(n, true);
 		      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
 		        if (reached[digraph.target(a)]) return false;
 		        reached.set(digraph.target(a), true);
 		  /// \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;
+		      }
 		      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
 		        reached.set(digraph.target(a), false);
+		      }
 		      reached.set(n, false);
 		      ++cnt;
+		    }
 		    return true;
+		  }
 		} //namespace lemon
 		#endif //LEMON_CONNECTIVITY_H

lemon/euler.h

Show inline comments

@@ -235,28 +235,28 @@
 		    ///
 		    ///\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.
 		  ///

test/CMakeLists.txt

Show inline comments

 		INCLUDE_DIRECTORIES(
 		  ${PROJECT_SOURCE_DIR}
 		  ${PROJECT_BINARY_DIR}
+		)
 		LINK_DIRECTORIES(${PROJECT_BINARY_DIR}/lemon)
 		SET(TESTS
 		  adaptors_test
 		  bfs_test
 		  circulation_test
 		  connectivity_test
 		  counter_test
 		  dfs_test
 		  digraph_test
 		  dijkstra_test
 		  dim_test
 		  edge_set_test
 		  error_test
 		  euler_test
 		  gomory_hu_test
 		  graph_copy_test
 		  graph_test
 		  graph_utils_test

test/Makefile.am

Show inline comments

 		EXTRA_DIST += \
 			test/CMakeLists.txt
 		noinst_HEADERS += \
 			test/graph_test.h \
 			test/test_tools.h
 		check_PROGRAMS += \
 			test/adaptors_test \
 			test/bfs_test \
 			test/circulation_test \
 			test/connectivity_test \
 			test/counter_test \
 			test/dfs_test \
 			test/digraph_test \
 			test/dijkstra_test \
 			test/dim_test \
 			test/edge_set_test \
 			test/error_test \
 			test/euler_test \
 			test/gomory_hu_test \
 			test/graph_copy_test \
 			test/graph_test \
 			test/graph_utils_test \
@@ -45,24 +46,25 @@
 		endif HAVE_LP
 		if HAVE_MIP
 		check_PROGRAMS += test/mip_test
 		endif HAVE_MIP
 		TESTS += $(check_PROGRAMS)
 		XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
 		test_adaptors_test_SOURCES = test/adaptors_test.cc
 		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_connectivity_test_SOURCES = test/connectivity_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_edge_set_test_SOURCES = test/edge_set_test.cc
 		test_error_test_SOURCES = test/error_test.cc
 		test_euler_test_SOURCES = test/euler_test.cc
 		test_gomory_hu_test_SOURCES = test/gomory_hu_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

0 comments (0 inline)

RhodeCode

Login to your account