OLD | NEW |
---|---|
1 // Copyright (c) 2016, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2016, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 import "package:test/test.dart"; | 5 import "package:test/test.dart"; |
6 | 6 |
7 import "package:collection/collection.dart"; | 7 import "package:collection/collection.dart"; |
8 | 8 |
9 void main() { | 9 void main() { |
10 group("mapMap()", () { | 10 group("mapMap()", () { |
(...skipping 163 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
174 "foo": ["bar"], | 174 "foo": ["bar"], |
175 "bar": ["baz"], | 175 "bar": ["baz"], |
176 "baz": ["foo"] | 176 "baz": ["foo"] |
177 }), equals({ | 177 }), equals({ |
178 "foo": ["bar", "baz", "foo"], | 178 "foo": ["bar", "baz", "foo"], |
179 "bar": ["baz", "foo", "bar"], | 179 "bar": ["baz", "foo", "bar"], |
180 "baz": ["foo", "bar", "baz"] | 180 "baz": ["foo", "bar", "baz"] |
181 })); | 181 })); |
182 }); | 182 }); |
183 }); | 183 }); |
184 | |
185 group("stronglyConnectedComponents()", () { | |
186 test("returns an empty list for an empty graph", () { | |
187 expect(stronglyConnectedComponents({}), isEmpty); | |
188 }); | |
189 | |
190 test("returns one set for a singleton graph", () { | |
191 expect(stronglyConnectedComponents({"a": []}), | |
192 equals([new Set.from(["a"])])); | |
193 }); | |
194 | |
195 test("returns two sets for a two-element tree", () { | |
196 expect(stronglyConnectedComponents({"a": ["b"], "b": []}), | |
197 equals([new Set.from(["a"]), new Set.from(["b"])])); | |
198 }); | |
199 | |
200 test("returns one set for a two-element loop", () { | |
201 expect(stronglyConnectedComponents({"a": ["b"], "b": ["a"]}), | |
202 equals([new Set.from(["a", "b"])])); | |
203 }); | |
204 | |
205 test("returns individual vertices for a tree", () { | |
Lasse Reichstein Nielsen
2016/06/23 14:44:03
At least document here that this is the expected t
nweiz
2016/06/23 20:52:58
Done.
| |
206 expect(stronglyConnectedComponents({ | |
207 "foo": ["bar"], | |
208 "bar": ["baz", "bang"], | |
209 "baz": ["qux"], | |
210 "bang": ["zap"], | |
211 "qux": [], | |
212 "zap": [] | |
213 }), equals([ | |
214 new Set.from(["foo"]), | |
215 new Set.from(["bar"]), | |
216 new Set.from(["bang"]), | |
217 new Set.from(["zap"]), | |
218 new Set.from(["baz"]), | |
219 new Set.from(["qux"]) | |
220 ])); | |
221 }); | |
222 | |
223 test("returns a single set for a fully cyclic graph", () { | |
224 expect(stronglyConnectedComponents({ | |
225 "foo": ["bar"], | |
226 "bar": ["baz"], | |
227 "baz": ["bang"], | |
228 "bang": ["foo"] | |
229 }), equals([new Set.from(["foo", "bar", "baz", "bang"])])); | |
230 }); | |
231 | |
232 test("returns separate sets for each strongly connected component", () { | |
233 // https://en.wikipedia.org/wiki/Strongly_connected_component#/media/File: Scc.png | |
234 expect(stronglyConnectedComponents({ | |
235 "a": ["b"], | |
236 "b": ["c", "e", "f"], | |
237 "c": ["d", "g"], | |
238 "d": ["c", "h"], | |
239 "e": ["a", "f"], | |
240 "f": ["g"], | |
241 "g": ["f"], | |
242 "h": ["g", "d"] | |
243 }), equals([ | |
244 new Set.from(["a", "b", "e"]), | |
245 new Set.from(["c", "d", "h"]), | |
246 new Set.from(["f", "g"]), | |
247 ])); | |
248 }); | |
249 | |
250 test("always returns components in topological order", () { | |
251 expect(stronglyConnectedComponents({ | |
252 "bar": ["baz", "bang"], | |
253 "zap": [], | |
254 "baz": ["qux"], | |
255 "qux": [], | |
256 "foo": ["bar"], | |
257 "bang": ["zap"] | |
258 }), equals([ | |
259 new Set.from(["foo"]), | |
260 new Set.from(["bar"]), | |
261 new Set.from(["bang"]), | |
262 new Set.from(["zap"]), | |
263 new Set.from(["baz"]), | |
264 new Set.from(["qux"]) | |
265 ])); | |
266 }); | |
267 }); | |
184 } | 268 } |
OLD | NEW |