获取图形中的所有网格(窗口)

Question

我必须获得表示电路的未加权图中的所有网格(窗口/回路/基本电路，一起覆盖图的所有边的最短回路，没有其他回路)的列表，以便对该电路进行网格分析(我可以假设它是一个平面图)。图(表示为元组(A，B，R)表示两个顶点和边的阻力)是从文件中加载的。

我正在使用Python和NetworkX库，但是它的cycle_basis函数不返回网格(它们显然不同于循环基础)。图形是无向的，所以我不能使用simple_cycles函数。我尝试修改此任务的BFS，但我不能保证其他周期中不包含周期。

我可能需要这样的东西：Algorithm for finding minimal cycles in a graph，但这个问题在上一个评论中没有任何关于算法的证据，我希望我的问题的答案比“实现霍顿的算法”更简单。

Answer 1

网格分析所需要的是图形的任何特定平面图形中的封闭区域的列表。

它比最小循环更容易找到，但是你得到的列表取决于你使用的平面图形。

如果您有一个平面图形，并且可以按顺时针或逆时针顺序获得每个顶点的邻居，那么很容易就可以在这些封闭区域周围进行跟踪。

否则，您可以执行以下操作：

1. 为不在树中的每条边生成一个生成树
2. ，生成一个仅包含该边的循环，再加上生成树中的边。

由于每个循环都包含不在任何其他循环中的一条边，因此可以保证没有任何循环包含在任何其他循环中。取决于你所说的“包含”是什么意思。重要的一点是，只要你对任何当前的来源都很小心，这些循环就会在分析中发挥作用。也许你想在生成树中避免它们。

由于您将使用这些循环来生成要求解的方程系统，其中每条边都是一个变量，因此使用更复杂的算法来查找“较小”的循环可能没有优势。