heimdalr / dag

Yet another directed acyclic graph (DAG) implementation in golang.
BSD 3-Clause "New" or "Revised" License
185 stars 35 forks source link

Stable ordered ancestors/descendants #21

Open jeremybeard opened 2 years ago

jeremybeard commented 2 years ago

I'm looking to produce a list of the vertices of a DAG, where a vertex in the list is somewhere after all of its ancestors, but where the list doesn't change across calls. I can use getLeaves and getOrderedAncestors to fairly easily produce the list without walking the graph myself, but the list can change across calls because sibling vertices are not ordered.

Would a getStableOrderedAncestors and getStableOrderedDescendants make sense here? Analogous to sort.Sort and sort.Stable. The sibling vertices could perhaps be ordered by comparing IDs.

seboghpub commented 2 years ago

Hey @jeremybeard, I think, that shouldn't be to hard. For (e.g.) GetOrderedAncestors() to return "stable" slices, one would only need to sort in:

I think.

jeremybeard commented 2 years ago

I took a quick stab (ignore the auto-formatting from my IDE) at it, and that looks right to me.

Is this something you'd like to be contributed? I tried to roll the change into walkAncestors with a new bool parameter, but the existing unstable iteration over vertices is done on a map, whereas the sorted vertices is a slice, so I'm not sure how to elegantly combine the two without a performance hit to the unstable case.

vtolstov commented 1 month ago

hi, any chance to get this added?