.
1 #include "test_tools.h"
2 #include <hugo/smart_graph.h>
3 #include <hugo/dijkstra.h>
10 void check_Dijkstra_SmartGraph_BinHeap_Compile()
13 typedef SmartGraph Graph;
15 typedef Graph::Edge Edge;
16 typedef Graph::Node Node;
17 typedef Graph::EdgeIt EdgeIt;
18 typedef Graph::NodeIt NodeIt;
19 typedef Graph::EdgeMap<VType> LengthMap;
21 typedef Dijkstra<Graph, LengthMap> DType;
30 DType::PredNodeMap pn(G);
33 DType dijkstra_test(G,cap);
37 l = dijkstra_test.dist(n);
38 e = dijkstra_test.pred(n);
39 n = dijkstra_test.predNode(n);
40 d = dijkstra_test.distMap();
41 p = dijkstra_test.predMap();
42 pn = dijkstra_test.predNodeMap();
43 b = dijkstra_test.reached(n);
50 typedef SmartGraph Graph;
52 typedef Graph::Edge Edge;
53 typedef Graph::Node Node;
54 typedef Graph::EdgeIt EdgeIt;
55 typedef Graph::NodeIt NodeIt;
56 typedef Graph::EdgeMap<int> LengthMap;
61 PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
63 for(int i=0;i<PET_SIZE;i++) {
71 Dijkstra<Graph, LengthMap>
72 dijkstra_test(G, cap);
75 check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
78 for(EdgeIt e(G); e!=INVALID; ++e) {
81 check( !dijkstra_test.reached(u) ||
82 (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= cap[e]),
83 "dist(head)-dist(tail)- edge_length= "
84 << dijkstra_test.dist(v) - dijkstra_test.dist(u)
88 ///\bug This works only for integer lengths
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 ) {
92 Edge e=dijkstra_test.pred(v);
94 check(u==dijkstra_test.predNode(v),"Wrong tree.");
95 check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == cap[e],
96 "Wrong distance! Difference: "
97 << std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u)