Skip to content

Instantly share code, notes, and snippets.

@Skarlso
Last active December 31, 2021 10:07
Show Gist options
  • Save Skarlso/4cf0ba3b2428a7113a279f6038dd7dce to your computer and use it in GitHub Desktop.
Save Skarlso/4cf0ba3b2428a7113a279f6038dd7dce to your computer and use it in GitHub Desktop.
Generic Graph Implementation
// 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
}
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)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment