Algorithm for finding minimal cycle basis of planar graph

I have a planar graph, where all nodes represent (X, Y) coordinates. The edges never intersect on the plane. The graph represents roads on of a city. Is there a Python library that provides an algorithm available for finding the minimal cycle basis, ie the enclosed regions. Or a relatively simple algorithm (efficiency is not the main problem currently) I'm currently using NetworkX, which only has cycle_basis , but no function for a minimal cycle basis. The only reference I have found is this algorithm, but I don't have the time to read/implement this in full.

---

Wait if the graph is actually a representation of a city, then there's one embedding of it, already. Just take t the faces of that embedding. You can't remove one face (ie. It's minimal) and the minimal cycle base is unique (first lemma of the paper you cite), so there's your solution!

链接地址: http://www.djcxy.com/p/29224.html

上一篇: 如何使用matplotlib或graphviz在networkx中绘制多图

下一篇: 求平面图的最小循环基的算法