alpar@774: #include "test_tools.h"
alpar@774: #include <hugo/smart_graph.h>
alpar@774: #include <hugo/bfs.h>
alpar@774: 
alpar@774: using namespace hugo;
alpar@774: 
alpar@774: const int PET_SIZE =5;
alpar@774: 
alpar@774: 
alpar@774: void check_Bfs_SmartGraph_Compile() 
alpar@774: {
alpar@774:   typedef int VType;
alpar@774:   typedef SmartGraph Graph;
alpar@774: 
alpar@774:   typedef Graph::Edge Edge;
alpar@774:   typedef Graph::Node Node;
alpar@774:   typedef Graph::EdgeIt EdgeIt;
alpar@774:   typedef Graph::NodeIt NodeIt;
alpar@774:   typedef Graph::EdgeMap<VType> LengthMap;
alpar@774:  
alpar@774:   typedef Bfs<Graph> BType;
alpar@774:   
alpar@774:   Graph G;
alpar@774:   Node n;
alpar@774:   Edge e;
alpar@774:   VType l;
alpar@774:   bool b;
alpar@774:   BType::DistMap d(G);
alpar@774:   BType::PredMap p(G);
alpar@774:   BType::PredNodeMap pn(G);
alpar@774:   LengthMap cap(G);
alpar@774:   
alpar@774:   BType bfs_test(G);
alpar@774:   
alpar@774:   bfs_test.run(n);
alpar@774:   
alpar@774:   l  = bfs_test.dist(n);
alpar@774:   e  = bfs_test.pred(n);
alpar@774:   n  = bfs_test.predNode(n);
alpar@774:   d  = bfs_test.distMap();
alpar@774:   p  = bfs_test.predMap();
alpar@774:   pn = bfs_test.predNodeMap();
alpar@774:   b  = bfs_test.reached(n);
alpar@774: 
alpar@774: }
alpar@774: 
alpar@774: int main()
alpar@774: {
alpar@774:     
alpar@774:   typedef SmartGraph Graph;
alpar@774: 
alpar@774:   typedef Graph::Edge Edge;
alpar@774:   typedef Graph::Node Node;
alpar@774:   typedef Graph::EdgeIt EdgeIt;
alpar@774:   typedef Graph::NodeIt NodeIt;
alpar@774:   typedef Graph::EdgeMap<int> LengthMap;
alpar@774: 
alpar@774:   Graph G;
alpar@774:   Node s, t;
alpar@774:   PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
alpar@774:    
alpar@774:   s=ps.outer[2];
alpar@774:   t=ps.inner[0];
alpar@774:   
alpar@774:   Bfs<Graph> bfs_test(G);
alpar@774:   bfs_test.run(s);
alpar@774:   
alpar@774:   check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
alpar@774: 
alpar@774: 
alpar@774:   for(EdgeIt e(G); e==INVALID; ++e) {
alpar@774:     Node u=G.tail(e);
alpar@774:     Node v=G.head(e);
alpar@774:     check( !bfs_test.reached(u) ||
alpar@774: 	   (bfs_test.dist(v) > bfs_test.dist(u)+1),
alpar@774: 	   "Wrong output.");
alpar@774:   }
alpar@774: 
alpar@774:   ///\bug This works only for integer lengths
alpar@774:   for(NodeIt v(G); v==INVALID; ++v)
alpar@774:     if ( bfs_test.reached(v) ) {
alpar@774:       Edge e=bfs_test.pred(v);
alpar@774:       Node u=G.tail(e);
alpar@774:       check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
alpar@774: 	    "Bad shortest path tree edge! Difference: " 
alpar@774: 	    << std::abs(bfs_test.dist(v) - bfs_test.dist(u) 
alpar@774: 			- 1));
alpar@774:     }
alpar@774: }