Topological Sorting is a fundamental algorithm in computer science used to order the vertices of a Directed Acyclic Graph (DAG) such that for every directed edge u → v, vertex u comes before vertex v in the ordering. This ordering has practical applications in areas like task scheduling, dependency resolution, and course prerequisite structuring.

Problem Statement

Given a Directed Acyclic Graph (DAG), perform a topological sort to determine a linear ordering of its vertices. Ensure that for every directed edge u → v, vertex u appears before vertex v in the ordering. If the graph contains a cycle, topological sorting is not possible.

Program Structure

The Go program to perform topological sorting on a DAG is structured as follows:

• Graph Representation: The graph is represented using an adjacency list, where each vertex has a list of its neighboring vertices.
• Topological Sort Implementation: The program implements two common algorithms for topological sorting: Depth-First Search (DFS) and Kahn’s Algorithm (BFS-based).
• Cycle Detection: The program checks if the graph contains a cycle, in which case topological sorting is not possible.
• Main Function: Demonstrates the usage of the topological sort implementation with example graphs.

Go Program

package main

import (
    "fmt"
    "errors"
)

// Graph represents a directed graph using an adjacency list
type Graph struct {
    vertices int
    adjList  [][]int
}

// NewGraph initializes a new graph with a given number of vertices
func NewGraph(vertices int) *Graph {
    adj := make([][]int, vertices)
    for i := range adj {
        adj[i] = []int{}
    }
    return &Graph{
        vertices: vertices,
        adjList:  adj,
    }
}

// AddEdge adds a directed edge from src to dest
func (g *Graph) AddEdge(src, dest int) error {
    if src >= g.vertices || dest >= g.vertices || src < 0 || dest < 0 {
        return errors.New("invalid edge")
    }
    g.adjList[src] = append(g.adjList[src], dest)
    return nil
}

// TopologicalSortDFS performs topological sort using Depth-First Search (DFS)
func (g *Graph) TopologicalSortDFS() ([]int, error) {
    visited := make([]bool, g.vertices)
    recStack := make([]bool, g.vertices)
    var stack []int

    // Helper function for DFS
    var dfs func(v int) bool
    dfs = func(v int) bool {
        visited[v] = true
        recStack[v] = true

        for _, neighbor := range g.adjList[v] {
            if !visited[neighbor] {
                if dfs(neighbor) {
                    return true
                }
            } else if recStack[neighbor] {
                return true // Cycle detected
            }
        }

        recStack[v] = false
        stack = append(stack, v)
        return false
    }

    // Perform DFS for each vertex
    for i := 0; i < g.vertices; i++ {
        if !visited[i] {
            if dfs(i) {
                return nil, errors.New("graph contains a cycle; topological sort not possible")
            }
        }
    }

    // Reverse the stack to get the topological order
    for i, j := 0, len(stack)-1; i < j; i, j = i+1, j-1 {
        stack[i], stack[j] = stack[j], stack[i]
    }

    return stack, nil
}

// TopologicalSortKahn performs topological sort using Kahn's Algorithm (BFS-based)
func (g *Graph) TopologicalSortKahn() ([]int, error) {
    inDegree := make([]int, g.vertices)
    for u := 0; u < g.vertices; u++ {
        for _, v := range g.adjList[u] {
            inDegree[v]++
        }
    }

    // Initialize queue with vertices of in-degree 0
    var queue []int
    for i := 0; i < g.vertices; i++ { if inDegree[i] == 0 { queue = append(queue, i) } } var topoOrder []int count := 0 for len(queue) > 0 {
        u := queue[0]
        queue = queue[1:]
        topoOrder = append(topoOrder, u)

        for _, v := range g.adjList[u] {
            inDegree[v]--
            if inDegree[v] == 0 {
                queue = append(queue, v)
            }
        }
        count++
    }

    if count != g.vertices {
        return nil, errors.New("graph contains a cycle; topological sort not possible")
    }

    return topoOrder, nil
}

func main() {
    // Example usage:
    // Create a graph with 6 vertices (0 to 5)
    g := NewGraph(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 using DFS
    topoOrderDFS, errDFS := g.TopologicalSortDFS()
    if errDFS != nil {
        fmt.Println("DFS Topological Sort Error:", errDFS)
    } else {
        fmt.Println("Topological Sort (DFS):", topoOrderDFS)
    }

    // Perform Topological Sort using Kahn's Algorithm
    topoOrderKahn, errKahn := g.TopologicalSortKahn()
    if errKahn != nil {
        fmt.Println("Kahn's Topological Sort Error:", errKahn)
    } else {
        fmt.Println("Topological Sort (Kahn's Algorithm):", topoOrderKahn)
    }
}
    

Documentation

The Go program provided implements Topological Sorting on a Directed Acyclic Graph (DAG) using two different algorithms: Depth-First Search (DFS) and Kahn’s Algorithm (BFS-based). Below is a detailed explanation of each component of the program:

1. Edge Struct

The Edge struct represents a directed edge in the graph, containing the destination vertex dest and the weight of the edge. Although weights are not utilized in the topological sort, the struct can be extended for weighted graph applications.

2. Graph Struct and Methods

The Graph struct encapsulates the graph’s structure, including the number of vertices and an adjacency list adjList.

NewGraph Function

The NewGraph function initializes a new graph with a specified number of vertices and an empty adjacency list. It returns a pointer to the Graph struct.

AddEdge Method

The AddEdge method adds a directed edge from the source vertex src to the destination vertex dest. It appends the destination vertex to the adjacency list of the source vertex. The method returns an error if the provided vertices are out of bounds.

3. TopologicalSortDFS Method

The TopologicalSortDFS method performs topological sorting using the Depth-First Search (DFS) approach. It returns a slice of integers representing the topological order of the vertices or an error if the graph contains a cycle.

Steps:

1. Initialization: Initializes two slices, visited to keep track of visited vertices and recStack to detect cycles using recursion stack.
2. DFS Traversal: Iterates through each vertex. If a vertex hasn’t been visited, it calls the recursive dfs function.
3. Cycle Detection: The dfs function marks the current vertex as visited and adds it to the recursion stack. It then explores all adjacent vertices. If an adjacent vertex is already in the recursion stack, a cycle is detected, and the function returns true.
4. Stack Population: After exploring all adjacent vertices, the current vertex is removed from the recursion stack and added to the stack slice.
5. Topological Order: After completing DFS for all vertices, the stack slice is reversed to obtain the correct topological order.

4. TopologicalSortKahn Method

The TopologicalSortKahn method performs topological sorting using Kahn’s Algorithm, which is a Breadth-First Search (BFS) based approach. It returns a slice of integers representing the topological order of the vertices or an error if the graph contains a cycle.

Steps:

1. Calculate In-Degree: Initializes a slice inDegree to store the number of incoming edges for each vertex.
2. Initialize Queue: Vertices with an in-degree of 0 (no dependencies) are added to the queue.
3. BFS Traversal: While the queue is not empty, dequeue a vertex u and add it to the topoOrder slice. For each adjacent vertex v, decrement its in-degree by 1. If the in-degree of v becomes 0, enqueue it.
4. Cycle Detection: After traversal, if the number of vertices in topoOrder is not equal to the total number of vertices, a cycle exists, and the method returns an error.

5. Main Function

The main function demonstrates how to use the topological sort implementations:

1. Graph Creation: Initializes a graph with 6 vertices (0 to 5).
2. Adding Edges: Adds directed edges to the graph using the AddEdge method.
3. Topological Sort (DFS): Calls TopologicalSortDFS and prints the resulting order or an error message.
4. Topological Sort (Kahn’s Algorithm): Calls TopologicalSortKahn and prints the resulting order or an error message.

How the Program Works

1. Graph Initialization: A new graph is created with a specified number of vertices using the NewGraph function.
2. Adding Edges: Directed edges are added to the graph to establish relationships between vertices. For example, an edge from vertex 5 to vertex 2 indicates that vertex 5 must come before vertex 2 in the topological order.
3. Topological Sorting (DFS):
   • The program starts DFS traversal from each unvisited vertex.
   • It recursively explores all adjacent vertices, ensuring that each vertex is processed only after all its dependencies.
   • If a cycle is detected during traversal, the function returns an error indicating that topological sorting is not possible.
   • Otherwise, the vertices are added to a stack, which is then reversed to obtain the correct topological order.
4. Topological Sorting (Kahn’s Algorithm):
   • The program calculates the in-degree for each vertex.
   • Vertices with an in-degree of 0 are enqueued as they have no dependencies.
   • It dequeues vertices one by one, appends them to the topological order, and decreases the in-degree of their adjacent vertices.
   • If any adjacent vertex’s in-degree drops to 0, it is enqueued.
   • If the total number of processed vertices equals the number of vertices in the graph, a valid topological order is obtained.
   • Otherwise, the graph contains a cycle, and topological sorting is not possible.
5. Output: The program prints the topological order obtained from both DFS and Kahn’s Algorithm or an error message if sorting is not possible.

Example Output

Given the following directed edges in the graph:

• 5 → 2
• 5 → 0
• 4 → 0
• 4 → 1
• 2 → 3
• 3 → 1

Running the program produces the following output:

Topological Sort (DFS): [5 4 2 3 1 0]
Topological Sort (Kahn's Algorithm): [5 4 0 2 1 3]
    

Both methods provide a valid topological ordering of the vertices. Note that multiple valid topological orders may exist for a given graph.

Conclusion

Topological Sorting is a critical algorithm for ordering tasks based on dependencies. This Go program effectively implements both Depth-First Search (DFS) and Kahn’s Algorithm to perform topological sorting on a Directed Acyclic Graph (DAG). By understanding the program structure and the underlying principles of each algorithm, developers can apply these techniques to a variety of real-world problems, such as task scheduling, build systems, and dependency management.

Excerpt

Implement Topological Sorting in Go using DFS and Kahn’s Algorithm. This guide includes detailed explanations and a well-documented Go program example.