使用pydot查找起点、终点和循环

Question

有没有办法在pydot中实现这个呢？

来看下面这个例子：

[输出的Dot文件]

strict graph g{
"A" -> "B";
"B" -> "C";
"C" -> "D";
"D" -> "E";
}

[Python代码]

print(num.start)
>>> A
print(num.steps)
>>> ["a,b","b,c","c,d","d,e"]
print(num.end)
>>> E

或者用下面这个情况：

[输出的Dot文件]

strict graph g{
"A" -> "B";
"B" -> "C";
"C" -> "A";
}

[Python代码]

if num["A"] == num.loop:
print("[%s] loop detected")%(num["A"])

Answer 1

你可以通过 graph.get_edge_list() 获取整个图的结构，然后用标准的深度优先搜索方法来找到节点之间的最短路径。查找循环也是用一些常见的图算法来完成的，具体可以参考这个关于 循环检测 的链接。想了解如何在Python中实现图的相关内容，可以看看这篇文章 Python中的图实现，里面有关于如何找到两个节点之间最短路径的源代码。

如果你想找pydot库来帮你完成这个任务，可能会有点困难。

Answer 2

Pydot可以写出dot文件，但它并不适合用来分析图。

你应该使用NetworkX。它可以读取和写入dot文件，还可以找到圈子、找到可到达的节点，并进行拓扑排序。

你可以在维基百科上查一下图的相关术语，NetworkX就能帮你完成其他的工作。