# Kosaraju's algorithm is too slow

I just implemented the Kosaraju's algorithm in Go. I tried to implement the same algorithm that is described in the relevant Wikipedia page:

For each vertex u of the graph, mark u as unvisited. Let L be empty.

For each vertex u of the graph do Visit(u), where Visit(u) is the recursive subroutine:
If u is unvisited then:
Mark u as visited.
For each out-neighbour v of u, do Visit(v).
Prepend u to L.
Otherwise do nothing.

For each element u of L in order, do Assign(u,u) where Assign(u,root) is the recursive subroutine:
If u has not been assigned to a component then:
Assign u as belonging to the component whose root is root.
For each in-neighbour v of u, do Assign(v,root).
Otherwise do nothing.


The Go code works as expected (i.e. gives the correct result), but it's unexpectedly slow. I implemented the very same algorithm in C# (.net 5) and got a 3x speedup. I would expect that Go would be at least as fast as C#... not 3x slower.

I'm here to see if I did something particularly bad in my Go code, performance-wise. I'm also open to criticism on the readability of my Go code -- I'm new to Go.

Here's the implementation file and the test file.

package main

var emptyStruct struct{}

type Graph struct {
edges       map[interface{}]map[interface{}]int
inNeighbors map[interface{}]map[interface{}]struct{}
}

func NewGraph(expectedNodes int) *Graph {
return &Graph{
edges:       make(map[interface{}]map[interface{}]int, expectedNodes),
inNeighbors: make(map[interface{}]map[interface{}]struct{}, expectedNodes),
}
}

func (graph *Graph) Connect(vertexFrom interface{}, vertexTo interface{}, weight int) {
if _, ok := graph.edges[vertexFrom]; !ok {
graph.edges[vertexFrom] = make(map[interface{}]int, len(graph.edges))
graph.inNeighbors[vertexFrom] = make(map[interface{}]struct{}, len(graph.inNeighbors))
}

if _, ok := graph.edges[vertexTo]; !ok {
graph.edges[vertexTo] = make(map[interface{}]int, len(graph.edges))
graph.inNeighbors[vertexTo] = make(map[interface{}]struct{}, len(graph.inNeighbors))
}

graph.edges[vertexFrom][vertexTo] = weight
graph.inNeighbors[vertexTo][vertexFrom] = emptyStruct
}

func (graph *Graph) FindAllOutNeighbors(vertex interface{}) map[interface{}]struct{} {
keys := make(map[interface{}]struct{}, len(graph.edges))

for key := range graph.edges[vertex] {
keys[key] = emptyStruct
}

return keys
}

func (graph *Graph) FindAllInNeighbors(vertex interface{}) map[interface{}]struct{} {
keys := make(map[interface{}]struct{}, len(graph.edges))

for key := range graph.inNeighbors[vertex] {
keys[key] = emptyStruct
}

return keys
}

func (graph *Graph) FindAllVertices() map[interface{}]struct{} {
keys := make(map[interface{}]struct{}, len(graph.edges))

for key := range graph.edges {
keys[key] = emptyStruct
}

return keys
}

func (graph *Graph) FindConnectedComponents() map[interface{}]map[interface{}]struct{} {
var visit func(interface{}, map[interface{}]struct{}, *[]interface{})
var assign func(interface{}, interface{}, map[interface{}]map[interface{}]struct{})

visit = func(vertex interface{}, unvisited map[interface{}]struct{}, L *[]interface{}) {
if _, ok := unvisited[vertex]; ok {
delete(unvisited, vertex)

for neighbor := range graph.FindAllOutNeighbors(vertex) {
visit(neighbor, unvisited, L)
}

*L = append(*L, vertex)
}
}

assign = func(vertex interface{}, root interface{}, components map[interface{}]map[interface{}]struct{}) {
hasBeenAssigned := false

for root := range components {
if _, ok := components[root][vertex]; ok {
hasBeenAssigned = true
break
}
}

if !hasBeenAssigned {
if _, ok := components[root]; !ok {
components[root] = make(map[interface{}]struct{})
}

components[root][vertex] = emptyStruct

for neighbor := range graph.FindAllInNeighbors(vertex) {
assign(neighbor, root, components)
}
}
}

unvisited := graph.FindAllVertices()

L := make([]interface{}, 0, len(unvisited))

for vertex := range graph.FindAllVertices() {
visit(vertex, unvisited, &L)
}

components := make(map[interface{}]map[interface{}]struct{})

for i := len(L) - 1; i >= 0; i -= 1 {
assign(L[i], L[i], components)
}

return components
}

package main

import "testing"

func TestFindConnectedComponents(t *testing.T) {
graph := NewGraph(8)

graph.Connect("1", "2", 1)
graph.Connect("2", "3", 1)
graph.Connect("2", "4", 1)
graph.Connect("3", "1", 1)
graph.Connect("3", "4", 1)

graph.Connect("4", "5", 1)
graph.Connect("5", "4", 1)

graph.Connect("6", "7", 1)
graph.Connect("6", "5", 1)
graph.Connect("7", "6", 1)
graph.Connect("7", "8", 1)
graph.Connect("8", "7", 1)
graph.Connect("8", "5", 1)

components := graph.FindConnectedComponents()

if len(components) != 3 {
t.Fatalf("Expected 3 components, found %d", len(components))
}
}
$$$$
`