我必须得到所有网格的列表(窗口/循环/基本电路,最短周期一起覆盖图的所有边缘,没有人包含其他周期)在未加权图表中表示电路用于该电路的网格分析(我可以假设它是一个平面图)。从文件加载图形(表示为元组(A,B,R),表示两个顶点和边缘的阻力)。
我正在使用Python和NetworkX库,但它的cycle_basis函数不返回网格(它们显然与循环基础不同)。该图是无向的,所以我不能使用simple_cycles函数。我试图修改BFS来执行此任务,但我无法保证其他周期中不包含任何循环。
我可能需要这样的东西:Algorithm for finding minimal cycles in a graph,但这个问题在最后一条评论中没有任何算法证明,我希望我的问题的答案比“实施Horton算法”更简单。
网格分析所需要的是图表的任何特定平面图中的封闭区域列表。
找到比最小周期更容易,但是哪个列表取决于您使用的平面图。
如果你有一个平面绘图,并且可以按顺时针或逆时针顺序获得每个顶点的邻居,那么只需跟踪这些封闭区域就很容易了。
否则,您可以执行以下操作:
由于每个循环包含一个不在任何其他循环中的边,因此可以保证任何其他循环都不包含循环...取决于“包含”的含义。重要的是,只要您对任何当前来源都很谨慎,这些循环就可以用于分析。也许你想在生成树中避免它们。
由于您将使用这些循环来生成要求解的方程组,其中每个边都是变量,因此使用更复杂的算法来找到“更小”的循环可能没有任何优势。