问题标签 [directed-acyclic-graphs]

我有一个有数千个顶点和边的 DAG。

我正在寻找能够以最人性化/最美观的方式将顶点定位在网格点上的算法。我的预感是最好的布局将类似于具有最小边长总和的布局。

您能否指出这种最小边长布局总和的有效算法，或者可以帮助我解决这个问题的其他算法？

这是一个非常幼稚的算法的部分输出：

我问了一个关于在没有重复字符的可变数量集中查找子序列的问题。解决方案是为每对字母创建一个矩阵，丢弃每组中没有出现的字母，然后在有向无环图中找到最长的路径。但是，我不想要最长的路径，我想要几条最长的路径（例如，如果它生成长度为 10、10、9、8、8、3、3、2 和 1 的子序列，我可能想要仅显示前 5 个子序列）。

因此，由于我不只寻找最长的路径，为了生成结果子序列，而不是使用维基百科文章中描述的最长路径算法，我使用的是一种简单的算法，它只是生成一个列表可能的子序列。这会生成一组类似于我之前问题的答案中的结果。

问题是我想减少它生成的子序列的数量。

例如，如果我有以下集合：

...我的算法目前将提出每组中出现的以下对：

这在技术上是正确的，但我想消除其中一些对。例如，注意2总是在 之后1。因此，我想消除A2andB2对（即A并且B永远不应该直接跳转到2......他们应该总是先通过1）。此外，1永远不要跳到除 之外的任何数字2，因为2总是紧跟在它之后。此外，请注意和0之间总是如何发生，所以我想消除这对（同样，应该总是在它跳转到 之前经过，因为所有集合都有这三个字母的位置：）。B3B3B03B < 0 < 3

为了清楚起见，当前的算法将提出这些子序列：（A为简洁起见，我只包括那些以开头的子序列）：

......所有标记的*都应该被淘汰。

生成所需子序列的（正确）对将是：

...并且子序列的完整列表将是：

换句话说，我试图从这个有向无环图出发：

对此：

我应该使用什么样的算法/逻辑来摆脱这些无关的对（即图形边缘）？还是您认为我首先生成配对的逻辑是应该改变的？

给定一个有向循环图，我如何获得代表输入图的各种 DAG/树？实际上，我想从给定的电路（有向和循环）图中提取各种树。

这是我的问题：我有一个（非空但可能不是不同的）集合 s_i 的序列 S，并且对于每个 s_i，需要知道 S（i ≠ j）中有多少个集合 s_j 是 s_i 的子集。

我还需要增量性能：一旦我有了所有的计数，我可以用 s_i 的某个子集替换一组 s_i 并逐步更新计数。

使用纯函数式代码执行所有这些将是一个巨大的优势（我在 Scala 中编写代码）。

由于集合包含是部分排序，我认为解决我的问题的最佳方法是构建一个 DAG，它表示集合的 Hasse 图，边表示包含，并将一个整数值连接到每个节点，表示节点下面的子 dag 加 1。但是，我已经被困了好几天，试图开发从偏序构建 Hasse 图的算法（我们不谈论增量！），即使我认为它会是一些标准的本科材料。

这是我的数据结构：

我的 DAG 由根列表和一些部分排序定义：

我被困在这里了。最后我想为 DAG 添加一个新值 v 是：

1. 在 DAG 中找到 v 的所有“根子集”rs_i，即 v 的子集，使得 rs_i 的任何超集都不是 v 的子集。这可以通过在图上执行搜索（BFS 或 DFS）很容易地完成（collect函数，可能不是最佳的甚至是有缺陷的）。
2. 构建新节点 n_v，其子节点是先前找到的 rs_i。
3. 现在，让我们找出应该附加 n_v 的位置：对于给定的根列表，找出 v 的超集。如果没有找到，将 n_v 添加到根并从根中删除 n_v 的子集。否则，对超集的孩子递归执行第 3 步。

我还没有完全实现这个算法，但对于我看似简单的问题来说，它似乎是不必要的迂回和非最优的。是否有一些更简单的算法可用（谷歌对此一无所知）？

假设我们有一个有一个源的 DAG。我想找到这样的节点n，使得来自源的任何完整路径都贯穿n（即n支配所有接收器）。换句话说：如果我们删除 的所有后继者n，那么所有路径都将以 结尾n。问题是节点在 DAG 中被增量标记为已删除。随着节点被标记为删除，其他节点可以开始满足上述属性。我怎样才能有效地检测到这种情况？

如果数据结构可以以比在每个源上单独运行单个源的算法更有效的方式对多个源执行此操作，则可以加分。

我有以下 DAG

这是关闭表

我将如何删除 path B > D（从而删除A > B > D）而不删除A > C > Dand C > D。

现在我正在使用以下查询，但它仅在每个节点只有 1 个父节点时才有效。

我打算在 pyqt 中创建一个节点图。qt 提供的抽象模型适用于一维、二维和树数据，但抽象类似乎分解为节点图之类的东西。

特别是 QAbstractModel 中的“父”函数返回单个父级的 QModelIndex。在 DAG 中，我可能会有多个父母。

我发现的一个资源是这篇博文：

http://invalidmagic.wordpress.com/2009/12/10/qgraphicsscene-used-as-a-qabstractitemmodel/

它提供了一些有用的信息，但我似乎无法理解该模型如何代表多个父母的概念。

我正在寻找有关如何在 Qt 中实现 DAG 模型的示例和建议。

我想要一种算法，如果有的话，它会在有向图中给出一个循环实例。谁能告诉我一个方向？在伪代码中，或者最好是在 Ruby 中？

我之前问过一个类似的问题，并按照那里的建议，我在 Ruby 中实现了卡恩算法，该算法检测图是否有循环，但我不仅想要它是否有循环，还想要这种循环的一个可能实例。

卡恩算法

上面的算法告诉一个图是否有循环：

但我不仅想要这样的循环示例：

如果我在检查结束时输出上述代码中的变量graph，它将给出：

其中包括我想要的循环，但它也包括与循环无关的额外边缘。

有几个与“* a *循环图”相关的问题和各自的相关答案/讨论，它们确实很有用。但是，我没有找到任何与“循环图”相关的内容，因此我选择在这里发布这个问题。

我有一些复杂的时间关系，比如

• a->b->c ( 'a' 有一个通过 'b' 到 'c' 的路径)
• b->d->c
• c->e->a （注意：- 这里c 有一个通过 e 的路径）

我需要以“图片”的形式来表示这些关系。如果“a”、“b”、“c”等可以显示为图像会很好，但这很简单。

我们是否有任何 JavaScript / JQuery 可用于在图中表示此类关系？我对其他技术（如 flex 等）持开放态度，但我的首选是 JQuery/JavaScript。

在最近的一次采访中，我被问到以下问题。

给定一组节点和边，起始节点指向最终结束节点。在下图中，它从 1 开始，到 15 结束。他们的问题是以节点 2（或任何节点）为起点，我们如何才能在其路径中找到下一个节点，其输入边并非都可以从节点 2 到达（即我们怎样才能达到14）。

我该怎么做，伪代码应该没问题。