Add a stronglyConnectedComponents() function.

lib/src/functions.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 'dart:math' as math;
+import 'dart:collection';
+
 import 'utils.dart';
 
 // TODO(nweiz): When sdk#26488 is fixed, use overloads to ensure that if [key]
 // or [value] isn't passed, `K2`/`V2` defaults to `K1`/`V1`, respectively.
 /// Creates a new map from [map] with new keys and values. 
 ///
 /// The return values of [key] are used as the keys and the return values of
 /// [value] are used as the values for the new map.
 Map/*<K2, V2>*/ mapMap/*<K1, V1, K2, V2>*/(Map/*<K1, V1>*/ map,
     {/*=K2*/ key(/*=K1*/ key, /*=V1*/ value),
@@ skipping 78 matching lines @@
   for (var element in values) {
     var elementOrderBy = orderBy(element);
     if (maxOrderBy == null || compare(elementOrderBy, maxOrderBy) > 0) {
       maxValue = element;
       maxOrderBy = elementOrderBy;
     }
   }
   return maxValue;
 }
 
 /// Returns the [transitive closure][] of [graph].

[Lasse Reichstein Nielsen, 2016/06/23 14:44:02]

Consider changing "Returns" to "Computes".
The line is fairly redundant with a function declared as "...
transitiveClosure(... graph)".

[nweiz, 2016/06/23 20:52:58]

I think the fact that "transitive closure" is a link is a pretty substantial
difference.

 ///
 /// [transitive closure]: https://en.wikipedia.org/wiki/Transitive_closure
 ///
-/// 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.
+/// Interprets [graph] as a directed graph with a vertex for each key and edges
+/// from each key to the values that the key maps to.

[Lasse Reichstein Nielsen, 2016/06/23 14:44:02]

Maybe even:
   with a vertex for each key and edges the vertex to the vertices it maps to.

Or not. I can't decide if it's better, but I'm trying to not mix abstraction
levels.

[nweiz, 2016/06/23 20:52:57]

I think that's less clear; it's still kind of mixing levels because it's
technically the keys that map to values, not the vertices.

 ///
 /// 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.
+/// that vertex has no outgoing edges. This isn't checked, but if it's not
+/// satisfied, the function may crash or provide unexpected output. For example,
+/// `{"a": ["b"]}` is not valid, but `{"a": ["b"], "b": []}` is.
 Map<dynamic/*=T*/, Set/*<T>*/> transitiveClosure/*<T>*/(
     Map<dynamic/*=T*/, Iterable/*<T>*/> graph) {
   // This uses [Warshall's algorithm][], modified not to add a vertex from each
   // node to itself.
   //
   // [Warshall's algorithm]: https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#Applications_and_generalizations.
   var result = /*<T, Set>*/{};
   graph.forEach((vertex, edges) {
     result[vertex] = new Set/*<T>*/.from(edges);
   });
 
   // Lists are faster to iterate than maps, so we create a list since we're
   // iterating repeatedly.
   var keys = graph.keys.toList();
   for (var vertex1 in keys) {
     for (var vertex2 in keys) {
       for (var vertex3 in keys) {
         if (result[vertex2].contains(vertex1) &&
             result[vertex1].contains(vertex3)) {
           result[vertex2].add(vertex3);
         }
       }
     }
   }
 
   return result;
 }
+
+/// Returns the [strongly connected components][] of [graph], in topological

[Lasse Reichstein Nielsen, 2016/06/23 14:44:02]

Also consider Returns -> Computes.

(Because I just don't like "returns" in the first line of function
descriptions).

[nweiz, 2016/06/23 20:52:57]

It's not explicitly mandated, but the documentation guide includes several
function descriptions starting with "Returns":
https://www.dartlang.org/effective-dart/documentation/

+/// order.
+///
+/// [strongly connected components]: https://en.wikipedia.org/wiki/Strongly_connected_component
+///
+/// Interprets [graph] as a directed graph with a vertex for each key and edges
+/// from each key to the values that the key maps to.

[Lasse Reichstein Nielsen, 2016/06/23 14:44:03]

Whatever you do above, do the same here.

[nweiz, 2016/06/23 20:52:57]

Acknowledged.

+///

[Lasse Reichstein Nielsen, 2016/06/23 14:44:02]

Maybe add a comment saying that the graph modulo its strongly connected
components is guaranteed to be a directed acyclic graph, so topological ordering
is possible. 
(But use words that users understand :)

[nweiz, 2016/06/23 20:52:57]

I think that's more complex than most users would understand. Those who care can
pretty easily prove it to themselves.

+/// Assumes that every vertex in the graph has a key to represent it, even if
+/// that vertex has no outgoing edges. This isn't checked, but if it's not
+/// satisfied, the function may crash or provide unexpected output. For example,
+/// `{"a": ["b"]}` is not valid, but `{"a": ["b"], "b": []}` is.
+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 result = /*<Set<T>>*/[];
+
+  // The order of these doesn't matter, so we use un-linked implementations to
+  // avoid unnecessary overhead.
+  var indices = new HashMap/*<T, int>*/();
+  var lowLinks = new HashMap/*<T, int>*/();
+  var onStack = new HashSet/*<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]);
+      }
+    }
+
+    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();
+}