transitiveClosure<T extends Object> function

Map<T, Set<T>> transitiveClosure<T extends Object>(
  1. Iterable<T> nodes,
  2. Iterable<T> edges(
    1. T
    ), {
  3. bool equals(
    1. T,
    2. T
    )?,
  4. int hashCode(
    1. T
    )?,
  5. bool acyclic = false,
})

Returns a transitive closure of a directed graph provided by nodes and edges.

The result is a map from nodes to the sets of nodes that are transitively reachable through edges. No particular ordering is guaranteed.

If equals is provided, it is used to compare nodes in the graph. If equals is omitted, the node's own Object.== is used instead.

Similarly, if hashCode is provided, it is used to produce a hash value for nodes to efficiently calculate the return value. If it is omitted, the key's own Object.hashCode is used.

If you supply one of equals or hashCode, you should generally also to supply the other.

Note: this requires that nodes and each iterable returned by edges contain no duplicate entries.

By default, this can handle either cyclic or acyclic graphs. If acyclic is true, this will run more efficiently but throw a CycleException if the graph is cyclical.

Implementation

Map<T, Set<T>> transitiveClosure<T extends Object>(
  Iterable<T> nodes,
  Iterable<T> Function(T) edges, {
  bool Function(T, T)? equals,
  int Function(T)? hashCode,
  bool acyclic = false,
}) {
  if (!acyclic) {
    return _cyclicTransitiveClosure(
      nodes,
      edges,
      equals: equals,
      hashCode: hashCode,
    );
  }

  final topologicalOrder =
      topologicalSort(nodes, edges, equals: equals, hashCode: hashCode);
  final result = LinkedHashMap<T, Set<T>>(equals: equals, hashCode: hashCode);
  for (final node in topologicalOrder.reversed) {
    final closure = LinkedHashSet<T>(equals: equals, hashCode: hashCode);
    for (var child in edges(node)) {
      closure.add(child);
      closure.addAll(result[child]!);
    }

    result[node] = closure;
  }

  return result;
}