0
\$\begingroup\$

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))
    }
}
```
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.