Index: test/functions_test.dart |
diff --git a/test/functions_test.dart b/test/functions_test.dart |
index 4d928bf29de56c60a003753378c179ef964435ef..fa88aaff444d91272beb9a6c847ccc7c5f8d6e1d 100644 |
--- a/test/functions_test.dart |
+++ b/test/functions_test.dart |
@@ -181,4 +181,73 @@ void main() { |
})); |
}); |
}); |
+ |
+ group("stronglyConnectedComponents()", () { |
+ test("returns an empty list for an empty graph", () { |
+ expect(stronglyConnectedComponents({}), isEmpty); |
+ }); |
Lasse Reichstein Nielsen
2016/06/16 08:21:33
Also test with singleton graphs: {"a":[]} and {"a
nweiz
2016/06/20 21:19:38
Done.
|
+ |
+ test("returns individual vertices for a tree", () { |
+ 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", () { |
Lasse Reichstein Nielsen
2016/06/16 08:21:33
You are checking for a specific topological orderi
nweiz
2016/06/20 21:19:38
It's a noble goal to try to preserve the invariant
|
+ 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"]) |
+ ])); |
+ }); |
+ }); |
} |