Topological Sort (Lexical ordering) implemented in python

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.

Example of lexical topological sorting Topological_Sorted_Lexical_Ordered_Graph


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).


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) implemented in Python 3.7

from dataclasses import dataclass, field
from collections import deque

@dataclass
class Graph :

    nodes : int
    adjlist : dict = field(default_factory = dict)                 # Stores the graph in an adjacency list
    incoming_edge_count : list = field(default_factory = list)     # For a node, it stores the number of incoming edges. 
    topo_order : list = field(default_factory = list)              # Stores the nodes in lexical topologically sorted order.
    zero_incoming_edge_node : list = field(default_factory = list) # Stores the nodes that have zero incoming edges.

    # Create an adjacency list for storing the edges
    def AddEdge(self, src, dst) :

        if src not in self.adjlist :
           self.adjlist[src] = []
        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 of Topological sorting in a lexical order implemented in Python 3.7

Topological Sorting In A Lexical Order : [0, 1, 3, 5, 6, 2, 4]
Copyright (c) 2020, Algotree.org.
All rights reserved.