Add dag package

[bufdev]

Competing idea to #2138.

This started as a vendoring of https://github.com/stevenle/topsort with proper license attribution, plus some cleanups to more closely match our code standards, but evolved into more functionality and more cleanups. We can edit this as we want for our needs. It's a super-simple package, and this is a universal concept.

@unmultimedio any thoughts about starting with this as a base?

[bufdev]

I've spent some more time on this in support of the direct-deps branch, and I think this is the better way to go here - it's more full-fledged now, and is mostly up to our standards.

[unmultimedio]

I've spent some more time on this in support of the direct-deps branch, and I think this is the better way to go here - it's more full-fledged now, and is mostly up to our standards.

Sure! Let's go with this one if you see it works as we need it. What I'm missing from this package (probably I'm not thinking it or checking it through), are these two:

1. how to sort a complete graph, w/out giving it any starting point, something like: sort the whole tree, return the sorted modules on it. Useful for workspace push or sync managed modules. Probably it's enough to add everything under the same "root", and then request to have the "root" node sorted.
2. are non-dependent nodes in the tree lexicographically sorted or any other way to they're deterministic?

[bufdev]

1. how to sort a complete graph, w/out giving it any starting point, something like: sort the whole tree, return the sorted modules on it. Useful for workspace push or sync managed modules. Probably it's enough to add everything under the same "root", and then request to have the "root" node sorted.

Isn't that just:

graph := NewGraph()
graph.Add("root") // whatever your concept of the starting point is
graph.TopoSort("root")

?

2. are non-dependent nodes in the tree lexicographically sorted or any other way to they're deterministic?

I don't understand the question, can you clarify?

[unmultimedio]

1. Yeah, that should be enough, thx
2. If a->b, a->c is graph.Sort("a") always b, c, a? or is the order non-deterministic? Because c, b, a is also a valid topological sort.

[bufdev]

Order is always deterministic, it uses the sort order of the keys, so it will be b, c, a.