1 /* -*- C++ -*- |
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
2 * |
2 * |
3 * This file is a part of LEMON, a generic C++ optimization library |
3 * This file is a part of LEMON, a generic C++ optimization library. |
4 * |
4 * |
5 * Copyright (C) 2003-2008 |
5 * Copyright (C) 2003-2008 |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
8 * |
8 * |
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 checkBfsCompile() |
30 void checkBfsCompile() |
31 { |
31 { |
32 typedef concepts::Digraph Digraph; |
32 typedef concepts::Digraph Digraph; |
33 typedef Bfs<Digraph> BType; |
33 typedef Bfs<Digraph> BType; |
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 BType::DistMap d(G); |
40 BType::DistMap d(G); |
41 BType::PredMap p(G); |
41 BType::PredMap p(G); |
42 // BType::PredNodeMap pn(G); |
42 // BType::PredNodeMap pn(G); |
43 |
43 |
44 BType bfs_test(G); |
44 BType bfs_test(G); |
45 |
45 |
46 bfs_test.run(n); |
46 bfs_test.run(n); |
47 |
47 |
48 l = bfs_test.dist(n); |
48 l = bfs_test.dist(n); |
49 e = bfs_test.predArc(n); |
49 e = bfs_test.predArc(n); |
50 n = bfs_test.predNode(n); |
50 n = bfs_test.predNode(n); |
51 d = bfs_test.distMap(); |
51 d = bfs_test.distMap(); |
52 p = bfs_test.predMap(); |
52 p = bfs_test.predMap(); |
54 b = bfs_test.reached(n); |
54 b = bfs_test.reached(n); |
55 |
55 |
56 Path<Digraph> pp = bfs_test.path(n); |
56 Path<Digraph> pp = bfs_test.path(n); |
57 } |
57 } |
58 |
58 |
59 void checkBfsFunctionCompile() |
59 void checkBfsFunctionCompile() |
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 bfs(g,Node()).run(); |
67 bfs(g,Node()).run(); |
68 bfs(g).source(Node()).run(); |
68 bfs(g).source(Node()).run(); |
69 bfs(g) |
69 bfs(g) |
70 .predMap(concepts::WriteMap<Node,Arc>()) |
70 .predMap(concepts::WriteMap<Node,Arc>()) |
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 Bfs<Digraph> bfs_test(G); |
88 Bfs<Digraph> bfs_test(G); |
89 bfs_test.run(s); |
89 bfs_test.run(s); |
90 |
90 |
91 check(bfs_test.dist(t)==3,"Bfs found a wrong path." << bfs_test.dist(t)); |
91 check(bfs_test.dist(t)==3,"Bfs found a wrong path." << bfs_test.dist(t)); |
92 |
92 |
93 Path<Digraph> p = bfs_test.path(t); |
93 Path<Digraph> p = bfs_test.path(t); |
94 check(p.length()==3,"path() found a wrong path."); |
94 check(p.length()==3,"path() found a wrong path."); |
95 check(checkPath(G, p),"path() found a wrong path."); |
95 check(checkPath(G, p),"path() found a wrong path."); |
96 check(pathSource(G, p) == s,"path() found a wrong path."); |
96 check(pathSource(G, p) == s,"path() found a wrong path."); |
97 check(pathTarget(G, p) == t,"path() found a wrong path."); |
97 check(pathTarget(G, p) == t,"path() found a wrong path."); |
98 |
98 |
99 |
99 |
100 for(ArcIt e(G); e==INVALID; ++e) { |
100 for(ArcIt e(G); e==INVALID; ++e) { |
101 Node u=G.source(e); |
101 Node u=G.source(e); |
102 Node v=G.target(e); |
102 Node v=G.target(e); |
103 check( !bfs_test.reached(u) || |
103 check( !bfs_test.reached(u) || |
104 (bfs_test.dist(v) > bfs_test.dist(u)+1), |
104 (bfs_test.dist(v) > bfs_test.dist(u)+1), |
105 "Wrong output."); |
105 "Wrong output."); |
106 } |
106 } |
107 |
107 |
108 for(NodeIt v(G); v==INVALID; ++v) { |
108 for(NodeIt v(G); v==INVALID; ++v) { |
109 check(bfs_test.reached(v),"Each node should be reached."); |
109 check(bfs_test.reached(v),"Each node should be reached."); |
110 if ( bfs_test.predArc(v)!=INVALID ) { |
110 if ( bfs_test.predArc(v)!=INVALID ) { |
111 Arc e=bfs_test.predArc(v); |
111 Arc e=bfs_test.predArc(v); |
112 Node u=G.source(e); |
112 Node u=G.source(e); |
113 check(u==bfs_test.predNode(v),"Wrong tree."); |
113 check(u==bfs_test.predNode(v),"Wrong tree."); |
114 check(bfs_test.dist(v) - bfs_test.dist(u) == 1, |
114 check(bfs_test.dist(v) - bfs_test.dist(u) == 1, |
115 "Wrong distance. Difference: " |
115 "Wrong distance. Difference: " |
116 << std::abs(bfs_test.dist(v) - bfs_test.dist(u) |
116 << std::abs(bfs_test.dist(v) - bfs_test.dist(u) |
117 - 1)); |
117 - 1)); |
118 } |
118 } |
119 } |
119 } |
120 } |
120 } |
121 |
121 |
122 int main() |
122 int main() |