alpar@906
|
1 |
/* -*- C++ -*-
|
alpar@921
|
2 |
* src/test/bfs_test.cc - Part of LEMON, a generic C++ optimization library
|
alpar@906
|
3 |
*
|
alpar@1164
|
4 |
* Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
alpar@906
|
5 |
* (Egervary Combinatorial Optimization Research Group, EGRES).
|
alpar@906
|
6 |
*
|
alpar@906
|
7 |
* Permission to use, modify and distribute this software is granted
|
alpar@906
|
8 |
* provided that this copyright notice appears in all copies. For
|
alpar@906
|
9 |
* precise terms see the accompanying LICENSE file.
|
alpar@906
|
10 |
*
|
alpar@906
|
11 |
* This software is provided "AS IS" with no warranty of any kind,
|
alpar@906
|
12 |
* express or implied, and with no claim as to its suitability for any
|
alpar@906
|
13 |
* purpose.
|
alpar@906
|
14 |
*
|
alpar@906
|
15 |
*/
|
alpar@906
|
16 |
|
alpar@774
|
17 |
#include "test_tools.h"
|
alpar@921
|
18 |
#include <lemon/smart_graph.h>
|
alpar@921
|
19 |
#include <lemon/bfs.h>
|
klao@959
|
20 |
#include<lemon/concept/graph.h>
|
alpar@774
|
21 |
|
alpar@921
|
22 |
using namespace lemon;
|
alpar@774
|
23 |
|
alpar@774
|
24 |
const int PET_SIZE =5;
|
alpar@774
|
25 |
|
alpar@774
|
26 |
|
alpar@793
|
27 |
void check_Bfs_Compile()
|
alpar@774
|
28 |
{
|
klao@959
|
29 |
typedef concept::StaticGraph Graph;
|
alpar@774
|
30 |
|
alpar@774
|
31 |
typedef Graph::Edge Edge;
|
alpar@774
|
32 |
typedef Graph::Node Node;
|
alpar@774
|
33 |
typedef Graph::EdgeIt EdgeIt;
|
alpar@774
|
34 |
typedef Graph::NodeIt NodeIt;
|
alpar@774
|
35 |
|
alpar@774
|
36 |
typedef Bfs<Graph> BType;
|
alpar@774
|
37 |
|
alpar@774
|
38 |
Graph G;
|
alpar@774
|
39 |
Node n;
|
alpar@774
|
40 |
Edge e;
|
alpar@793
|
41 |
int l;
|
alpar@774
|
42 |
bool b;
|
alpar@774
|
43 |
BType::DistMap d(G);
|
alpar@774
|
44 |
BType::PredMap p(G);
|
alpar@1218
|
45 |
// BType::PredNodeMap pn(G);
|
alpar@774
|
46 |
|
alpar@774
|
47 |
BType bfs_test(G);
|
alpar@774
|
48 |
|
alpar@774
|
49 |
bfs_test.run(n);
|
alpar@774
|
50 |
|
alpar@774
|
51 |
l = bfs_test.dist(n);
|
alpar@774
|
52 |
e = bfs_test.pred(n);
|
alpar@774
|
53 |
n = bfs_test.predNode(n);
|
alpar@774
|
54 |
d = bfs_test.distMap();
|
alpar@774
|
55 |
p = bfs_test.predMap();
|
alpar@1218
|
56 |
// pn = bfs_test.predNodeMap();
|
alpar@774
|
57 |
b = bfs_test.reached(n);
|
alpar@774
|
58 |
|
alpar@774
|
59 |
}
|
alpar@774
|
60 |
|
alpar@774
|
61 |
int main()
|
alpar@774
|
62 |
{
|
alpar@774
|
63 |
|
alpar@774
|
64 |
typedef SmartGraph Graph;
|
alpar@774
|
65 |
|
alpar@774
|
66 |
typedef Graph::Edge Edge;
|
alpar@774
|
67 |
typedef Graph::Node Node;
|
alpar@774
|
68 |
typedef Graph::EdgeIt EdgeIt;
|
alpar@774
|
69 |
typedef Graph::NodeIt NodeIt;
|
alpar@774
|
70 |
typedef Graph::EdgeMap<int> LengthMap;
|
alpar@774
|
71 |
|
alpar@774
|
72 |
Graph G;
|
alpar@774
|
73 |
Node s, t;
|
alpar@774
|
74 |
PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
|
alpar@774
|
75 |
|
alpar@774
|
76 |
s=ps.outer[2];
|
alpar@774
|
77 |
t=ps.inner[0];
|
alpar@774
|
78 |
|
alpar@774
|
79 |
Bfs<Graph> bfs_test(G);
|
alpar@774
|
80 |
bfs_test.run(s);
|
alpar@774
|
81 |
|
alpar@774
|
82 |
check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
|
alpar@774
|
83 |
|
alpar@774
|
84 |
|
alpar@774
|
85 |
for(EdgeIt e(G); e==INVALID; ++e) {
|
alpar@986
|
86 |
Node u=G.source(e);
|
alpar@986
|
87 |
Node v=G.target(e);
|
alpar@774
|
88 |
check( !bfs_test.reached(u) ||
|
alpar@774
|
89 |
(bfs_test.dist(v) > bfs_test.dist(u)+1),
|
alpar@774
|
90 |
"Wrong output.");
|
alpar@774
|
91 |
}
|
alpar@774
|
92 |
|
alpar@780
|
93 |
for(NodeIt v(G); v==INVALID; ++v) {
|
alpar@780
|
94 |
check(bfs_test.reached(v),"Each node should be reached.");
|
alpar@780
|
95 |
if ( bfs_test.pred(v)!=INVALID ) {
|
alpar@774
|
96 |
Edge e=bfs_test.pred(v);
|
alpar@986
|
97 |
Node u=G.source(e);
|
alpar@780
|
98 |
check(u==bfs_test.predNode(v),"Wrong tree.");
|
alpar@774
|
99 |
check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
|
alpar@780
|
100 |
"Wrong distance. Difference: "
|
alpar@774
|
101 |
<< std::abs(bfs_test.dist(v) - bfs_test.dist(u)
|
alpar@774
|
102 |
- 1));
|
alpar@774
|
103 |
}
|
alpar@780
|
104 |
}
|
alpar@774
|
105 |
}
|
alpar@780
|
106 |
|