breath first search for graph data

bfs.go

package main

const (
	visited    = 0
	completion = -1
)

type Status struct {
	Node      int
	Unvisited []int
	Visited   map[int]int
}

func NewStatus() *Status {
	return &Status{
		Node:      0,
		Unvisited: []int{},
		Visited:   map[int]int{}, // for O(1) access
	}
}

func (self *Status) findNextNode() int {
	for i := range self.Unvisited {
		node := self.Unvisited[i]
		if _, ok := self.Visited[node]; ok == false {
			self.Unvisited = self.Unvisited[i+1:]
			return node
		}
	}
	return completion
}

type Graph struct {
	Nodes map[int][]int
}

func NewGraph(nodes map[int][]int) *Graph {
	return &Graph{Nodes: nodes}
}

func Search(graph Graph, status Status) *Status {
	if len(status.Visited) > 0 {
		node := status.findNextNode()
		status.Node = node
	}

	status.Visited[status.Node] = visited
	status.Unvisited = append(status.Unvisited, graph.Nodes[status.Node]...)
	return &status
}

bfs_test.go

// exec: $ go test
package main

import "testing"

func assert(t *testing.T, graph *Graph, status *Status, expects int) *Status {
	newStatus := Search(*graph, *status)
	if newStatus.Node != expects {
		t.Errorf("expects node is %d but %d", expects, newStatus.Node)
	}
	return newStatus
}

func TestSearch(t *testing.T) {
	nodes := map[int][]int{
		0: {1, 2},
		1: {},
		2: {4, 3},
		3: {2},
		4: {0},
		5: {2}, // unreachable
	}

	graph := NewGraph(nodes)
	status := NewStatus()

	status = assert(t, graph, status, 0)
	status = assert(t, graph, status, 1)
	status = assert(t, graph, status, 2)
	status = assert(t, graph, status, 4)
	status = assert(t, graph, status, 3)
	status = assert(t, graph, status, -1)
}