我正在寻找一种可以存储任何 DAG 的数据结构，但可以有效地（即，在边/顶点的数量上以次线性方式）检测添加边是否会产生循环（从而防止您破坏非循环不变量）。有谁知道这样的事情？

谢谢！

让我们假设一个有问题的图是一个 DAG（有向无环图）。

问题：当且仅当只有一个顶点没有传入边时，我是否可以得出结论，这样的图将具有唯一的拓扑排序？

换句话说，只有一个没有传入边的顶点是必要的（但还不够）来生成唯一的拓扑排序吗？

假设我有一种可以编写的编程语言： x = f(g(1), h(1)) 在这种情况下，有向无环图将显示计算的依赖关系，就像在电子表格中一样（假设非递归表达式）：

这是一个简单的示例，但尝试在 DAG 中“压缩”更复杂的表达式变得有趣。这里的目标是根据依赖关系优化重新计算的次数。

有哪些算法和论文可用于处理这个问题？

我有一个修订哈希键。我想获得包含任何内容的最接近的修订版，但 .hgtags 除外。

例如，考虑 Mercurial 历史的以下片段：

在这种情况下，如果给定的版本是633cf1f61665，那么我正在寻找该版本9451e8f187b1，因为它是最接近的版本，它不仅包含 .hgtags，还包含其他内容。

在给定的情况下633cf1f61665，我如何9451e8f187b1使用尽可能少的 hg.exe 调用来定位？

编辑

我已经修复了输出，它应该显示来自同一分支的修订。

编辑2

我会试着解释一下自己。让我们定义两个概念：

• 一个沉闷的变更集 - 由hg tag操作创建的变更集。
• 一个有趣的变更集 - 任何非枯燥的变更集。

所以，我的问题可以改写如下：

例如，给定633cf1f61665或6cad328c622c或9451e8f187b1所需的修订是9451e8f187b1.

我正在寻找我们是否可以在 java 中拥有一个 DAWG api，这对于像我这样的爱好设计优化器可能具有很高的价值。

DAWG 是有向无环词图，它是一种存储词的高效内存机制。

因此，如果有人对 DAWG java API 或使用 LinkedHashMaps 实现 DAWG 有任何想法，请回答这个问题。

我需要在网页中显示有向无环图。我不是在寻找现成的库或解决方案。我正在寻找建议、建议或朝着正确的方向前进。

1. DAG 可视化

我不确定节点和关系将如何表示。可行的解决方案可能是 Treemaps、良好的旧节点和线或两者的组合。如果一个节点在屏幕上出现多次，我没有问题。

我不需要所有节点从一开始就出现在屏幕上。例如，用户可以通过双击或缩放来扩展节点。

我愿意接受所有的建议和意见。

2. 技术

实现必须具有一些功能：

• 拖放
• 飞涨
• 鼠标与节点交互的事件

从我的角度来看，我有 2 个选项（Flash 是不可能的）：

一个。HTML5 画布

缺点：没有向量，基本上只是一张图片；节点上没有隐式鼠标事件；

优点：速度；受欢迎程度；动画

湾。SVG

缺点：节点多时速度慢；

优点：矢量图形；元素在 DOM 中，所以你可以有事件等等；

C。HTML5 Canvas 和 SVG 的混合体

我从老师那里得到了一些我们应该用来测试程序的输入文件。任务是从文件中读取，创建有向图并打印输出。但是如果有一个循环，我们应该终止程序。

我有一些名为house1 和house2 的文件。在文件 house1 中没有任何循环，但在 house2 中有。但我不知道为什么我的程序找不到那个循环。在这里我有所有的代码，任何关于我应该在哪里看的帮助都是珍贵的:)

我试图弄清楚如何使用节点图来处理一组数据。它适用于处理声音数据的应用程序，就像你有一堆吉他踏板一样。您有一些具有预定义过程的节点在有向图中相互连接。每个节点轮流处理数据，当一个节点完成后，它会向下一个节点发出信号以执行此操作。这个想法是您使用 ui 将这些节点拼凑在一起。

我正在使用 Qt 来创建 UI，因此我正在查看它的文档以查看是否有可以用于上述问题的东西。我找到了 Qt 状态机，从我能读到它似乎在做我需要的事情，进入一个状态，你做一些处理，当它完成时给出一个完成的信号，并且图中的下一个状态开始. 此外，您可以嵌套状态，让我能够通过组合现有节点来创建新节点，这似乎是一个有吸引力的想法。

然而，创建状态机是为了改变小部件的属性（改变它们的状态），而不是为了包装过程。例如，一个按钮被按下并且状态机改变另一个小部件的状态，例如，如果按钮被释放，则状态被交换回来。

因此，任何对 Qt、状态机或节点图处理有更多经验的人都可以给我一个提示，是否调整状态机来包装我的程序是否会起作用。或者，如果我可以使用 Qt 库中的其他内容？

在“使用 Gradle 构建和测试”一书中有一张 DAG 的图片，我不明白，也没有得到很好的解释。

DAG 图片包含像“projects”、“dependencies”、“clean”、“help”、“tasks”和“properties”这样的节点，它们是独立的，不参考其他节点。

1）我认为在有向图中节点必须有引用（边）。那是错的吗？

2) 另一个问题是：这些独立节点是否是 DAG 的“属性”或“帮助”部分？

不幸的是，我无法将该图像上传到这个问题。

我对类似的主题进行了搜索，但是对于我的理解和理解水平而言，答案太模糊了，而且我认为它们对我的问题不够具体。

类似的线程：
树（有向无环图）实现
表示一个DAG（有向无环图）

问题：

我已经格式化了一个文本文件，其中包含以下格式的数据...
示例数据集：
GO:0000109#is_a: GO:0000110#is_a: GO:0000111#is_a: GO:0000112#is_a: GO:0000113#is_a: GO :0070312#is_a: GO:0070522#is_a: GO:0070912#is_a: GO:0070913#is_a: GO:0071942#part_of: GO:0008622
GO:0000112#part_of: GO:0000442
GO:00000168#is_a: GO: #is_a: GO:0034967#is_a: GO:0070210#is_a: GO:0070211#is_a: GO:0070822#is_a: GO:0070823#is_a: GO:0070824
GO:0000120#is_a: GO:0000500#is_a: GO: 0005668#is_a: GO:0070860
GO:0000123#is_a: GO:0005671#is_a: GO:0043189#is_a: GO:0070461#is_a: GO:0070775#is_a: GO:0072487
GO:0000126#is_a: GO#0 is_a: GO:0034733
GO:0000127#part_of: GO:0034734#part_of: GO:0034735
GO:0000133#is_a: GO:0031560#is_a: GO:0031561#is_a: GO:0031562#is_a: GO:0031563#part_of: GO:0031500
GO:0000137#part_of: GO:0000136

我希望从这些数据中构建一个加权的有向 DAG（上面只是一个片段）。106kb的整个数据集在这里：Source

--------------------------------------------------

逐行考虑，每行数据说明如下... 以
第一行为例：
GO:0000109#is_a: GO:0000110#is_a: GO:0000111#is_a: GO:0000112#is_a : GO:0000113#is_a: GO:0070312#is_a: GO:0070522#is_a: GO:0070912#is_a: GO:0070913#is_a: GO:0071942#part_of: GO:0008622

'#' 是行数据的分隔符/标记器。
第一项，GO:0000109 是节点名称。
is_a: GO:xxxxxxx OR part_of: GO:xxxxxxx 后面的项是连接到 GO:0000109 的节点。
如数据集中所述，随后的一些术语也有联系。
当为is_a时，边的权重为0.8。
为part_of时，边的权重为0.6。

--------------------------------------------------

我有关于 DAG 的 Google-d，我理解这个概念。但是，我仍然不知道如何将其放入代码中。我正在使用 Java。
据我了解，图通常由节点和弧组成。这个图是否需要邻接表来确定连接的方向？如果是这样，我不确定如何结合图形和邻接表来相互通信。构建完图后，我的次要目标是从根节点中找出每个节点的度数。数据集中有一个根节点。

为了说明，我画了下面第一行数据的连接示例：
图片链接

我希望你们能理解我在这里想要达到的目标。感谢您浏览我的问题。:)