1

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:

  • Please post all example code in C++ or C# (if you're going to post example code)

  • This is my first question. If I've done something wrong please let me know.

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

Community
  • 1
  • 1
Glaze
  • 11
  • 5
  • I've been searching for the answer for 2 days prior to this question and will continue. Will obviously post the answer if I find one! – Glaze Apr 27 '16 at 12:00
  • Do you want to compute the LCA for _all_ parents of your start node ( this might not produce a result for graphs with multiple minimal elements) or do you search for the _closest_ node that is a LCA to at least 2 parents of your start node (this might have several solutions). To see the difference, add edges `(C,H), (D,H)` to your sample graph - would the desired result be `E` or `B` for start node `H`? – collapsar Apr 27 '16 at 17:17
  • Thank you for your comment! Really good point! I will update the graph and question to a more complex graph to show exactly what I want. – Glaze Apr 27 '16 at 18:15
  • I currently have a shitty but working algorithm. I'll post the answer when I've improved it. – Glaze Apr 28 '16 at 06:58
  • Doesn't `H` have three common ancestors: `E`, `B` and `A` (since all paths inbound to `H` can be backtracked to reach all 3 of those vertices)? Similarly for `E` isn't its common ancestors `B` and `A`? – MT0 Apr 28 '16 at 09:28
  • With that logic H should have a connection to C, G, F and G too? That's not what I want. – Glaze Apr 28 '16 at 09:56
  • I think you're logic is flawed, or I'm not getting your point.. Think of it as subsystems E-F-G-H is a subsystems and B-C-D-H and B-C-D-E and A-B-C-D-E-F-G-H-I. Reading the subsystems, E and H has a connection, also B-H, B-E, A-I – Glaze Apr 28 '16 at 10:02

1 Answers1

0

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.

MT0
  • 143,790
  • 11
  • 59
  • 117
  • First off. Thank you so much for taking the time to fix my problem. You know what! I was writing to explain how you're wrong. But you're right. As i can find a two connections from `H` to `C` through F-E-C and G-E-C. That means that they're "connected". I will update the graph once more! – Glaze Apr 28 '16 at 11:01
  • @Glaze What you are doing appears to be finding "biconnected components" of a directed acyclic graph... So from `B` to `H` there are (at least) two distinct paths `B -> C -> H` and `B -> D -> H` where there are no common edges between the paths and the only common vertices are the end-points. `A` to `H` does not have these two distinct paths as all the paths will contain edge `A -> B` and vertex `B`. – MT0 Apr 28 '16 at 12:45
  • Googling for biconnected components I found that is exactly what I want. After I've split up the graph into biconnected components I can easily find those connections that I'm looking for. Maybe you can write an answer like "You're actually looking for biconnected components" and I'll mark it answered. As that is what the question actually calls for. Btw, that was what I was talking about when I mentioned "subsystems". – Glaze Apr 28 '16 at 13:45
  • Reworked the question. Could you please take a look at it. It would mean so much! @MT0 – Glaze Apr 29 '16 at 07:36