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

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 and insert the node with zero incoming edges into a set (min-heap) S.
      i.e If incoming_edge_count of node N equals 0, insert node N into the set S
      Note : Set S stores the lexically smallest node with zero incoming edges (incoming_edge_count) at the top.
2.    While the set S is not empty.
3.        Get the topmost node N from the set.
4.        Iterate through all the adjacent nodes of node N.
5.            Reduce the incoming edge count of the adjacent node by 1. i.e incoming_edge_count [adj_node] –;
6.            If the incoming edge count of the adjacent node equals 0, insert it into the set S.
7.        Insert node N into a list. (This list will store the lexically ordered nodes in topological order).
8.       Remove the topmost node N from the set / min-heap.

Example Topologically_Sorted_Lexical_Order_C++

Data structure used for storing graph : Adjacency List
Data structure used for lexical order topological sorting : Set

Time complexity : 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.

C++ Topological Sort (Lexical ordering)

#include<iostream>
#include<list>
#include<vector>
#include<set>

using namespace std;

class Graph{

    private:
        int nodes;              // number of nodes in the graph
        list<int> *adj_list;    // Stores the graph
        vector<int> incoming_edge_count;  // Stores the incoming edges for a node
        list<int> topo_list;    // Stores the lexical order of topological traversal
        set<int> order_set;     // Stores the nodes in order of least incoming edges

    public:
        Graph(){
        }

        Graph (int nodes) {
            this->nodes = nodes;
            adj_list  = new list<int> [nodes];
            incoming_edge_count.resize(nodes, 0);
        }

        ~Graph(){ 
            delete [] adj_list;
        }

        void AddEdge (int src, int dst) {
            adj_list[src].push_back(dst);
            incoming_edge_count[dst]++; // For every incoming edge, increase the count
        }

        void TopologicalSort() {

            for (int i=0; i<nodes; i++) {
                if (incoming_edge_count[i] == 0) { 
                    order_set.insert(i);
                }   
            }

            set<int> :: iterator sitr;

            // Pickup the node with least incoming edges in lexical order
            while (!order_set.empty()) {

               sitr = order_set.begin();
               for (auto& node : adj_list[*sitr]) {
                   incoming_edge_count[node]--;
                   if (incoming_edge_count[node] == 0) {
                      order_set.insert(node);
                   }
               }
               topo_list.push_back(*sitr);
               order_set.erase(sitr);
            }

            for (auto & node: topo_list) {
                cout << node << " ";
            }
        }
};

int main()
{
    Graph g(5);
    // Store the edges of the directed graph in adjacency list.
    g.AddEdge(1,0);
    g.AddEdge(1,2);
    g.AddEdge(1,3);
    g.AddEdge(3,0);
    g.AddEdge(3,2);
    g.AddEdge(4,0);
    g.AddEdge(4,3);

    cout << "Topological Sorting, Lexical Order: "; 
    g.TopologicalSort();
    return 0;
}

Output

Topological Sorting, Lexical Order: 1 4 3 0 2