Golang tsort implementation

main.go

package main

import (
	"errors"
	"fmt"
	"os"
)

type edge struct{ from, to int }

func main() {
	var edges = []edge{
		{3, 8},
		{3, 10},
		{5, 11},
		{7, 8},
		{7, 11},
		{8, 9},
		{11, 2},
		{11, 9},
		{11, 10},
	}
	l, err := tsort(edges)
	if err != nil {
		fmt.Fprintf(os.Stderr, "%s\n", err)
	} else {
		fmt.Printf("%+v\n", l)
	}
}

func tsort(edges []edge) ([]int, error) {
	inEdges := make(map[int]map[int]struct{})
	outEdges := make(map[int]map[int]struct{})
	for _, e := range edges {
		if _, ok := inEdges[e.to]; !ok {
			inEdges[e.to] = make(map[int]struct{})
		}
		inEdges[e.to][e.from] = struct{}{}
		if _, ok := outEdges[e.from]; !ok {
			outEdges[e.from] = make(map[int]struct{})
		}
		outEdges[e.from][e.to] = struct{}{}
	}
	s := make(map[int]struct{})
	for m := range outEdges {
		if len(inEdges[m]) == 0 {
			s[m] = struct{}{}
		}
	}
	var l []int
	for len(s) > 0 {
		var n int
		for n = range s {
			break
		}
		delete(s, n)
		l = append(l, n)
		for m := range outEdges[n] {
			delete(outEdges[n], m)
			delete(inEdges[m], n)
			if len(inEdges[m]) == 0 {
				s[m] = struct{}{}
			}
		}
	}
	for _, es := range inEdges {
		if len(es) > 0 {
			return nil, errors.New("has cycle")
		}
	}
	return l, nil
}

func tsort(edges []edge, n int) ([]int, error) {
	ts := make([]int, 0, n)
	qs := make([]int, 0, n)
	vs := make([]bool, n)
	deg := make([]int, n)
	xs := make([]bool, n*n)
	adj := make([][]bool, n)
	for i := 0; i < n; i++ {
		adj[i] = xs[i*n : (i+1)*n]
	}
	for _, e := range edges {
		if !adj[e.from][e.to] {
			adj[e.from][e.to] = true
			deg[e.to]++
		}
	}
	for i := 0; i < n; i++ {
		if deg[i] == 0 {
			qs = append(qs, i)
			vs[i] = true
		}
	}
	if len(qs) == 0 && n > 0 {
		return nil, errors.New("has cycle")
	}
	var x int
	for len(qs) > 0 {
		x, qs = qs[0], qs[1:]
		ts = append(ts, x)
		for i := 0; i < n; i++ {
			if adj[x][i] && !vs[i] {
				deg[i]--
				if deg[i] == 0 {
					qs = append(qs, i)
					vs[i] = true
				}
			}
		}
	}
	if len(ts) < n {
		return nil, errors.New("dependency has a cycle")
	}
	return ts, nil
}

With cycle detection error.

func tsort(n int, adj [][]bool) ([]int, error) {
	ts := make([]int, 0, n) // result
	qs := make([]int, 0, n) // breadth-first search
	vs := make([]bool, n)   // visited
	deg := make([]int, n)   // indegree
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if adj[i][j] {
				deg[j]++
			}
		}
	}
	for i := 0; i < n; i++ {
		if deg[i] == 0 {
			qs = append(qs, i)
			vs[i] = true
		}
	}
	var x int
	for len(qs) > 0 {
		x, qs = qs[0], qs[1:]
		ts = append(ts, x)
		for i := 0; i < n; i++ {
			if adj[x][i] && !vs[i] {
				deg[i]--
				if deg[i] == 0 {
					qs = append(qs, i)
					vs[i] = true
				}
			}
		}
	}
	if len(ts) == n {
		return ts, nil
	}
	var ps [][2]int // linked list
	var ks []int    // depth-first search
	for i := 0; i < n; i++ {
		if !vs[i] {
			ks = append(ks, len(ps))
			ps = append(ps, [2]int{i, -1})
		}
	}
	for k := 0; len(ks) > 0; {
		k, ks = ks[len(ks)-1], ks[:len(ks)-1]
		for i, j := ps[k][0], 0; j < n; j++ {
			if !vs[j] && adj[i][j] {
				for l, m := k, 2; ; m++ {
					if j == ps[l][0] {
						xs := make([]int, m)
						xs[len(xs)-1] = j
						for m -= 2; k >= 0 && m >= 0; m-- {
							xs[m], k = ps[k][0], ps[k][1]
						}
						return nil, cycleError(xs)
					}
					if l = ps[l][1]; l < 0 {
						break
					}
				}
				ks = append(ks, len(ps))
				ps = append(ps, [2]int{j, k})
			}
		}
	}
	return nil, cycleError(nil)
}

type cycleError []int

func (err cycleError) Error() string {
	return "dependency has a cycle"
}