Add a stronglyConnectedComponents() function.

lib/src/functions.dart

Index: lib/src/functions.dart
diff --git a/lib/src/functions.dart b/lib/src/functions.dart
index 9c973b8aede3a69286ff6ea9ef68f7bc9d360867..a418628c8fcb054d9c9bbf3566027e43b0b1eecb 100644
--- a/lib/src/functions.dart
+++ b/lib/src/functions.dart
@@ -2,6 +2,8 @@
 // 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 'dart:math' as math;
+
 import 'utils.dart';
 
 // TODO(nweiz): When sdk#26488 is fixed, use overloads to ensure that if [key]
@@ -137,3 +139,64 @@ Map<dynamic/*=T*/, Set/*<T>*/> transitiveClosure/*<T>*/(
 
   return result;
 }
+
+/// Returns the [strongly connected components][] of [graph], in topological
+/// order.
+///
+/// [strongly connected components]: https://en.wikipedia.org/wiki/Strongly_connected_component
+///
+/// This interprets [graph] as a directed graph with a vertex for each key and
+/// edges from each key to the values associated with that key.

[Lasse Reichstein Nielsen, 2016/06/16 08:21:33]

associated with that key -> that the key maps to.
(maybe).

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

Done.

+///
+/// Assumes that every vertex in the graph has a key to represent it, even if
+/// that vertex has no outgoing edges. For example, `{"a": ["b"]}` is not valid,
+/// but `{"a": ["b"], "b": []}` is.

[Lasse Reichstein Nielsen, 2016/06/16 08:21:33]

Emphasize that this isn't checked, but if it fails to be satisfied, the function
may fail. 
It means that failing to be valid might show up as a null access error instead
of a nice argument error.

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

Done.

+List<Set/*<T>*/> stronglyConnectedComponents/*<T>*/(
+    Map<dynamic/*=T*/, Iterable/*<T>*/> graph) {
+  // This uses [Tarjan's algorithm][].
+  //
+  // [Tarjan's algorithm]: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
+  var index = 0;
+  var stack = /*<T>*/[];
+  var indices = /*<T, int>*/{};
+  var lowLinks = /*<T, int>*/{};
+  var onStack = new Set/*<T>*/();

[Lasse Reichstein Nielsen, 2016/06/16 08:21:33]

You are using linked-hash-maps and -sets. The order isn't important, so using
unlinked hash-map/-set will be more efficient.

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

Done.

+  var result = /*<Set<T>>*/[];
+
+  strongConnect(/*=T*/ vertex) {
+    indices[vertex] = index;
+    lowLinks[vertex] = index;
+    index++;
+
+    stack.add(vertex);
+    onStack.add(vertex);
+
+    for (var successor in graph[vertex]) {
+      if (!indices.containsKey(successor)) {
+        strongConnect(successor);
+        lowLinks[vertex] = math.min(lowLinks[vertex], lowLinks[successor]);
+      } else if (onStack.contains(successor)) {
+        lowLinks[vertex] = math.min(lowLinks[vertex], lowLinks[successor]);

[Lasse Reichstein Nielsen, 2016/06/16 08:21:33]

It annoys me to have two identical lines in separate branches, but I can't find
a better way to write it. :(

+      }
+    }
+
+    if (lowLinks[vertex] == indices[vertex]) {
+      var component = new Set/*<T>*/();
+      var/*=T*/ neighbor;
+      do {
+        neighbor = stack.removeLast();
+        onStack.remove(neighbor);
+        component.add(neighbor);
+      } while (neighbor != vertex);
+      result.add(component);
+    }
+  }
+
+  for (var vertex in graph.keys) {
+    if (!indices.containsKey(vertex)) strongConnect(vertex);
+  }
+
+  // Tarjan's algorithm produces a reverse-topological sort, so we reverse it to
+  // get a normal topological sort.
+  return result.reversed.toList();
+}