author | alpar |
Mon, 06 Sep 2004 08:59:25 +0000 | |
changeset 807 | ce85435185c3 |
parent 780 | e06d0d16595f |
child 880 | 9d0bfd35b97c |
permissions | -rw-r--r-- |
alpar@774 | 1 |
#include "test_tools.h" |
alpar@774 | 2 |
#include <hugo/smart_graph.h> |
alpar@774 | 3 |
#include <hugo/bfs.h> |
alpar@793 | 4 |
#include<hugo/skeletons/graph.h> |
alpar@774 | 5 |
|
alpar@774 | 6 |
using namespace hugo; |
alpar@774 | 7 |
|
alpar@774 | 8 |
const int PET_SIZE =5; |
alpar@774 | 9 |
|
alpar@774 | 10 |
|
alpar@793 | 11 |
void check_Bfs_Compile() |
alpar@774 | 12 |
{ |
alpar@793 | 13 |
typedef skeleton::StaticGraphSkeleton Graph; |
alpar@774 | 14 |
|
alpar@774 | 15 |
typedef Graph::Edge Edge; |
alpar@774 | 16 |
typedef Graph::Node Node; |
alpar@774 | 17 |
typedef Graph::EdgeIt EdgeIt; |
alpar@774 | 18 |
typedef Graph::NodeIt NodeIt; |
alpar@774 | 19 |
|
alpar@774 | 20 |
typedef Bfs<Graph> BType; |
alpar@774 | 21 |
|
alpar@774 | 22 |
Graph G; |
alpar@774 | 23 |
Node n; |
alpar@774 | 24 |
Edge e; |
alpar@793 | 25 |
int l; |
alpar@774 | 26 |
bool b; |
alpar@774 | 27 |
BType::DistMap d(G); |
alpar@774 | 28 |
BType::PredMap p(G); |
alpar@774 | 29 |
BType::PredNodeMap pn(G); |
alpar@774 | 30 |
|
alpar@774 | 31 |
BType bfs_test(G); |
alpar@774 | 32 |
|
alpar@774 | 33 |
bfs_test.run(n); |
alpar@774 | 34 |
|
alpar@774 | 35 |
l = bfs_test.dist(n); |
alpar@774 | 36 |
e = bfs_test.pred(n); |
alpar@774 | 37 |
n = bfs_test.predNode(n); |
alpar@774 | 38 |
d = bfs_test.distMap(); |
alpar@774 | 39 |
p = bfs_test.predMap(); |
alpar@774 | 40 |
pn = bfs_test.predNodeMap(); |
alpar@774 | 41 |
b = bfs_test.reached(n); |
alpar@774 | 42 |
|
alpar@774 | 43 |
} |
alpar@774 | 44 |
|
alpar@774 | 45 |
int main() |
alpar@774 | 46 |
{ |
alpar@774 | 47 |
|
alpar@774 | 48 |
typedef SmartGraph Graph; |
alpar@774 | 49 |
|
alpar@774 | 50 |
typedef Graph::Edge Edge; |
alpar@774 | 51 |
typedef Graph::Node Node; |
alpar@774 | 52 |
typedef Graph::EdgeIt EdgeIt; |
alpar@774 | 53 |
typedef Graph::NodeIt NodeIt; |
alpar@774 | 54 |
typedef Graph::EdgeMap<int> LengthMap; |
alpar@774 | 55 |
|
alpar@774 | 56 |
Graph G; |
alpar@774 | 57 |
Node s, t; |
alpar@774 | 58 |
PetStruct<Graph> ps = addPetersen(G,PET_SIZE); |
alpar@774 | 59 |
|
alpar@774 | 60 |
s=ps.outer[2]; |
alpar@774 | 61 |
t=ps.inner[0]; |
alpar@774 | 62 |
|
alpar@774 | 63 |
Bfs<Graph> bfs_test(G); |
alpar@774 | 64 |
bfs_test.run(s); |
alpar@774 | 65 |
|
alpar@774 | 66 |
check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t)); |
alpar@774 | 67 |
|
alpar@774 | 68 |
|
alpar@774 | 69 |
for(EdgeIt e(G); e==INVALID; ++e) { |
alpar@774 | 70 |
Node u=G.tail(e); |
alpar@774 | 71 |
Node v=G.head(e); |
alpar@774 | 72 |
check( !bfs_test.reached(u) || |
alpar@774 | 73 |
(bfs_test.dist(v) > bfs_test.dist(u)+1), |
alpar@774 | 74 |
"Wrong output."); |
alpar@774 | 75 |
} |
alpar@774 | 76 |
|
alpar@780 | 77 |
for(NodeIt v(G); v==INVALID; ++v) { |
alpar@780 | 78 |
check(bfs_test.reached(v),"Each node should be reached."); |
alpar@780 | 79 |
if ( bfs_test.pred(v)!=INVALID ) { |
alpar@774 | 80 |
Edge e=bfs_test.pred(v); |
alpar@774 | 81 |
Node u=G.tail(e); |
alpar@780 | 82 |
check(u==bfs_test.predNode(v),"Wrong tree."); |
alpar@774 | 83 |
check(bfs_test.dist(v) - bfs_test.dist(u) == 1, |
alpar@780 | 84 |
"Wrong distance. Difference: " |
alpar@774 | 85 |
<< std::abs(bfs_test.dist(v) - bfs_test.dist(u) |
alpar@774 | 86 |
- 1)); |
alpar@774 | 87 |
} |
alpar@780 | 88 |
} |
alpar@774 | 89 |
} |
alpar@780 | 90 |