问题标签 [directed-acyclic-graphs]

我正在寻找一种简单的方法来表示文件中的简单依赖项。最好我想使用一些已经定义了语法的格式（例如 JSON、YAML 等）。我倾向于graphviz的点语法

还有其他方法可以做到这一点吗？

这将供用户在应用程序中编写简单的依赖项并由其解析。

查询类似于

返回所有顶点，使得（可从（A 和（B 或 C）））和（不可从（D 和 E））。

可以使用任何类型的可达性布尔约束来形成查询。

有没有快速执行此查询的有效方法？除了实际找到所有项目可达关注点的集合之外，那么这些集合上的并集、交集和集减法呢？

我试图找到一个有向无环图的宽度......由一个任意排序的节点列表表示，甚至没有邻接列表。

图形/列表用于类似 GNU Make 的并行工作流管理器，它使用文件作为执行顺序的标准。每个节点都有一个源文件和目标文件列表。我们有一个哈希表，因此，给定一个文件名，可以确定生成它的节点。这样，我们可以通过使用该表检查生成每个源文件的节点来确定节点的父节点。

这是我在这一点上唯一的能力，没有严重改变代码。该代码已经公开使用了一段时间，我们最不想做的就是显着改变结构并发布一个糟糕的版本。不，我们没有时间进行严格的测试（我在学术环境中）。理想情况下，我们希望我们可以做到这一点，而不会做任何比向节点添加字段更危险的事情。

我将发布一个社区 wiki 答案，概述我当前的方法及其缺陷。如果有人想编辑它，或将其用作起点，请随意。如果我可以做任何事情来澄清事情，我可以在需要时回答问题或发布代码。

谢谢！

编辑：对于任何关心的人，这将在 C 中。是的，我知道我的伪代码在一些非常糟糕的 Python 外观中。我有点希望语言并不重要。

一段时间以来，我正在使用一种算法，该算法以复杂度 O(V + E) 运行，以在有向无环图上从 A 点到 B 点找到最大路径，这包括进行洪水填充以查找可以从哪些节点访问注意 A，以及每个节点有多少个“父节点”（来自其他节点的边）。然后，我做了一个 BFS，但只在我已经使用了它的所有“父节点”时才“激活”一个节点。

这个算法有什么特别的名字吗？我把它告诉了一个信息学教授，他只是把它叫做“DAG 上的最大路径”，但是当你说“我用 Fenwick 树解决了第一个问题，用 Dijkstra 解决了第二个问题，用 Dijkstra 解决了第三个问题时，这听起来并不好最大路径”。

我的理解是，在make执行时，它会在内部生成一个 DAG 来表示项目中的所有依赖项。有没有办法得到那个 DAG 并绘制它，比如使用 graphviz 之类的东西？

我在 Ubuntu 8.04 上使用 gnu make。

编辑

我刚刚遇到了这些名为mamdag和mamdot的工具。他们应该与nmake和gnu make一起工作，但我似乎找不到让gnu make吐出mam文件的选项。

它可以在这里下载- 这些包：

初始化
ast-base
ast-gpl

刚刚发现 AT&T 的 Glenn Fowler 的这篇文章描述了 MAM 语言和 mamdot 工具。

似乎您必须修补 gnu make 才能使其正常工作，尽管我还不是 100% 确定。

也许还有另一种方式？

在 Floyd–Warshall/Dijkstra 回复洪水到来之前，请让我解释一下情况，因为我确信任何一种算法都可以针对这种情况进行调整，并且必须如此，因为这不是一个玩具示例程序（请注意，在 java所以必须保持它在内存方面的可管理性）

我所拥有的是从节点 0 到节点 n 生成的网络图，节点 3 无法链接到节点 5，因为当节点 3 选择它的外链接时节点 5 不存在。每个“节点”都表示为 in_neighbours[nodeID] 和 out_neighbours[nodeID] 表示 nodeId=3，所以我们谈论的是节点 3。还要注意 in_/out_ 都已排序，（in_ 自然排序为 5 将选择它的 out 链接一次全部，只有这样 6 才会选择 out_links，因此 3 的 in_ 永远不能包含 {6, 5, 7}) 并且 ofc 都可以包含重复项。（in/out 是大小为 n 的 ArrayList 数组，其中 out_ 的大小始终为 d 或 m，与 n 一起由用户在启动时指定）

没有重量。我必须做的是找到averageDistance()

到目前为止，我所拥有的是最好的情况。注意我只想找到 j & i 之间的距离，而不是同时找到所有距离（内存不足，将在 m=20 d=1 000 000 时进行测试）

所以我问如果“更新鲜”（ofc 此时图表已完成）节点 i 是否直接链接到它的任何老伙伴，如果是这样，距离是 1 跳。

如果节点向后遍历，它只是我还是“最短”路径将始终是第一个找到的路径？

我如何检查它是否不是 1，基本情况之后的“else”？我的数学相当薄弱，请温柔:) 任何提示如何利用链接已排序的事实？

这不是家庭作业或我试图欺骗的东西，它与代码本身无关，这必须是一个有用的工具，“学习”是一路走来的。

以下是图的外观 nodeID，out links，in links for m=7 n=13，（注意 0 个周期就是图的初始化方式）：

抱歉读了这么久。 编辑：方法中的代码错误，这是我现在认为正确的。

修改 dist nr2，试试看是否有路径：

可能重复：
[python]：两个节点之间的路径

谁能指出一些有关如何执行此操作的资源？我正在networkx用作我的python库。

谢谢！

我有一个无环有向图。我想以一种方式为每个顶点分配级别，以保证如果边（v1，v2）在图中，那么级别（v1）>级别（v2）。如果 level(v1) = level(v3) 每当 (v1,v2) 和 (v3,v2) 在图表中时，我也想要它。此外，可能的水平是离散的（不妨将它们视为自然数）。理想的情况是当 (v1,v2) 在图中并且没有从 v1 到 v2 的其他路径时 level(v1) = level(v2) + 1，但有时在其他约束条件下这是不可能的 -例如，考虑一个具有五个顶点的图，其边为 (a,b) (b,d) (d,e) (a,c) (c,e)。
有谁知道一个体面的算法来解决这个问题？我的图表相当小（|V| <= 25 左右），所以我不需要快速的东西——简单更重要。

到目前为止，我的想法是找到一个最小元素，将其指定为 0 级，找到所有父级，将它们指定为 1 级，并通过在适当的顶点上添加 +0.5 来解决矛盾，但这看起来很糟糕。

另外，我觉得删除所有“隐式”边可能会有所帮助（即，如果图形同时包含（v1，v2）和（v2，v3），则删除（v1，v3）。

我有一个大的有向无环图（DAG），我想根据以下标准有效地从中绘制一个样本节点：

1. 我指定了一个永远不能被采样的固定节点 A
2. 直接或间接引用 A 的节点永远不会被采样
3. 所有其他节点以相等的概率进行采样

节点存储为带有指向它们所引用的其他节点的指针的对象，整个图可以从直接或间接引用其他所有内容的单个根节点到达。

有没有一个好的算法来做到这一点？理想情况下不需要大量额外内存，因为 DAG 很大！

我有一个大的有向无环图，我想在位图图像中可视化。

理想情况下，我希望所有根节点都位于图像顶部，所有叶节点都位于底部，即图形边缘都指向向下。

是否有一种很好的算法可以计算出满足这些约束的所有节点的坐标并产生良好的可视化效果？