Topological Sort in Data Structure: Methods and Applications

Here are the examples of topological sort algorithms:

Example 1:

Step 1: Start DFS from node 0 (no incoming edges). Push node 0 to the stack and move to the next node with fewer adjacent nodes (node 1).

Step 2: Node 1 has no adjacent nodes. Push node 1 to the stack and proceed.

Step 3: Choose node 2 (next in line) and perform DFS on its adjacent nodes. Push node 3, then node 2 into the stack.

Step 4: DFS for node 4 is called. Since its adjacent nodes (0, 1) are already in the stack, just push node 4.

Step 5: For node 5, since its adjacent nodes are already in the stack, push node 5.

Step 6: Finally, pop all elements from the stack and print them in reverse order for the topological sort.

Program Implementation

Here is the CPP program for topological sorting using DFS:

C++ Code

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

class Graph {
    int V;  // Number of vertices
    vector<int>* adj;  // Adjacency list representation of graph

    void dfs(int node, vector<bool>& visited, stack<int>& topoStack) {
        visited[node] = true;

        // Visit all the adjacent nodes
        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                dfs(neighbor, visited, topoStack);
            }
        }

        // Push the node to stack after visiting all its adjacent nodes
        topoStack.push(node);
    }

public:
    // Constructor
    Graph(int vertices) {
        V = vertices;
        adj = new vector<int>[V];
    }

    // Add edge to the graph
    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }

    // Function to perform Topological Sort
    void topologicalSort() {
        stack<int> topoStack;  // Stack to store the topological order
        vector<bool> visited(V, false);  // Visited array

        // Perform DFS for each unvisited node
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                dfs(i, visited, topoStack);
            }
        }

        // Print the topological order
        cout << "Topological Sort: ";
        while (!topoStack.empty()) {
            cout << topoStack.top() << " ";
            topoStack.pop();
        }
        cout << endl;
    }
};

int main() {
    // Create a graph with 6 vertices
    Graph g(6);

    // Add edges to the graph
    g.addEdge(5, 2);
    g.addEdge(5, 0);
    g.addEdge(4, 0);
    g.addEdge(4, 1);
    g.addEdge(2, 3);
    g.addEdge(3, 1);

    // Perform topological sort
    g.topologicalSort();

    return 0;
}

Explanation

The above program implements topological sorting using DFS in a directed graph. It initialises a graph with vertices and an adjacency list. It makes use of a DFS function to explore all unvisited nodes and push them onto a stack after processing their neighbours. The stack represents a valid topological order wherein each node appears before any dependent node.

Output

Topological Sort: 5 4 2 3 1 0

Complexity Analysis

• Time Complexity: O(V + E) 
• Space Complexity: O(V + E)

Example 2:

Let’s walk through how topological sorting works with a concrete example to better understand the process.

Step 1. Initial Setup

We have a directed graph with nodes and directed edges between them. We maintain an array in-degree[] to keep track of each node's incoming edges, initially filling in the in-degree array and obtaining a list of nodes with zero in-degree.

Step 2. Process Node 0

Remove all outgoing edges from node 0 (to nodes 1, 4, 6). Update the in-degrees of nodes 1, 4, 6. Since the in-degrees of these nodes are now zero, add them to the queue.

Step 3. Process Node 6

Remove all outgoing edges from nodes 6 (to 2, 3). Update the in-degrees of nodes 2 and 3. Since the in-degrees of these nodes are now zero, add them to the queue.

Step 4. Process Node 1 

Remove the outgoing edge from node 1 (to node 2). Update the in-degree of node 2. Since it is now zero, add it to the queue.

Step 5: Process Node 4

Remove the outgoing edge from node 4 (to node 5). Update in-degree of node 5. Add it to the queue because its in-degree is now 0.

Step 6: Process Node 3

Remove the outgoing edge from node 3 (to node 8). Update the in-degree of node 8. It will not be added to the queue since the in-degree is still non-zero.

Step 7. Process Node 2

Remove outgoing edges from node 2 (to nodes 7 and 5). Update the in-degrees of nodes 7 and 5. Since the in-degree of node 5 is now zero, add it to the queue.

Step 8. Process Node 5

Remove the outgoing edge from node 5 (to node 9). Update the in-degree of node 9. It will not be added to the queue since the in-degree is still non-zero.

Step 9. Process Node 7

Remove the outgoing edge from node 7 (to node 8). Update the in-degree of node 8. Since its in-degree node is now zero, add it to the queue.

Step 10: Process Node 8

We remove the outgoing edge from node 8 to node 9. The in-degree of node 9 is updated, it now becomes zero hence, we add it to the queue.

Step 11: Process Node 9

Node 9 has no outgoing edges and, therefore, ends the process.

Program Implementation

Here is the CPP program for topological sorting using BFS:

C++ Code

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Graph {
public:
    int vertexCount;  // Total number of vertices in the graph
    vector<vector<int>> adjacencyList;  // Representation of the graph using an adjacency list

    Graph(int vertexCount) {
        this->vertexCount = vertexCount;
        adjacencyList.resize(vertexCount);
    }

    void addEdge(int source, int destination) {
        adjacencyList[source].push_back(destination);
    }

    vector<int> performTopologicalSort() {
        vector<int> inDegree(vertexCount, 0);  // Array to maintain incoming edge counts for each vertex
        vector<int> sortedOrder;  // Vector to store the final topological order

        // Determine in-degree for each vertex
        for (int u = 0; u < vertexCount; ++u) {
            for (const int& v : adjacencyList[u]) {
                inDegree[v]++;
            }
        }

        // Queue to hold vertices with no incoming edges
        queue<int> q;
        for (int i = 0; i < vertexCount; ++i) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }

        // Processing the graph's nodes 
        while (!q.empty()) {
            int currentVertex = q.front();
            q.pop();
            sortedOrder.push_back(currentVertex);

            // Reduce the in-degree of neighboring vertices
            for (const int& neighbor : adjacencyList[currentVertex]) {
                if (--inDegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }

        // Verify whether a cycle exists in the graph
        if (sortedOrder.size() != vertexCount) {
            cout << "The graph contains a cycle!" << endl;
            return {};
       }

       return sortedOrder;
   }
};

int main() {
    Graph g(10);  // Initialize a graph with ten vertices

   // Establish edges following the defined topological order 
   g.addEdge(0, 6);
   g.addEdge(6, 1);
   g.addEdge(1, 4);
   g.addEdge(4, 3);
   g.addEdge(3, 2);
   g.addEdge(2, 5);
   g.addEdge(5, 7);
   g.addEdge(7, 8);
   g.addEdge(8,9 );

   // Execute topological sort and display results 
   vector<int> topoSortResult = g.performTopologicalSort();

     if (!topoSortResult.empty()) { 
         cout << "Topological Order: "; 
           for (const int& index : topoSortResult) { 

              cout << index << " "; } 

      cout << endl; 
     } 

return 0;
  
}

Explanation

In this C++ program, the algorithm Kahn has been applied for topological sorting. It tracks the in-degree of each vertex from those that begin at a zero in-degree; the processing of those, in turn, revisits their neighbours and updates their in-degrees. Vertices are inserted into the queue if they are of degree zero. If no cycles cause the program to stop processing at least one vertex, the order of processing gives the graph the topological order.

Output

[0, 6, 1, 4, 3, 2, 5, 7, 8, 9]

Here are the key differences between topological sorting and depth-first traversal:

Here are the advantages of topological sorting in data structures:

• Processing is done in an order where all dependencies are satisfied.
• It is an algorithm that helps detect cycles in a graph; if it fails to sort, then a cycle exists.
• These are also important in various applications like task scheduling, dependency resolution, and building systems.
• Space complexity is O(V + E), which is manageable in most graphs.

Here are the disadvantages of topological sort in data structures:

• Topological sort is not possible if the graph is not a DAG.
• Cyclic graphs don’t have valid topological orderings.
• The cycle creates an impossible set of constraints.
• Topological ordering is not applicable to cyclic graphs.

Here are the applications of topological sort in data structures:

• Task Scheduling: Topological sorting is used to schedule tasks that have dependencies. Each task must be completed before others depending on it. Examples: project planning and job scheduling.
• Build Systems: In software development, topological sorting is used in build systems (e.g., Makefiles, Gradle, Maven) to determine the order in which files or modules must be compiled.
• Package Dependency Management: Used in package managers (e.g., npm, pip) to resolve dependencies between software packages. Topological sorting ensures that packages are installed in the correct order.
• Course Prerequisite Scheduling: In an educational system, topological sorting is helpful to determine how courses have to be scheduled, considering the necessary prerequisites for each course that must be duly observed.
• Compilation Order in Compilers: Topological sorting has a very important place in compiler design because it ensures that the various interdependent code modules will be arranged so that they can be compiled in the required manner.
• Cyclic Dependency Detection: Topological sorting may help in cycle detection within graphs, where this notion asserts the impossibility of performing certain tasks or dependencies.
• Route Planning in Networks: Topological sorting makes it relevant in optimising network routing or sequencing tasks in the network that have dependent operations.
• Version Control Systems: Examples of version control systems, such as Git, use the topology of sorting to process commits and branches in a manner that will respect the history of the commit.
• Data Workflow Management: In data pipelines (ETL), certain tasks have to be executed in a specific order. Topological sorting is applied to control the application order according to the dependencies of the tasks.

In conclusion, topological sorting is an important technique for arranging tasks in cases involving dependencies expressed through directed acyclic graphs (DAGs). This helps accomplish explicit tasks before the next one, according to the precedence constraints. Their applications range from task scheduling to compilation and dependency resolution. The sorting is only possible on acyclic graphs since the presence of a cycle would make any valid ordering impossible. The efficacy and correctness of the topological sorting algorithm make it crucial in solving various problems in computer science and engineering in the real world.

1. Why topological sorting?

Because it orders the vertices according to the graph's topology, hence the name. Topological ordering, in this sense, refers to the arrangement or structure of the graph, subject to dependencies among tasks or nodes contained in a directed acyclic graph (DAG).

2. Where are the two methods for topological sorting?

The two methods are Kahn’s Algorithm (BFS-based) and DFS-based Algorithm. Kahn’s algorithm uses in-degrees and a queue to process nodes. The DFS-based algorithm uses depth-first traversal, adding nodes to a stack during backtracking to generate the topological order.

3. What is topological sort with Dijkstra?

Dijkstra's algorithm is used mainly for the shortest path on a weighted graph. It is not strictly topological sorting but could be adapted to turn into topological sorting in edges of equal weights, in which case it models a topological sort of a node based on the dependencies in certain instances.

4. What is a cyclic graph?

A cyclic graph contains at least one cycle. A cycle is a path that begins and ends at the same vertex, with all other vertices in the path being distinct. In a directed cyclic graph, edges have direction and can be travelled from vertex to vertex until returning to the originating vertex. Topological sorting is impossible through the cyclic graphs since it requires a DAG or directed acyclic graph.