Fun with Go: Topological Sort

tsort.go

package main

import "fmt"

/* Graph representation */
type Dag struct {
        outgoing_edges map[int][]int
        incoming_edges map[int][]int
}

/* Initializes maps */
func makeDag() *Dag {
        return &Dag{make(map[int][]int), make(map[int][]int)}
}

/* Adds edge @v1->@v2 to @dag */
func (dag *Dag) addEdge(v1, v2 int) {
        dag.outgoing_edges[v1] = append(dag.outgoing_edges[v1], v2)
        dag.incoming_edges[v2] = append(dag.incoming_edges[v2], v1)
}

/* Removes edge @v1->@v2 from @dag */
func (dag *Dag) removeEdge(v1, v2 int) {
        dag.outgoing_edges[v1] = remove(dag.outgoing_edges[v1], v2)
        dag.incoming_edges[v2] = remove(dag.incoming_edges[v2], v1)
}

/* Returns a slice of vertices with outgoing edges */
func (dag *Dag) outgoing() []int {
        return keys(dag.outgoing_edges)
}

/* Returns a slice of vertices with incoming edges */
func (dag *Dag) incoming() []int {
        return keys(dag.incoming_edges)
}

/* Returns the keys of @m as a slice */
func keys(m map[int] []int) []int {
        s := make([]int, 0)
        for k, _ := range m {
                s = append(s, k)
        }
        return s
}

/* Removes all elements from @s equal to @x */
func remove(s []int, x int) []int {
        s2 := make([]int, 0)
        for _, e := range s {
                if e != x {
                        s2 = append(s2, e)
                }
        }
        return s2
}

/* Returns all elements in @s1 not in @s2 */
func intersection(s1, s2 []int) []int {
        for _, e := range s2 {
                s1 = remove(s1, e)
        }
        return s1
}

/* Returns topological sort of @dag as a slice of ints */
func tsort(dag *Dag) []int{
        result := make([]int, 0)
        nodes := intersection(dag.outgoing(), dag.incoming())

        for len(nodes) > 0 {
                src := nodes[0]
                nodes = nodes[1:]
                result = append(result, src)

                tmp := make([]int, len(dag.outgoing_edges[src]))
                copy(tmp, dag.outgoing_edges[src])
                for _, dest := range tmp {
                        dag.removeEdge(src, dest)
                        if len(dag.incoming_edges[dest]) == 0 {
                                nodes = append(nodes, dest)
                        }
                }
        }
        return result
}

func main() {
        dag := makeDag()
        dag.addEdge(7, 11)
        dag.addEdge(5, 11)
        dag.addEdge(7, 8)
        dag.addEdge(3, 8)
        dag.addEdge(11, 2)
        dag.addEdge(11, 9)
        dag.addEdge(8, 9)
        dag.addEdge(11, 10)
        dag.addEdge(3, 10)

        fmt.Println(tsort(dag))
}