如何将有向无环图 (DAG) 转换为树 [英] How to convert Directed Acyclic Graph (DAG) to Tree

问题描述

我一直在寻找将 DAG 转换为树的 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?

澄清更新

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

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 依赖于 A、C 和 E
• C 依赖于 A
• D 依赖于 A
• E 取决于 C 和 A

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

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

--A

--+--B

-----+--C

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

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

--+--E

拓扑排序

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

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

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

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

谢谢

罗汉

推荐答案

对此有图形理论答案和程序员的答案.我假设您可以自己处理程序员部分.对于图论的答案:

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:

• DAG 是一组模块，A 需要 B，同时 B(或 B 需要的模块之一)需要 A，用模块的话说:没有循环依赖.我见过循环依赖的发生(在 Gentoo 论坛上搜索示例)，所以你甚至不能 100% 确定你有一个 DAG，但让我们假设你有.对循环依赖项进行检查并不难，因此我建议您在模块加载器中的某处进行检查.
• 在树中，永远不会发生的事情是 A 依赖于 B 和 C，而 B 和 C 都依赖于 D(菱形)，但这可能发生在 DAG 中.
• 此外，一棵树只有一个根节点，但 DAG 可以有多个根"节点(即不依赖任何模块).例如像 GIMP 这样的程序，GIMP 程序将是模块集的根节点，但对于 GENTOO，几乎所有具有 GUI 的程序都是根"节点，而库等则是它们的依赖项.(即 Konqueror 和 Kmail 都依赖于 Qtlib，但没有什么依赖于 Konqueror，没有什么依赖于 Kmail)

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

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

我无法将其显示为 ASCII-art 树，原因很简单，无法将其转换为树.但是，如果您想显示 A 所依赖的内容，则可以这样显示:

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

如您所见，您的树中会出现双重条目 - 在这种情况下，仅" D 但是如果您在 Gentoo 树上执行全部展开"，我向您保证您的树将有至少 1000 倍的数量节点，因为有模块.(至少有 100 个包依赖于 Qt，所以 Qt 依赖的所有东西都会在树中出现至少 100 次).

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.

上面树的缺点是，如果您单击打开 B，然后单击 D，您会看到 A 和 B 依赖于 D，但并不是说 C 也依赖于 D.但是，根据您的情况，这可能不是很重要 - 如果您维护已加载模块的列表，则在加载 C 时，您会看到您已经加载了 D，并且它不是为 C 加载的，而是为 B 加载的.它已加载，仅此而已事项.如果你动态维护直接依赖于某个模块的东西，你也可以处理相反的问题(卸载).

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 与 C 加载在同一个容器中，您将永远无法将 C 加载到与 C 相同的容器中好.或者你可能不得不忍受把所有东西都放在一个容器里(不是我完全理解你所说的加载到同一个容器"是什么意思)

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

祝你好运！

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