C Programming Data Structures Topological Sorting Complete Guide

C Programming Data Structures: Topological Sorting

• Task Scheduling: Ensures that all tasks are performed in the correct sequence.
• Project Management: Helps in identifying dependencies within projects.
• Compiler Optimization: Orders compiler instructions for optimal execution.
• Event Dependency Resolution: Arranges events based on who needs to happen first.

Key Concepts in Topological Sorting:

1. Graph Representation:

   • Adjacency List: Efficient for storing sparse graphs.
   • Adjacency Matrix: Suitable for dense graphs but consumes more memory.

2. Directed Acyclic Graph (DAG):

   • A graph with directed edges and no cycles.
   • Topological sort is feasible only in DAGs.

3. DFS-Based Approach:

   • Utilizes Depth-First Search (DFS) to traverse the graph.
   • Each node's neighbors are visited recursively.
   • Once a vertex has been visited, it is pushed onto a stack.

4. Kahn’s Algorithm:

   • Uses Breadth First Search (BFS).
   • Builds a list of nodes with zero in-degree.
   • Removes nodes with zero in-degree one by one; updates in-degrees of their neighbors.

5. In-Degree of Nodes:

   • In-degree: Number of incoming edges to a node.
   • Nodes with zero in-degree must come at the beginning of the topological sort.

6. Cycle Detection:

   • Since topological sorting is possible only in DAGs, cycle detection is necessary.
   • Algorithms like DFS or Kahn’s can be adapted for this purpose.

Steps in DFS-Based Topological Sort:

1. Initialization:

   • Create a boolean array visited[] to keep track of visited nodes.
   • Initialize an empty stack S.

2. Recursive DFS Function:

   • Mark the current node as visited.
   • Recursively visit all of its adjacent vertices (neighbors) by checking each unvisited neighbor.
   • After visiting all neighbors, push the current node onto the stack S.

3. Topological Sort Generation:

   • Call the recursive DFS function for all unvisited nodes.
   • Extract elements from the stack S to form the topologically sorted list; nodes at the bottom of the stack represent nodes with higher priority.

Steps in Kahn’s Algorithm:

1. Compute In-Degree:

   • Traverse the graph and compute in-degrees for all vertices.

2. Queue Initialization:

   • Create a queue Q and enqueue all vertices with zero in-degree.

3. Sort Process:

   • While Q is not empty, do the following:
     • Dequeue a node from Q.
     • Decrease in-degree by one for all its outgoing edges.
     • If in-degree becomes zero, enqueue the node to Q.
     • Add the dequeued node to the topological order list.

4. Cycle Detection:

   • If Q runs out of nodes and the number of visited nodes doesn't match the total number of vertices, then there is a cycle.

C Programming Implementation: Below we will demonstrate both DFS-based and Kahn's algorithm implementation in C for better understanding.

DFS-Based Topological Sort Implementation:

#include <stdio.h>
#include <stdlib.h>

// Node structure
typedef struct Node {
    int dest;
    struct Node* next;
} Node;

// Graph structure
typedef struct Graph {
    int V;
    Node** adjList;
} Graph;

// Adds an edge from src to dest in the graph
Node* createNode(int dest) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = graph->adjList[src];
    graph->adjList[src] = newNode;
}

Graph* createGraph(int vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = vertices;

    graph->adjList = malloc(vertices * sizeof(struct Node*));

    int i;
    for (i = 0; i < vertices; ++i)
        graph->adjList[i] = NULL;

    return graph;
}

// Recursive DFS function
void DFSVisit(Graph* graph, int vertex, int visited[], struct Stack* S) {
    visited[vertex] = 1;
    Node* adjListPtr = graph->adjList[vertex];

    while(adjListPtr != NULL){
        int connectedVertex = adjListPtr->dest;
        if(visited[connectedVertex] == 0) {
            DFSVisit(graph, connectedVertex, visited, S);
        }
        adjListPtr = adjListPtr->next;
    }

    // Pushes the vertex in the stack
    push(S, vertex);
}

void topologicalSortDFS(Graph* graph) {
    if(graph == NULL)
        return;
    
    int vertices = graph->V;
    struct Stack* S = createStack(vertices);

    int* visited = malloc(vertices * sizeof(int));
    int j;
    for (j = 0; j < vertices; j++)
        visited[j] = 0;

    // Visiting a vertex means that all children nodes were pushed into the stack
    for (j = 0; j < vertices; j++) {
        if(visited[j] == 0) {
            DFSVisit(graph, j, visited, S);
        }
    }

    // Print contents of the stack
    while(!isEmpty(S)) {
        printf("%d ", pop(S) );
    }
    freeStack(S);
    free(visited);
}

// Support functions for the stack operations used in DFS-based topological sort
struct Stack* createStack(int capacity) {
   ...
}

int isEmpty(struct Stack* s) {
   ...
}

int isFull(struct Stack* s) {
   ...
}

void push(struct Stack* s, int item) {
   ...
}

int pop(struct Stack* s) {
   ...
}

void freeStack(struct Stack* s) {
   ...
}

// Main function 
int main() {
    Graph* graph = createGraph(5);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 2, 3);
    addEdge(graph, 2, 4);
    printf("Topological Sort:\n");
    topologicalSortDFS(graph);

    return 0;
}

Kahn’s Algorithm Implementation:

#include <stdio.h>
#include <stdlib.h>
#include <queue>

// Node structure
struct Node {
    int dest;
    Node* next;
};

// Graph structure
struct Graph {
    int V;
    Node** adjList;
};

// Adds an edge from src to dest in the graph
Node* createNode(int dest) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = graph->adjList[src];
    graph->adjList[src] = newNode;
}

Graph* createGraph(int vertices) {
    int i;
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = vertices;

    graph->adjList = malloc(vertices * sizeof(Node*));

    for (i = 0; i <=vertices; ++i)
        graph->adjList[i] = NULL;

    return graph;
}

void topologicalSortKahn(Graph* graph) {
    // Array to store in-degrees of all vertices
    int in_degree[V];
    fill(in_degree, in_degree + V, 0);  // Initialize in-degrees to 0

    int i;
    // Computing in.degrees for each vertex
    for (i = 0; i < V; i++) {
        Node* temp = graph->adjList[i];
        while(temp) {
            in_degree[temp->dest]++;
            temp = temp->next;
        }
    }

    // Create a queue and enqueue all vertices with in-degree 0
    std::queue<int> q;
    for (i = 0; i < V; i++)
        if (in_degree[i] == 0)
            q.push(i);

    // Initialize count of visited vertices
    int count = 0;

    // Store topological order
    int* top_order = (int*)malloc(V * sizeof(int));

    // Dequeuing vertices one by one from Q
    while (!q.empty()) {
        // Get front vertex from Q and dequeue it
        int u = q.front();
        q.pop();

        // Put the dequeued vertex to topological order array
        top_order[count++]  = u;

        // Traverse the adjacency list of dequeued vertex u and decrease in-degrees of all adjacent nodes by one
        Node* temp = graph->adjList[u];
        while(temp) {
            // If in-degree becomes zero, add it
            if (--in_degree[temp->dest] == 0)
                q.push(temp->dest);

            temp = temp->next;
        }
    }

    if (count != V) { 
        printf("There exists a cycle in the graph.\n");
        return;
    }

    // Printing topologically sorted order
    printf("Topological Sort:\n");
    for (i = 0; i < V; i++)
        printf("%d ", top_order[i]);
    printf("\n");

    free(top_order);
}

// Main function driver
int main() {
    Graph* graph = createGraph(5);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 2, 3);
    addEdge(graph, 2, 4);
    printf("Topological Sort:\n");
    topologicalSortKahn(graph);
   
    return 0;
}

Explanation:

• DFS-Based Approach:

  • The core idea here is to leverage DFS to explore the graph and determine the relative order of nodes.
  • Nodes are explored, and upon their complete exploration (all descendants have been pushed to stack), they are added to the stack.
  • Finally, the stack is unwound to get the correct topological order.

• Kahn’s Algorithm:

  • This iterative approach involves finding nodes with zero in-degree and processing them first.
  • The algorithm removes nodes with zero in-degree one by one and updates the in-degrees of neighbors.
  • If there are no nodes to process and not all nodes were processed, the graph contains a cycle.

Applications: Apart from academic uses, topological sorting is fundamental in various real-world areas.

• Task Scheduling: It ensures precedence constraints are met, allowing efficient task execution.
• Dependency Resolution: Useful in package managers to resolve software dependencies.

Complexity Analysis:

• Time Complexity:

  • For DFS-based sorting, (O(V+E)), where (V) is the number of vertices, and (E) is the number of edges.
  • For Kahn’s algorithm, also (O(V+E)).

• Space Complexity:

  • Both algorithms use space proportional to the graph, i.e., (O(V+E)).

Important Information Summary:

• Topological Sorting linearly orders vertices in a DAG.
• Use Cases: Task scheduling, project management, compiler instruction optimization.
• Implementations: DFS-based and Kahn’s algorithm.
• Data Structures: Adjacency List, Adjacency Matrix, Queue, Stack.
• Cycle Detection: Necessary to avoid attempting a topological sort on graphs with cycles.
• Complexity: Time complexity (O(V+E)) and space complexity (O(V+E)) for both methods.
• Applications: Real-world systems requiring dependency resolution or ordered task execution.