寻找平面图最小循环基的算法
Algorithm for finding minimal cycle basis of planar graph
我有一个平面图，其中所有节点代表 (X, Y) 坐标。边从不在平面上相交。该图表示城市的道路。
是否有 Python 库提供可用于查找最小循环基础（即封闭区域）的算法。或者比较简单的算法（目前效率不是主要问题）
我目前正在使用 NetworkX，它只有 cycle_basis，但没有最小周期基础的功能。我找到的唯一参考文献是 this algorithm，但我没有时间完整地 read/implement。
等等，如果该图实际上是一个城市的表示，那么它已经有一个嵌入了。只需采用嵌入的面孔即可。你不能删除一个面（即它是最小的）并且最小循环基是唯一的（你引用的论文的第一个引理），所以这就是你的解决方案！
我有一个平面图，其中所有节点代表 (X, Y) 坐标。边从不在平面上相交。该图表示城市的道路。
是否有 Python 库提供可用于查找最小循环基础（即封闭区域）的算法。或者比较简单的算法（目前效率不是主要问题）
我目前正在使用 NetworkX，它只有 cycle_basis，但没有最小周期基础的功能。我找到的唯一参考文献是 this algorithm，但我没有时间完整地 read/implement。
等等，如果该图实际上是一个城市的表示，那么它已经有一个嵌入了。只需采用嵌入的面孔即可。你不能删除一个面（即它是最小的）并且最小循环基是唯一的（你引用的论文的第一个引理），所以这就是你的解决方案！