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 (354d4ae) implements GetAncestorsGraph() and GetDescendantsGraph():

dag/dag.go

Lines 668 to 675 in 354d4ae

	// GetAncestorsGraph returns a new DAG consisting of the vertex with id id and
	// all its ancestors (i.e. the subgraph). GetAncestorsGraph also returns the id
	// of the (copy of the) given vertex within the new graph (i.e. the id of the
	// single leaf of the new graph). GetAncestorsGraph returns an error, if id is
	// empty or unknown.
	//
	// Note, the new graph is a copy of the relevant part of the original graph.
	func (d *DAG) GetAncestorsGraph(id string) (*DAG, string, error) {

and:

dag/dag.go

Lines 655 to 662 in 354d4ae

	// GetDescendantsGraph returns a new DAG consisting of the vertex with id id and
	// all its descendants (i.e. the subgraph). GetDescendantsGraph also returns the
	// id of the (copy of the) given vertex within the new graph (i.e. the id of the
	// single root of the new graph). GetDescendantsGraph returns an error, if id is
	// empty or unknown.
	//
	// Note, the new graph is a copy of the relevant part of the original graph.
	func (d *DAG) GetDescendantsGraph(id string) (*DAG, string, error) {

@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?