transitiveClosure<T> function

Map<T, Set<T>> transitiveClosure <T>(Map<T, Iterable<T>> graph)

Returns the transitive closure of graph.

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 

Map<T, Set<T>> transitiveClosure<T>(Map<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<T>>{};
  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;
}