Generic Graph Implementation

graph.go

// BFS returns the shortest path between two nodes,
// as a list of edges. Eq is used to determine parity between nodes. The Eq functions makes
// this function generic enough instead of trying to shoehorn some other `comparable` type
// into `Node`.
// Note, this would be much more user-friendly, if it would return a map of `cameFrom`s which
// then could be traversed back to find the shortest path, rather than returning a slice of
// edges which is difficult to follow back.
func (g *Graph[Node, Edge]) BFS(from, to Node, eq func(self, other Node) bool) []Edge {
	queue := []Node{from}
	path := make([]Edge, 0)
	// this should be a map for O(1) recall, but in that case I would have to also get a function
	// which returns a unique identifier for the nodes. But since I already have an Eq function
	// I can use that.
	seen := make([]Node, 0)
	var current Node
	for len(queue) > 0 {
		current, queue = queue[0], queue[1:]
		edges := current.Edges()
		// For each edge, gather the nodes. The edges contain from -> to syntax,
		// so we ignore the `from` one. We are only interested in the `to`.
		for _, edge := range edges {
			path = append(path, edge)
			_, dest := edge.Nodes()
			if eq(dest, to) {
				return path
			}
			visited := false
			for _, s := range seen {
				if eq(s, dest) {
					visited = true
					break
				}
			}
			if !visited {
				seen = append(seen, dest)
				queue = append(queue, dest)
			}
		}
	}
	return nil
}

graph_test.go

package chapter06

import (
	"testing"

	"github.com/stretchr/testify/assert"
)

func TestGraph_BFS(t *testing.T) {
	A := &GraphNode{
		Value: "A",
	}
	B := &GraphNode{
		Value: "B",
	}
	start := &GraphNode{
		Value: "start",
	}
	start.GraphEdges = []*GraphEdge{
		{
			From: start,
			To:   A,
		},
		{
			From: start,
			To:   B,
		},
	}
	C := &GraphNode{
		Value: "C",
	}
	D := &GraphNode{
		Value: "D",
	}
	A.GraphEdges = []*GraphEdge{
		{
			From: A,
			To:   C,
		},
		{
			From: A,
			To:   D,
		},
	}
	E := &GraphNode{
		Value: "E",
	}
	F := &GraphNode{
		Value: "F",
	}
	B.GraphEdges = []*GraphEdge{
		{
			From: B,
			To:   E,
		},
		{
			From: B,
			To:   F,
		},
	}
	graph := New[*GraphNode, *GraphEdge]([]*GraphNode{start, A, B, C, D, E, F})
	got := graph.BFS(start, F, func(self, other *GraphNode) bool {
		return self.Value == other.Value
	})
	startEdge := got[len(got)-1]
	_, to := startEdge.Nodes()
	assert.Equal(t, F, to)
	// Find who points to `from` -> which would be simpler if this would be a MAP.
	// `cameFrom` should be a map, so it's easy to follow backwards.
	var bFrom *GraphNode
	for _, e := range got {
		edgeFrom, edgeTo := e.Nodes()
		if edgeTo == B {
			bFrom = edgeFrom
			break
		}
	}
	assert.Equal(t, start, bFrom)
}