topologicalSort<T> function

List<T> topologicalSort<T>(Map<T, List<T>> graph)

Implementation

List<T> topologicalSort<T>(Map<T, List<T>> graph) {
  final Map<T, int> inDegree = {};
  final Set<T> nodes = {...graph.keys};
  for (final neighbors in graph.values) {
    nodes.addAll(neighbors);
  }

  for (final node in nodes) {
    inDegree[node] = 0;
  }
  graph.forEach((u, neighbors) {
    for (final v in neighbors) {
      inDegree[v] = (inDegree[v] ?? 0) + 1;
    }
  });

  final List<T> queue = [
    for (final n in nodes)
      if ((inDegree[n] ?? 0) == 0) n,
  ];

  final List<T> order = [];

  while (queue.isNotEmpty) {
    final T u = queue.removeAt(0);
    order.add(u);
    for (final v in graph[u] ?? const []) {
      final deg = (inDegree[v] ?? 0) - 1;
      inDegree[v] = deg;
      if (deg == 0) queue.add(v);
    }
  }

  if (order.length != nodes.length) {
    throw StateError(
      'Graph has at least one cycle; topological sort not possible.',
    );
  }

  return order;
}