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