public static List topologicalSort()

in baremaps-postgres/src/main/java/org/apache/baremaps/postgres/refresh/DependencyGraphBuilder.java [78:111]

• 30 lines of code
• 10 McCabe index (conditional complexity)

  public static List<DatabaseObject> topologicalSort(MutableGraph<DatabaseObject> graph) {
    var inDegree = new HashMap<DatabaseObject, Integer>();
    for (var node : graph.nodes()) {
      inDegree.put(node, 0);
    }

    for (var node : graph.nodes()) {
      for (var successor : graph.successors(node)) {
        inDegree.compute(successor, (k, v) -> v == null ? 1 : v + 1);
      }
    }

    var queue = new LinkedList<DatabaseObject>();
    for (var entry : inDegree.entrySet()) {
      if (entry.getValue() == 0) {
        queue.add(entry.getKey());
      }
    }

    var result = new ArrayList<DatabaseObject>();
    while (!queue.isEmpty()) {
      var current = queue.poll();
      result.add(current);
      for (var succ : graph.successors(current)) {
        var newVal = inDegree.get(succ) - 1;
        inDegree.put(succ, newVal);
        if (newVal == 0) {
          queue.add(succ);
        }
      }
    }

    return result;
  }