transitiveClosure<T> function

*<Null safety>*

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

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] = 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;
}