alpar@578: #include "test_tools.h"
alpar@568: #include <hugo/smart_graph.h>
alpar@568: #include <hugo/dijkstra.h>
alpar@793: #include<hugo/skeletons/graph.h>
alpar@793: #include<hugo/skeletons/maps.h>
alpar@568: using namespace hugo;
alpar@568: 
alpar@568: const int PET_SIZE =5;
alpar@568: 
alpar@570: 
alpar@793: void check_Dijkstra_BinHeap_Compile() 
alpar@570: {
alpar@570:   typedef int VType;
alpar@793:   typedef skeleton::StaticGraphSkeleton Graph;
alpar@570: 
alpar@570:   typedef Graph::Edge Edge;
alpar@570:   typedef Graph::Node Node;
alpar@570:   typedef Graph::EdgeIt EdgeIt;
alpar@570:   typedef Graph::NodeIt NodeIt;
alpar@793:   typedef skeleton::ReadMap<Edge,VType> LengthMap;
alpar@570:  
alpar@570:   typedef Dijkstra<Graph, LengthMap> DType;
alpar@570:   
alpar@570:   Graph G;
alpar@570:   Node n;
alpar@570:   Edge e;
alpar@570:   VType l;
alpar@570:   bool b;
alpar@570:   DType::DistMap d(G);
alpar@570:   DType::PredMap p(G);
alpar@570:   DType::PredNodeMap pn(G);
alpar@793:   LengthMap cap;
alpar@570: 
alpar@570:   DType dijkstra_test(G,cap);
alpar@570: 
alpar@570:   dijkstra_test.run(n);
alpar@570: 
alpar@570:   l  = dijkstra_test.dist(n);
alpar@570:   e  = dijkstra_test.pred(n);
alpar@570:   n  = dijkstra_test.predNode(n);
alpar@570:   d  = dijkstra_test.distMap();
alpar@570:   p  = dijkstra_test.predMap();
alpar@570:   pn = dijkstra_test.predNodeMap();
alpar@570:   b  = dijkstra_test.reached(n);
alpar@570: 
alpar@570: }
alpar@570: 
alpar@568: int main()
alpar@568: {
alpar@568:     
alpar@568:   typedef SmartGraph Graph;
alpar@568: 
alpar@568:   typedef Graph::Edge Edge;
alpar@568:   typedef Graph::Node Node;
alpar@568:   typedef Graph::EdgeIt EdgeIt;
alpar@568:   typedef Graph::NodeIt NodeIt;
alpar@568:   typedef Graph::EdgeMap<int> LengthMap;
alpar@568: 
alpar@568:   Graph G;
alpar@568:   Node s, t;
alpar@568:   LengthMap cap(G);
alpar@568:   PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
alpar@578:    
alpar@568:   for(int i=0;i<PET_SIZE;i++) {
alpar@568:     cap[ps.outcir[i]]=4;
alpar@568:     cap[ps.incir[i]]=1;
alpar@568:     cap[ps.chords[i]]=10;
alpar@568:   }
alpar@568:   s=ps.outer[0];
alpar@568:   t=ps.inner[1];
alpar@568:   
alpar@568:   Dijkstra<Graph, LengthMap> 
alpar@568: 	dijkstra_test(G, cap);
alpar@568:   dijkstra_test.run(s);
alpar@568:   
alpar@568:   check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
alpar@585: 
alpar@585: 
hegyi@776:   for(EdgeIt e(G); e!=INVALID; ++e) {
alpar@585:     Node u=G.tail(e);
alpar@585:     Node v=G.head(e);
alpar@585:     check( !dijkstra_test.reached(u) ||
alpar@585: 	   (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= cap[e]),
alpar@585: 	   "dist(head)-dist(tail)- edge_length= " 
alpar@585: 	   << dijkstra_test.dist(v) - dijkstra_test.dist(u) 
alpar@585: 	   - cap[e]);
alpar@585:   }
alpar@585: 
alpar@585:   ///\bug This works only for integer lengths
alpar@780:   for(NodeIt v(G); v!=INVALID; ++v){
alpar@780:     check(dijkstra_test.reached(v),"Each node should be reached.");
alpar@780:     if ( dijkstra_test.pred(v)!=INVALID ) {
alpar@585:       Edge e=dijkstra_test.pred(v);
alpar@585:       Node u=G.tail(e);
alpar@780:       check(u==dijkstra_test.predNode(v),"Wrong tree.");
alpar@585:       check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == cap[e],
alpar@780: 	    "Wrong distance! Difference: " 
alpar@585: 	    << std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u) 
alpar@585: 			    - cap[e]));
alpar@585:     }
alpar@780:   }
alpar@568: }
alpar@780: