如何将定向非循环图（DAG）转换为树 [英] How to convert Directed Acyclic Graph (DAG) to Tree

问题描述

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

澄清更新

我有一个包含我的应用程序需要加载。每个模块都有一个它所依赖的模块列表。例如，这里是我的模块A，BC，D和E

• A没有依赖关系


• B取决于A，C和E


• C取决于A


• D取决于A


• E取决于C和A

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

- A

- + - B

----- + - C

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

- + - E

拓扑排序

感谢信息，如果我执行拓扑排序并反转输出，我将具有以下顺序

• A


• B


• C


• D


• E

我想保持层次结构，以便将我的模块加载到正确的上下文中，例如...模块E应该在与B
相同的容器中

谢谢

Rohan

解决方案

有图形理论答案和程序员的答案。我假设你可以自己处理程序员。对于图形理论答案：

• DAG是一组模块，它不会发生A需要B，同时， B（或其中一个模块B需要）需要A，在模块中说：无循环依赖。我看到循环依赖发生（搜索Gentoo论坛的例子），所以你甚至不能100％确定你有一个DAG，但让我们假设你有。对循环依赖性进行检查并不是很困难，所以建议您在模块加载程序中的某个位置进行。


• 在树中，永远不会发生的事情是A取决于B和C，B和C都取决于D（钻石），但这可能发生在DAG中。


• 另外，一棵树只有一个根节点，但是DAG可以有多个根节点（即没有依赖的模块）。例如像GIMP这样的程序，GIMP程序将是模块集合的根节点，但对于GENTOO，几乎任何带有GUI的程序都是根节点，而库等则是依赖关系的。 （IE的Konqueror和Kmail依赖于Qtlib，但没有任何依赖于Konqueror，没有任何依赖于Kmail）

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

然而，（高级程序员答案）如果你想要树的图形表示，你只对某个特定模块的依赖性感兴趣，而不是依赖于该模块。让我举个例子：

  A取决于B和C 
 B取决于D和E 
 C取决于D和F 
  

我不能将其显示为ASCII艺术树，因为简单的原因，这不能转换成一棵树。
但是，如果要显示A取决于什么，您可以显示：

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

如你所见，你在树中获得双重条目 - 在这种情况下，只有只D，但是如果你在Gentoo树上做一个展开所有，我保证你的树至少有有1000个节点的数量，因为有模块。 （至少有100个软件包依赖于Qt，所以Qt所依赖的一切将在树中至少存在100次）。

如果你有一个大或复杂树，最好是动态扩展树，而不是提前，否则可能会有一个非常内存密集的过程。

上面的树是，如果你点击打开B，然后D，你看到A和B依赖于D，但不是也取决于D.但是，根据你的情况，这可能不是很重要 - 如果你维护一个加载的模块的列表，加载C你看到你已经加载了D，并没有关系，它没有为C加载，但是B.它被加载，这是重要的。如果你动态地维护什么直接取决于某个模块，你可以处理相反的问题（卸载）。

然而，你不能用一棵树是你最后一句话中的内容：保留拓扑顺序，即如果B与C一样加载在同一个容器中，那么您永远也不会在同一个容器中加载C。或者你可能必须把所有东西放在一个容器中（不是我完全明白你的意思是装入同一个容器）

祝你好运！

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

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 has no dependencies
• B depends on A, C and E
• C depends on A
• D depends on A
• E depends on C and 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

• A
• B
• C
• D
• E

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

Thanks

Rohan

解决方案

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.
• 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 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.

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:

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).

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.

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")

Good luck!

这篇关于如何将定向非循环图（DAG）转换为树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！