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", () { |
| 206 expect(stronglyConnectedComponents({ |
| 207 "foo": ["bar"], |
| 208 "bar": ["baz", "bang"], |
| 209 "baz": ["qux"], |
| 210 "bang": ["zap"], |
| 211 "qux": [], |
| 212 "zap": [] |
| 213 }), equals([ |
| 214 // This is expected to return *a* topological ordering, but this isn't |
| 215 // the only valid one. If the function implementation changes in the |
| 216 // future, this test may need to be updated. |
| 217 new Set.from(["foo"]), |
| 218 new Set.from(["bar"]), |
| 219 new Set.from(["bang"]), |
| 220 new Set.from(["zap"]), |
| 221 new Set.from(["baz"]), |
| 222 new Set.from(["qux"]) |
| 223 ])); |
| 224 }); |
| 225 |
| 226 test("returns a single set for a fully cyclic graph", () { |
| 227 expect(stronglyConnectedComponents({ |
| 228 "foo": ["bar"], |
| 229 "bar": ["baz"], |
| 230 "baz": ["bang"], |
| 231 "bang": ["foo"] |
| 232 }), equals([new Set.from(["foo", "bar", "baz", "bang"])])); |
| 233 }); |
| 234 |
| 235 test("returns separate sets for each strongly connected component", () { |
| 236 // https://en.wikipedia.org/wiki/Strongly_connected_component#/media/File:
Scc.png |
| 237 expect(stronglyConnectedComponents({ |
| 238 "a": ["b"], |
| 239 "b": ["c", "e", "f"], |
| 240 "c": ["d", "g"], |
| 241 "d": ["c", "h"], |
| 242 "e": ["a", "f"], |
| 243 "f": ["g"], |
| 244 "g": ["f"], |
| 245 "h": ["g", "d"] |
| 246 }), equals([ |
| 247 // This is expected to return *a* topological ordering, but this isn't |
| 248 // the only valid one. If the function implementation changes in the |
| 249 // future, this test may need to be updated. |
| 250 new Set.from(["a", "b", "e"]), |
| 251 new Set.from(["c", "d", "h"]), |
| 252 new Set.from(["f", "g"]), |
| 253 ])); |
| 254 }); |
| 255 |
| 256 test("always returns components in topological order", () { |
| 257 expect(stronglyConnectedComponents({ |
| 258 "bar": ["baz", "bang"], |
| 259 "zap": [], |
| 260 "baz": ["qux"], |
| 261 "qux": [], |
| 262 "foo": ["bar"], |
| 263 "bang": ["zap"] |
| 264 }), equals([ |
| 265 // This is expected to return *a* topological ordering, but this isn't |
| 266 // the only valid one. If the function implementation changes in the |
| 267 // future, this test may need to be updated. |
| 268 new Set.from(["foo"]), |
| 269 new Set.from(["bar"]), |
| 270 new Set.from(["bang"]), |
| 271 new Set.from(["zap"]), |
| 272 new Set.from(["baz"]), |
| 273 new Set.from(["qux"]) |
| 274 ])); |
| 275 }); |
| 276 }); |
184 } | 277 } |
OLD | NEW |