tree 29c4609795005a6ea517821013aef6b2e910d5ad
parent b565cc679cd5af598dc863890a3e1cce98eb1c57
author Lorenz Brun <lorenz@monogon.tech> 1680787615 +0200
committer Lorenz Brun <lorenz@monogon.tech> 1680791168 +0000

g/a/toposort: add bad reference validation

In a lot of cases where toposort is used to build dependency trees it
might be necessary to validate that the edges which make up the tree
do not reference nodes which are not present.

This is implemented by still implicitly creating nodes when AddEdge is
called, which allows arbitrary ordering of AddEdge/AddNode calls, but
on explicit calls to AddNode the node is also marked as being explicitly
added.
This information is later used to implement ImplicitNodeReferences which
returns all invalid references in the graph.

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