问题标签 [directed-graph]

根据维基百科，我用 Python 实现了 Tarjan 的强连接组件算法，但它不起作用。该算法很短，我找不到任何区别，所以我不知道为什么它不起作用。我试图检查原始文件，但找不到它。

这是代码。

如果您愿意，可以直观地检查图表。如您所见，这是对维基百科中伪代码的非常正向的翻译。但是，这是输出：

应该只有一个强连通分量，而不是三个。我希望这个问题在各个方面都是正确的，如果不是，我很抱歉。无论如何，非常感谢你。

这是 tarjan 循环检测的有效 C# 实现。

该算法可在此处找到： http ://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

注意 DepGraph 只是一个顶点列表。并且 Vertex 有一个代表边缘的其他 Vertex 列表。index 和 lowlink 也被初始化为 -1

编辑：这是有效的......我只是误解了结果。

免责声明：作者是 Erlang 的新手。

我想在 Erlang 中实现某种最短路径算法。

Erlang中有图数据结构的标准实现：http ://www.erlang.org/doc/man/digraph.html

但是，我还没有找到有关它使用的实际数据结构的任何信息。

主要是我想知道：

• 为顶点动作获取所有“邻居”的最坏情况是什么？
• 从图中获取顶点的最坏情况是什么？

我们得到一个包含以下事实的图表：

我们被要求定义一个规则，cycle(X)确定是否有一个从节点开始的循环X。

我真的迷失了如何做到这一点，我尝试遍历节点并检查下一个节点是否会再次成为起始节点，但我似乎无法让它工作

免责声明：作者是 Erlang 的新手。

想象一下，我们有一个由 1M 个节点组成的图，每个节点有 0-4 个邻居（边从每个节点发到这些邻居，所以图是有向和连通的）。

这是我选择的数据结构：

为了存储图表，我使用基于 ETS 表的 digraph。这允许快速 (O(1)) 访问节点的邻居。

对于未访问的节点列表，我使用 gb_sets:take_smallest （节点已经排序，取完后同时删除）。

对于前辈列表，我使用 dict 结构，它允许以以下方式存储前辈：{Node1,Node1_predecessor},{Node2,Node2_predecessor}。

对于访问节点的列表，我使用一个简单的列表。

问题：

1. 当我尝试在 digraph 结构和 Unvisited_nodes 结构中更新节点的权重时，代码变得非常难以阅读和维护。将一个“对象”与需要在两个数据结构中同时更新的“字段”保持一致似乎不是正确的方法。这样做的正确方法是什么？
2. 同样的问题是关于前辈名单的。我应该在哪里存储节点“对象”的前任“字段”？也许在图中（有向图结构）？
3. 也许我应该根据过程和消息而不是对象（节点和边）及其字段（权重）重新考虑整个 Dijkstra 算法？

升级版：

这是基于 Antonakos 建议的代码：

我有一个有向图，其中有两条有向路径。

我想要一个算法来确定两条路径之间的相似性。

这篇文章提到使用Levenshtein 距离来确定近似相似度。我也意识到汉明距离使用了类似的度量。

我的问题是：

您如何处理两条路径相互平行的情况。也就是说，如果两条路径没有相似的节点，但会被认为是“相似的”，因为它们的路径以相同的方向行进，彼此非常接近。

谢谢

我正在为 NetworkX 中的有向图编写一些代码，并且遇到了一个问题，这可能是我有问题的编程经验的结果。我想要做的是以下几点：

我有一个有向图 G，顶部有两个“父节点”，所有其他节点都从中流出。在绘制此网络图时，我想将作为“父 1”后代的每个节点绘制为一种颜色，而将所有其他节点绘制为另一种颜色。这意味着我需要一份 Parent 1 的继任者名单。

现在，我可以使用以下方法轻松获得它们的第一层：

问题是这只给了我第一代接班人。最好是，我想要后继者的后继者，后继者的后继者等。任意，因为能够运行分析并制作图表而不必确切知道其中有多少代，这将是非常有用的.

知道如何解决这个问题吗？

我必须向 SVG 有向图添加一些交互功能。

到目前为止，我要展示的图表是从点文件生成的，并呈现为 SVG。我想知道是否有一些简单的方法可以向此类 SVG 文档添加交互性（可能使用 Javascript）。

我需要的是在鼠标移过一个节点时显示一些信息，并可以比较两个节点。

由于我的模型是自动生成的，因此我更愿意保留点生成的 SVG，并使用单独的 Javascript 在其上添加附加信息。

使用它来表示可以是周期性的有向图是否有任何重大障碍？

编辑：

这比它可能应该的更令人困惑。这是一个 RPG 的对话图，这就是我目前所拥有的。我试图确定是否可以将其重构为更简单的形式：

为 NPC 初始化：

一段对话，带有响应选项：

一个响应选择，然后可以循环回到地图中的另一段对话：

我有一个数据文件，其中包含代表河流流量关系的配对值列表。

该文件具有这种结构

我需要做的是读取这个文件，然后对于任何给定的节点，我需要打印所有 UPSTREAM 节点。

在上面的例子中，如果我输入 C，我会得到 E、B、A。

我在 linux 机器上使用 perl，我写这篇文章的人也是。谢谢。