如何将有向无环图（DAG）转换为树

I have been looking for C# examples to transform a DAG into a Tree.

我一直在寻找C#示例来将DAG转换为树。

Does anyone have an examples or pointers in the right direction?

有没有人有正确方向的例子或指针?

Clarification Update

I have a graph that contains a list of modules that my application is required to load. Each module has a list of modules it depends on. For example here are my modules, A, B C, D and E

我有一个图表,其中包含我的应用程序需要加载的模块列表。每个模块都有一个依赖的模块列表。例如,这里是我的模块,A,B C,D和E.

A has no dependencies

A没有依赖关系

B depends on A, C and E

B取决于A,C和E.

C depends on A

C取决于A.

D depends on A

D取决于A.

E depends on C and A

E取决于C和A.

I want resolve dependencies and generate a tree that looks like this...

我想要解决依赖关系并生成一个看起来像这样的树...

--A

--+--B

-----+--C

---------+--D

--+--E

Topological Sort

Thanks for the information, if I perform a Topological sort and reverse the output i will have the following order

感谢您的信息,如果我执行拓扑排序并反转输出,我将按以下顺序

I want to maintain the hierarchical structure so that my modules are loaded into the correct context, for example... module E should be in the same container as B

我想维护层次结构,以便我的模块加载到正确的上下文中,例如...模块E应该与B在同一个容器中

Thanks

Rohan

5 个解决方案

#1

There's the graph theoretical answer and the programmer's answer to this. I assume you can handle the programmers part yourself. For 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.

DAG是一组模块,它永远不会发生A需要B,同时,B(或模块B需要的一个)需要A,在模块中说:没有循环依赖。我已经看到循环依赖发生了(搜索Gentoo论坛的例子),所以你甚至不能100%确定你有DAG,但我们假设你有。检查循环依赖关系并不是很难,所以我建议你在模块加载器的某个地方这样做。

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.

在树中,永远不会发生的事情是A取决于B和C,B和C都依赖于D(钻石),但这可能发生在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)

此外,树只有一个根节点,但DAG可以有多个“根”节点(即没有任何依赖的模块)。例如,像GIMP这样的程序,GIMP程序将是模块集的根节点,但对于GENTOO,几乎任何具有GUI的程序都是“根”节点,而库等是它们的依赖性。 (I.E. Konqueror和Kmail都依赖于Qtlib,但没有任何东西取决于Konqueror,也没有任何东西取决于Kmail)

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

正如其他人所指出的那样,Graph对你的问题的理论答案是DAG不能转换为树,而每棵树都是DAG。

However, (high-level programmers answer) if you want the tree for graphical representations, you're only interested in the dependencies of a specific module, not what's depending on that module. Let me 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 ASCII-art tree, for the simple reason that this can't be converted into a tree. However, if you want to show what A depends on, you can show this:

我无法将其显示为ASCII艺术树,原因很简单,因为它无法转换为树。但是,如果要显示A所依赖的内容,可以显示以下内容:

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

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

如你所见,你在树中得到了双重条目 - 在这种情况下“只有”D但如果你在Gentoo树上做“全部展开”,我保证你的树至少有1000倍的节点数量有模块。 (至少有100个依赖于Qt的软件包,因此Qt所依赖的所有内容都将在树中至少出现100次)。

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

如果您有一个“大”或“复杂”树,最好不要提前动态扩展树,否则您可能会有一个内存密集型进程。

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

上面这棵树的缺点是,如果你点击打开B,然后是D,你会看到A和B依赖于D,但不是C也依赖于D.但是,根据你的情况,这可能并不重要 - 如果你维护一个已加载模块的列表,在加载C时你会看到你已经加载了D,并且没有为C加载它没关系,但对于B.它被加载,这一切都很重要。如果你动态维护直接依赖于某个模块的东西,你也可以处理相反的问题(卸载)。

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

但是,你不能用树做的就是你的最后一句话:保留拓扑顺序,即如果B加载到与C相同的容器中,你也永远不会在同一个容器中加载C.或者你可能不得不忍受把所有东西放在一个容器里(不是我完全理解你的意思是“加载到同一个容器中”)

Good luck!

#2

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

DAG和树在数学上不是一回事。因此,任何转换都会引入歧义。根据定义,树没有周期,周期。

#3

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

您要查找的是为了找到加载模块的顺序,是您的DAG的拓扑类型。如果边缘从一个模块转到它所依赖的模块(我认为最有可能),你将不得不按照拓扑排序的相反顺序加载模块,因为模块将出现在所有模块之前取决于它。

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

如果您表示DAG使得边缘从依赖于模块的模块转移到依赖于它们的模块(您可以通过反转上图中的所有边缘来实现这一点),您可以按照拓扑的顺序加载模块分类。

#4

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

这在很大程度上取决于您如何代表您的DAG。例如,它可以是一个邻接矩阵(如果从节点i到节点j的边缘为A [i,j] = 1,则为0),或者作为指针系统,或者作为节点数组和数组边缘....

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

此外,还不清楚您尝试应用的转换。连接的DAG是一棵树,所以我担心你需要澄清一下你的问题。

#5

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

如果所有子树都有一个根节点,则只能这样做。

#1