60 Digraph::Arc e; |
60 Digraph::Arc e; |
61 int l; |
61 int l; |
62 bool b; |
62 bool b; |
63 BType::DistMap d(G); |
63 BType::DistMap d(G); |
64 BType::PredMap p(G); |
64 BType::PredMap p(G); |
65 // BType::PredNodeMap pn(G); |
|
66 |
65 |
67 BType bfs_test(G); |
66 BType bfs_test(G); |
68 |
67 |
69 bfs_test.run(n); |
68 bfs_test.run(n); |
70 |
69 |
71 l = bfs_test.dist(n); |
70 l = bfs_test.dist(n); |
72 e = bfs_test.predArc(n); |
71 e = bfs_test.predArc(n); |
73 n = bfs_test.predNode(n); |
72 n = bfs_test.predNode(n); |
74 d = bfs_test.distMap(); |
73 d = bfs_test.distMap(); |
75 |
|
76 p = bfs_test.predMap(); |
74 p = bfs_test.predMap(); |
77 // pn = bfs_test.predNodeMap(); |
|
78 b = bfs_test.reached(n); |
75 b = bfs_test.reached(n); |
79 |
76 |
80 Path<Digraph> pp = bfs_test.path(n); |
77 Path<Digraph> pp = bfs_test.path(n); |
81 } |
78 } |
82 |
79 |
86 typedef concepts::Digraph Digraph; |
83 typedef concepts::Digraph Digraph; |
87 typedef Digraph::Arc Arc; |
84 typedef Digraph::Arc Arc; |
88 typedef Digraph::Node Node; |
85 typedef Digraph::Node Node; |
89 |
86 |
90 Digraph g; |
87 Digraph g; |
91 bfs(g,Node()).run(); |
88 bool b; |
92 bfs(g).source(Node()).run(); |
89 bfs(g).run(Node()); |
|
90 b=bfs(g).run(Node(),Node()); |
|
91 bfs(g).run(); |
93 bfs(g) |
92 bfs(g) |
94 .predMap(concepts::WriteMap<Node,Arc>()) |
93 .predMap(concepts::ReadWriteMap<Node,Arc>()) |
95 .distMap(concepts::WriteMap<Node,VType>()) |
94 .distMap(concepts::ReadWriteMap<Node,VType>()) |
96 .reachedMap(concepts::ReadWriteMap<Node,bool>()) |
95 .reachedMap(concepts::ReadWriteMap<Node,bool>()) |
97 .processedMap(concepts::WriteMap<Node,bool>()) |
96 .processedMap(concepts::WriteMap<Node,bool>()) |
98 .run(Node()); |
97 .run(Node()); |
|
98 b=bfs(g) |
|
99 .predMap(concepts::ReadWriteMap<Node,Arc>()) |
|
100 .distMap(concepts::ReadWriteMap<Node,VType>()) |
|
101 .reachedMap(concepts::ReadWriteMap<Node,bool>()) |
|
102 .processedMap(concepts::WriteMap<Node,bool>()) |
|
103 .path(concepts::Path<Digraph>()) |
|
104 .dist(VType()) |
|
105 .run(Node(),Node()); |
|
106 bfs(g) |
|
107 .predMap(concepts::ReadWriteMap<Node,Arc>()) |
|
108 .distMap(concepts::ReadWriteMap<Node,VType>()) |
|
109 .reachedMap(concepts::ReadWriteMap<Node,bool>()) |
|
110 .processedMap(concepts::WriteMap<Node,bool>()) |
|
111 .run(); |
99 } |
112 } |
100 |
113 |
101 template <class Digraph> |
114 template <class Digraph> |
102 void checkBfs() { |
115 void checkBfs() { |
103 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
116 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
112 run(); |
125 run(); |
113 |
126 |
114 Bfs<Digraph> bfs_test(G); |
127 Bfs<Digraph> bfs_test(G); |
115 bfs_test.run(s); |
128 bfs_test.run(s); |
116 |
129 |
117 check(bfs_test.dist(t)==2,"Bfs found a wrong path." << bfs_test.dist(t)); |
130 check(bfs_test.dist(t)==2,"Bfs found a wrong path."); |
118 |
131 |
119 Path<Digraph> p = bfs_test.path(t); |
132 Path<Digraph> p = bfs_test.path(t); |
120 check(p.length()==2,"path() found a wrong path."); |
133 check(p.length()==2,"path() found a wrong path."); |
121 check(checkPath(G, p),"path() found a wrong path."); |
134 check(checkPath(G, p),"path() found a wrong path."); |
122 check(pathSource(G, p) == s,"path() found a wrong path."); |
135 check(pathSource(G, p) == s,"path() found a wrong path."); |
126 for(ArcIt a(G); a!=INVALID; ++a) { |
139 for(ArcIt a(G); a!=INVALID; ++a) { |
127 Node u=G.source(a); |
140 Node u=G.source(a); |
128 Node v=G.target(a); |
141 Node v=G.target(a); |
129 check( !bfs_test.reached(u) || |
142 check( !bfs_test.reached(u) || |
130 (bfs_test.dist(v) <= bfs_test.dist(u)+1), |
143 (bfs_test.dist(v) <= bfs_test.dist(u)+1), |
131 "Wrong output." << G.id(v) << ' ' << G.id(u)); |
144 "Wrong output. " << G.id(u) << "->" << G.id(v)); |
132 } |
145 } |
133 |
146 |
134 for(NodeIt v(G); v!=INVALID; ++v) { |
147 for(NodeIt v(G); v!=INVALID; ++v) { |
135 if (bfs_test.reached(v)) { |
148 if (bfs_test.reached(v)) { |
136 check(v==s || bfs_test.predArc(v)!=INVALID, "Wrong tree."); |
149 check(v==s || bfs_test.predArc(v)!=INVALID, "Wrong tree."); |
138 Arc a=bfs_test.predArc(v); |
151 Arc a=bfs_test.predArc(v); |
139 Node u=G.source(a); |
152 Node u=G.source(a); |
140 check(u==bfs_test.predNode(v),"Wrong tree."); |
153 check(u==bfs_test.predNode(v),"Wrong tree."); |
141 check(bfs_test.dist(v) - bfs_test.dist(u) == 1, |
154 check(bfs_test.dist(v) - bfs_test.dist(u) == 1, |
142 "Wrong distance. Difference: " |
155 "Wrong distance. Difference: " |
143 << std::abs(bfs_test.dist(v) - bfs_test.dist(u) |
156 << std::abs(bfs_test.dist(v) - bfs_test.dist(u) - 1)); |
144 - 1)); |
|
145 } |
157 } |
146 } |
158 } |
|
159 } |
|
160 |
|
161 { |
|
162 NullMap<Node,Arc> myPredMap; |
|
163 bfs(G).predMap(myPredMap).run(s); |
147 } |
164 } |
148 } |
165 } |
149 |
166 |
150 int main() |
167 int main() |
151 { |
168 { |