CODEWITHSUNDEEP
graphgraph-theorydirected-acyclic-graphsleast-common-ancestor
Glaze
Glaze

Reputation: 11

Splitting a Directed Acyclic Graph (DAG) into components, then finding root and last child in those components

I want to split a graph into its components (like in the example DAG below. Note the colored identifiers of each node as they represent the components). After I've found the components in the picture I want to find the root and last child of that component. Take the blue component for example, the root is E and the last child is H. Green: root B - last child H.

Example graph: Example Graph

If you can find a connection between E-H, B- E, B-H, A-I without splitting it into components. Let me know, as that is my final goal.

About the compiling of components. That is actually my final goal. I just wanted to include that to maybe get you a better understanding of what I'm trying to achieve. This can be don't once I find these connections.

Questions I found helpful but not answered my question:

(These answers might be sufficient but I don't know how to implement it)

Note:

// Big edit: Reworked the question to make it more clear what I want. Introduced components as I might think that will be more helpful.

Upvotes: 1

Views: 2873

Answers (1)

MT0
MT0

Reputation: 167981

Too long for a comment but I don't think you are finding all the common ancestors:

From wikipedia:

In graph theory and computer science, the lowest common ancestor (LCA) of two nodes v and w in a tree or directed acyclic graph (DAG) is the lowest (i.e. deepest) node that has both v and w as descendants, where we define each node to be a descendant of itself (so if v has a direct connection from w, w is the lowest common ancestor).

If you consider the LCA of the parents then there are 4 parents of vertex H which are C, D, F and G then you can consider the LCA to be the values for any pair of parents:

  • LCA( C, D ) = B
  • LCA( C, F ) = C
  • LCA( C, G ) = C
  • LCA( D, F ) = D
  • LCA( D, G ) = D
  • LCA( F, G ) = E

so, the LCAs of the parents of H are B, C, D and E.

The common ancestors will be the lowest common ancestor(s) and their ancestors - so A, B, C, D and E.

You need to address why A, C and D are being excluded as common ancestors.

Upvotes: 0

Related Questions