问题标签 [directed-acyclic-graphs]

好奇什么被认为是判断有向无环图强度的可靠算法/方法 - 特别是某些节点的强度。我对此的主要问题可以归结为以下两个图表：

（如果图表未显示，请单击此处或访问此链接：http ://www.flickr.com/photos/86396568@N00/2893003041/

在我看来，A 的地位比 A 强。我判断强度的依据是如果一个链接被击倒，一个节点可以保持多强。我称第一个为细“高跷”，第二个为粗“茎”。

以下是我目前考虑的判断节点强度的方法：

1）计算下面的节点数，减去上面的节点数。

• A=7, a=7, B=5, b=1

2）计算每个节点的完整路径（到终止）的数量，将它们的长度相加。

• A=17 (1+5+5+5+1), B=12 (4+4+4), a=9 (3+3+3), b=2
• 这使高跷更坚固，而不是茎。

3）计算每条可能的路径，将每个节点视为目的地。

• A=9 (A->B, A->C, A->D, A->E, A->G, 2xA->F, 2xA->H), B=6, a=9, b= 2

到目前为止，3 似乎是最好的选择，但有没有更好的、适用于 DAG 的通用选项？这是具有已知最佳方法的东西吗？原则是在图表中使用尽可能多的信息，并以直观的方式解释解决方案。

有没有办法让scons输出它内部生成的有向无环图？也许是graphviz格式？

如何检查有向图是否是无环的？算法是如何命名的？我会很感激参考。

我正在寻找一种算法来“反转”（反转？从里到外？）一个 DAG：

我使用的表示是不可变的，真正的 DAG（没有“父”指针）。我想以某种方式遍历图形，同时构建具有等效节点的“镜像”图形，但节点之间的关系方向倒置。

所以输入是一组“根”（这里是{A}）。输出应该是结果图中的一组“根”：{G, F}。（根是指没有传入引用的节点。叶子是没有传出引用的节点。）

输入的根变成输出的叶子，反之亦然。变换应该是自身的逆。

（出于好奇，我想向我用来表示 XML 以进行结构查询的库添加一个功能，通过它我可以将第一棵树中的每个节点映射到第二棵树中的“镜像”（然后返回再次）为我的查询规则提供更多的导航灵活性。）

我如何找到从单个源到所有最终目的地的最长路径，即对于源 i1，给出 i1 -> o1 和 i1 -> o2 之间的最长路径。

上图中描述的图例如下： (i1, i2) 是开始节点 (o1, o2) 是结束节点 (1-8) 是子图 边可能有 +ive/-ive 权重

该网络中最长的路径按以下顺序排列：

最差路径：i1 -> 1 -> 4 -> o1

然后，所有路径 i1 ... -> ... o1

然后 i1 -> 5 -> 6 -> o2

需要一种方法来忽略 (i1 -> 3) 或 (3 -> 4) 子网的选择，即使它们比 i1 -> 5 长

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

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

澄清更新

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

• A 没有依赖关系
• B 取决于 A、C 和 E
• C 取决于 A
• D 取决于 A
• E 取决于 C 和 A

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

- 一种

--+--B

-----+--C

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

--+--E

拓扑排序

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

• 一种
• 乙
• C
• D
• 乙

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

谢谢

罗汉

如何在 C 中实现这种数据结构？它是一种类似于 DAWG 的结构，但空间效率是 DAWG 的两倍，比仅压缩前缀的 trie 更有效。

我是GitX的作者。GitX 的功能之一是分支的可视化，可以在这里看到。

这种可视化当前是通过读取从 git 以正确顺序发出的提交来完成的。对于每个提交，父母都是已知的，因此以正确的方式建立通道相当容易。

我想通过使用我自己的提交池并自己线性化提交来加快这个过程。这允许我重用现有的已加载提交并允许 git 更快地发出提交，因为它不必以正确的顺序发出它们。

但是，我不确定使用什么算法来实现这一点。重要的是构建是增量的，因为提交的加载可能需要很长时间（100,000 次提交超过 5 秒，应该全部显示）。

Gitk 也是如此，这里有一个补丁说明了它是如何实现的，但是我的 TCL 技能很弱，而且补丁的注释不是很彻底，而且有点难以理解。

我还希望这个算法高效，因为它必须处理数十万次提交。它还必须显示在表格中，因此快速访问特定行很重要。

我将描述到目前为止的输入、我想要的输出和一些观察结果。

输入：

• 我有一个哈希表形式的当前提交池，将提交 ID 映射到提交对象。此池不必是完整的（具有所有必要的提交）
• 我在 git 的新提交中加载了一个单独的线程，每次加载新提交时都可以调用一个回调。没有保证提交的顺序，但在大多数情况下，下一个提交是前一个提交的父级。
• 一个提交对象有自己的修订 id 和所有其父对象的修订 id
• 我有一个应该列出的分支负责人列表。也就是说，没有应该显示的 DAG 的单个“顶部”。也不必有单个图根。

输出：

• 我需要按拓扑顺序线性化这些提交。也就是说，一个提交在其父项被列出之后不能被列出。
• 我还需要可以在上面的屏幕截图中看到的“分支线”。这些可能需要预先计算，因为它们中的大多数依赖于他们的孩子。

几点说明：

• 有必要重新定位提交列表。例如，我们可能必须提交不相关的提交（分支头），直到出现使一个头成为另一个头的祖先的提交。
• 必须显示多个分支提示
• 重要的是这个过程是增量的，以便在数据仍在加载时至少有部分视图可用。这意味着必须在中途插入新数据并且必须重新调整分支线。

我有一个 XML 文件，它对表示偏序的有向无环图 (DAG)进行编码 。这样的图对于指定依赖关系和查找关键路径等事情很有用。出于好奇，我当前的应用程序是为构建系统指定组件依赖项，因此顶点是组件，边指定编译时依赖项。这是一个简单的例子：

这个 DAG 可以这样绘制：

_{（来源：iparelan.com）}

我想应用一个XSLT 样式表来生成另一个 XML 文档，该文档只包含与偏序的最小元素相对应的顶点。也就是说，那些没有传入边的顶点。示例图的最小顶点集是{A, B, F}。对于我的构建依赖应用程序，找到这个集合很有价值，因为我知道如果我构建这个集合的成员，那么我的项目中的所有内容都将被构建。

这是我当前的样式表解决方案（我正在使用 Apache Ant 的xslt任务在 Java 上使用 Xalan 运行它）。directed-edge-to一个关键的观察是在任何元素中都不会引用最小顶点：

应用此样式表会产生以下输出（我认为这是正确的）：

问题是，我对这个解决方案并不完全满意。我想知道是否有一种方法可以将selectof thefor-each和testof theif与 XPath 语法结合起来。

我想写一些类似的东西：

但这并不符合我的要求，因为该current()函数没有引用外部//vertex表达式选择的节点。

到目前为止，我的解决方案使用XPath 1.0和XSLT 1.0语法，尽管我也对XPath 2.0和XSLT 2.0语法持开放态度。

如果您愿意，这是 Ant 构建脚本：

dot目标生成用于渲染图形的Graphviz Dot 语言 代码。这里是xml-to-dot.xsl：

维基百科：有向无环图

不确定叶节点是否仍然是正确的术语，因为它不是真正的树（每个节点可以有多个子节点，也可以有多个父节点），而且我实际上正在尝试找到所有根节点（这实际上只是语义问题，如果你反转所有边的方向，它们将是叶节点）。

现在我们只是遍历整个图（可以从指定的节点访问），但这有点贵，所以我想知道是否有更好的算法来做这件事。我在想的一件事是我们跟踪已经访问过的节点（在遍历不同的路径时）并且不重新检查这些节点。

还有其他算法优化吗？

我们还考虑过保留一个该节点是其后代的根节点的列表，但如果我们需要检查它是否在每次添加、移动或更改节点时都发生变化，那么维护这样一个列表似乎也会相当昂贵。删除。

编辑：

这不仅仅是查找单个节点，而是查找作为端点的所有节点。

也没有节点的主列表。每个节点都有一个它的子节点和它的父节点的列表。（嗯，这并不完全正确，但是提前从数据库中提取数百万个节点的成本非常高，并且可能会导致 OutOfMemory 异常）

编辑2：

可能会或可能不会改变可能的解决方案，但该图是最底层的，因为最多有几十个根节点（我试图找到）和数百万个（可能是数千万或数亿个）叶节点（我'我开始）。