如何将有向无环图 (DAG) 转换为树
我一直在寻找将 DAG 转换为树的 C# 示例。
有人有正确方向的例子或指针吗？
澄清更新
我有一个图表，其中包含我的应用程序需要加载的模块列表。 每个模块都有一个它所依赖的模块列表。 例如，这是我的模块 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 位于同一个容器中
谢谢
罗汉
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
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
这是图论答案和程序员的答案。 我想你可以自己处理程序员部分。 对于图论答案：
正如其他人指出的那样，您的问题的图理论答案是 DAG 不能转换为树，而每个树是一个 DAG。
但是，（高级程序员回答）如果您想要树进行图形表示，您只对特定模块的依赖关系感兴趣，而不是依赖于该模块的内容。 让我举个例子：
我无法将其显示为 ASCII-art 树，原因很简单，它无法转换为树。
但是，如果您想显示 A 所依赖的内容，您可以显示以下内容：
正如您所看到的，您在树中获得了双重条目 - 在本例中“仅”D 但如果您在 Gentoo 树上执行“全部展开”，我向您保证，您的树的节点数量至少是模块数量的 1000 倍。 （至少有 100 个包依赖于 Qt，因此 Qt 依赖的所有内容都将在树中至少出现 100 次）。
如果您有一个“大”或“复杂”树，最好动态扩展树，而不是提前，否则您可能会遇到非常占用内存的过程。
上面树的缺点是，如果您单击打开 B，然后单击 D，您会看到 A 和 B 依赖于 D，但不会看到 C 也依赖于 D。但是，根据您的情况，这可能根本不重要- 如果您维护已加载模块的列表，则在加载 C 时，您会看到已经加载了 D，并且没有为 C 加载，但为 B 加载并不重要。它已加载，这才是最重要的。 如果动态维护直接依赖于某个模块的内容，也可以处理相反的问题（卸载）。
然而，你不能用树做的是你最后一句话中的内容：保留拓扑顺序，即如果 B 与 C 加载到同一个容器中，你将永远无法将 C 加载到同一个容器中。 或者您可能不得不忍受将所有东西放入一个容器中（并不是说我完全理解“装入同一个容器”的意思）
祝您好运！
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:
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:
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:
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 和树不是同一件事。 因此，任何转换都会带来歧义。 根据定义，树没有循环、周期。
A DAG and a tree are not the same thing mathematically. Thus, any conversion introduces ambiguity. A tree by definition has no cycles, period.
为了找到加载模块的顺序，您正在寻找的是 拓扑排序< /a> 你的 DAG。 如果边缘从一个模块到它所依赖的模块（我认为这是最有可能的），则必须以拓扑排序的相反顺序加载模块，因为一个模块将出现在所有模块之前这取决于什么。
如果您表示 DAG，使得边从依赖的模块到依赖它们的模块（您可以通过反转上图中的所有边来得到这一点），您可以按照拓扑的顺序加载模块种类。
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.
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。 例如，它可以是一个邻接矩阵（如果从节点 i 到节点 j 存在一条边，则 A[i,j] = 1，否则为 0），或者作为指针系统，或者作为节点数组和数组边缘....
此外，尚不清楚您要应用什么转换。 连接的 DAG 是一棵树，所以恐怕您需要稍微澄清一下您的问题。
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....
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.
答案是你想要获得一个生成树。 这甚至是为无向图定义的，因此即使有环，您也可以忽略边的方向，获得无向图并获得后者的生成树。 您需要哪种生成树取决于您，因为存在多种可能性，例如最小生成树。
我正在寻找一种算法来获得“冗余”生成树，该生成树保留所有边缘但“复制”节点。 不幸的是，我还没有找到这个问题的名称，但我认为如果你自上而下地进行算法，那么这个算法是很简单的，并且没有循环可以迷失。不过，最好给这个问题一个名字，这样寻找现成的快速实施。
概括来说就是拥有一个由生成树组成的森林。
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.
仅当所有子树都有一个根节点时才可以这样做。
You can only do that if all subtrees have a single root node.