1.1 --- a/lemon/connectivity.h	Wed Apr 29 19:22:14 2009 +0100
     1.2 +++ b/lemon/connectivity.h	Wed May 06 14:37:44 2009 +0200
     1.3 @@ -1370,6 +1370,7 @@
     1.4      typedef typename Graph::Node Node;
     1.5      typedef typename Graph::NodeIt NodeIt;
     1.6      typedef typename Graph::Arc Arc;
     1.7 +    if (NodeIt(graph) == INVALID) return true;
     1.8      Dfs<Graph> dfs(graph);
     1.9      dfs.init();
    1.10      dfs.addSource(NodeIt(graph));
    1.11 @@ -1545,17 +1546,16 @@
    1.12    /// \brief Returns true when there are not parallel edges in the graph.
    1.13    ///
    1.14    /// Returns true when there are not parallel edges in the graph.
    1.15 -  template <typename Digraph>
    1.16 -  bool parallelFree(const Digraph& digraph) {
    1.17 -    typename Digraph::template NodeMap<bool> reached(digraph, false);
    1.18 -    for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
    1.19 -      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
    1.20 -        if (reached[digraph.target(a)]) return false;
    1.21 -        reached.set(digraph.target(a), true);
    1.22 +  template <typename Graph>
    1.23 +  bool parallelFree(const Graph& graph) {
    1.24 +    typename Graph::template NodeMap<int> reached(graph, 0);
    1.25 +    int cnt = 1;
    1.26 +    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
    1.27 +      for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
    1.28 +        if (reached[graph.target(a)] == cnt) return false;
    1.29 +        reached[graph.target(a)] = cnt;
    1.30        }
    1.31 -      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
    1.32 -        reached.set(digraph.target(a), false);
    1.33 -      }
    1.34 +      ++cnt;
    1.35      }
    1.36      return true;
    1.37    }
    1.38 @@ -1565,19 +1565,17 @@
    1.39    ///
    1.40    /// Returns true when there are not loop edges and parallel edges in
    1.41    /// the graph.
    1.42 -  template <typename Digraph>
    1.43 -  bool simpleDigraph(const Digraph& digraph) {
    1.44 -    typename Digraph::template NodeMap<bool> reached(digraph, false);
    1.45 -    for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
    1.46 -      reached.set(n, true);
    1.47 -      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
    1.48 -        if (reached[digraph.target(a)]) return false;
    1.49 -        reached.set(digraph.target(a), true);
    1.50 +  template <typename Graph>
    1.51 +  bool simpleGraph(const Graph& graph) {
    1.52 +    typename Graph::template NodeMap<int> reached(graph, 0);
    1.53 +    int cnt = 1;
    1.54 +    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
    1.55 +      reached[n] = cnt;
    1.56 +      for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
    1.57 +        if (reached[graph.target(a)] == cnt) return false;
    1.58 +        reached[graph.target(a)] = cnt;
    1.59        }
    1.60 -      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
    1.61 -        reached.set(digraph.target(a), false);
    1.62 -      }
    1.63 -      reached.set(n, false);
    1.64 +      ++cnt;
    1.65      }
    1.66      return true;
    1.67    }