dijkstra.gno

  1// Package dijkstra finds the cheapest route from one node to every other node
  2// of a weighted directed graph, as a pure, reusable package.
  3//
  4// It is Dijkstra's algorithm with a binary min-heap keyed on node index, so a
  5// node is never queued twice and the queue never grows past the node count.
  6// Complexity is O((V+E) log V), and both V and E are capped (MaxNodes,
  7// MaxEdges) so a realm can reason about the gas before it calls.
  8//
  9// The result is *deterministic*. Two nodes sitting at the same distance settle
 10// in the order they were added to the graph, and a relaxation that merely ties
 11// the incumbent never replaces it, so the predecessor chain Path walks is the
 12// same on every node that runs the code. A shortest-path routine that broke
 13// ties by map iteration order would make a Render differ between validators,
 14// which is a consensus bug rather than a cosmetic one.
 15//
 16// Weights are non-negative by construction: AddEdge panics on a negative one.
 17// That is not a simplification, it is the precondition the algorithm needs. A
 18// settled node is never revisited, so one negative edge silently returns a
 19// wrong answer rather than an error.
 20//
 21// A live demo of this package is at
 22// [r/moul/x/daily/dijkstrademo](/r/moul/x/daily/dijkstrademo/v0).
 23package dijkstra
 24
 25import (
 26	"errors"
 27	"strings"
 28)
 29
 30const (
 31	// MaxNodes bounds the graph so a caller can size gas up front.
 32	MaxNodes = 512
 33	// MaxEdges bounds the arcs for the same reason. Both are deliberately
 34	// small: this is a package for a realm's routing table, not for a road
 35	// network.
 36	MaxEdges = 4000
 37	// Unreachable is the distance reported for a node no path reaches. It is
 38	// returned alongside ok=false, never on its own.
 39	Unreachable = -1
 40)
 41
 42// ErrUnknownNode is returned by lookups naming a node the graph never saw.
 43var ErrUnknownNode = errors.New("dijkstra: unknown node")
 44
 45type arc struct {
 46	to     int
 47	weight int
 48}
 49
 50// Graph is a weighted directed graph over named nodes. The zero value is not
 51// usable, build one with New.
 52type Graph struct {
 53	names []string       // node index -> name, in insertion order
 54	index map[string]int // name -> node index. Looked up, never ranged over
 55	adj   [][]arc        // node index -> outgoing arcs, in insertion order
 56	edges int
 57}
 58
 59// New returns an empty Graph.
 60func New() *Graph {
 61	return &Graph{index: map[string]int{}}
 62}
 63
 64// AddNode registers a node with no arcs and returns its index. Adding a node
 65// twice returns the existing index and changes nothing, which is how a caller
 66// declares an island that nothing reaches.
 67//
 68// It panics on an empty name, and past MaxNodes.
 69func (g *Graph) AddNode(name string) int {
 70	if name == "" {
 71		panic("dijkstra: empty node name")
 72	}
 73	if i, ok := g.index[name]; ok {
 74		return i
 75	}
 76	if len(g.names) >= MaxNodes {
 77		panic("dijkstra: too many nodes")
 78	}
 79	i := len(g.names)
 80	g.names = append(g.names, name)
 81	g.index[name] = i
 82	g.adj = append(g.adj, nil)
 83	return i
 84}
 85
 86// AddEdge records a one-way arc from -> to costing weight, registering either
 87// endpoint that is new. Parallel arcs are kept rather than collapsed: the
 88// search takes the cheapest, and dropping the others would lose information a
 89// caller may want to render.
 90//
 91// It panics on a negative weight (the algorithm's precondition), on a
 92// self-loop (it can never shorten a path and is always a caller mistake), and
 93// past MaxEdges.
 94func (g *Graph) AddEdge(from, to string, weight int) {
 95	if weight < 0 {
 96		panic("dijkstra: negative weight")
 97	}
 98	if from == to {
 99		panic("dijkstra: self-loop")
100	}
101	if g.edges >= MaxEdges {
102		panic("dijkstra: too many edges")
103	}
104	f := g.AddNode(from)
105	t := g.AddNode(to)
106	g.adj[f] = append(g.adj[f], arc{to: t, weight: weight})
107	g.edges++
108}
109
110// AddUndirected records the same cost in both directions. It is two arcs and
111// counts as two against MaxEdges, because that is what it is.
112func (g *Graph) AddUndirected(a, b string, weight int) {
113	g.AddEdge(a, b, weight)
114	g.AddEdge(b, a, weight)
115}
116
117// Len returns the number of nodes.
118func (g *Graph) Len() int { return len(g.names) }
119
120// Edges returns the number of arcs. An AddUndirected call contributes two.
121func (g *Graph) Edges() int { return g.edges }
122
123// Names returns the node names in insertion order. The slice is a copy, so a
124// caller cannot reorder the graph's own index by sorting it.
125func (g *Graph) Names() []string {
126	out := make([]string, len(g.names))
127	copy(out, g.names)
128	return out
129}
130
131// Has reports whether the graph knows a node by that name.
132func (g *Graph) Has(name string) bool {
133	_, ok := g.index[name]
134	return ok
135}
136
137// Result holds one single-source run. It is a snapshot: mutating the graph
138// afterwards does not update it.
139type Result struct {
140	g      *Graph
141	src    int
142	dist   []int
143	prev   []int
144	done   []bool
145	order  []int
146	relaxs int
147}
148
149// From runs the search outward from source and returns the distances to every
150// node. It panics when source is not in the graph, because a typo'd source
151// silently returning "nothing is reachable" is the failure mode this package
152// exists to avoid.
153func (g *Graph) From(source string) *Result {
154	s, ok := g.index[source]
155	if !ok {
156		panic("dijkstra: unknown source: " + source)
157	}
158
159	n := len(g.names)
160	r := &Result{g: g, src: s}
161	r.dist = make([]int, n)
162	r.prev = make([]int, n)
163	r.done = make([]bool, n)
164	for i := 0; i < n; i++ {
165		r.dist[i] = Unreachable
166		r.prev[i] = -1
167	}
168
169	q := newQueue(n, r.dist)
170	r.dist[s] = 0
171	q.push(s)
172
173	for !q.empty() {
174		u := q.pop()
175		r.done[u] = true
176		r.order = append(r.order, u)
177		du := r.dist[u]
178
179		for _, a := range g.adj[u] {
180			v := a.to
181			if r.done[v] {
182				// Weights are non-negative, so a settled node can never be
183				// improved. This is the line a negative edge would break.
184				continue
185			}
186			cand := du + a.weight
187			if r.dist[v] == Unreachable {
188				r.dist[v] = cand
189				r.prev[v] = u
190				r.relaxs++
191				q.push(v)
192				continue
193			}
194			if cand < r.dist[v] {
195				// Strictly cheaper, never merely equal: a tie leaves the
196				// incumbent predecessor in place, which is what makes Path
197				// reproducible rather than dependent on arc order.
198				r.dist[v] = cand
199				r.prev[v] = u
200				r.relaxs++
201				q.decreased(v)
202			}
203		}
204	}
205	return r
206}
207
208// Source returns the node the run started from.
209func (r *Result) Source() string { return r.g.names[r.src] }
210
211// Dist returns the total weight of the cheapest route to name. ok is false for
212// a node no route reaches and for a name the graph does not know, which are
213// different mistakes with the same remedy: check Has first if you need to tell
214// them apart.
215func (r *Result) Dist(name string) (dist int, ok bool) {
216	i, known := r.g.index[name]
217	if !known || r.dist[i] == Unreachable {
218		return Unreachable, false
219	}
220	return r.dist[i], true
221}
222
223// Path returns the cheapest route to name, source first and name last. It
224// returns nil when no route reaches name, and a one-element slice for the
225// source itself.
226func (r *Result) Path(name string) []string {
227	i, known := r.g.index[name]
228	if !known || r.dist[i] == Unreachable {
229		return nil
230	}
231	var rev []int
232	for at := i; at != -1; at = r.prev[at] {
233		rev = append(rev, at)
234	}
235	out := make([]string, len(rev))
236	for k, at := range rev {
237		out[len(rev)-1-k] = r.g.names[at]
238	}
239	return out
240}
241
242// PathString renders Path joined with sep, or "" when there is no route. It
243// exists so a Render does not have to carry its own join loop.
244func (r *Result) PathString(name, sep string) string {
245	p := r.Path(name)
246	if p == nil {
247		return ""
248	}
249	return strings.Join(p, sep)
250}
251
252// Via returns the node immediately before name on the cheapest route, and
253// false for the source and for anything unreachable.
254func (r *Result) Via(name string) (string, bool) {
255	i, known := r.g.index[name]
256	if !known || r.dist[i] == Unreachable || r.prev[i] == -1 {
257		return "", false
258	}
259	return r.g.names[r.prev[i]], true
260}
261
262// Reachable returns how many nodes have a route, the source included.
263func (r *Result) Reachable() int {
264	return len(r.order)
265}
266
267// Order returns the nodes in the sequence the search settled them: the source
268// first, then always the closest node still outstanding. That sequence is the
269// algorithm, and a demo that shows it teaches more than one that prints only
270// the answer.
271func (r *Result) Order() []string {
272	out := make([]string, len(r.order))
273	for i, at := range r.order {
274		out[i] = r.g.names[at]
275	}
276	return out
277}
278
279// Relaxations returns how many arcs the run actually improved a distance with.
280// It is the honest cost figure: the arc count is what was looked at, this is
281// what was paid for.
282func (r *Result) Relaxations() int { return r.relaxs }