topologicalSort<T> function

List<T> topologicalSort<T>(
  1. Iterable<T> nodes,
  2. Iterable<T> edges(
    1. T
    ), {
  3. bool equals(
    1. T,
    2. T
    )?,
  4. int hashCode(
    1. T
    )?,
  5. Comparator<T>? secondarySort,
})

Returns a topological sort of the nodes of the directed edges of a graph provided by nodes and edges.

Each element of the returned iterable is guaranteed to appear after all nodes that have edges leading to that node. The result is not guaranteed to be unique, nor is it guaranteed to be stable across releases of this package; however, it will be stable for a given input within a given package version.

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.

If you supply secondarySort, the resulting list will be sorted by that comparison function as much as possible without violating the topological ordering. Note that even with a secondary sort, the result is still not guaranteed to be unique or stable across releases of this package.

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

Throws a CycleException<T> if the graph is cyclical.

Implementation

List<T> topologicalSort<T>(
  Iterable<T> nodes,
  Iterable<T> Function(T) edges, {
  bool Function(T, T)? equals,
  int Function(T)? hashCode,
  Comparator<T>? secondarySort,
}) {
  if (secondarySort != null) {
    return _topologicalSortWithSecondary(
      [...nodes],
      edges,
      secondarySort,
      equals,
      hashCode,
    );
  }

  // https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search
  final result = QueueList<T>();
  final permanentMark = HashSet<T>(equals: equals, hashCode: hashCode);
  final temporaryMark = LinkedHashSet<T>(equals: equals, hashCode: hashCode);
  final stack = [...nodes];
  while (stack.isNotEmpty) {
    final node = stack.removeLast();
    if (permanentMark.contains(node)) continue;

    // If we're visiting this node while it's already marked and not through a
    // dependency, that must mean we've traversed all its dependencies and it's
    // safe to add it to the result.
    if (temporaryMark.contains(node)) {
      temporaryMark.remove(node);
      permanentMark.add(node);
      result.addFirst(node);
    } else {
      temporaryMark.add(node);

      // Revisit this node once we've visited all its children.
      stack.add(node);
      for (var child in edges(node)) {
        if (temporaryMark.contains(child)) throw CycleException(temporaryMark);
        stack.add(child);
      }
    }
  }

  return result;
}