Algotree > Algorithms > Tree & Graph Traversal > Python : Topological Sort (Lexical ordering)

Python : Topological Sort (Lexical ordering)

Lexical topological sorting of a Directed Acyclic Graph (DAG) a.k.a Kahn’s Algorithm

Criteria for lexical topological sorting : The smallest vertex with no incoming edges is accessed first followed by the vertices on the outgoing paths. If more than one vertex has zero incoming edges, the smallest vertex is chosen first to maintain the topological lexical order.

The idea of the algorithm is mentioned below
Preprocess edges

While storing an edge from the source node to the destination node, keep track of the incoming edges (incoming_edge_count) for the destination node.
i.e The incoming edge count for the destination node increases with every incoming edge i.e incoming_edge_count [destination] ++

Algorithm : Lexical Topological Sort

1.    Iterate through all the nodes.
      i.e If incoming_edge_count of node N equals 0, insert node N into the list L ( zero_incoming_edge_node )
      Note : List L stores the node with zero incoming edges.
2.    While the list L is not empty.
3.        Sort the list L.
4.        Pop the first node N from the list.
5.        Iterate through all the adjacent nodes of node N.
6.            Reduce the incoming edge count of the adjacent node by 1. i.e incoming_edge_count [adj_node] –;
7.            If the incoming edge count of the adjacent node equals 0, insert it into the list L.
8.        Insert node N into the topo list. (This list will store the lexically ordered nodes in topological order).

Example Topologically_Sorted_Lexical_Order_Python

Data structure used for storing graph : Adjacency List

Time complexity of lexical topological sorting : O(V+E) for an adjacency list implementation of a graph. ‘V’ is the number of vertices and ‘E’ is the number of edges in a graph.

Python : Topological Sort (Lexical ordering)

from collections import defaultdict

class Graph :

    def __init__(self, nodes : int) :
        self.nodes = nodes
        # adjlit is implemented as a dictionary. The default dictionary would create an empty 
        # list as a default (value) for the nonexistent keys.
        self.adjlist = defaultdict(list)  # Stores the graph in an adjacency list
        self.incoming_edge_count = []     # For a node, it stores the number of incoming edges. 
        self.topo_order = []              # Stores the nodes in lexical topologically sorted order.
        self.zero_incoming_edge_node = [] # Stores the nodes that have zero incoming edges.

    # Create an adjacency list for storing the edges
    def AddEdge (self, src : int, dst : int) :
        self.adjlist[src].append(dst)
        self.incoming_edge_count[dst] += 1

    def TopologicalSort (self) :

        for node in range(self.nodes) :
            if self.incoming_edge_count[node] == 0 :
               self.zero_incoming_edge_node.append(node)

        while self.zero_incoming_edge_node :
            self.zero_incoming_edge_node.sort()
            src = self.zero_incoming_edge_node.pop(0)

            # Iterate through the adjacency list
            if src in self.adjlist :
                for node in self.adjlist[src] :
                    self.incoming_edge_count[node] -= 1
                    if self.incoming_edge_count[node] == 0 :
                        self.zero_incoming_edge_node.append(node)

            self.topo_order.append(src)

        print("Topological Sorting In A Lexical Order : " + str(self.topo_order))

def main() :

    node_cnt = 7
    g = Graph(node_cnt)
    g.incoming_edge_count = [0] * node_cnt # For a node, it stores the number of incoming edges.

    g.AddEdge(0,2)
    g.AddEdge(0,5)
    g.AddEdge(1,3)
    g.AddEdge(1,6)
    g.AddEdge(2,4)
    g.AddEdge(3,5)
    g.AddEdge(5,2)
    g.AddEdge(5,4)
    g.AddEdge(6,2)

    g.TopologicalSort()

if __name__ == "__main__" :
    main()

Output

Topological Sorting In A Lexical Order : [0, 1, 3, 5, 6, 2, 4]