问题标签 [directed-acyclic-graphs]

给定一个带有 |V| 的 DAG = n 并且有 s 个源，我们必须呈现子图，使得每个子图大约有 k1=√|s| 源和近似 k2=√|n| 节点。

如果我们将 DAG 的高度定义为从某个源到某个汇的最大路径长度。

我们要求生成的所有子图都具有大致相同的高度。

每对节点集（子图）的交集为空。

您可以在附图中看到右分区的示例（图中的每条边都指向上方）。

示例中有 36 个节点和 8 个接收器 [#10,11,12,13,20,21,22,23]。所以每个子图应该有 6 个节点和 2 或 3 个接收器。

你对算法有想法吗？

非常感谢

假设我有一个Task可以依赖于 other 的对象Tasks。有没有办法明智地急切/加入加载所有给定任务的子任务集？

我需要将依赖项存储在 DAG 中。（我们正在细粒度地绘制新的学校课程）

我们正在使用 Rails 3

注意事项

• 比深更宽
• 很大
• 我估计每个节点有 5-10 个链接。随着系统的发展，这将增加。
• 多读少写
• 最常见的是查找：
  • 一级和二级依赖
  • 搜索/验证依赖关系

我知道 SQL，我会考虑 NoSQL。

寻找指向实现选项的良好比较的指针。

也对我们可以快速开始的东西感兴趣，但以后过渡到更健壮/可扩展的东西会不那么痛苦。

我使用python 绑定到igraph来表示一个有向树。我想找到从该图中的一个节点到另一个节点的所有可能路径。不幸的是，我在 igraph 中找不到执行此任务的现成函数？

编辑

对无限数量路径的关注

我正在谈论的图实际上是具有单根的有向无环图（DAG）。它表示事件的单向级联，在级联的各个级别上，可以拆分或合并在一起。正如我所说，这是一个单向图。还规定该图不包含任何循环。由于这两个原因，无限的路径列表是不可能的。

我想做什么？

我的目标是找到从图形顶部（根）到给定节点的所有可能路径。

假设我有一个图表，其中节点是各种类型的工作负载，边是工作负载之间的依赖关系。（这是一个 DAG，因为不能存在循环依赖。）

我还有一组可以执行工作的多个代理。

一些工作负载种类可以分配给任何代理，其他的必须分配给特定代理，而其他的必须分配给特定代理组中的一个代理。

如何分配工作负载，以便：

• 在完成所有阻塞工作负载之前，不会向代理分配工作负载

• 完成总工作负载图需要尽可能短的时间。（请注意，最小化代理空闲时间通常是好的，但不是基本要求 - 可能存在一个特定代理空闲更长时间但完成所有代理的所有作业的总时间最少的情况。）

工作负载具有持续时间估计值，但为简单起见，假设每个工作负载都需要相同的计算时间。（只需将每个工作负载分解为多个连续依赖的工作负载，直到每个工作负载实际上都是一个恒定时间操作。）

我知道拓扑 DAG 排序，但这会产生一个单一的、串行的节点排序。我有多个并行运行的代理，并且这些关系使得可以通过对任务进行不明显的重新排序来进行潜在的大型时序优化。

这样做的结果最好呈现为最小总持续时间的甘特图。实际上，如果您将问题视为将里程碑中的错误票分配给团队中的工程师，目标是尽快完成里程碑，那么您就会明白这一点。（不......请不要告诉我将我的图表导入 MS Project 然后导出它:) - 我对它背后的算法感兴趣！）

非常感谢指向众所周知的算法、软件库或一般问题和原则的指针！

我有一种单级树结构：

其中 p 是父节点，c 是子节点，b 是假设分支。

我想在只有一个父节点只能分支到一个子节点并且两个分支不能共享父节点和/或子节点的约束下找到所有分支组合。

例如，如果combo是一组组合：

我想这就是全部。=)

对于这种结构的任意树，如何在 Python 中自动实现这一点，即 p:s、c:s 和 b:s 的数量是任意的。

编辑：

它不是一棵树，而是一个二部有 向无环图

我得到一串字符，其中每对后续字符都包含一条边。我的意思是这是字符串：ABBCAD。字符串的边缘是：

最短路径距离为 A->D

手头的任务是使用上述规则从字符串在内存中建立一个有向无环图，并找到以根节点为起点的最短路径（在示例中为 A 标签），并在终端节点结束。

NJKUUGHBNNJHYAPOYJHNRMNIKAIILFGJSNAICZQRNM

我收集了适合该任务的一种方法是使用深度优先搜索算法。

这不是家庭作业...

在具有非负加权边的 DAG G 中，如何找到 G 中两个顶点之间的最大权重路径？

感谢你们！

我想在数据结构上有一个迭代器。现在我不知道数据结构是什么，也许它是一个 DAG（有向无环图），但也许它也可能是一个链表。所以我想把它包装成一个迭代器，现在不要考虑特定的数据结构。

我知道如何使用类似递归的访问者来访问 DAG，但我无法找出一个简单而干净的结构来实现迭代器方法next()和hasNext().

在迭代器内部，我创建了一个当前节点实例，并使用 for 循环遍历所有子节点，然后返回父节点。需要一个“已访问”标志。所以我DagElement有这些更多的属性：

我不认为这是一个干净的解决方案。

有什么建议吗？

这不是家庭作业。

视觉上它看起来像一棵树，但所有叶子都是唯一的（在数据库中具有唯一的 ID）。它们之上的层次结构有些随意。每个复选框有 3 种状态：开、关和部分。叶子可以只检查或不检查。孩子的状态应该驱动父母的状态。单击复选框应该“切换”它，并向上或向下传播必要的更改。如果您单击部分选中的父级，它应该变为完全选中。每个孩子都有一个指向父母列表的指针（如果必须，我可以将其更改为一组）。每个父母都有一个按字母顺序排列的孩子列表。同时，出于展示的目的，这个结构是一棵树，我可以展开和折叠，如下图所示。

我确信这个算法之前已经被发明了。由于叶子的数量已经达到20,000，我确实关心实践中的表现。但是，我不会试图以代码简短易读为代价来榨取算法中的每一滴性能。

我认为原则上我应该走下来（如果有任何地方可以去）并确定所有应该更换的叶子。在那之后，我应该走上去。从这组叶子中，我应该找出一组可能受到影响的父母。然后将其过滤到需要更改的父级集，以及需要更改的值。然后将它们添加到集合中。然后我需要从这些节点上走并重复。在我有一组叶子和其他需要更改的节点以及它们的值之后，我将需要这样做......或类似的事情。基于矩阵的表示将过于昂贵。

我在C++using中一起破解这个东西MFC，但我的问题几乎与语言无关。但是，我更喜欢具体的实现而不是算法。一些语言，如 Python、Perl、Scala 可能有太现代的技巧。我会尝试坚持一些更传统的东西，比如 Java、C#（减去 LINQ）。

欢迎代码、链接、参考和问题。