[ACCEPTED]-How to convert Directed Acyclic Graph (DAG) to Tree-directed-acyclic-graphs

Accepted answer
Score: 25

There's the graph theoretical answer and 48 the programmer's answer to this. I assume 47 you can handle the programmers part yourself. For 46 the graph theorethical answer:

  • A DAG is a set of modules where it never happens that A needs B, and at the same time, B (or one of the modules B needs) needs A, in modules-speak: no circular dependency. I've seen circular dependencies happen (search the Gentoo forums for examples), so you can't even be 100% sure you have a DAG, but let's assume you have. It it not very hard to do a check on circular dependencies, so I'd recommend you do so somewhere in your module loader.
  • In a tree, something that never can happen is that A depends on B and C and that both B and C depend on D (a diamond), but this can happen in a DAG.
  • Also, a tree has exactly one root node, but a DAG can have multiple "root" nodes (i.e. modules that nothing depends on). For example a program like the GIMP, the GIMP program will be the root node of the set of modules, but for GENTOO, almost any program with a GUI is a "root" node, while the libraries etc are dependencies of them. (I.E. both Konqueror and Kmail depend on Qtlib, but nothing depends on Konqueror, and nothing depends on Kmail)

The Graph 45 theorethical answer to your question, as 44 others pointed out, is that a DAG can't 43 be converted to a tree, while every tree 42 is a DAG.

However, (high-level programmers 41 answer) if you want the tree for graphical 40 representations, you're only interested 39 in the dependencies of a specific module, not 38 what's depending on that module. Let me 37 give an example:

A depends on B and C
B depends on D and E
C depends on D and F

I can't show this as an 36 ASCII-art tree, for the simple reason that 35 this can't be converted into a tree. However, if 34 you want to show what A depends on, you 33 can show this:

A
+--B
|  +--D
|  +--E
+--C
   +--D
   +--F

As you see, you get double 32 entries in your tree - in this case "only" D 31 but if you do an "expand all" on the Gentoo 30 tree, I guarantee you that your tree will 29 have at least 1000 times the amount of nodes 28 as there are modules. (there are at least 27 100 packages that depend on Qt, so everything 26 Qt depends on will be present at least 100 25 times in the tree).

If you have a "large" or 24 "complex" tree, It might be best to expand 23 the tree dynamically, not in advance, otherwise 22 you might have a very memory-intensive process.

The 21 disadvantage of the tree above is that if 20 you click open B, then D, you see that A 19 and B depend on D, but not that also C depends 18 on D. However, depending on your situation, this 17 might not be important at all - if you maintain 16 a list of loaded modules, on loading C you 15 see that you have loaded D already, and 14 it doesn't matter it wasn't loaded for C, but 13 for B. It is loaded, that's all that matters. If 12 you dynamically maintain what directly depends 11 on a certain module, you can handle the 10 opposite problem (unloading) as well.

However, what 9 you can't do with a tree is what's in your 8 final sentence: preserve topological order, i.e. if 7 B gets loaded in the same container as C, you'll 6 never get to load C in the same container 5 as well. Or you might have to be put up 4 with putting everything in one container 3 (not that I fully understand what you mean 2 with "loading into the same container")

Good 1 luck!

Score: 5

A DAG and a tree are not the same thing 3 mathematically. Thus, any conversion introduces 2 ambiguity. A tree by definition has no 1 cycles, period.

Score: 2

What you're looking for, in order to find 13 the order to load your modules in, is the 12 Topological sort of your DAG. If the edges go from a module 11 to the modules it depends on (which I think 10 is the most likely), you'll have to load 9 the modules in the reverse order of the 8 topological sort because a module will appear 7 -before- all the modules on which it depends.

If 6 you represent the DAG such that the edges 5 go from the depended on modules to the modules 4 that depend on them (you can get this by 3 reversing all the edges in the graph above), you 2 can just load the modules in the order of 1 the topological sort.

Score: 1

It depends a lot on how you are representing 8 your DAG. For example, it could be an adjacency 7 matrix (A[i,j] = 1 if there's an edge from 6 node i to node j, else 0), or as a system 5 of pointers, or as an array of nodes and 4 an array of edges....

Further, it's not clear 3 what transformation you're trying to apply. A 2 connected DAG is a tree, so I'm afraid you 1 need to clarify your question a bit.

Score: 1

The answer is that you want to obtain a 17 spanning tree. This is even defined for undirected graphs, so 16 even if you have cycles you could ignore 15 the direction of the edges, obtain an undirected 14 graph and get the spannign tree of the latter. Which 13 spanning tree you need is up to you as there 12 are many possibilities, e.g. minimum spanning trees.

What I was 11 looking for is an algorithm to obtain a 10 'redundant' spanning tree that keeps all 9 edges but 'copies' nodes. Unfortunately 8 I have not yet found what is the name for 7 this, but I think the algorithm is straightforward 6 if you go top-down and there are no cycles 5 to get lost in. Still it would be good to 4 have a name for this problem so as to look 3 for ready-made fast implementations.

The 2 generalization would be to have a forest 1 of spanning trees.

Score: 0

You can only do that if all subtrees have 1 a single root node.

More Related questions