17 */ |
17 */ |
18 |
18 |
19 #include <lemon/concepts/digraph.h> |
19 #include <lemon/concepts/digraph.h> |
20 #include <lemon/smart_graph.h> |
20 #include <lemon/smart_graph.h> |
21 #include <lemon/list_graph.h> |
21 #include <lemon/list_graph.h> |
|
22 #include <lemon/lgf_reader.h> |
22 #include <lemon/bfs.h> |
23 #include <lemon/bfs.h> |
23 #include <lemon/path.h> |
24 #include <lemon/path.h> |
24 |
25 |
25 #include "graph_test.h" |
26 #include "graph_test.h" |
26 #include "test_tools.h" |
27 #include "test_tools.h" |
27 |
28 |
28 using namespace lemon; |
29 using namespace lemon; |
|
30 |
|
31 char test_lgf[] = |
|
32 "@nodes\n" |
|
33 "label\n" |
|
34 "0\n" |
|
35 "1\n" |
|
36 "2\n" |
|
37 "3\n" |
|
38 "4\n" |
|
39 "5\n" |
|
40 "@arcs\n" |
|
41 " label\n" |
|
42 "0 1 0\n" |
|
43 "1 2 1\n" |
|
44 "2 3 2\n" |
|
45 "3 4 3\n" |
|
46 "0 3 4\n" |
|
47 "0 3 5\n" |
|
48 "5 2 6\n" |
|
49 "@attributes\n" |
|
50 "source 0\n" |
|
51 "target 4\n"; |
29 |
52 |
30 void checkBfsCompile() |
53 void checkBfsCompile() |
31 { |
54 { |
32 typedef concepts::Digraph Digraph; |
55 typedef concepts::Digraph Digraph; |
33 typedef Bfs<Digraph> BType; |
56 typedef Bfs<Digraph> BType; |
47 |
70 |
48 l = bfs_test.dist(n); |
71 l = bfs_test.dist(n); |
49 e = bfs_test.predArc(n); |
72 e = bfs_test.predArc(n); |
50 n = bfs_test.predNode(n); |
73 n = bfs_test.predNode(n); |
51 d = bfs_test.distMap(); |
74 d = bfs_test.distMap(); |
|
75 |
52 p = bfs_test.predMap(); |
76 p = bfs_test.predMap(); |
53 // pn = bfs_test.predNodeMap(); |
77 // pn = bfs_test.predNodeMap(); |
54 b = bfs_test.reached(n); |
78 b = bfs_test.reached(n); |
55 |
79 |
56 Path<Digraph> pp = bfs_test.path(n); |
80 Path<Digraph> pp = bfs_test.path(n); |
78 void checkBfs() { |
102 void checkBfs() { |
79 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
103 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
80 |
104 |
81 Digraph G; |
105 Digraph G; |
82 Node s, t; |
106 Node s, t; |
83 PetStruct<Digraph> ps = addPetersen(G, 5); |
|
84 |
107 |
85 s=ps.outer[2]; |
108 std::istringstream input(test_lgf); |
86 t=ps.inner[0]; |
109 digraphReader(input, G). |
|
110 node("source", s). |
|
111 node("target", t). |
|
112 run(); |
87 |
113 |
88 Bfs<Digraph> bfs_test(G); |
114 Bfs<Digraph> bfs_test(G); |
89 bfs_test.run(s); |
115 bfs_test.run(s); |
90 |
116 |
91 check(bfs_test.dist(t)==3,"Bfs found a wrong path." << bfs_test.dist(t)); |
117 check(bfs_test.dist(t)==2,"Bfs found a wrong path." << bfs_test.dist(t)); |
92 |
118 |
93 Path<Digraph> p = bfs_test.path(t); |
119 Path<Digraph> p = bfs_test.path(t); |
94 check(p.length()==3,"path() found a wrong path."); |
120 check(p.length()==2,"path() found a wrong path."); |
95 check(checkPath(G, p),"path() found a wrong path."); |
121 check(checkPath(G, p),"path() found a wrong path."); |
96 check(pathSource(G, p) == s,"path() found a wrong path."); |
122 check(pathSource(G, p) == s,"path() found a wrong path."); |
97 check(pathTarget(G, p) == t,"path() found a wrong path."); |
123 check(pathTarget(G, p) == t,"path() found a wrong path."); |
98 |
124 |
99 |
125 |
100 for(ArcIt e(G); e!=INVALID; ++e) { |
126 for(ArcIt a(G); a!=INVALID; ++a) { |
101 Node u=G.source(e); |
127 Node u=G.source(a); |
102 Node v=G.target(e); |
128 Node v=G.target(a); |
103 check( !bfs_test.reached(u) || |
129 check( !bfs_test.reached(u) || |
104 (bfs_test.dist(v) <= bfs_test.dist(u)+1), |
130 (bfs_test.dist(v) <= bfs_test.dist(u)+1), |
105 "Wrong output."); |
131 "Wrong output." << G.id(v) << ' ' << G.id(u)); |
106 } |
132 } |
107 |
133 |
108 for(NodeIt v(G); v!=INVALID; ++v) { |
134 for(NodeIt v(G); v!=INVALID; ++v) { |
109 check(bfs_test.reached(v),"Each node should be reached."); |
135 if (bfs_test.reached(v)) { |
110 if ( bfs_test.predArc(v)!=INVALID ) { |
136 check(v==s || bfs_test.predArc(v)!=INVALID, "Wrong tree."); |
111 Arc e=bfs_test.predArc(v); |
137 if (bfs_test.predArc(v)!=INVALID ) { |
112 Node u=G.source(e); |
138 Arc a=bfs_test.predArc(v); |
113 check(u==bfs_test.predNode(v),"Wrong tree."); |
139 Node u=G.source(a); |
114 check(bfs_test.dist(v) - bfs_test.dist(u) == 1, |
140 check(u==bfs_test.predNode(v),"Wrong tree."); |
115 "Wrong distance. Difference: " |
141 check(bfs_test.dist(v) - bfs_test.dist(u) == 1, |
116 << std::abs(bfs_test.dist(v) - bfs_test.dist(u) |
142 "Wrong distance. Difference: " |
117 - 1)); |
143 << std::abs(bfs_test.dist(v) - bfs_test.dist(u) |
|
144 - 1)); |
|
145 } |
118 } |
146 } |
119 } |
147 } |
120 } |
148 } |
121 |
149 |
122 int main() |
150 int main() |