tree 5d08ccdc172f131c99b7acaabb108d2d4d4ce53b
parent cf33f6805a7842a1aa7fac377468d9ca54f8d05b
author Lorenz Brun <lorenz@monogon.tech> 1678981796 +0100
committer Lorenz Brun <lorenz@monogon.tech> 1679311426 +0000

g/a/toposort: add topological sorting pkg

This adds a package which implements topological sorting.
There are existing Go packages out there which do this, but all of
them have various shortcomings, either in the API or in
performance or stability.

This uses a fairly simple DFS-based algorithm for doing the majority
of the work. It uses generics for the nodes to allow for flexibility and
is covered by a fuzz test to check for correctness.

Change-Id: I4ae3f0b97ef801350b87cdae3a3d9a1ba63830e3
Reviewed-on: https://review.monogon.dev/c/monogon/+/1351
Tested-by: Jenkins CI
Reviewed-by: Serge Bazanski <serge@monogon.tech>