COIN-OR::LEMON - Graph Library

Changeset 780:e06d0d16595f in lemon-0.x


Ignore:
Timestamp:
09/01/04 17:08:41 (20 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1073
Message:
  • DFS class (bfs.h and bfs_test.cc) added
  • Bugfixes in Dijkstra and Bfs
Location:
src
Files:
2 added
5 edited

Legend:

Unmodified
Added
Removed
  • src/hugo/bfs.h

    r774 r780  
    281281    ///\pre \ref run() must be called before using this function.
    282282    ///
    283     bool reached(Node v) { return v==source || (*predecessor)[v]==INVALID; }
     283    bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
    284284   
    285285  };
  • src/hugo/dijkstra.h

    r776 r780  
    280280    ///\ref predNode(Node v).  \pre \ref run() must be called before using
    281281    ///this function.
     282    ///\todo predEdge could be a better name.
    282283    Edge pred(Node v) const { return (*predecessor)[v]; }
    283284
     
    318319    ///\pre \ref run() must be called before using this function.
    319320    ///
    320     bool reached(Node v) { return v==source || (*predecessor)[v]==INVALID; }
     321    bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
    321322   
    322323  };
  • src/test/Makefile.am

    r774 r780  
    33noinst_HEADERS = test_tools.h
    44
    5 check_PROGRAMS = graph_test dijkstra_test bfs_test time_measure_test \
     5check_PROGRAMS = graph_test dijkstra_test bfs_test dfs_test time_measure_test \
    66        error_test xy_test \
    77        unionfind_test test_tools_pass test_tools_fail
     
    1313dijkstra_test_SOURCES = dijkstra_test.cc
    1414bfs_test_SOURCES = bfs_test.cc
     15dfs_test_SOURCES = dfs_test.cc
    1516unionfind_test_SOURCES = unionfind_test.cc
    1617time_measure_test_SOURCES = time_measure_test.cc
  • src/test/bfs_test.cc

    r774 r780  
    7777  }
    7878
    79   ///\bug This works only for integer lengths
    80   for(NodeIt v(G); v==INVALID; ++v)
    81     if ( bfs_test.reached(v) ) {
     79  for(NodeIt v(G); v==INVALID; ++v) {
     80    check(bfs_test.reached(v),"Each node should be reached.");
     81    if ( bfs_test.pred(v)!=INVALID ) {
    8282      Edge e=bfs_test.pred(v);
    8383      Node u=G.tail(e);
     84      check(u==bfs_test.predNode(v),"Wrong tree.");
    8485      check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
    85             "Bad shortest path tree edge! Difference: "
     86            "Wrong distance. Difference: "
    8687            << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
    8788                        - 1));
    8889    }
     90  }
    8991}
     92
  • src/test/dijkstra_test.cc

    r776 r780  
    8787
    8888  ///\bug This works only for integer lengths
    89   for(NodeIt v(G); v!=INVALID; ++v)
    90     if ( dijkstra_test.reached(v) ) {
     89  for(NodeIt v(G); v!=INVALID; ++v){
     90    check(dijkstra_test.reached(v),"Each node should be reached.");
     91    if ( dijkstra_test.pred(v)!=INVALID ) {
    9192      Edge e=dijkstra_test.pred(v);
    9293      Node u=G.tail(e);
     94      check(u==dijkstra_test.predNode(v),"Wrong tree.");
    9395      check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == cap[e],
    94             "Bad shortest path tree edge! Difference: "
     96            "Wrong distance! Difference: "
    9597            << std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u)
    9698                            - cap[e]));
    9799    }
     100  }
    98101}
     102
Note: See TracChangeset for help on using the changeset viewer.