COIN-OR::LEMON - Graph Library

Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • test/bfs_test.cc

    r209 r228  
    2020#include <lemon/smart_graph.h>
    2121#include <lemon/list_graph.h>
     22#include <lemon/lgf_reader.h>
    2223#include <lemon/bfs.h>
    2324#include <lemon/path.h>
     
    2728
    2829using namespace lemon;
     30
     31char test_lgf[] =
     32  "@nodes\n"
     33  "label\n"
     34  "0\n"
     35  "1\n"
     36  "2\n"
     37  "3\n"
     38  "4\n"
     39  "5\n"
     40  "@arcs\n"
     41  "     label\n"
     42  "0 1  0\n"
     43  "1 2  1\n"
     44  "2 3  2\n"
     45  "3 4  3\n"
     46  "0 3  4\n"
     47  "0 3  5\n"
     48  "5 2  6\n"
     49  "@attributes\n"
     50  "source 0\n"
     51  "target 4\n";
    2952
    3053void checkBfsCompile()
     
    5073  n  = bfs_test.predNode(n);
    5174  d  = bfs_test.distMap();
     75
    5276  p  = bfs_test.predMap();
    5377  //  pn = bfs_test.predNodeMap();
     
    81105  Digraph G;
    82106  Node s, t;
    83   PetStruct<Digraph> ps = addPetersen(G, 5);
    84107
    85   s=ps.outer[2];
    86   t=ps.inner[0];
     108  std::istringstream input(test_lgf);
     109  digraphReader(input, G).
     110    node("source", s).
     111    node("target", t).
     112    run();
    87113
    88114  Bfs<Digraph> bfs_test(G);
    89115  bfs_test.run(s);
    90116
    91   check(bfs_test.dist(t)==3,"Bfs found a wrong path." << bfs_test.dist(t));
     117  check(bfs_test.dist(t)==2,"Bfs found a wrong path." << bfs_test.dist(t));
    92118
    93119  Path<Digraph> p = bfs_test.path(t);
    94   check(p.length()==3,"path() found a wrong path.");
     120  check(p.length()==2,"path() found a wrong path.");
    95121  check(checkPath(G, p),"path() found a wrong path.");
    96122  check(pathSource(G, p) == s,"path() found a wrong path.");
     
    98124
    99125
    100   for(ArcIt e(G); e==INVALID; ++e) {
    101     Node u=G.source(e);
    102     Node v=G.target(e);
     126  for(ArcIt a(G); a!=INVALID; ++a) {
     127    Node u=G.source(a);
     128    Node v=G.target(a);
    103129    check( !bfs_test.reached(u) ||
    104            (bfs_test.dist(v) > bfs_test.dist(u)+1),
    105            "Wrong output.");
     130           (bfs_test.dist(v) <= bfs_test.dist(u)+1),
     131           "Wrong output." << G.id(v) << ' ' << G.id(u));
    106132  }
    107133
    108   for(NodeIt v(G); v==INVALID; ++v) {
    109     check(bfs_test.reached(v),"Each node should be reached.");
    110     if ( bfs_test.predArc(v)!=INVALID ) {
    111       Arc e=bfs_test.predArc(v);
    112       Node u=G.source(e);
    113       check(u==bfs_test.predNode(v),"Wrong tree.");
    114       check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
    115             "Wrong distance. Difference: "
    116             << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
    117                         - 1));
     134  for(NodeIt v(G); v!=INVALID; ++v) {
     135    if (bfs_test.reached(v)) {
     136      check(v==s || bfs_test.predArc(v)!=INVALID, "Wrong tree.");
     137      if (bfs_test.predArc(v)!=INVALID ) {
     138        Arc a=bfs_test.predArc(v);
     139        Node u=G.source(a);
     140        check(u==bfs_test.predNode(v),"Wrong tree.");
     141        check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
     142              "Wrong distance. Difference: "
     143              << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
     144                          - 1));
     145      }
    118146    }
    119147  }
Note: See TracChangeset for help on using the changeset viewer.