dijkstrademo.gno

  1// Package dijkstrademo is a small gnoweb demo of the shortest-path search
  2// provided by the [p/moul/x/daily/dijkstra](/p/moul/x/daily/dijkstra/v0)
  3// library: the cheapest route to every node, the order the search settles
  4// them in, and the tie-break that makes both reproducible.
  5//
  6// It contains no search logic of its own. Stateless, so Render is
  7// deterministic: every figure below comes from the fixed graphs declared at
  8// the top of this file, never from chain state, which is what lets an example
  9// test pin the page.
 10package dijkstrademo
 11
 12import (
 13	"strconv"
 14	"strings"
 15
 16	"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/kit/ui/v0"
 17	"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/daily/dijkstra/v0"
 18)
 19
 20// link is one arc of the worked example: a small directed delivery network
 21// where the obvious route is the wrong one twice over.
 22type link struct {
 23	from, to string
 24	cost     int
 25}
 26
 27var network = []link{
 28	{"depot", "north", 2},
 29	{"depot", "east", 4},
 30	{"north", "east", 1},
 31	{"north", "ridge", 3},
 32	{"east", "port", 6},
 33	{"ridge", "port", 3},
 34	{"port", "beacon", 2},
 35}
 36
 37// The source of the worked example, and a node nothing reaches, to show that
 38// unreachable is an answer rather than an error.
 39const (
 40	source   = "depot"
 41	isolated = "quarry"
 42)
 43
 44// fanout is the determinism example: one hub, three spokes, all at the same
 45// cost. Which one settles first is decided by the order they were declared
 46// in, never by a map.
 47var fanout = []string{"west", "south", "crater"}
 48
 49// Render renders the demo for gnoweb.
 50//
 51//	Render("") / Render("/") -> the full demo
 52func Render(path string) string {
 53	var b strings.Builder
 54
 55	b.WriteString("# Dijkstra\n\n")
 56	b.WriteString("The cheapest route from one node to every other node of a ")
 57	b.WriteString("weighted graph, demoing the ")
 58	b.WriteString("[`p/moul/x/daily/dijkstra`](/p/moul/x/daily/dijkstra/v0) library.\n\n")
 59
 60	g := dijkstra.New()
 61	for _, l := range network {
 62		g.AddEdge(l.from, l.to, l.cost)
 63	}
 64	g.AddNode(isolated)
 65	r := g.From(source)
 66
 67	b.WriteString("## The network\n\n")
 68	b.WriteString("Arcs are one-way. ")
 69	b.WriteString(strconv.Itoa(g.Len()) + " nodes, " + strconv.Itoa(g.Edges()))
 70	b.WriteString(" arcs, searched from `" + source + "`.\n\n")
 71	nt := ui.NewTable("from", "to", "cost")
 72	for _, l := range network {
 73		nt.Row(ui.Cell(l.from), ui.Cell(l.to), strconv.Itoa(l.cost))
 74	}
 75	b.WriteString(nt.String() + "\n")
 76	b.WriteString("`" + isolated + "` is in the graph with no arcs at all.\n\n")
 77
 78	b.WriteString("## Cheapest route to each node\n\n")
 79	rt := ui.NewTable("node", "distance", "arrives via", "route")
 80	for _, n := range g.Names() {
 81		d, ok := r.Dist(n)
 82		if !ok {
 83			rt.Row(ui.Cell(n), "unreachable", "", "")
 84			continue
 85		}
 86		via, hasVia := r.Via(n)
 87		if !hasVia {
 88			via = "source"
 89		}
 90		rt.Row(ui.Cell(n), strconv.Itoa(d), ui.Cell(via), route(r.Path(n)))
 91	}
 92	b.WriteString(rt.String() + "\n")
 93	b.WriteString("Two of those rows are the point of the algorithm. `east` is ")
 94	b.WriteString("reachable directly for 4, and the answer is 3, through ")
 95	b.WriteString("`north`. `port` is first offered at 9 by `east`, and ends at ")
 96	b.WriteString("8 through `ridge`, which the search only discovers two ")
 97	b.WriteString("settlements later.\n\n")
 98
 99	b.WriteString("## The order the search settles nodes\n\n")
100	b.WriteString("Always the closest node still outstanding, never the next ")
101	b.WriteString("one along an arc. That is the whole difference from a ")
102	b.WriteString("breadth-first walk, and it is why a cheap long way round ")
103	b.WriteString("still wins.\n\n")
104	ot := ui.NewTable("step", "settles", "at distance")
105	for i, n := range r.Order() {
106		d, _ := r.Dist(n)
107		ot.Row(strconv.Itoa(i+1), ui.Cell(n), strconv.Itoa(d))
108	}
109	b.WriteString(ot.String() + "\n")
110	b.WriteString(strconv.Itoa(r.Reachable()) + " of " + strconv.Itoa(g.Len()))
111	b.WriteString(" nodes were reached, in " + strconv.Itoa(r.Relaxations()))
112	b.WriteString(" improvements. An arc that is looked at and rejected costs ")
113	b.WriteString("a comparison; only an improvement costs a write.\n\n")
114
115	b.WriteString("## Ties, and why a realm should care\n\n")
116	b.WriteString("Three spokes, all 5 away from the hub. Nothing in the ")
117	b.WriteString("distances separates them, so something else has to, and ")
118	b.WriteString("that something must not be map iteration order: a `Render` ")
119	b.WriteString("that reshuffled between validating nodes would be a ")
120	b.WriteString("consensus bug, not a cosmetic one.\n\n")
121	tt := ui.NewTable("declared", "settle order")
122	tt.Row(names(fanout), route(settleFanout(fanout)))
123	reversed := reverse(fanout)
124	tt.Row(names(reversed), route(settleFanout(reversed)))
125	b.WriteString(tt.String() + "\n")
126	b.WriteString("The tie resolves to the order the graph was built in, and ")
127	b.WriteString("nothing else. Build it the same way twice and you get the ")
128	b.WriteString("same page twice.\n\n")
129
130	b.WriteString("## What it will not do\n\n")
131	b.WriteString("A negative arc panics at `AddEdge`, where the caller can ")
132	b.WriteString("still fix it. Accepting one would not return an error ")
133	b.WriteString("later, it would return a confident wrong answer: the ")
134	b.WriteString("search never revisits a settled node, so a negative arc ")
135	b.WriteString("pointing back at one is simply never seen.\n\n")
136	lt := ui.NewTable("limit", "value", "why")
137	lt.Row("`MaxNodes`", strconv.Itoa(dijkstra.MaxNodes),
138		"the frontier holds at most one entry per node, so this bounds memory")
139	lt.Row("`MaxEdges`", strconv.Itoa(dijkstra.MaxEdges),
140		"arcs bound the work, not the memory")
141	lt.Row("negative arc", "panics", "the algorithm's precondition, not a simplification")
142	lt.Row("self-loop", "panics", "it can never shorten a path, so it is a caller mistake")
143	b.WriteString(lt.String() + "\n")
144	b.WriteString("Both caps are small on purpose. This is a routing table ")
145	b.WriteString("for a realm, not a road atlas, and a caller that can state ")
146	b.WriteString("the worst case up front can price the gas before it sends ")
147	b.WriteString("the transaction.\n")
148
149	return b.String()
150}
151
152// route joins a path with an arrow. Each node name is escaped on its own and
153// the separator never is: running the whole joined string through the
154// escaper would turn the arrows into a literal backslash soup, which is the
155// bug this spelling exists to avoid.
156func route(path []string) string {
157	if len(path) == 0 {
158		return ""
159	}
160	cells := make([]string, len(path))
161	for i, n := range path {
162		cells[i] = ui.Cell(n)
163	}
164	return strings.Join(cells, " -> ")
165}
166
167// names renders a declaration order as a comma-separated list, escaped the
168// same way.
169func names(in []string) string {
170	cells := make([]string, len(in))
171	for i, n := range in {
172		cells[i] = ui.Cell(n)
173	}
174	return strings.Join(cells, ", ")
175}
176
177// settleFanout builds the hub-and-spoke graph with the spokes declared in the
178// given order and returns the order the search settles them in.
179func settleFanout(spokes []string) []string {
180	g := dijkstra.New()
181	g.AddNode("hub")
182	for _, s := range spokes {
183		g.AddNode(s)
184	}
185	for _, s := range spokes {
186		g.AddEdge("hub", s, 5)
187	}
188	return g.From("hub").Order()
189}
190
191// reverse copies a slice back to front. Written out rather than imported
192// because there is no sensible shared home for three lines of it.
193func reverse(in []string) []string {
194	out := make([]string, len(in))
195	for i, s := range in {
196		out[len(in)-1-i] = s
197	}
198	return out
199}