| // 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") |
| } |