Ruby's TSort topological sort & strongly connected components in pure Go — MRI-compatible, no cgo.
go-ruby-tsort is a pure-Go (no cgo) reimplementation of Ruby's TSort standard library — topological sorting and strongly connected components over an arbitrary directed graph, using Tarjan's algorithm exactly as MRI 4.0.5's tsort.rb does. TSort interprets any object as a graph through two callbacks — one that yields every node, one that yields a node's children — and this package models that functionally: you supply the two iterators and get back the sorted nodes (or the SCCs). Component grouping, internal ordering and the reverse-topological emission order all match MRI byte-for-byte, including the quirks (a self-loop is a single-node SCC and does not raise; the TSort::Cyclic message is topological sort failed: [...]). It was extracted from rbgo into a reusable standalone library: no dependency on the Ruby runtime, the dependency runs the other way. It is the topological-sort backend for go-embedded-ruby, bound by rbgo as a native module just like go-ruby-regexp, go-ruby-erb and go-ruby-yaml — differential-tested against MRI, 100% coverage, CI green across 6 arches and 3 OSes.
TSort(nodes, children) returns the nodes sorted children-first (a depends-on b → b precedes a), raising *Cyclic on a real cycle (an SCC of size ≥ 2) with MRI’s exact topological sort failed: [...] message — while a self-loop, being a size-1 SCC, returns normally.
StronglyConnectedComponents(nodes, children) returns Tarjan SCCs in reverse topological order; each component’s internal order is its DFS-discovery order, matching MRI byte-for-byte.
EachStronglyConnectedComponent and the …From(start, …) variant that walks only the subgraph reachable from a start node and never enumerates the full node set — the iterator shapes of tsort.rb.
Options.Identity decides node equality (Ruby’s eql?/hash) so a host like rbgo can plug in boxed Ruby objects; Options.Inspect renders nodes for the Cyclic message, with a built-in Ruby-style #inspect for the numeric tower, strings, Symbol, booleans, nil and arrays.
The whole port follows MRI 4.0.5’s tsort.rb exactly — component grouping, each component’s ordering and the reverse-topological emission order all match, including the quirk that a self-loop does not raise.
A corpus of fixed and deterministically-random digraphs sorted both here and by the system ruby (TSort.tsort, strongly_connected_components, each_strongly_connected_component_from), TSort::Cyclic messages included, compared byte-for-byte; 100% coverage, gofmt + go vet clean, green across all six 64-bit Go arches and three OSes.
A faithful port of Ruby's TSort in pure Go, cgo disabled, so it cross-compiles and embeds anywhere. It returns nodes sorted children-first, computes Tarjan strongly connected components in reverse topological order, and offers the iterator and …From forms, with host-supplied node identity and inspect. Validated differentially against the system ruby binary — sorted nodes, SCC structure and TSort::Cyclic messages compared byte-for-byte. It is a standalone, reusable module extracted from rbgo's internals, and the topological-sort backend for the sibling org github.com/go-embedded-ruby.