问题标签 [directed-acyclic-graphs]

获取具有直接和间接外键依赖关系的表列表到 DBIx::Class 子类 foo 的最快方法是什么？我有一个基于 DBIx::Class::Schema 的 MySQL 数据库。DBIx::Class 可以直接使用，还是 SQL::Translator 可以通过生成有向图来帮助？

给定以下类：

对于输入 Foo，输出应为 [ Bar, Baz ]。

鉴于此依赖关系图：从下到上遍历它的“好”方法是什么？

我对每个“周期”的预期结果是：

头脑风暴

“深度优先搜索”不起作用的原因：

算法

我真的不想重新发明轮子：那么是否已经有一种算法可以解决这个问题，或者有没有人有一个“聪明”的方法？

我有这个 DAG（它类似于二叉树，但它是一个图。有这个指定的名称吗？）：

（每个数字是一个节点，节点中的数字例如，程序应该以随机数运行）

它表示为列表列表：

我必须尽可能以更实用的方式找到最大化节点总和的路径：

我已经搜索过，这与 projecteuler #18 非常相似，但是 project euler 询问路径的孔总和，在我的作业中，我不仅要找到总和，还要找到所有节点。我试图为我的问题调整一些非常好的解决方案，但我没有成功。一些忠告？

我正在研究一个涉及逻辑电路（可以表示为 DAG）的研究问题。DAG 中的每个节点都有一个给定的权重，可以是负数。我的目标是找到一个连通子图，使得节点权重的总和最大。

给定边权重的最大权重连接子图问题显然是 NP-hard，但我希望有向无环性质以及我处理节点权重而不是边权重的事实使问题更容易一些。有人可以指出我如何开始解决这个问题的正确方向吗？

谢谢

我正在使用的框架由依赖于其他服务的有状态服务组成，形成一个有向无环图http://en.wikipedia.org/wiki/Directed_acyclic_graph

我想尽可能高效地启动服务。这意味着在可能的情况下并行启动服务。例如，在维基百科链接的图表中。我会同时启动 3、5 和 7，因为它们没有任何依赖关系。我见过拓扑排序，但仅此一项并不能告诉您可以并行启动什么。我正在寻找用于分组服务的库/api，例如：

这告诉我先开始“a”，然后并行开始“b”、“c”和“d”，然后是“e”，依此类推。

我找到了一些对顶点建模的库，但我正在寻找的分组没有。到目前为止，我已经找到了一些有向图的实现，但是，我需要一个许可许可证（例如非 gpl）。我找到了ComputeNodeOrder http://www.docjar.com/docs/api/org/eclipse/osgi/internal/resolver/ComputeNodeOrder.Digraph.html（来自Equinox org.eclipse.osgi_3.6.2.R36x_v20110210），Jgrapht（ lgpl) http://www.jgrapht.org/javadoc/ , Jung http://jung.sourceforge.net/index.html , Plexus http://plexus.codehaus.org/plexus-utils/apidocs/org/codehaus /plexus/util/dag/DAG.html但不确定是否有任何/所有这些都可以满足我的需要。

我正在考虑将DAG表示为Dictionary(Of Integer, List(Of Integer)) 其中键将是顶点 ID，并且列表将包含沿边缘的所有目标顶点。

稍后我将使用此结构来：

我有一个 DAG G=(V,E)，它是邻接表表示。我正在尝试根据附加到顶点的一些参数来压缩它。

现在我有一个图 G=(V,E) 和一个包含 V 子集的列表。

知道如何有效地从原始图中找到子集顶点的边吗？

我需要使用原始图连接子集。

看这张图

{9: [10], 7: [9], 8: [9], 6: [7], 3: [8], 2: [3, 4], 5: [4, 6], 4: [ 7]，1：[2]}

现在如果我取子集 [1,4,7]

如何找到子集的连接？请参阅传递闭包作为一个问题。我需要在传递闭包中找到所有边，但不是重复项。

我无法理解第 9 页的有向无环图

http://mitpress.mit.edu/books/chapters/0262033844chap27.pdf

谁能解释一下？

所以我有一个基本上是这样的问题：我有一堆字符串，我想构造一个 DAG，使得每条路径都对应一个字符串，反之亦然。但是，我可以自由地任意排列我的字符串。字符的顺序无关紧要。我生成的 DAG 具有与之相关的成本。基本上，DAG 中一个分支的成本与其子路径的长度成正比。

例如，假设我有字符串 BAAA、CAAA、DAAA，并且我构造了一个 DAG 来表示它们而不对它们进行置换。我得到：

() -> (B, C, D) -> A -> A -> A

其中元组表示分支。

就我的目的而言，更便宜的表示是：

() -> A -> A -> A -> (B, C, D)

问题是：给定 n 个字符串，对字符串进行置换，使得对应的 DAG 成本最低，其中成本函数为：如果我们从源头开始深度遍历图，从左到右顺序，我们的节点总数访问，具有多样性。

所以第一个例子的成本是12，因为我们必须在遍历中多次访问A。第二个示例的成本是 6，因为在处理分支之前我们只访问 A 一次。

我感觉这个问题是NP Hard。这似乎是一个关于形式语言的问题，我对这些算法还不够熟悉，无法弄清楚我应该如何进行缩减。我本身不需要完整的答案，但如果有人能指出一类似乎相关的众所周知的问题，我将不胜感激。

我正在计算图像的DAG的关键路径，根据这个算法在另一篇文章中。我的老师要求实现aarray，我简化了作业语句，通过数组实现的简单图形。

这是我的代码，其中我有 3 个数组 v、u 和 d，分别代表边的起点节点、边的终点节点以及每对顶点之间的距离，如上图所示。在图像的图表中，项目的持续时间等于 25，对应于与关键路径的距离之和。

我的代码未能根据此链接的伪代码计算好距离

我做错了什么或者它如何解决代码来告诉我项目的持续时间是多少（对应于与关键路径的距离总和）？只能计算到前 3 个顶点的距离。