Add a stronglyConnectedComponents() function.

test/functions_test.dart

 // Copyright (c) 2016, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 import "package:test/test.dart";
 
 import "package:collection/collection.dart";
 
 void main() {
   group("mapMap()", () {
@@ skipping 163 matching lines @@
         "foo": ["bar"],
         "bar": ["baz"],
         "baz": ["foo"]
       }), equals({
         "foo": ["bar", "baz", "foo"],
         "bar": ["baz", "foo", "bar"],
         "baz": ["foo", "bar", "baz"]
       }));
     });
   });
+
+  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":["a"]}
Maybe even two-element graphs: 
{"a":["b"],"b":["a"]} and {"a":[""],"b":["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 ordering here, there are more
possible topological orderings of the connected components of that graph. 

I don't think it's viable to specify which topological ordering is actually
picked. It depends on the iteration order of the keys and the order of the edges
for each key, both properties that are artificial wrt. the abstract graph
represented by the map. The final ordering is pretty much an accident of
implementation.

So, maybe just test that the components are correct, independent of order, and
that the result is topologically ordered, by testing that for each edge, the
component of the start vertex occurs earlier than the component of the end
vertex in the result.

That avoids testing for a specific ordering.

Alternatively, don't promise topological ordering at all. That allows you to
change the algorithm to something completely different in the future without
breaking tests. (Unless you actually need the topological ordering).

[nweiz, 2016/06/20 21:19:38]

It's a noble goal to try to preserve the invariant that all tests will pass for
all valid implementations of the code in question, but there's a point where
that becomes impractical. In this case, it would be a lot of effort to
automatically verify that the sets are in *a* topological order. On the other
hand, it's easy to verify by hand that a given order is topological, so if the
implementation changes it'll be easy to update this test and manually ensure
that the result is still correct.
It is important for my use case that this be topological.

+      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"])
+      ]));
+    });
+  });
 }