disjointsetdemo.gno

 1// Package disjointsetdemo is a small gnoweb demo of the union-find structure
 2// provided by the [p/moul/x/daily/disjointset](/p/moul/x/daily/disjointset/v0)
 3// library: it merges a fixed list of pairs and shows the resulting partition.
 4//
 5// It contains no union-find logic of its own. Stateless, so Render is
 6// deterministic — and the library's Partition is order-independent, which is
 7// what makes the output safe to pin.
 8package disjointsetdemo
 9
10import (
11	"strconv"
12	"strings"
13
14	"gno.land/p/moul/x/daily/disjointset/v0"
15)
16
17// n is the universe size; pairs are the merges applied, in order.
18const n = 10
19
20var pairs = [][2]int{{0, 1}, {2, 3}, {1, 3}, {5, 6}, {7, 8}, {8, 9}}
21
22func build() *disjointset.DisjointSet {
23	d := disjointset.New(n)
24	for _, p := range pairs {
25		d.Union(p[0], p[1])
26	}
27	return d
28}
29
30// Render renders the demo for gnoweb.
31func Render(path string) string {
32	d := build()
33
34	var b strings.Builder
35	b.WriteString("# Union-Find\n\n")
36	b.WriteString("Disjoint-set forest with path compression and union by rank, demoing the ")
37	b.WriteString("[`p/moul/x/daily/disjointset`](/p/moul/x/daily/disjointset/v0) library.\n\n")
38
39	b.WriteString("## Merges applied\n\n")
40	for _, p := range pairs {
41		b.WriteString("- `Union(")
42		b.WriteString(strconv.Itoa(p[0]))
43		b.WriteString(", ")
44		b.WriteString(strconv.Itoa(p[1]))
45		b.WriteString(")`\n")
46	}
47
48	b.WriteString("\n## Partition of [0, ")
49	b.WriteString(strconv.Itoa(n))
50	b.WriteString(")\n\n**")
51	b.WriteString(strconv.Itoa(d.Groups()))
52	b.WriteString("** groups:\n\n")
53	for _, g := range d.Partition() {
54		b.WriteString("- `{")
55		nums := []string{}
56		for _, x := range g {
57			nums = append(nums, strconv.Itoa(x))
58		}
59		b.WriteString(strings.Join(nums, ", "))
60		b.WriteString("}`\n")
61	}
62
63	b.WriteString("\n> Groups come out sorted, ordered by their smallest member, ")
64	b.WriteString("so the partition is identical whatever order the merges arrive in.\n")
65	return b.String()
66}