Algorithm to find a hierarchy tree in a directed acyclic graph?

Question

I have a graph with properties as shown below:

Adjacency Matrix:

Graph Representation:

Which algorithm can be applied to find a hierarchy tree of the above graph? In my words, a hierarchy tree is one in which nodes are connected and directed towards their immediate child only and any edge from current to child of child or any other should be removed.

For the above graph, a hierarchy tree would look like the following:

Hierarchy Tree:

Can you please reupload the images? It says that the first two aren't available. — Danstahr, Sep 27 '13 at 08:00
Images should be uploaded to StackOverflow (well, technically imgur) in case external links go down. Click on "Add image" when [edit]ing the page and point it to a file stored on your computer or online. — Bernhard Barker, Sep 27 '13 at 08:07
@luiso1979 As I read it, all edges to non-child ancestors should be removed. — Bernhard Barker, Sep 27 '13 at 09:58
@luiso1979 [Ancestors](http://www-math.ucdenver.edu/~wcherowi/courses/m4408/glossary.html#Ancestor) which aren't [children](http://www-math.ucdenver.edu/~wcherowi/courses/m4408/glossary.html#Child). 5 isn't an ancestor of 4, thus 4-5 shouldn't be removed. 6-5 is the only edge from a node to its non-child ancestor (5 is 6's ancestor, but not its child). — Bernhard Barker, Sep 27 '13 at 10:19
Sorry, I was confusing ancestor and descendant. I meant "non-child descendants". — Bernhard Barker, Sep 28 '13 at 10:44

score 6 · Accepted Answer · edited May 23 '17 at 11:46

6

I think Transitive Reduction is what you're looking for. Check this one : https://cs.stackexchange.com/questions/7096/transitive-reduction-of-dag

Implementation Link

edited May 23 '17 at 11:46

Community

1
1

answered Sep 27 '13 at 10:08

Danstahr

4,190
22
38

Algorithm to find a hierarchy tree in a directed acyclic graph?

1 Answers1