问题标签 [directed-acyclic-graphs]

我不确定这是否有一个简单的解决方案或者是一个“命名”算法，所以我想我会在这里问。

我有一个来自编译器的数据流图（DFG）。这是一个弧加权 DAG。弧权重表示各种操作的延迟，节点表示操作本身（加法、减法、加载等）。我试图找到允许计算在其关键路径上运行的最小资源集。

我已经通过以下方式做到了这一点：

然后资源数组将具有确保没有争用所需的最少资源，最终时钟值将是关键路径（这只是为了证明这不是作业问题=]）

我只是想知道这是否有一个“名称”，或者是否有其他一些可爱的方式来做到这一点。谢谢！

我正在尝试实现将有向无环图转换为树的算法（为了好玩，学习，kata，命名它）。所以我想出了数据结构Node：

这很简单。方法：

并测试：

更重要的是，数据结构需要一些改进：

• 覆盖 GetHash、toString、Equals、== 运算符
• 实施 IComparable
• LinkedList 可能是更好的选择

此外，在转换之前，还有一些需要检查的事项：

• 多图
• 如果是 DAG（循环）
• DAG 中的钻石
• DAG 中的多个根

总而言之，它归结为几个问题： 如何提高转化率？由于这是一个递归，因此可能会炸毁堆栈。我可以添加堆栈来记住它。如果我做持续传递风格，我会更有效率吗？

我觉得在这种情况下不可变数据结构会更好。这是正确的吗？

Childs 是正确的名字吗？:)

人们为 java 推荐了哪些“绘图”算法库，可以执行以下操作：

1. 将自定义对象作为节点（假设所有相同的对象类型）
2. 允许指定这些节点之间的连接
3. 在这些节点上提供标准算法（循环检测、最短路径...）
4. 允许节点+连接上的自定义访问者（访问者模式）

不要过于复杂（如果可能的话）。有一些不错的javadoc（+一个maven包会很好）。

我有一个最好用图表表示的数据集。它由 6 或 7 个不同“类型”的节点组成，这些节点具有有向边（相互依赖，保证没有循环依赖）。数据集本质上是分层配置的模板，用户需要能够从所需的不同层中选择配置的点点滴滴，并自动引入相关的位。

一般的 UI 需求是用户从多选框（每个节点类型一个这样的框）中选择或取消选择项目，并根据需要使其他框中的“依赖”项目变为选中或取消选择。我需要能够从服务器上拉下数据集，让用户选择所需的位（在客户端的 javascript 中完成依赖处理以实现响应），然后在完成后将结果提交回来。

数据集足够大且足够复杂，以至于将其实际显示为图表会让用户感到不知所措和困惑。只需要基本的图遍历操作，因为所需要的只是将选择级联出依赖项。（例如，如果没有其他选定的节点仍然依赖于它们，则用户取消选择节点将导致该节点依赖项变为未选中。选择节点的用户将导致该节点的所有依赖项都被选中。）从起始节点开始沿着有向边进行简单的深度或广度优先搜索就足以访问所有受影响的节点。如果我可以沿任一方向跟随边缘，则奖励。（如果不是，我可以很容易地生成一个边缘反转图并在需要时使用它。）

我在这里挖掘并找到了对许多 javascript 图形可视化库的引用，但是这些讨论中的大多数似乎都将“图形”解释为“图表”，我在这里没有图表需求。我的挖掘使我得到了这个列表：Raphael、protovis、flare、D3、jsVis、Dracula 和 prefuse。从这个列表来看，如果我只是忽略可视化方面，jsVis 或 Dracula 可能具有我需要的底层图形结构，但如果是这种情况，我从文档中不清楚。我必须排除其他一些，因为我不能引入任何 Flash 依赖项。不幸的是，我没有时间用这么多的库来制作原型。（不过，我将深入研究 jsVis 和 dracula，除非在这里提供一些方便的输入。）

如果有人对该列表中的某些内容有经验并相信它的图形部分可以独立于可视化部分使用，那肯定会满足我的需求。如果有其他库可以满足我的需求，那也很棒。关于许可的最后一个要求：库需要以非版权左的方式“免费” - 所以理想情况下是 Apache v2.0、BSD、MIT 或类似的东西。

有点超出我的深度，需要给朋友打电话。我有一个需要遍历的有向无环图，并且我第一次跌跌撞撞地进入图论。我最近读了很多关于它的书，但不幸的是我没有时间在学术上弄清楚这一点。有人可以帮我解决如何处理这棵树的问题吗？

以下是规则：

• 有n 个根节点（我称它们为“源”）
• 有n个端节点
• 源节点带有一个数值
• 下游节点（我称它们为“工作”节点）对传入的值执行各种操作，如 Add、Mult 等。

从下图中可以看出，节点a、b、 和c需要在d、e、 或之前进行处理f。

走这棵树的正确顺序是什么？

我有一个关键字表，其中每个关键字都分配了一个 id 并且是唯一的。我有第二个表，它将父关键字的 ID 链接到子关键字的 ID。一个关键字最多可以有大约 800 个孩子或根本没有。孩子们可以成为更多关键字的父母（等等……）

我遇到的问题是孩子（或孙子或曾孙）可能是导致循环结构的初始关键字的父项。我正在尝试使用递归函数为初始关键字构建树数据结构，但该函数要么永远不会结束，要么超过 Python 中的 1000 级递归限制。

是否有更好的方法来设计我的父/子表以防止这种情况（或在插入期间进行预先检查），或者是否有更好的方法来编写递归函数来防止这种情况发生？我试图限制递归函数的深度，但遇到了单级问题（即子级是父级的父级）。同样，我的目标是为初始关键字创建树结构。

我正在寻找在大图尺寸上执行拓扑排序的现实世界应用程序。

我认为您可以找到此类实例的一些领域是生物信息学、依赖关系解析、数据库、硬件设计、数据仓库……但我希望你们中的一些人可能已经遇到或听说过任何需要的特定算法/项目/应用程序/数据集顶级排序。

即使数据/项目可能无法公开访问，任何提示（以及对潜在图形大小数量级的估计）也可能会有所帮助。

抽象的问题：

我有一个有向无环图（DAG），其中包含查询时互斥的顶点子集（每个子集只有一个项目应该出现在查询的结果中）。当我查询图结构时，我想获取从给定顶点流出的一组顶点，同时只从图中顶点的已知子集中选择一个项目。

具体问题：

我有一个 DAG，用于存储我的程序集（顶点）及其依赖项（边）。给定一个程序集或一组程序集，我需要查询以获取所有涉及的程序集及其依赖项的集合。困难的部分是每个程序集都有多个版本，并且只能将程序集的一个实例加载到进程中。给定程序集的依赖关系在程序集的各个版本之间发生变化。

这个问题或问题组有名称吗？我可以研究以找到解决方案的标准算法？

可能的解决方案领域：

传递闭包似乎接近一个很好的解决方案，但从子集（程序集版本）中选择的项目将根据通过图的路径（可能通过多个分支）而改变，因此您几乎需要跟踪通过图的路径以生成传递闭包。

图形数据库可能会提供很多帮助，但我们现在希望避免走这条路，除非我们绝对必须这样做。

我正在寻找一种算法来计算通过 DAG 中特定节点的路径数（类似于“介数”的概念），具有以下条件和约束：

我需要对图中的一组源/目标节点进行计数，而不是所有节点，即对于中间节点 n，我想知道从节点集 S 到节点集 D 有多少条不同的最短路径通过通过 n （并且通过不同，我的意思是每两条路径至少有一个非公共节点）

考虑到 DAG 可能非常大但边缘稀疏，因此您可能建议使用哪些算法来执行此操作，因此不优先考虑节点上的深层嵌套循环。

我在看 CouchDB。文档有版本，您可能有冲突的版本。它是否像 dvcs 一样将版本序列存储为有向无环图 (DAG)？如果没有，它是如何实现的？