List topologicalSort()

in lib/src/topological_sort.dart [31:56]

• 23 lines of code
• 5 McCabe index (conditional complexity)

List<T> topologicalSort<T>(Iterable<T> nodes, Iterable<T> Function(T) edges,
    {bool Function(T, T)? equals, int Function(T)? hashCode}) {
  // https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search
  var result = QueueList<T>();
  var permanentMark = HashSet<T>(equals: equals, hashCode: hashCode);
  var temporaryMark = LinkedHashSet<T>(equals: equals, hashCode: hashCode);
  void visit(T node) {
    if (permanentMark.contains(node)) return;
    if (temporaryMark.contains(node)) {
      throw CycleException(temporaryMark);
    }

    temporaryMark.add(node);
    for (var child in edges(node)) {
      visit(child);
    }
    temporaryMark.remove(node);
    permanentMark.add(node);
    result.addFirst(node);
  }

  for (var node in nodes) {
    visit(node);
  }
  return result;
}