问题标签 [directed-acyclic-graphs]

我有几个类，每个类都是运算符的子类。操作员有多个输入和输出，各种类型：图像、数字、字符串。每个子类都实现了一个执行计算的 run() 方法。现在我想为这些 Operator 设计一个容器，将简单的 Operator 变成更大的 Operator。容器应该尽可能高效，所以我打算使用线程。我在 Boost 图形库中找到了一个示例，该示例允许我计算我应该进行计算的顺序：http: //www.boost.org/doc/libs/1_49_0/libs/graph/doc/file_dependency_example.html，但我认为可能有更好的方法来做到这一点：每个操作员都可以在阻塞状态下等待，直到其所有输入都准备好。如果容器子类化 Operator 会很好，允许递归地组合它们。我有一种感觉，这是一种已知的设计模式。

我想将 DAG 表示为 JSON 文本，并想知道是否有人尝试过这个，以及他们在验证 JSON 是否实际上是 DAG 时处理的任何问题。

我将 gRbase 包中的“dag”函数与 plot 结合使用来创建一些 DAG。

在“dag”帮助页面中，我在参数中看到了这一点：

x，包含图表生成类的列表，请参见下面的示例

在下面的示例中，我看到如下内容：

因此，当我执行此代码时，它可以工作并给我图表：

为什么当我创建自己的列表时出现以下错误？

我正在为我正在使用的数据结构寻找数学形式，以便我可以追踪相关的定理和算法。

假设您有以下内容：

• 主题的有向无环图。
• 在每个主题中，主题、一组文档中的项目和一组组中的项目之间存在一个或多个关系。
• 这些组可能是一个简单的集合，也可能最终成为一个 DAG。它们用于管理文档与主题关联的可见性。

直到最近我才遇到hypergraphs，这似乎相关但过于笼统。这种数据结构有形式主义吗？如果不是，能否用数学术语更简洁地描述它？

The Algorithm Design Manual中有两个相关的 excises 。

基本上，我知道如何解决第一个消费税，但我不知道如何使用第一个解决方案作为提示来解决第二个消费税。

算术表达式树的消费税

上面是一个算术表达式树。假设算术表达式以树的形式给出。每个叶子都是一个整数，每个内部节点都是标准算术运算之一（+，-，*，/）。例如，表达式 2 + 3 * 4 + (3 * 4)/5 由上图中的树表示。给出一个计算这样一个表达式的 O(n) 算法，其中树中有 n 个节点。

好的，这并不难。我的解决方案是这样的：

我只是使用递归的方式来解决表达式树的结果。

算术表达式DAG的 Excise

假设一个算术表达式被给出为一个 DAG（有向无环图），其中删除了公共子表达式。每个叶子都是一个整数，每个内部节点都是标准算术运算之一（+，-，*，/）。例如，表达式 2 + 3 * 4 + (3 * 4)/5 由上图中的 DAG 表示。给出一个 O(n + m) 算法来评估这样一个 DAG，其中 DAG 中有 n 个节点和 m 个边。提示：修改树案例的算法以达到所需的效率。

好的，描述中有这样一个提示：提示：针对树的情况修改一个算法，以达到预期的效率。

实际上，我对这个提示感到很困惑。对于一个典型的树相关的事情，我们通常可以使用递归来解决。但是，如果这是一个图，我的第一个直觉是使用 BFS 或 DFS 来解决它。那么我如何将 BFS 或 DFS 与树相关联，尽管 DFS 实际上是递归的？

假设我们有一个边用数字标记的 DAG。将路径的值定义为标签的乘积。对于每个（源，汇）对，我想找到从源到汇的所有路径的值的总和。您可以使用动态规划在多项式时间内完成此操作，但在如何分解问题方面仍然可以做出一些选择。就我而言，我有一个 DAG，必须用不同的标签反复评估。我的问题是：对于给定的 DAG，我们如何预先计算一个好的策略来重复计算不同标签的这些值？如果有一种算法可以找到最佳方法，例如最小化乘法次数的方法，那就太好了。但也许这问得太多了，我会对一个能很好分解的算法感到非常满意。

是否有用于图论操作的良好 C 库？我特别需要计算有向图的强连通分量。我在 Ruby 中实现了Tarjan 的算法，如下所示：

它正在处理小图，但随着图变大，由于递归调用方法，它开始返回“堆栈级别太深”错误strong_connect。我想我需要一个 C 库并从编写主程序的 Ruby 访问它。

除了库之外，任何在 Ruby 库中使用它的建议都会有所帮助。

我对直接无环图 (DAG) 很感兴趣，在阅读了 Wikipedia 上的拓扑排序后，我没有发现任何特别提到涉及层编号的方法（尽管在绘图中广泛提到了层）。使用这种方法，图形在技术上不是拓扑排序的，但是知道每个节点都包含正确的层（级别）编号，我们总是可以判断一个特定节点是否比另一个节点“更大”。另一方面，只要我们没有有序列表，我们就无法在拓扑上枚举节点（尽管这可以通过比较节点级别的最终常规排序来完成）。

这种方法允许实现任意连接，同时保持关卡信息的正确性。步骤可以是：

• 对于任何新添加的节点（没有任何连接），应用的级别为 1。
• 如果请求两个节点之间的连接（从 m 到 n）并且 n.level > m.level 那么它们只是简单地连接，不需要对其他节点进行级别修复。
• 如果对于请求的连接（从 m 到 n）n.level<=m.level，那么我们将 n.level 更改为 (m.level + 1) 并递归检查 n 的任何依赖关系是否有类似的级别增加（或者如果级别不增加，则不增加在递归步骤上是兼容的）。
• 如果我们保留递归输入节点的列表，那么我们可以检测到尝试循环并执行某种撤消操作（将所有受影响节点的级别返回到以前的值）

对于任何一组已知节点和它们之间的连接，我们只需将所有应用 level=1 的节点添加到它们，并尝试应用它们之间的所有已知连接（忽略和撤消 cicles）。

最终级别信息不仅​​允许在拓扑上比较节点，而且还包含其他有用的信息。例如：

• 每个 level = 1 的节点都没有传入连接（每条路径都从其中一个开始）。所以任何 DAG 枚举都可以从它们开始。
• 最长路径（边数）不能长于（最大层级+1）

我想对于一些人工数据（n 个节点，每个节点（n）连接到节点（n + 1）），这个算法可能非常慢。但是对于我尝试使用的真实数据（维基百科类别 - 800,000 个节点 - 2,000,000 个连接），时间很合适（5-10 分钟），关卡和循环尝试的数量很低（369 个关卡，1000 次循环尝试）

那么这种方法是新的还是众所周知的，但只是没有在维基百科和其他资源中广泛呈现？既然它不是一个排序（技术上），它应该被称为数据重组吗？

我正在开发一个 Ruby on Rails 系统，该系统有一个与自身Project相关的表（循环关系是不可能的）。通过这种方式，一个项目可以成为多个其他项目的一部分，这非常有用，并且是新应用程序所基于的遗留系统的杀手级功能。我需要一种方法来在单个页面上显示所有项目及其、和其他简单属性。每个项目都必须相对于它们的每个父项显示（重复条目很好），并且每个属性值必须由浏览器与其他属性对齐（没有一个总是会中断的“静态宽度”渣滓）。项目也必须是可折叠的，尽管我怀疑这与解决方案无关。has_and_belongs_to_manynameshort_name

当前的解决方案类似于如何在 HTML 表格中呈现树？解决方案：使用 a<table>并使用 CSS 在最左侧的列中实现“树状”结构padding-left。通过存储每个项目的父项目 ID 来保持完整的父子关系。因为这不是语义标记，所以很难用 JavaScript 处理结果表。如果要折叠一个节点，则必须在折叠的一个节点<tr>之后遍历每个节点，直到找到同一级别的节点，而不仅仅是删除子节点列表。此外，多个项目不止一次展示

是否有一种语义方式可以在 HTML（任何版本）中表示这样的数据结构，而不会牺牲所有合理设置样式的能力？据我所知，表格列表无法正确对齐，并且无法将列表与表格混合。

我没有标记ruby或ruby-on-rails因为编程语言与任务无关，只是为了解释现有系统的结构。

所以基本上，我有一个 n x m 浮点值数组，我试图找到任何第一行值和任何第 m 行值之间的最短路径。图中的节点对于不在边缘且不在底行的任何节点(i, j)都有子节点。我正在寻找一种算法来及时解决这个特定问题。我目前的思路围绕 A* 搜索展开，但请告诉我您的想法。{(i, j+1), (i-1, j+1), i+1, j+1)}(0 < i < n-1)(j < m-1)