问题标签 [directed-graph]

我正在使用的框架由依赖于其他服务的有状态服务组成，形成一个有向无环图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但不确定是否有任何/所有这些都可以满足我的需要。

是否在任何地方描述了有向图原子性和隔离保证？

尤其：

1. 另一个进程会在什么状态下看到有向图，如果另一个进程试图在 del_vertex 中间访问它（vertices()、out_neighbours() 等）：在 del_vertex 之前，在 del_vertex 中间（即顶点被删除，边没有或边缘被删除，顶点不被删除）还是在 del_vertex 之后（即另一个进程将被阻塞直到操作结束）？
2. 关于 del_vertices 的相同问题。

如果我理解正确，有向图是使用 3 个 ets 表实现的。它们之间是否有任何额外的锁定机制以使结果保持一致？

简而言之，我需要一种快速算法来计算简单有向图中有多少条非循环路径。

简单的图表是指没有自环或多重边的图表。路径可以从任何节点开始，并且必须在没有出边的节点上结束。如果一条路径中没有边出现两次，则该路径是非循环的。

我的图（经验数据集）只有 20-160 个节点，但是，其中一些有很多循环，因此会有非常多的路径，而我的幼稚方法对于某些图来说根本不够快我有。

我目前正在做的是使用递归函数沿着所有可能的边缘“下降”，同时跟踪我已经访问过哪些节点（并避免它们）。到目前为止，我最快的解决方案是用 C++ 编写的，并在递归函数中使用 std::bitset 参数来跟踪哪些节点已被访问（访问的节点由位 1 标记）。该程序在样本数据集上运行 1-2 分钟（取决于计算机速度）。对于其他数据集，运行需要超过一天的时间，或者显然更长。

样本数据集： http: //pastie.org/1763781 （每行是一个边对）

示例数据集的解决方案（第一个数字是我开始的节点，第二个数字是从该节点开始的路径计数，最后一个数字是总路径计数）： http: //pastie.org/1763790

如果您对更复杂的算法有想法，请告诉我。我也对近似解决方案感兴趣（用一些蒙特卡洛方法估计路径的数量）。最终我还想测量平均路径长度。

编辑：也以相同的标题发布在 MathOverflow 上，因为它可能在那里更相关。希望这不违反规则。无法链接，因为网站不允许超过 2 个链接...

这是生成的图表当前的样子： 这是代码：

如果我删除 2 条红线，那么它会按照我想要的方式排列：

我怎样才能让它像这样排列并且同时有两条红线？

我需要在 php 和 MySQL 中建立一个家谱。我对那里缺乏开源可定制的 html 家谱构建软件感到非常惊讶，但我离题了。我花了很多时间阅读有关存储 MySQL 有向图和家谱的信息。一切对我来说都是有意义的：有一个带有节点（人）的表和一个带有边（关系）的表。

我唯一的问题是我不确定存储不一定相邻的关系的最佳方式，例如兄弟姐妹和祖父母关系。起初我认为这没什么大不了的，因为我可以无形地强制执行可以解决这些连接的父母（每个人都有父母）。

但是，我还需要能够存储可能没有共同父母的关系，例如浪漫伴侣。我读过的所有内容都暗示了亲子关系，但是由于浪漫的伴侣没有共同的父母（希望如此），我不确定如何将其存储在边表中。我应该使用不同的表，还是什么？如果它在同一张表中，我该如何表示？只要我在不熟悉的关系中这样做，我也可以和家人一起这样做。

总结一下，三个问题：

• 我如何表示横向关系？
• 如果横向关系有共同的父母，我该如何存储？这应该family是存储其他横向关系的桌子上的标志吗？
• 如何在孩子距离两个或更多边缘（祖父母）但直接父母不可用的情况下存储父子关系？

感谢任何帮助，如果有人对一些 javascript/html 家谱构建软件有任何建议，那就太好了。

我得到了一个图表，它可以在 2 个节点之间有多个拱门。

例子 ：

4 个节点 1->2 2->3 3->4 3->4 1->4

找到从节点 A 到节点 B 的道路数量的最佳方法是什么？

该示例的答案是 3 : 1->2->3->4 ；1->2->3->4 和 1->4

节点和拱门的限制为 1 000 000

我只考虑蛮力算法。

还有其他想法吗？编辑：

图是非循环的

我想在我的程序中嵌入流程图绘图画布。用户可以：

• 画“节点”（矩形节点就够了）和“边”（最好是正交的）连接“节点”；
• 使用鼠标拖动节点进行布局和调整矩形大小；
• 鼠标选择一个或多个节点进行删除、复制、粘贴等操作；
• 通过鼠标选择一个或多个节点来编辑它们的预定义属性（体积、温度、压力等）。
• 改变颜色（可选）
• 将数据保存到文件/从文件中读取数据。

绘制完成后，程序只需要获取连接逻辑（在有向图等数据结构中）和属性进行进一步计算。

是否有任何免费或开源的 C++ 库可以做到这一点？（跨平台不需要，windows下就够了。）

令 G 为包含循环的未加权有向图。我正在寻找一种算法，它可以找到/创建所有无环图 G'，由 G 中的所有顶点和 G 的边的子集组成，小到足以使 G' 无环。

更正式：所需的算法消耗 G 并创建一组无环图 S，其中 S 中的每个图 G' 满足以下属性：

1. G'包含G的所有顶点。
2. G' 包含 G 的边的子集，因此 G' 是非循环的。
3. G'的边数最大化。这意味着：不存在满足属性 1 和 2 的 G''，使得 G'' 包含比 G' 更多的边，并且 G'' 是无环的。

背景：原始图 G 对元素之间的成对排序进行建模。由于图中的循环，这不能被用作对所有元素的排序。因此，最大无环图 G' 应该对该排序进行尽可能最佳的近似建模，尽量尊重成对排序关系。

在一种简单的方法中，可以删除所有可能的边组合，并在每次删除后检查非循环性。在这种情况下，存在一个强烈分支的变化树，这意味着时间和空间复杂度不好。

注意：问题可能与生成树有关，您可以将 G' 图定义为一种有向生成树。但请记住，在我的场景中，G' 中的一对边可能具有相同的起始顶点或相同的结束顶点。这与文献中使用的一些有向生成树的定义相冲突。

编辑：添加了与生成树相关的直观描述、背景信息和注释。

可能重复：
在有向图中检测循环的最佳算法

我正在寻找一种算法来查找有向图中的循环。

我的图只在节点中有标签，而不是在边缘，它可以变得非常大。

算法的输出应该是作为一组列表的循环，每个列表应该包含循环中涉及的节点的标签，因此，列表中的第一个和最后一个元素应该是相同的。

我使用的图表很可能只有一个连通分量，没有强连通分量。预计周期数会很低（我仍然需要检查）。

欢迎任何针对此或类似内容的好的算法。

非常感谢。

PS：如果有不清楚的地方随时问我更多细节，例如，图（到目前为止）存储为一组边，从一个节点到几个节点，通常是一个，这应该是无关紧要的，恕我直言。

我有一个有向图。下面是循环吗？箭头在循环中有特定的方向吗？