7.3. Topological Sorting

This section discusses two algorithms for topological sorting.

The task of topological sorting is to sort vertices in a linear order such that for each vertex, all target vertices associated with its incoming edges must appear prior to it.

By Incoming Scores

The followings demonstrate how to perform a topological sort by incoming scores, where the incoming score of a vertex is define as the sum of all source vertices:

By Depth-First

The followings demonstrate how to perform a topological sort by depth-first traversing:

Implementation

Let us define the topological_sort() method under the Graph class that performs topological sort by either incoming scores or depth-first search:

public List<Integer> topological_sort(boolean depth_first) {
    Deque<Integer> global = getVerticesWithNoIncomingEdges();
    List<Deque<Edge>> outgoingEdgesAll = getOutgoingEdges();
    List<Integer> order = new ArrayList<>();

    while (!global.isEmpty()) {
        Deque<Integer> local = new ArrayDeque<>();
        int vertex = global.poll();
        order.add(vertex);
        Deque<Edge> outgoingEdges = outgoingEdgesAll.get(vertex);
        
        while (!outgoingEdges.isEmpty()) {
            Edge edge = outgoingEdges.poll();

            //Remove edge in all incomingEdges of the target vertex
            List<Edge> incomingEdges = getIncomingEdges(edge.getTarget());
            incomingEdges.remove(edge);

            //If the vertex has no incoming edges, add it to the local queue awaited to be added to the global deque
            if (incomingEdges.isEmpty())
                local.add(edge.getTarget());
        }

        //Transfer all vertices in local to global
        while (!local.isEmpty())
            if (depth_first) global.addFirst(local.removeLast());
            else global.addLast(local.removeFirst());
    }

    if (!hasNoEdge()) throw new IllegalArgumentException("Cyclic graph.");
    return order;
}

• L2: starts with vertices with no incoming edges.

• L3: retrieves outgoing edges of each source vertex.

• L4: consists of the list of vertices in topological order.

• L6: iterates until no more vertex to visit:

  • L8-9: adds a source vertex to order.

  • L12: iterates through all the outgoing edges of the source vertex:

    • L17: removes the outgoing edge from the graph.

    • L20-21: adds the target vertex if it has no incoming edge left to local.

  • L25-27: adds all vertices in local to global.

What is the worst-case complexity of the topological_sort() method?