graphs.go

// A graph is a data structure which has several Nodes connected by Edges. Each Node has some data, and Edges may have properties as well.
// Graphs can be cyclical and tend to not be directional, although they can be directional if the implementation requires it.
package main

import "fmt"

type Hashable[K comparable] interface {
	Hash() K
}

// Edge is defined as a pair of nodes with no associated order to them.
// Any given Node may have multiple Edges.
type Edge [2]uint

type Graph[K comparable, V Hashable[K]] struct {
	// A graph is compromised of a set of nodes, and a set of edges.
	// Nodes stand on their own and have data in them; edges are simply two unordered pairs of nodes.
	// This is a simple, undirected graph implementation, and, as such, there may be loops.
	nodes map[K]V
	edges map[K][]K
}

func (g *Graph[K, V]) Add(node V) {
	if g.nodes == nil {
		g.nodes = make(map[K]V)
	}

	g.nodes[node.Hash()] = node
}

func (g *Graph[K, V]) AddEdge(a, b V) {
	key1 := a.Hash()
	key2 := b.Hash()

	_, ok1 := g.nodes[key1]
	_, ok2 := g.nodes[key2]
	if !ok1 || !ok2 {
		panic("node absent from graph")
	}

	if g.edges == nil {
		g.edges = make(map[K][]K)
	}

	g.edges[key1] = append(g.edges[key1], key2)
	// This is cyclical, which is important so that we can clear up connections if either 'end' is removed
	g.edges[key2] = append(g.edges[key2], key1)
}

// Bfs uses breadth-first search to find the first Node that causes the predicate to return true, starting at the start Node.
// If a Node is found, it is deposited in dst and true is returned.
// If the entire graph is exhausted and no result is found, false is returned.
func Bfs[K comparable, V Hashable[K]](graph Graph[K, V], start V, goal func(V) bool) (V, bool) {
	var t struct{}
	queue := []K{start.Hash()}
	visited := make(map[K]struct{})
	for {
		if len(queue) == 0 {
			break
		}

		key := queue[0]
		queue = queue[1:]
		if _, ok := visited[key]; ok {
			continue
		}

		node, ok := graph.nodes[key]
		if !ok {
			// Something terrible went wrong. This indicates an implementation failure on our part.
			panic("edge had no corresponding node in graph")
		}

		if goal(node) {
			return node, true
		}

		visited[key] = t
		queue = append(queue, graph.edges[key]...)
	}

	var defaultValue V
	return defaultValue, false
}

type Key = uint64

type Node int

func (n Node) Hash() uint64 {
	return Key(n)
}

func main() {
	var graph Graph[Key, Node]
	nodes := []Node{Node(1), Node(2), Node(3), Node(4), Node(5)}
	for _, node := range nodes {
		graph.Add(node)
	}

	for _, node1 := range nodes {
		for _, node2 := range nodes {
			if node1 == node2 {
				continue
			}
			graph.AddEdge(node1, node2)
		}
	}

	dst, _ := Bfs(graph, nodes[2], func(node Node) bool {
		return node == Node(5)
	})

	fmt.Printf("%v\n", dst)
}