25 #include "graph_test.h" |
25 #include "graph_test.h" |
26 #include "test_tools.h" |
26 #include "test_tools.h" |
27 |
27 |
28 using namespace lemon; |
28 using namespace lemon; |
29 |
29 |
30 void checkDfsCompile() |
30 void checkDfsCompile() |
31 { |
31 { |
32 typedef concepts::Digraph Digraph; |
32 typedef concepts::Digraph Digraph; |
33 typedef Dfs<Digraph> DType; |
33 typedef Dfs<Digraph> DType; |
34 |
34 |
35 Digraph G; |
35 Digraph G; |
36 Digraph::Node n; |
36 Digraph::Node n; |
37 Digraph::Arc e; |
37 Digraph::Arc e; |
38 int l; |
38 int l; |
39 bool b; |
39 bool b; |
40 DType::DistMap d(G); |
40 DType::DistMap d(G); |
41 DType::PredMap p(G); |
41 DType::PredMap p(G); |
42 // DType::PredNodeMap pn(G); |
42 // DType::PredNodeMap pn(G); |
43 |
43 |
44 DType dfs_test(G); |
44 DType dfs_test(G); |
45 |
45 |
46 dfs_test.run(n); |
46 dfs_test.run(n); |
47 |
47 |
48 l = dfs_test.dist(n); |
48 l = dfs_test.dist(n); |
49 e = dfs_test.predArc(n); |
49 e = dfs_test.predArc(n); |
50 n = dfs_test.predNode(n); |
50 n = dfs_test.predNode(n); |
51 d = dfs_test.distMap(); |
51 d = dfs_test.distMap(); |
52 p = dfs_test.predMap(); |
52 p = dfs_test.predMap(); |
54 b = dfs_test.reached(n); |
54 b = dfs_test.reached(n); |
55 |
55 |
56 Path<Digraph> pp = dfs_test.path(n); |
56 Path<Digraph> pp = dfs_test.path(n); |
57 } |
57 } |
58 |
58 |
59 void checkDfsFunctionCompile() |
59 void checkDfsFunctionCompile() |
60 { |
60 { |
61 typedef int VType; |
61 typedef int VType; |
62 typedef concepts::Digraph Digraph; |
62 typedef concepts::Digraph Digraph; |
63 typedef Digraph::Arc Arc; |
63 typedef Digraph::Arc Arc; |
64 typedef Digraph::Node Node; |
64 typedef Digraph::Node Node; |
65 |
65 |
66 Digraph g; |
66 Digraph g; |
67 dfs(g,Node()).run(); |
67 dfs(g,Node()).run(); |
68 dfs(g).source(Node()).run(); |
68 dfs(g).source(Node()).run(); |
69 dfs(g) |
69 dfs(g) |
70 .predMap(concepts::WriteMap<Node,Arc>()) |
70 .predMap(concepts::WriteMap<Node,Arc>()) |
71 .distMap(concepts::WriteMap<Node,VType>()) |
71 .distMap(concepts::WriteMap<Node,VType>()) |
72 .reachedMap(concepts::ReadWriteMap<Node,bool>()) |
72 .reachedMap(concepts::ReadWriteMap<Node,bool>()) |
73 .processedMap(concepts::WriteMap<Node,bool>()) |
73 .processedMap(concepts::WriteMap<Node,bool>()) |
74 .run(Node()); |
74 .run(Node()); |
75 } |
75 } |
76 |
76 |
77 template <class Digraph> |
77 template <class Digraph> |
78 void checkDfs() { |
78 void checkDfs() { |
79 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
79 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
80 |
80 |
81 Digraph G; |
81 Digraph G; |
82 Node s, t; |
82 Node s, t; |
83 PetStruct<Digraph> ps = addPetersen(G, 5); |
83 PetStruct<Digraph> ps = addPetersen(G, 5); |
84 |
84 |
85 s=ps.outer[2]; |
85 s=ps.outer[2]; |
86 t=ps.inner[0]; |
86 t=ps.inner[0]; |
87 |
87 |
88 Dfs<Digraph> dfs_test(G); |
88 Dfs<Digraph> dfs_test(G); |
89 dfs_test.run(s); |
89 dfs_test.run(s); |
90 |
90 |
91 Path<Digraph> p = dfs_test.path(t); |
91 Path<Digraph> p = dfs_test.path(t); |
92 check(p.length() == dfs_test.dist(t),"path() found a wrong path."); |
92 check(p.length() == dfs_test.dist(t),"path() found a wrong path."); |
93 check(checkPath(G, p),"path() found a wrong path."); |
93 check(checkPath(G, p),"path() found a wrong path."); |
94 check(pathSource(G, p) == s,"path() found a wrong path."); |
94 check(pathSource(G, p) == s,"path() found a wrong path."); |
95 check(pathTarget(G, p) == t,"path() found a wrong path."); |
95 check(pathTarget(G, p) == t,"path() found a wrong path."); |
96 |
96 |
97 for(NodeIt v(G); v!=INVALID; ++v) { |
97 for(NodeIt v(G); v!=INVALID; ++v) { |
98 check(dfs_test.reached(v),"Each node should be reached."); |
98 check(dfs_test.reached(v),"Each node should be reached."); |
99 if ( dfs_test.predArc(v)!=INVALID ) { |
99 if ( dfs_test.predArc(v)!=INVALID ) { |
100 Arc e=dfs_test.predArc(v); |
100 Arc e=dfs_test.predArc(v); |
101 Node u=G.source(e); |
101 Node u=G.source(e); |
102 check(u==dfs_test.predNode(v),"Wrong tree."); |
102 check(u==dfs_test.predNode(v),"Wrong tree."); |
103 check(dfs_test.dist(v) - dfs_test.dist(u) == 1, |
103 check(dfs_test.dist(v) - dfs_test.dist(u) == 1, |
104 "Wrong distance. (" << dfs_test.dist(u) << "->" |
104 "Wrong distance. (" << dfs_test.dist(u) << "->" |
105 <<dfs_test.dist(v) << ')'); |
105 <<dfs_test.dist(v) << ')'); |
106 } |
106 } |
107 } |
107 } |
108 } |
108 } |
109 |
109 |
110 int main() |
110 int main() |