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> |
|
23 |
22 #include <lemon/dfs.h> |
24 #include <lemon/dfs.h> |
23 #include <lemon/path.h> |
25 #include <lemon/path.h> |
24 |
26 |
25 #include "graph_test.h" |
27 #include "graph_test.h" |
26 #include "test_tools.h" |
28 #include "test_tools.h" |
27 |
29 |
28 using namespace lemon; |
30 using namespace lemon; |
|
31 |
|
32 char test_lgf[] = |
|
33 "@nodes\n" |
|
34 "label\n" |
|
35 "0\n" |
|
36 "1\n" |
|
37 "2\n" |
|
38 "3\n" |
|
39 "4\n" |
|
40 "5\n" |
|
41 "6\n" |
|
42 "@arcs\n" |
|
43 " label\n" |
|
44 "0 1 0\n" |
|
45 "1 2 1\n" |
|
46 "2 3 2\n" |
|
47 "1 4 3\n" |
|
48 "4 2 4\n" |
|
49 "4 5 5\n" |
|
50 "5 0 6\n" |
|
51 "6 3 7\n" |
|
52 "@attributes\n" |
|
53 "source 0\n" |
|
54 "target 5\n"; |
29 |
55 |
30 void checkDfsCompile() |
56 void checkDfsCompile() |
31 { |
57 { |
32 typedef concepts::Digraph Digraph; |
58 typedef concepts::Digraph Digraph; |
33 typedef Dfs<Digraph> DType; |
59 typedef Dfs<Digraph> DType; |
37 Digraph::Arc e; |
63 Digraph::Arc e; |
38 int l; |
64 int l; |
39 bool b; |
65 bool b; |
40 DType::DistMap d(G); |
66 DType::DistMap d(G); |
41 DType::PredMap p(G); |
67 DType::PredMap p(G); |
42 // DType::PredNodeMap pn(G); |
|
43 |
68 |
44 DType dfs_test(G); |
69 DType dfs_test(G); |
45 |
70 |
46 dfs_test.run(n); |
71 dfs_test.run(n); |
47 |
72 |
48 l = dfs_test.dist(n); |
73 l = dfs_test.dist(n); |
49 e = dfs_test.predArc(n); |
74 e = dfs_test.predArc(n); |
50 n = dfs_test.predNode(n); |
75 n = dfs_test.predNode(n); |
51 d = dfs_test.distMap(); |
76 d = dfs_test.distMap(); |
52 p = dfs_test.predMap(); |
77 p = dfs_test.predMap(); |
53 // pn = dfs_test.predNodeMap(); |
|
54 b = dfs_test.reached(n); |
78 b = dfs_test.reached(n); |
55 |
79 |
56 Path<Digraph> pp = dfs_test.path(n); |
80 Path<Digraph> pp = dfs_test.path(n); |
57 } |
81 } |
58 |
82 |
78 void checkDfs() { |
102 void checkDfs() { |
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 Dfs<Digraph> dfs_test(G); |
114 Dfs<Digraph> dfs_test(G); |
89 dfs_test.run(s); |
115 dfs_test.run(s); |
90 |
116 |
91 Path<Digraph> p = dfs_test.path(t); |
117 Path<Digraph> p = dfs_test.path(t); |
93 check(checkPath(G, p),"path() found a wrong path."); |
119 check(checkPath(G, p),"path() found a wrong path."); |
94 check(pathSource(G, p) == s,"path() found a wrong path."); |
120 check(pathSource(G, p) == s,"path() found a wrong path."); |
95 check(pathTarget(G, p) == t,"path() found a wrong path."); |
121 check(pathTarget(G, p) == t,"path() found a wrong path."); |
96 |
122 |
97 for(NodeIt v(G); v!=INVALID; ++v) { |
123 for(NodeIt v(G); v!=INVALID; ++v) { |
98 check(dfs_test.reached(v),"Each node should be reached."); |
124 if (dfs_test.reached(v)) { |
99 if ( dfs_test.predArc(v)!=INVALID ) { |
125 check(v==s || dfs_test.predArc(v)!=INVALID, "Wrong tree."); |
100 Arc e=dfs_test.predArc(v); |
126 if (dfs_test.predArc(v)!=INVALID ) { |
101 Node u=G.source(e); |
127 Arc e=dfs_test.predArc(v); |
102 check(u==dfs_test.predNode(v),"Wrong tree."); |
128 Node u=G.source(e); |
103 check(dfs_test.dist(v) - dfs_test.dist(u) == 1, |
129 check(u==dfs_test.predNode(v),"Wrong tree."); |
104 "Wrong distance. (" << dfs_test.dist(u) << "->" |
130 check(dfs_test.dist(v) - dfs_test.dist(u) == 1, |
105 <<dfs_test.dist(v) << ')'); |
131 "Wrong distance. (" << dfs_test.dist(u) << "->" |
|
132 <<dfs_test.dist(v) << ')'); |
|
133 } |
106 } |
134 } |
107 } |
135 } |
108 } |
136 } |
109 |
137 |
110 int main() |
138 int main() |