ordered descendant and ancestors improvements

[vtolstov]

For some dags some vertices can have the same order. For example ProjectCreate/NetworkCreate/ContactCreate can depends on AccountCreate, so first is Account create, but other in the same order. Does it possible to return [][]Vertex from Descendants and Ancestors ? This can be useful to parallel processing some vertices when it can be on the same order.

[vtolstov]

@sebogh do you have time for it or suggestions how the best to implement this?

[vtolstov]

if i'm write pr, can you merge it ?

[sebogh]

For some dags some vertices can have the same order. For example ProjectCreate/NetworkCreate/ContactCreate can depends on AccountCreate, so first is Account create, but other in the same order. Does it possible to return [][]Vertex from Descendants and Ancestors ? This can be useful to parallel processing some vertices when it can be on the same order.

Please elaborate (there is no order among the descendants of a DAG).

[vtolstov]

for example func OrderedDescendants returns in ordered descendants, but if i have two vertex that depends on the same another vertex it order is the same, so it can be executed in parallel.

[vtolstov]

gentle ping..

[ChristianKniep]

@vtolstov I am fooling around with DAGs and what I would want is an GetOrderedChildren(id string) []interface{}. Is that what you have asked here as well? For that I reckon vertex function to compare is required. Once that is done I'll wrap that around the GetChildren() function and order the result.

@sebogh Even though not needed for a DAG, do you reckon if I implement such a function you are willing to merge it?

[sebogh]

Hey, didn't look into it for some time. Sorry.

@vtolstov, probably it is me but I still don't understand what order you talk about. Is it "the time when a certain child was added"? If so, no! The DAG concept does not have such property - there is no ordering in direct children.

However, you may easily add any property to (all) your vertices that allows you to order them (including e.g. a timestamp).

And this seems to be where @ChristianKniep joins in. Yes, one could extend the implementation GetOrderedAncestors(), GetOrderedDescendants() etc. to consider an (optional) sorting function which, if provided, ensures direct children of a vertex are processed in this order.

I'm certainly happy to approve PRs.

[sebogh]

Thinking it over I guess what @vtolstov needs is to have GetOrderedAncestors() and GetOrderedDescendants() return a "subgraph" (which is somewhat related to #13).

[sebogh]

@vtolstov, @ChristianKniep the latest master (https://github.com/heimdalr/dag/commit/354d4ae9e40ad387e0ac8855a3ca8da0770e3052) implements GetAncestorsGraph() and GetDescendantsGraph():

https://github.com/heimdalr/dag/blob/354d4ae9e40ad387e0ac8855a3ca8da0770e3052/dag.go#L668-L675

and:

https://github.com/heimdalr/dag/blob/354d4ae9e40ad387e0ac8855a3ca8da0770e3052/dag.go#L655-L662

@vtolstov does that help in any way?

[vtolstov]

@vtolstov I am fooling around with DAGs and what I would want is an GetOrderedChildren(id string) []interface{}. Is that what you have asked here as well? For that I reckon vertex function to compare is required. Once that is done I'll wrap that around the GetChildren() function and order the result.

yes i mean something like this

[vtolstov]

mostly my question about this case

         yyyyy 
xxxx =>          =>  end
         zzzzz

when i'm traverse deep down in graph i want to know that yyyyy and zzzzz belongs to single xxxxx, and in my case (i'm execute this steps via grpc calls) i can call it in parallel (don't wait for completion, use WaitGroup) and after both of them completed go to end vertex

[vtolstov]

@ChristianKniep do you have any interest to add call to have []interface{} that you mean?