Index: test/functions_test.dart |
diff --git a/test/functions_test.dart b/test/functions_test.dart |
index 4d928bf29de56c60a003753378c179ef964435ef..5e750db4b547c35b0b5d934e740d23272f0ba9a0 100644 |
--- a/test/functions_test.dart |
+++ b/test/functions_test.dart |
@@ -181,4 +181,88 @@ void main() { |
})); |
}); |
}); |
+ |
+ group("stronglyConnectedComponents()", () { |
+ test("returns an empty list for an empty graph", () { |
+ expect(stronglyConnectedComponents({}), isEmpty); |
+ }); |
+ |
+ test("returns one set for a singleton graph", () { |
+ expect(stronglyConnectedComponents({"a": []}), |
+ equals([new Set.from(["a"])])); |
+ }); |
+ |
+ test("returns two sets for a two-element tree", () { |
+ expect(stronglyConnectedComponents({"a": ["b"], "b": []}), |
+ equals([new Set.from(["a"]), new Set.from(["b"])])); |
+ }); |
+ |
+ test("returns one set for a two-element loop", () { |
+ expect(stronglyConnectedComponents({"a": ["b"], "b": ["a"]}), |
+ equals([new Set.from(["a", "b"])])); |
+ }); |
+ |
+ 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.
|
+ expect(stronglyConnectedComponents({ |
+ "foo": ["bar"], |
+ "bar": ["baz", "bang"], |
+ "baz": ["qux"], |
+ "bang": ["zap"], |
+ "qux": [], |
+ "zap": [] |
+ }), equals([ |
+ new Set.from(["foo"]), |
+ new Set.from(["bar"]), |
+ new Set.from(["bang"]), |
+ new Set.from(["zap"]), |
+ new Set.from(["baz"]), |
+ new Set.from(["qux"]) |
+ ])); |
+ }); |
+ |
+ test("returns a single set for a fully cyclic graph", () { |
+ expect(stronglyConnectedComponents({ |
+ "foo": ["bar"], |
+ "bar": ["baz"], |
+ "baz": ["bang"], |
+ "bang": ["foo"] |
+ }), equals([new Set.from(["foo", "bar", "baz", "bang"])])); |
+ }); |
+ |
+ test("returns separate sets for each strongly connected component", () { |
+ // https://en.wikipedia.org/wiki/Strongly_connected_component#/media/File:Scc.png |
+ expect(stronglyConnectedComponents({ |
+ "a": ["b"], |
+ "b": ["c", "e", "f"], |
+ "c": ["d", "g"], |
+ "d": ["c", "h"], |
+ "e": ["a", "f"], |
+ "f": ["g"], |
+ "g": ["f"], |
+ "h": ["g", "d"] |
+ }), equals([ |
+ new Set.from(["a", "b", "e"]), |
+ new Set.from(["c", "d", "h"]), |
+ new Set.from(["f", "g"]), |
+ ])); |
+ }); |
+ |
+ test("always returns components in topological order", () { |
+ expect(stronglyConnectedComponents({ |
+ "bar": ["baz", "bang"], |
+ "zap": [], |
+ "baz": ["qux"], |
+ "qux": [], |
+ "foo": ["bar"], |
+ "bang": ["zap"] |
+ }), equals([ |
+ new Set.from(["foo"]), |
+ new Set.from(["bar"]), |
+ new Set.from(["bang"]), |
+ new Set.from(["zap"]), |
+ new Set.from(["baz"]), |
+ new Set.from(["qux"]) |
+ ])); |
+ }); |
+ }); |
} |