|
alpar@578
|
1 |
#include "test_tools.h"
|
|
alpar@568
|
2 |
#include <hugo/smart_graph.h>
|
|
alpar@568
|
3 |
#include <hugo/dijkstra.h>
|
|
alpar@793
|
4 |
#include<hugo/skeletons/graph.h>
|
|
alpar@793
|
5 |
#include<hugo/skeletons/maps.h>
|
|
alpar@568
|
6 |
using namespace hugo;
|
|
alpar@568
|
7 |
|
|
alpar@568
|
8 |
const int PET_SIZE =5;
|
|
alpar@568
|
9 |
|
|
alpar@570
|
10 |
|
|
alpar@793
|
11 |
void check_Dijkstra_BinHeap_Compile()
|
|
alpar@570
|
12 |
{
|
|
alpar@570
|
13 |
typedef int VType;
|
|
alpar@793
|
14 |
typedef skeleton::StaticGraphSkeleton Graph;
|
|
alpar@570
|
15 |
|
|
alpar@570
|
16 |
typedef Graph::Edge Edge;
|
|
alpar@570
|
17 |
typedef Graph::Node Node;
|
|
alpar@570
|
18 |
typedef Graph::EdgeIt EdgeIt;
|
|
alpar@570
|
19 |
typedef Graph::NodeIt NodeIt;
|
|
alpar@793
|
20 |
typedef skeleton::ReadMap<Edge,VType> LengthMap;
|
|
alpar@570
|
21 |
|
|
alpar@570
|
22 |
typedef Dijkstra<Graph, LengthMap> DType;
|
|
alpar@570
|
23 |
|
|
alpar@570
|
24 |
Graph G;
|
|
alpar@570
|
25 |
Node n;
|
|
alpar@570
|
26 |
Edge e;
|
|
alpar@570
|
27 |
VType l;
|
|
alpar@570
|
28 |
bool b;
|
|
alpar@570
|
29 |
DType::DistMap d(G);
|
|
alpar@570
|
30 |
DType::PredMap p(G);
|
|
alpar@570
|
31 |
DType::PredNodeMap pn(G);
|
|
alpar@793
|
32 |
LengthMap cap;
|
|
alpar@570
|
33 |
|
|
alpar@570
|
34 |
DType dijkstra_test(G,cap);
|
|
alpar@570
|
35 |
|
|
alpar@570
|
36 |
dijkstra_test.run(n);
|
|
alpar@570
|
37 |
|
|
alpar@570
|
38 |
l = dijkstra_test.dist(n);
|
|
alpar@570
|
39 |
e = dijkstra_test.pred(n);
|
|
alpar@570
|
40 |
n = dijkstra_test.predNode(n);
|
|
alpar@570
|
41 |
d = dijkstra_test.distMap();
|
|
alpar@570
|
42 |
p = dijkstra_test.predMap();
|
|
alpar@570
|
43 |
pn = dijkstra_test.predNodeMap();
|
|
alpar@570
|
44 |
b = dijkstra_test.reached(n);
|
|
alpar@570
|
45 |
|
|
alpar@570
|
46 |
}
|
|
alpar@570
|
47 |
|
|
alpar@568
|
48 |
int main()
|
|
alpar@568
|
49 |
{
|
|
alpar@568
|
50 |
|
|
alpar@568
|
51 |
typedef SmartGraph Graph;
|
|
alpar@568
|
52 |
|
|
alpar@568
|
53 |
typedef Graph::Edge Edge;
|
|
alpar@568
|
54 |
typedef Graph::Node Node;
|
|
alpar@568
|
55 |
typedef Graph::EdgeIt EdgeIt;
|
|
alpar@568
|
56 |
typedef Graph::NodeIt NodeIt;
|
|
alpar@568
|
57 |
typedef Graph::EdgeMap<int> LengthMap;
|
|
alpar@568
|
58 |
|
|
alpar@568
|
59 |
Graph G;
|
|
alpar@568
|
60 |
Node s, t;
|
|
alpar@568
|
61 |
LengthMap cap(G);
|
|
alpar@568
|
62 |
PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
|
|
alpar@578
|
63 |
|
|
alpar@568
|
64 |
for(int i=0;i<PET_SIZE;i++) {
|
|
alpar@568
|
65 |
cap[ps.outcir[i]]=4;
|
|
alpar@568
|
66 |
cap[ps.incir[i]]=1;
|
|
alpar@568
|
67 |
cap[ps.chords[i]]=10;
|
|
alpar@568
|
68 |
}
|
|
alpar@568
|
69 |
s=ps.outer[0];
|
|
alpar@568
|
70 |
t=ps.inner[1];
|
|
alpar@568
|
71 |
|
|
alpar@568
|
72 |
Dijkstra<Graph, LengthMap>
|
|
alpar@568
|
73 |
dijkstra_test(G, cap);
|
|
alpar@568
|
74 |
dijkstra_test.run(s);
|
|
alpar@568
|
75 |
|
|
alpar@568
|
76 |
check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
|
|
alpar@585
|
77 |
|
|
alpar@585
|
78 |
|
|
hegyi@776
|
79 |
for(EdgeIt e(G); e!=INVALID; ++e) {
|
|
alpar@585
|
80 |
Node u=G.tail(e);
|
|
alpar@585
|
81 |
Node v=G.head(e);
|
|
alpar@585
|
82 |
check( !dijkstra_test.reached(u) ||
|
|
alpar@585
|
83 |
(dijkstra_test.dist(v) - dijkstra_test.dist(u) <= cap[e]),
|
|
alpar@585
|
84 |
"dist(head)-dist(tail)- edge_length= "
|
|
alpar@585
|
85 |
<< dijkstra_test.dist(v) - dijkstra_test.dist(u)
|
|
alpar@585
|
86 |
- cap[e]);
|
|
alpar@585
|
87 |
}
|
|
alpar@585
|
88 |
|
|
alpar@585
|
89 |
///\bug This works only for integer lengths
|
|
alpar@780
|
90 |
for(NodeIt v(G); v!=INVALID; ++v){
|
|
alpar@780
|
91 |
check(dijkstra_test.reached(v),"Each node should be reached.");
|
|
alpar@780
|
92 |
if ( dijkstra_test.pred(v)!=INVALID ) {
|
|
alpar@585
|
93 |
Edge e=dijkstra_test.pred(v);
|
|
alpar@585
|
94 |
Node u=G.tail(e);
|
|
alpar@780
|
95 |
check(u==dijkstra_test.predNode(v),"Wrong tree.");
|
|
alpar@585
|
96 |
check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == cap[e],
|
|
alpar@780
|
97 |
"Wrong distance! Difference: "
|
|
alpar@585
|
98 |
<< std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u)
|
|
alpar@585
|
99 |
- cap[e]));
|
|
alpar@585
|
100 |
}
|
|
alpar@780
|
101 |
}
|
|
alpar@568
|
102 |
}
|
|
alpar@780
|
103 |
|