C# 如何将有向无环图 (DAG) 转换为树

How to convert Directed Acyclic Graph (DAG) to Tree

提问by Rohan West

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

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

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、BC、D 和 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

• 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

---+--B

-----+--C

-----+----C

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

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

--+--E

---+---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

• 一种
• 乙
• C
• D
• 乙

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

罗汉

采纳答案by arnsholt

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)

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

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.

正如其他人指出的那样，您的问题的图形理论答案是 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!

祝你好运！

回答by Mitch Wheat

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

只有当所有子树都有一个根节点时才能这样做。

回答by MarkusQ

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 isa tree, so I'm afraid you need to clarify your question a bit.

此外，尚不清楚您要应用什么转换。连接的 DAG是一棵树，所以恐怕您需要稍微澄清一下您的问题。

回答by dsimcha

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 和树在数学上不是一回事。因此，任何转换都会引入歧义。根据定义，树没有周期，周期。

回答by arnsholt

What you're looking for, in order to find the order to load your modules in, is the Topological sortof 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 使得边从依赖的模块到依赖它们的模块（你可以通过反转上图中的所有边来得到这个），你可以只按照拓扑的顺序加载模块种类。

回答by Radio Controlled

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

答案是你想获得一棵生成树。这甚至是为无向图定义的，因此即使您有循环，您也可以忽略边的方向，获得无向图并获得后者的生成树。您需要哪种生成树取决于您，因为有很多可能性，例如最小生成树。

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

我正在寻找的是一种获得“冗余”生成树的算法，该生成树保留除“副本”节点之外的所有边。不幸的是，我还没有找到这个问题的名字，但我认为如果你自上而下并且没有迷路的循环，算法很简单。仍然为这个问题命名会很好，以便寻找现成的快速实现。

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

概括是有一个生成树的森林。