1.1 --- a/test/bfs_test.cc	Fri Jul 18 17:26:12 2008 +0100
     1.2 +++ b/test/bfs_test.cc	Mon Jul 21 16:30:28 2008 +0200
     1.3 @@ -19,6 +19,7 @@
     1.4  #include <lemon/concepts/digraph.h>
     1.5  #include <lemon/smart_graph.h>
     1.6  #include <lemon/list_graph.h>
     1.7 +#include <lemon/lgf_reader.h>
     1.8  #include <lemon/bfs.h>
     1.9  #include <lemon/path.h>
    1.10  
    1.11 @@ -27,6 +28,28 @@
    1.12  
    1.13  using namespace lemon;
    1.14  
    1.15 +char test_lgf[] =
    1.16 +  "@nodes\n"
    1.17 +  "label\n"
    1.18 +  "0\n"
    1.19 +  "1\n"
    1.20 +  "2\n"
    1.21 +  "3\n"
    1.22 +  "4\n"
    1.23 +  "5\n"
    1.24 +  "@arcs\n"
    1.25 +  "     label\n"
    1.26 +  "0 1  0\n"
    1.27 +  "1 2  1\n"
    1.28 +  "2 3  2\n"
    1.29 +  "3 4  3\n"
    1.30 +  "0 3  4\n"
    1.31 +  "0 3  5\n"
    1.32 +  "5 2  6\n"
    1.33 +  "@attributes\n"
    1.34 +  "source 0\n"
    1.35 +  "target 4\n";
    1.36 +
    1.37  void checkBfsCompile()
    1.38  {
    1.39    typedef concepts::Digraph Digraph;
    1.40 @@ -49,6 +72,7 @@
    1.41    e  = bfs_test.predArc(n);
    1.42    n  = bfs_test.predNode(n);
    1.43    d  = bfs_test.distMap();
    1.44 +
    1.45    p  = bfs_test.predMap();
    1.46    //  pn = bfs_test.predNodeMap();
    1.47    b  = bfs_test.reached(n);
    1.48 @@ -80,41 +104,45 @@
    1.49  
    1.50    Digraph G;
    1.51    Node s, t;
    1.52 -  PetStruct<Digraph> ps = addPetersen(G, 5);
    1.53  
    1.54 -  s=ps.outer[2];
    1.55 -  t=ps.inner[0];
    1.56 +  std::istringstream input(test_lgf);
    1.57 +  digraphReader(input, G).
    1.58 +    node("source", s).
    1.59 +    node("target", t).
    1.60 +    run();
    1.61  
    1.62    Bfs<Digraph> bfs_test(G);
    1.63    bfs_test.run(s);
    1.64  
    1.65 -  check(bfs_test.dist(t)==3,"Bfs found a wrong path." << bfs_test.dist(t));
    1.66 +  check(bfs_test.dist(t)==2,"Bfs found a wrong path." << bfs_test.dist(t));
    1.67  
    1.68    Path<Digraph> p = bfs_test.path(t);
    1.69 -  check(p.length()==3,"path() found a wrong path.");
    1.70 +  check(p.length()==2,"path() found a wrong path.");
    1.71    check(checkPath(G, p),"path() found a wrong path.");
    1.72    check(pathSource(G, p) == s,"path() found a wrong path.");
    1.73    check(pathTarget(G, p) == t,"path() found a wrong path.");
    1.74  
    1.75  
    1.76 -  for(ArcIt e(G); e!=INVALID; ++e) {
    1.77 -    Node u=G.source(e);
    1.78 -    Node v=G.target(e);
    1.79 +  for(ArcIt a(G); a!=INVALID; ++a) {
    1.80 +    Node u=G.source(a);
    1.81 +    Node v=G.target(a);
    1.82      check( !bfs_test.reached(u) ||
    1.83             (bfs_test.dist(v) <= bfs_test.dist(u)+1),
    1.84 -           "Wrong output.");
    1.85 +           "Wrong output." << G.id(v) << ' ' << G.id(u));
    1.86    }
    1.87  
    1.88    for(NodeIt v(G); v!=INVALID; ++v) {
    1.89 -    check(bfs_test.reached(v),"Each node should be reached.");
    1.90 -    if ( bfs_test.predArc(v)!=INVALID ) {
    1.91 -      Arc e=bfs_test.predArc(v);
    1.92 -      Node u=G.source(e);
    1.93 -      check(u==bfs_test.predNode(v),"Wrong tree.");
    1.94 -      check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
    1.95 -            "Wrong distance. Difference: "
    1.96 -            << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
    1.97 -                        - 1));
    1.98 +    if (bfs_test.reached(v)) {
    1.99 +      check(v==s || bfs_test.predArc(v)!=INVALID, "Wrong tree.");
   1.100 +      if (bfs_test.predArc(v)!=INVALID ) {
   1.101 +        Arc a=bfs_test.predArc(v);
   1.102 +        Node u=G.source(a);
   1.103 +        check(u==bfs_test.predNode(v),"Wrong tree.");
   1.104 +        check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
   1.105 +              "Wrong distance. Difference: "
   1.106 +              << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
   1.107 +                          - 1));
   1.108 +      }
   1.109      }
   1.110    }
   1.111  }