Search Apps Documentation Source Content File Folder Download Copy Actions Download State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

v0 source pure

Package toposort orders a dependency graph so that every node comes after everything it depends on — the "install the...

Readme View source

gno.land/p/moul/x/daily/toposort/v0

Topological sort of a dependency graph — New, FromPairs, Add, DependOn, Sort, CycleNodes, Nodes, DependenciesOf, String.

Orders a graph so every node comes after everything it depends on — the "install these packages in a safe order" problem — using Kahn's algorithm.

1import "gno.land/p/moul/x/daily/toposort/v0"
2
3g := toposort.FromPairs([][2]string{
4    {"realm", "ui"}, {"ui", "markdown"}, {"markdown", "strings"},
5})
6order, err := g.Sort()   // ["strings" "markdown" "ui" "realm"], nil

Deterministic by construction. Among nodes that become ready at the same time, the lexicographically smallest is always emitted first, so a given graph has exactly one possible answer regardless of insertion order. Adjacency is kept in sorted slices and no map is ever iterated — Go/gno map iteration order is unspecified, and a realm whose Render reshuffled between identical calls would be a bug.

A cycle is reported, not hidden: Sort returns ErrCycle along with the partial order it managed, and CycleNodes names the nodes still stuck so a caller can say exactly which dependencies are tangled.

Edge cases: a self-dependency is ignored as a trivial cycle but the node stays in the graph; duplicate edges collapse; empty names are rejected; Nodes and DependenciesOf return copies, so a caller cannot mutate the graph through them.

Live demo: r/moul/x/daily/toposortdemo · render it at /r/moul/x/daily/toposortdemo/v0.

Part of moul/gno-contracts — moul's versioned gno.land contracts. See the repository for the full catalog, build/test tooling, and usage.

🧪 Highly experimental — potentially vibe-coded. Not audited; may break, change, or be removed at any time. Do not use with anything of value. Full disclaimer: DISCLAIMER.

Overview

Package toposort orders a dependency graph so that every node comes after everything it depends on — the "install these packages in a safe order" problem — as a pure, reusable package.

It uses Kahn's algorithm, and it is *deterministic*: ready nodes are always taken in lexicographic order, so a given graph always yields the exact same ordering. That matters on-chain, where a Render that reshuffled between identical calls would be a bug. Adjacency is kept in sorted slices rather than maps for the same reason — Go/gno map iteration order is unspecified.

A cycle is reported as an error naming the nodes still stuck, rather than panicking or silently dropping them.

A live demo of this package is at r/moul/x/daily/toposortdemo(/r/moul/x/daily/toposortdemo/v0).

Variables 1

var ErrCycle 

1var ErrCycle = errors.New("toposort: graph has a cycle")
source

ErrCycle is returned by Sort when the graph is not a DAG. Use CycleNodes to recover which nodes are involved.

Functions 2

func FromPairs 

1func FromPairs(pairs [][2]string) *Graph
source

FromPairs builds a Graph from "node depends on dep" pairs. Each pair is {node, dep}. Handy for tests and literal declarations.

func New 

1func New() *Graph
source

New returns an empty Graph.

Types 1

type Graph

struct 
1type Graph struct {
2	nodes []string            // every known node, kept sorted and unique
3	deps  map[string][]string // node -> the nodes it depends on (sorted, unique)
4}
source

Graph is a directed dependency graph. The zero value is not usable — build one with New.

Methods on Graph

func Add

method on Graph 
1func (g *Graph) Add(node string)
source

Add registers a node with no dependencies. Adding twice is a no-op; it is how you declare a leaf that nothing depends on.

func CycleNodes

method on Graph 
1func (g *Graph) CycleNodes() []string
source

CycleNodes returns the nodes that could not be ordered — i.e. those on or downstream of a cycle — in lexicographic order. Empty when the graph is a DAG.

func DependOn

method on Graph 
1func (g *Graph) DependOn(node, dep string)
source

DependOn records that node depends on dep, so dep must come first. Both endpoints are registered. A self-dependency is ignored (it would be a trivial cycle and is never what the caller means). Duplicate edges collapse.

func DependenciesOf

method on Graph 
1func (g *Graph) DependenciesOf(node string) []string
source

DependenciesOf returns node's direct dependencies, sorted.

func Len

method on Graph 
1func (g *Graph) Len() int
source

Len returns how many nodes the graph holds.

func Nodes

method on Graph 
1func (g *Graph) Nodes() []string
source

Nodes returns every node in lexicographic order.

func Sort

method on Graph 
1func (g *Graph) Sort() ([]string, error)
source

Sort returns the nodes ordered so every node follows its dependencies.

Among nodes that are simultaneously ready, the lexicographically smallest is emitted first, which makes the result unique for a given graph. On a cycle it returns ErrCycle along with the partial order computed so far.

func String

method on Graph 
1func (g *Graph) String() string
source

String renders the graph as "node <- dep1, dep2" lines, sorted. Useful for debugging and for demos.

Imports 3

  • errors stdlib
  • sort stdlib
  • strings stdlib

Source Files 3