transitiveClosure<T> function

Map<T, Set<T>> transitiveClosure<T>(
  1. 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.


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]:
  var result = <T, Set<T>>{};
  graph.forEach((vertex, edges) {
    result[vertex] = 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)) {

  return result;