render_example_test.gno

 1package dijkstrademo
 2
 3// ExampleRender pins the realm Render output as a testable example.
 4//
 5// The block below is copied verbatim from what gno printed, never hand typed:
 6// every distance and every ordering in it is computed by the library under
 7// test, so a change in the search shows up here as a diff rather than as
 8// prose.
 9func ExampleRender() {
10	print(Render(""))
11	// Output:
12	// # Dijkstra
13	//
14	// The cheapest route from one node to every other node of a weighted graph, demoing the [`p/moul/x/daily/dijkstra`](/p/moul/x/daily/dijkstra/v0) library.
15	//
16	// ## The network
17	//
18	// Arcs are one-way. 7 nodes, 7 arcs, searched from `depot`.
19	//
20	// | from | to | cost |
21	// | --- | --- | --- |
22	// | depot | north | 2 |
23	// | depot | east | 4 |
24	// | north | east | 1 |
25	// | north | ridge | 3 |
26	// | east | port | 6 |
27	// | ridge | port | 3 |
28	// | port | beacon | 2 |
29	//
30	// `quarry` is in the graph with no arcs at all.
31	//
32	// ## Cheapest route to each node
33	//
34	// | node | distance | arrives via | route |
35	// | --- | --- | --- | --- |
36	// | depot | 0 | source | depot |
37	// | north | 2 | depot | depot -> north |
38	// | east | 3 | north | depot -> north -> east |
39	// | ridge | 5 | north | depot -> north -> ridge |
40	// | port | 8 | ridge | depot -> north -> ridge -> port |
41	// | beacon | 10 | port | depot -> north -> ridge -> port -> beacon |
42	// | quarry | unreachable |  |  |
43	//
44	// Two of those rows are the point of the algorithm. `east` is reachable directly for 4, and the answer is 3, through `north`. `port` is first offered at 9 by `east`, and ends at 8 through `ridge`, which the search only discovers two settlements later.
45	//
46	// ## The order the search settles nodes
47	//
48	// Always the closest node still outstanding, never the next one along an arc. That is the whole difference from a breadth-first walk, and it is why a cheap long way round still wins.
49	//
50	// | step | settles | at distance |
51	// | --- | --- | --- |
52	// | 1 | depot | 0 |
53	// | 2 | north | 2 |
54	// | 3 | east | 3 |
55	// | 4 | ridge | 5 |
56	// | 5 | port | 8 |
57	// | 6 | beacon | 10 |
58	//
59	// 6 of 7 nodes were reached, in 7 improvements. An arc that is looked at and rejected costs a comparison; only an improvement costs a write.
60	//
61	// ## Ties, and why a realm should care
62	//
63	// Three spokes, all 5 away from the hub. Nothing in the distances separates them, so something else has to, and that something must not be map iteration order: a `Render` that reshuffled between validating nodes would be a consensus bug, not a cosmetic one.
64	//
65	// | declared | settle order |
66	// | --- | --- |
67	// | west, south, crater | hub -> west -> south -> crater |
68	// | crater, south, west | hub -> crater -> south -> west |
69	//
70	// The tie resolves to the order the graph was built in, and nothing else. Build it the same way twice and you get the same page twice.
71	//
72	// ## What it will not do
73	//
74	// A negative arc panics at `AddEdge`, where the caller can still fix it. Accepting one would not return an error later, it would return a confident wrong answer: the search never revisits a settled node, so a negative arc pointing back at one is simply never seen.
75	//
76	// | limit | value | why |
77	// | --- | --- | --- |
78	// | `MaxNodes` | 512 | the frontier holds at most one entry per node, so this bounds memory |
79	// | `MaxEdges` | 4000 | arcs bound the work, not the memory |
80	// | negative arc | panics | the algorithm's precondition, not a simplification |
81	// | self-loop | panics | it can never shorten a path, so it is a caller mistake |
82	//
83	// Both caps are small on purpose. This is a routing table for a realm, not a road atlas, and a caller that can state the worst case up front can price the gas before it sends the transaction.
84}