1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/test/bfs_test.cc	Mon Aug 30 12:01:47 2004 +0000
     1.3 @@ -0,0 +1,89 @@
     1.4 +#include "test_tools.h"
     1.5 +#include <hugo/smart_graph.h>
     1.6 +#include <hugo/bfs.h>
     1.7 +
     1.8 +using namespace hugo;
     1.9 +
    1.10 +const int PET_SIZE =5;
    1.11 +
    1.12 +
    1.13 +void check_Bfs_SmartGraph_Compile() 
    1.14 +{
    1.15 +  typedef int VType;
    1.16 +  typedef SmartGraph Graph;
    1.17 +
    1.18 +  typedef Graph::Edge Edge;
    1.19 +  typedef Graph::Node Node;
    1.20 +  typedef Graph::EdgeIt EdgeIt;
    1.21 +  typedef Graph::NodeIt NodeIt;
    1.22 +  typedef Graph::EdgeMap<VType> LengthMap;
    1.23 + 
    1.24 +  typedef Bfs<Graph> BType;
    1.25 +  
    1.26 +  Graph G;
    1.27 +  Node n;
    1.28 +  Edge e;
    1.29 +  VType l;
    1.30 +  bool b;
    1.31 +  BType::DistMap d(G);
    1.32 +  BType::PredMap p(G);
    1.33 +  BType::PredNodeMap pn(G);
    1.34 +  LengthMap cap(G);
    1.35 +  
    1.36 +  BType bfs_test(G);
    1.37 +  
    1.38 +  bfs_test.run(n);
    1.39 +  
    1.40 +  l  = bfs_test.dist(n);
    1.41 +  e  = bfs_test.pred(n);
    1.42 +  n  = bfs_test.predNode(n);
    1.43 +  d  = bfs_test.distMap();
    1.44 +  p  = bfs_test.predMap();
    1.45 +  pn = bfs_test.predNodeMap();
    1.46 +  b  = bfs_test.reached(n);
    1.47 +
    1.48 +}
    1.49 +
    1.50 +int main()
    1.51 +{
    1.52 +    
    1.53 +  typedef SmartGraph Graph;
    1.54 +
    1.55 +  typedef Graph::Edge Edge;
    1.56 +  typedef Graph::Node Node;
    1.57 +  typedef Graph::EdgeIt EdgeIt;
    1.58 +  typedef Graph::NodeIt NodeIt;
    1.59 +  typedef Graph::EdgeMap<int> LengthMap;
    1.60 +
    1.61 +  Graph G;
    1.62 +  Node s, t;
    1.63 +  PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
    1.64 +   
    1.65 +  s=ps.outer[2];
    1.66 +  t=ps.inner[0];
    1.67 +  
    1.68 +  Bfs<Graph> bfs_test(G);
    1.69 +  bfs_test.run(s);
    1.70 +  
    1.71 +  check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
    1.72 +
    1.73 +
    1.74 +  for(EdgeIt e(G); e==INVALID; ++e) {
    1.75 +    Node u=G.tail(e);
    1.76 +    Node v=G.head(e);
    1.77 +    check( !bfs_test.reached(u) ||
    1.78 +	   (bfs_test.dist(v) > bfs_test.dist(u)+1),
    1.79 +	   "Wrong output.");
    1.80 +  }
    1.81 +
    1.82 +  ///\bug This works only for integer lengths
    1.83 +  for(NodeIt v(G); v==INVALID; ++v)
    1.84 +    if ( bfs_test.reached(v) ) {
    1.85 +      Edge e=bfs_test.pred(v);
    1.86 +      Node u=G.tail(e);
    1.87 +      check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
    1.88 +	    "Bad shortest path tree edge! Difference: " 
    1.89 +	    << std::abs(bfs_test.dist(v) - bfs_test.dist(u) 
    1.90 +			- 1));
    1.91 +    }
    1.92 +}