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