| author | marci |
| Thu, 02 Sep 2004 16:59:30 +0000 | |
| changeset 789 | 65c5c7d37578 |
| child 793 | 9cd0aeea47b0 |
| permissions | -rw-r--r-- |
| alpar@780 | 1 |
#include "test_tools.h" |
| alpar@780 | 2 |
#include <hugo/smart_graph.h> |
| alpar@780 | 3 |
#include <hugo/dfs.h> |
| alpar@780 | 4 |
|
| alpar@780 | 5 |
using namespace hugo; |
| alpar@780 | 6 |
|
| alpar@780 | 7 |
const int PET_SIZE =5; |
| alpar@780 | 8 |
|
| alpar@780 | 9 |
|
| alpar@780 | 10 |
void check_Dfs_SmartGraph_Compile() |
| alpar@780 | 11 |
{
|
| alpar@780 | 12 |
typedef int VType; |
| alpar@780 | 13 |
typedef SmartGraph Graph; |
| alpar@780 | 14 |
|
| alpar@780 | 15 |
typedef Graph::Edge Edge; |
| alpar@780 | 16 |
typedef Graph::Node Node; |
| alpar@780 | 17 |
typedef Graph::EdgeIt EdgeIt; |
| alpar@780 | 18 |
typedef Graph::NodeIt NodeIt; |
| alpar@780 | 19 |
typedef Graph::EdgeMap<VType> LengthMap; |
| alpar@780 | 20 |
|
| alpar@780 | 21 |
typedef Dfs<Graph> BType; |
| alpar@780 | 22 |
|
| alpar@780 | 23 |
Graph G; |
| alpar@780 | 24 |
Node n; |
| alpar@780 | 25 |
Edge e; |
| alpar@780 | 26 |
VType l; |
| alpar@780 | 27 |
bool b; |
| alpar@780 | 28 |
BType::DistMap d(G); |
| alpar@780 | 29 |
BType::PredMap p(G); |
| alpar@780 | 30 |
BType::PredNodeMap pn(G); |
| alpar@780 | 31 |
LengthMap cap(G); |
| alpar@780 | 32 |
|
| alpar@780 | 33 |
BType dfs_test(G); |
| alpar@780 | 34 |
|
| alpar@780 | 35 |
dfs_test.run(n); |
| alpar@780 | 36 |
|
| alpar@780 | 37 |
l = dfs_test.dist(n); |
| alpar@780 | 38 |
e = dfs_test.pred(n); |
| alpar@780 | 39 |
n = dfs_test.predNode(n); |
| alpar@780 | 40 |
d = dfs_test.distMap(); |
| alpar@780 | 41 |
p = dfs_test.predMap(); |
| alpar@780 | 42 |
pn = dfs_test.predNodeMap(); |
| alpar@780 | 43 |
b = dfs_test.reached(n); |
| alpar@780 | 44 |
|
| alpar@780 | 45 |
} |
| alpar@780 | 46 |
|
| alpar@780 | 47 |
int main() |
| alpar@780 | 48 |
{
|
| alpar@780 | 49 |
|
| alpar@780 | 50 |
typedef SmartGraph Graph; |
| alpar@780 | 51 |
|
| alpar@780 | 52 |
typedef Graph::Edge Edge; |
| alpar@780 | 53 |
typedef Graph::Node Node; |
| alpar@780 | 54 |
typedef Graph::EdgeIt EdgeIt; |
| alpar@780 | 55 |
typedef Graph::NodeIt NodeIt; |
| alpar@780 | 56 |
typedef Graph::EdgeMap<int> LengthMap; |
| alpar@780 | 57 |
|
| alpar@780 | 58 |
Graph G; |
| alpar@780 | 59 |
Node s, t; |
| alpar@780 | 60 |
PetStruct<Graph> ps = addPetersen(G,PET_SIZE); |
| alpar@780 | 61 |
|
| alpar@780 | 62 |
s=ps.outer[2]; |
| alpar@780 | 63 |
t=ps.inner[0]; |
| alpar@780 | 64 |
|
| alpar@780 | 65 |
Dfs<Graph> dfs_test(G); |
| alpar@780 | 66 |
dfs_test.run(s); |
| alpar@780 | 67 |
|
| alpar@780 | 68 |
for(NodeIt v(G); v!=INVALID; ++v) {
|
| alpar@780 | 69 |
check(dfs_test.reached(v),"Each node should be reached."); |
| alpar@780 | 70 |
if ( dfs_test.pred(v)!=INVALID ) {
|
| alpar@780 | 71 |
Edge e=dfs_test.pred(v); |
| alpar@780 | 72 |
Node u=G.tail(e); |
| alpar@780 | 73 |
check(u==dfs_test.predNode(v),"Wrong tree."); |
| alpar@780 | 74 |
check(dfs_test.dist(v) - dfs_test.dist(u) == 1, |
| alpar@780 | 75 |
"Wrong distance." << dfs_test.dist(v) << " " <<dfs_test.dist(u) ); |
| alpar@780 | 76 |
} |
| alpar@780 | 77 |
} |
| alpar@780 | 78 |
} |
| alpar@780 | 79 |