stronglyConnectedComponents<T> function

List<Set<T>> stronglyConnectedComponents <T>(Map<T, Iterable<T>> graph)

Returns the strongly connected components of graph, in topological order.

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.

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.

Implementation 

List<Set<T>> stronglyConnectedComponents<T>(Map<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>();
      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();
}