Correction in doc: skeleton/path.h has been moved to the 'skeletons' module.
1 #include "test_tools.h"
2 #include <hugo/smart_graph.h>
3 #include <hugo/dijkstra.h>
4 #include<hugo/skeletons/graph.h>
5 #include<hugo/skeletons/maps.h>
11 void check_Dijkstra_BinHeap_Compile()
14 typedef skeleton::StaticGraphSkeleton Graph;
16 typedef Graph::Edge Edge;
17 typedef Graph::Node Node;
18 typedef Graph::EdgeIt EdgeIt;
19 typedef Graph::NodeIt NodeIt;
20 typedef skeleton::ReadMap<Edge,VType> LengthMap;
22 typedef Dijkstra<Graph, LengthMap> DType;
31 DType::PredNodeMap pn(G);
34 DType dijkstra_test(G,cap);
38 l = dijkstra_test.dist(n);
39 e = dijkstra_test.pred(n);
40 n = dijkstra_test.predNode(n);
41 d = dijkstra_test.distMap();
42 p = dijkstra_test.predMap();
43 pn = dijkstra_test.predNodeMap();
44 b = dijkstra_test.reached(n);
51 typedef SmartGraph Graph;
53 typedef Graph::Edge Edge;
54 typedef Graph::Node Node;
55 typedef Graph::EdgeIt EdgeIt;
56 typedef Graph::NodeIt NodeIt;
57 typedef Graph::EdgeMap<int> LengthMap;
62 PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
64 for(int i=0;i<PET_SIZE;i++) {
72 Dijkstra<Graph, LengthMap>
73 dijkstra_test(G, cap);
76 check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
79 for(EdgeIt e(G); e!=INVALID; ++e) {
82 check( !dijkstra_test.reached(u) ||
83 (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= cap[e]),
84 "dist(head)-dist(tail)- edge_length= "
85 << dijkstra_test.dist(v) - dijkstra_test.dist(u)
89 ///\bug This works only for integer lengths
90 for(NodeIt v(G); v!=INVALID; ++v){
91 check(dijkstra_test.reached(v),"Each node should be reached.");
92 if ( dijkstra_test.pred(v)!=INVALID ) {
93 Edge e=dijkstra_test.pred(v);
95 check(u==dijkstra_test.predNode(v),"Wrong tree.");
96 check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == cap[e],
97 "Wrong distance! Difference: "
98 << std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u)