# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 1241613464 -7200
# Node ID dcba640438c7a47d35ef78b8b1d77f8f566b6578
# Parent  e01957e96c6796a11d9f3bbf751eea8ae274221c
Bug fixes in connectivity.h (#285)

 - Bug fix in tree().
 - Rename simpleDigraph() to simpleGraph() (it works for both
   directed and undirected graphs).
 - Possibly faster implementation for parallelFree() and
   simpleGraph().

diff -r e01957e96c67 -r dcba640438c7 lemon/connectivity.h
--- a/lemon/connectivity.h	Wed Apr 29 19:22:14 2009 +0100
+++ b/lemon/connectivity.h	Wed May 06 14:37:44 2009 +0200
@@ -1370,6 +1370,7 @@
     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));
@@ -1545,17 +1546,16 @@
   /// \brief Returns true when there are not parallel edges in the graph.
   ///
   /// Returns true when there are not parallel edges in the graph.
-  template <typename Digraph>
-  bool parallelFree(const Digraph& 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);
+  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;
   }
@@ -1565,19 +1565,17 @@
   ///
   /// 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);
+  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;
   }