Topological Sorting in Data Structures

Graph Applications : Topological Sorting.

Topological Sorting:

Topological sorting is used to order the vertices in a directed acyclic graph in such a way that for every directed edge from vertex A to vertex B, vertex A comes before vertex B in the ordering. In simpler terms, it provides an order in which you can process the nodes of a graph while respecting dependencies.

Simple Example:

Imagine you have a set of tasks to complete, where some tasks must be done before others. For example:

Task A: Wake up
Task B: Take shower
Task C: Get Dressed
Task D: Eat breakfast
Task E: Leave for work

Some of these tasks have dependencies: You must wake up before you can take a shower or eat breakfast. You must take a shower and get dressed before you leave for work. We can represent these tasks and their dependencies as a directed acyclic graph.

A valid topological sort of these tasks would be:

Wake up
Take shower
Get Dressed
Eat breakfast
Leave for work

Another valid topological sort would be:

Wake up
Eat breakfast
Take shower
Get Dressed
Leave for work

The key is that “Wake up” must come before “Take shower” and “Eat breakfast”, and “Take shower” and “Get Dressed” must come before “Leave for work”.

Important Points:

Topological sort is only possible for directed acyclic graphs. If a graph has cycles, it cannot be topologically sorted.
There can be multiple valid topological orderings for a given DAG.
The algorithm works by finding nodes with no incoming edges, adding them to the result, removing them from the graph, and repeating until all nodes are processed.

Algorithm:

Initialization:
- Create a visited array to keep track of visited nodes during DFS.
- Create a stack to store the topologically sorted vertices.
DFS Traversal:
- For each vertex in the graph:
  - If the vertex is not visited, call the topologicalSortUtil

topologicalSortUtil Function:
- Mark the current vertex as visited.
- For each neighbor of the current vertex:
  - If the neighbor is not visited, recursively call topologicalSortUtil on the neighbor.
- After visiting all neighbors, push the current vertex onto the stack.
Output:
- Pop all vertices from the stack and print them. This gives the topological order.

Assignment 5. Set A a) SPPU:

Write a C program for the implementation of Topological Sorting.

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

#define MAX_VERTICES 100

// Structure for a node in the adjacency list
struct Node {
    int vertex;
    struct Node* next;
};

// Structure for the graph
struct Graph {
    int numVertices;
    struct Node** adjLists;
    int* visited;
};

// Structure for the stack
struct Stack {
    int data[MAX_VERTICES];
    int top;
};

// Function to create a new node
struct Node* createNode(int v) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// Function to create a graph
struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->numVertices = vertices;
    graph->adjLists = (struct Node**)malloc(vertices * sizeof(struct Node*));
    graph->visited = (int*)malloc(vertices * sizeof(int));

    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->visited[i] = 0;
    }
    return graph;
}

// Function to add an edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
}

// Function to initialize the stack
void initializeStack(struct Stack* stack) {
    stack->top = -1;
}

// Function to push a vertex onto the stack
void push(struct Stack* stack, int vertex) {
    if (stack->top == MAX_VERTICES - 1) {
        printf("Stack overflow!\n");
        return;
    }
    stack->data[++stack->top] = vertex;
}

// Function to pop a vertex from the stack
int pop(struct Stack* stack) {
    if (stack->top == -1) {
        printf("Stack underflow!\n");
        return -1;
    }
    return stack->data[stack->top--];
}

// Recursive function for topological sort
void topologicalSortUtil(struct Graph* graph, int vertex, struct Stack* stack) {
    graph->visited[vertex] = 1; // Mark the current vertex as visited

    // Traverse all adjacent vertices
    struct Node* temp = graph->adjLists[vertex];
    while (temp != NULL) {
        int adjVertex = temp->vertex;
        if (!graph->visited[adjVertex]) {
            topologicalSortUtil(graph, adjVertex, stack);
        }
        temp = temp->next;
    }

    // Push the current vertex onto the stack
    push(stack, vertex);
}

// Function to perform topological sort
void topologicalSort(struct Graph* graph) {
    struct Stack stack;
    initializeStack(&stack);

    // Perform DFS for all unvisited vertices
    for (int i = 0; i < graph->numVertices; i++) {
        if (!graph->visited[i]) {
            topologicalSortUtil(graph, i, &stack);
        }
    }

    // Print the topological order (vertices popped from the stack)
    printf("Topological Order: ");
    while (stack.top != -1) {
        printf("%d ", pop(&stack));
    }
    printf("\n");
}

int main() {
    int vertices, edges;
    printf("Enter the number of vertices: ");
    scanf("%d", &vertices);
    printf("Enter the number of edges: ");
    scanf("%d", &edges);

    struct Graph* graph = createGraph(vertices);

    printf("Enter the edges (source destination):\n");
    for (int i = 0; i < edges; i++) {
        int src, dest;
        scanf("%d %d", &src, &dest);
        addEdge(graph, src, dest);
    }

    topologicalSort(graph);

    return 0;
}

Understanding Program Code:

1. Graph Representation:
  - The graph is represented using an adjacency list. Each vertex has a linked list of its neighboring vertices.
2. Stack Implementation:
  - A stack is used to store vertices in the order they are finished during DFS traversal.
  - The stack ensures that vertices are popped in the correct topological order.
3. DFS Traversal:
  - The topologicalSortUtil function performs a DFS traversal.
  - It marks vertices as visited and recursively visits all their neighbors.
  - After visiting all neighbors, the current vertex is pushed onto the stack.
4. Topological Order:
  - The stack stores vertices in reverse order of their finishing times.
  - Popping vertices from the stack gives the topological order.
5. Input and Output:
  - The user inputs the number of vertices, edges, and the edges themselves.
  - The program outputs the topological order of the vertices.

Graph Applications : Topological Sorting.

Topological Sorting:

Algorithm:

Assignment 5. Set A a) SPPU:

Write a C program for the implementation of Topological Sorting.

Quick Links

Help and Support