To implement a graph that supports topological sorting in Go using generics, we can use the golang.org/x/exp/constraints package to define a generic type for our graph nodes. Below is a simple implementation of a directed graph with a method for topological sorting.
Implementation
package main
import (
"fmt"
"golang.org/x/exp/constraints"
)
// Graph represents a directed graph using an adjacency list.
type Graph[T constraints.Ordered] struct {
adjacencyList map[T][]T
}
// NewGraph creates a new graph.
func NewGraph[T constraints.Ordered]() *Graph[T] {
return &Graph[T]{adjacencyList: make(map[T][]T)}
}
// AddEdge adds a directed edge from source to destination.
func (g *Graph[T]) AddEdge(source, destination T) {
g.adjacencyList[source] = append(g.adjacencyList[source], destination)
}
// TopologicalSort performs a topological sort on the graph.
func (g *Graph[T]) TopologicalSort() ([]T, error) {
visited := make(map[T]bool)
stack := []T{}
tempStack := make(map[T]bool)
var visit func(node T) error
visit = func(node T) error {
if tempStack[node] {
return fmt.Errorf("graph contains a cycle")
}
if !visited[node] {
tempStack[node] = true
for _, neighbor := range g.adjacencyList[node] {
if err := visit(neighbor); err != nil {
return err
}
}
tempStack[node] = false
visited[node] = true
stack = append(stack, node)
}
return nil
}
for node := range g.adjacencyList {
if err := visit(node); err != nil {
return nil, err
}
}
// 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
}
func main() {
graph := NewGraph[int]()
graph.AddEdge(5, 2)
graph.AddEdge(5, 0)
graph.AddEdge(4, 0)
graph.AddEdge(4, 1)
graph.AddEdge(2, 3)
graph.AddEdge(3, 1)
order, err := graph.TopologicalSort()
if err != nil {
fmt.Println("Error:", err)
} else {
fmt.Println("Topological Sort Order:", order)
}
}
Explanation
-
Graph Structure: The Graph struct uses a map to represent the adjacency list of the graph. The keys are the nodes, and the values are slices of nodes that represent directed edges.
-
AddEdge Method: This method adds a directed edge from the source node to the destination node.
-
TopologicalSort Method: This method performs a topological sort using Depth-First Search (DFS). It uses a visited map to track visited nodes and a tempStack to detect cycles. If a cycle is detected, it returns an error.
-
Main Function: In the main function, we create a graph, add edges, and then perform a topological sort, printing the result.
Usage
You can run this code in a Go environment. It will output the topological order of the nodes in the graph. If the graph contains a cycle, it will return an error indicating that a cycle was detected.