Implement topological sorting of a directed graph Python Program

Topological Sorting: Implement topological sorting of a directed graph Python Program?

Topological sorting of a directed graph is a linear ordering of its vertices such that for every directed edge 

$uv$ from vertex $u$ to vertex $v$, $u$ comes before $v$ in the ordering. Topological sorting is only possible for Directed Acyclic Graphs (DAGs).

Approach

There are two common algorithms for topological sorting:

1. Kahn's Algorithm (BFS-based)
2. Depth-First Search (DFS)-based Algorithm

Both methods are efficient and have a time complexity of $O(V + E)$, where $V$ is the number of vertices and $E$ is the number of edges.

Kahn's Algorithm (BFS-based)

Kahn's Algorithm uses an in-degree approach. It processes vertices with zero in-degrees and updates the in-degrees of their neighbors.

Here’s how you can implement it:

from collections import deque, defaultdict

def topological_sort_kahn(graph):

    # Calculate in-degrees of all nodes

    in_degree = {u: 0 for u in graph}

    for u in graph:

        for v in graph[u]:

            in_degree[v] += 1

    # Queue for vertices with no incoming edges

    zero_in_degree_queue = deque([u for u in in_degree if in_degree[u] == 0])

    

    topo_order = []

    while zero_in_degree_queue:

        u = zero_in_degree_queue.popleft()

        topo_order.append(u)

        for v in graph[u]:

            in_degree[v] -= 1

            if in_degree[v] == 0:

                zero_in_degree_queue.append(v)

    # Check if topological sorting is possible (graph might contain a cycle)

    if len(topo_order) == len(graph):

        return topo_order

    else:

        raise ValueError("The graph contains a cycle, so topological sorting is not possible")

# Example usage:

graph_adj_list = {

    5: [2, 0],

    4: [0, 1],

    2: [3],

    3: [1],

    0: [],

    1: []

}

print(topological_sort_kahn(graph_adj_list))  # Output: [4, 5, 2, 3, 0, 1]

DFS-based Algorithm

The DFS-based approach involves performing DFS traversal and recording the finish times of vertices. The topological order is the reverse of the finish times.

Here’s how you can implement it:

def topological_sort_dfs(graph):

    def dfs(v):

        visited.add(v)

        for neighbor in graph[v]:

            if neighbor not in visited:

                dfs(neighbor)

        topo_order.appendleft(v)

    

    visited = set()

    topo_order = deque()

    for vertex in graph:

        if vertex not in visited:

            dfs(vertex)

    return list(topo_order)

# Example usage:

graph_adj_list = {

    5: [2, 0],

    4: [0, 1],

    2: [3],

    3: [1],

    0: [],

    1: []

}

print(topological_sort_dfs(graph_adj_list))  # Output: [5, 4, 2, 3, 1, 0]

Explanation

1. Kahn's Algorithm:

   • Compute In-degrees: Calculate the in-degree (number of incoming edges) for each vertex.
   • Queue Initialization: Initialize a queue with all vertices having zero in-degrees.
   • Process Queue: Process each vertex from the queue, update the in-degrees of its neighbors, and add any neighbor with zero in-degrees to the queue.
   • Check for Cycles: Ensure the result contains all vertices; otherwise, the graph has a cycle.

2. DFS-based Algorithm:

   • DFS Traversal: Perform DFS and record the vertices in a stack or deque. The topological order is obtained by reversing the stack (or deque).
   • Visited Set: Ensure vertices are not revisited.

Complexity

• Time Complexity: $O(V + E)$ for both algorithms.
• Space Complexity: $O(V + E)$ due to storing the graph and the auxiliary data structures (in-degrees, visited set, etc.).

Both algorithms effectively perform topological sorting, and you can choose the one that best fits your needs based on the specific characteristics of your problem or preference for algorithmic approach.