Implementing a Topological Sort Graph in Go with Generics

implement a graph which topological sort. Use golang and generics

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

1. 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.

2. AddEdge Method: This method adds a directed edge from the source node to the destination node.

3. 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.

4. 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.