Stable ordered ancestors/descendants

[jeremybeard]

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]

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:

• dag/dag.go

  Line 596 in d38d4f9

  for parent := range d.inboundEdge[v] {

  and

• dag/dag.go

  Line 606 in d38d4f9

  for parent := range d.inboundEdge[top] {

I think.

[jeremybeard]

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]

hi, any chance to get this added?