Bug fix in Dfs::start(s,t) (#392)
authorAlpar Juttner <alpar@cs.elte.hu>
Wed, 22 Sep 2010 08:53:09 +0200
changeset 737e24922c56bc2
parent 731 bb871cb8ac06
child 738 c85f53572941
child 756 54464584b157
Bug fix in Dfs::start(s,t) (#392)
lemon/dfs.h
test/dfs_test.cc
     1.1 --- a/lemon/dfs.h	Tue Jun 22 15:39:26 2010 +0200
     1.2 +++ b/lemon/dfs.h	Wed Sep 22 08:53:09 2010 +0200
     1.3 @@ -558,7 +558,7 @@
     1.4      ///added with addSource() before using this function.
     1.5      void start(Node t)
     1.6      {
     1.7 -      while ( !emptyQueue() && G->target(_stack[_stack_head])!=t )
     1.8 +      while ( !emptyQueue() && !(*_reached)[t] )
     1.9          processNextArc();
    1.10      }
    1.11  
    1.12 @@ -1511,7 +1511,7 @@
    1.13      /// \pre init() must be called and a root node should be added
    1.14      /// with addSource() before using this function.
    1.15      void start(Node t) {
    1.16 -      while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t )
    1.17 +      while ( !emptyQueue() && !(*_reached)[t] )
    1.18          processNextArc();
    1.19      }
    1.20  
     2.1 --- a/test/dfs_test.cc	Tue Jun 22 15:39:26 2010 +0200
     2.2 +++ b/test/dfs_test.cc	Wed Sep 22 08:53:09 2010 +0200
     2.3 @@ -50,7 +50,10 @@
     2.4    "6 3  7\n"
     2.5    "@attributes\n"
     2.6    "source 0\n"
     2.7 -  "target 5\n";
     2.8 +  "target 5\n"
     2.9 +  "source1 6\n"
    2.10 +  "target1 3\n";
    2.11 +
    2.12  
    2.13  void checkDfsCompile()
    2.14  {
    2.15 @@ -144,11 +147,14 @@
    2.16  
    2.17    Digraph G;
    2.18    Node s, t;
    2.19 +  Node s1, t1;
    2.20  
    2.21    std::istringstream input(test_lgf);
    2.22    digraphReader(G, input).
    2.23      node("source", s).
    2.24      node("target", t).
    2.25 +    node("source1", s1).
    2.26 +    node("target1", t1).
    2.27      run();
    2.28  
    2.29    Dfs<Digraph> dfs_test(G);
    2.30 @@ -175,6 +181,11 @@
    2.31    }
    2.32  
    2.33    {
    2.34 +  Dfs<Digraph> dfs(G);
    2.35 +  check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6.");
    2.36 +  }
    2.37 +  
    2.38 +  {
    2.39      NullMap<Node,Arc> myPredMap;
    2.40      dfs(G).predMap(myPredMap).run(s);
    2.41    }