blob: ed902816daba76f6a29532d73f056d6c77829fec [file] [log] [blame]
 // Copyright 2020 The Go Authors. All rights reserved. // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. // Package graph implements general purpose graph algorithms. package graph import "errors" // A Graph is a collection of nodes. A node may have an arbitrary number // of edges. An edge connects two nodes. Both nodes and edges must be // comparable. This is an undirected simple graph. type Graph[Node NodeC[Edge], Edge EdgeC[Node]] struct { nodes []Node } // NodeC is the contraints on a node in a graph, given the Edge type. type NodeC[Edge any] interface { comparable Edges() []Edge } // Edgec is the constraints on an edge in a graph, given the Node type. type EdgeC[Node any] interface { comparable Nodes() (a, b Node) } // New creates a new Graph from a collection of Nodes. func New[Node NodeC[Edge], Edge EdgeC[Node]](nodes []Node) *Graph[Node, Edge] { return &Graph[Node, Edge]{nodes: nodes} } // nodePath holds the path to a node during ShortestPath. // This should ideally be a type defined inside ShortestPath, // but the translator tool doesn't support that. type nodePath[Node NodeC[Edge], Edge EdgeC[Node]] struct { node Node path []Edge } // ShortestPath returns the shortest path between two nodes, // as an ordered list of edges. If there are multiple shortest paths, // which one is returned is unpredictable. func (g *Graph[Node, Edge]) ShortestPath(from, to Node) ([]Edge, error) { visited := make(map[Node]bool) visited[from] = true workqueue := []nodePath[Node, Edge]{nodePath[Node, Edge]{from, nil}} for len(workqueue) > 0 { current := workqueue workqueue = nil for _, np := range current { edges := np.node.Edges() for _, edge := range edges { a, b := edge.Nodes() if a == np.node { a = b } if !visited[a] { ve := append([]Edge(nil), np.path...) ve = append(ve, edge) if a == to { return ve, nil } workqueue = append(workqueue, nodePath[Node, Edge]{a, ve}) visited[a] = true } } } } return nil, errors.New("no path") }