Boost planar_face_traversal未正确识别外层面节点的问题
问题根因定位
图的出边容器类型不兼容平面嵌入要求
你定义的图用setS作为出边列表容器,该容器会自动对存储的邻接边按字典序固定排序,无法修改邻居的排布顺序。而boyer_myrvold_planarity_test生成平面嵌入时,需要按圆周旋转顺序存储每个顶点的邻居序列,这个顺序不一定和字典序匹配。
之前节点数小于8时,刚好所有顶点的邻接字典序和算法需要的旋转顺序一致,因此没有暴露问题;节点数升高后,核心连接点的邻居数量增多,算法生成的旋转顺序和setS的固定字典序不匹配,直接导致嵌入结果失效。embedding类型未正确定义
代码中使用的vec_t是未定义的类型,算法无法正确把生成的邻居旋转顺序写入embedding数组,直接导致后续面遍历的顺序混乱,你看到的单独输出6、7的单顶点碎片面,就是遍历被错误顺序打断的结果。外层面判定逻辑完全错误
代码中通过if (c>3)判断是否保存为外层面,这个逻辑没有任何平面几何依据:- 当图存在较大的内部面(比如四边形、五边形内部面)时,会被错误识别为外层面,覆盖之前的正确结果;
- 当图大部分内部面是三角形(边数=3)、外层面边数大于3时,这个判断才会偶然在小图上生效,图结构稍复杂就会失效。
你本次的示例图中,中心顶点6连接所有外围顶点,形成6个三角形内部面,这些面的c值都是3,被代码排除在外,剩下的碎片面因为c值过小根本不会被保存,最终拿到的面序列和预期完全不符。
修正方案
- 调整图的出边容器类型,把
setS替换为vecS,允许邻接边的顺序按照平面旋转排布,适配嵌入遍历要求:typedef adjacency_list < vecS, // 替换原setS vecS, undirectedS, property<vertex_index_t, int>, property<edge_index_t, int> > SimpleGraph; - 显式定义合法的embedding类型,不要使用未声明的
vec_t:using vertex_desc = SimpleGraph::vertex_descriptor; std::vector<std::vector<vertex_desc>> embedding(num_vertices(tempGSN)); - 调整visitor的面存储逻辑,不要通过面的顶点数判断外层面:
struct output_visitor : public planar_face_traversal_visitor{ int c = 0; std::vector<int> current_face; std::vector<std::vector<int>> all_faces; // 存储所有遍历到的面 void begin_face(){ current_face.clear(); c = 0; }; void end_face(){ all_faces.push_back(current_face); c = 0; }; }; struct vertex_output_visitor : public output_visitor { template <typename Vertex> void next_vertex(Vertex v){ current_face.push_back(static_cast<int>(v)); c ++; } }; - 遍历完成后直接取最后一个存储的面作为外层面:
Boost的planar_face_traversal会优先遍历所有和邻接边相邻的有界面,最后一个触发end_face的序列就是包围全图的外部面,即你需要的外层面节点序列。if (is_planar){ vertex_output_visitor v_vis; planar_face_traversal(tempGSN, &embedding[0], v_vis); // 最后一个面即为外层面 std::vector<int> outer_face = v_vis.all_faces.back(); // 后续业务逻辑处理outer_face即可 }
注意:如果保留
setS作为出边容器,即使embedding定义正确,算法写入的邻居顺序也会因为set的自动排序失效,遍历结果始终和实际嵌入不匹配,这是问题在节点数增加后突然出现的核心原因。
内容的提问来源于stack exchange,提问作者ma7642
相关产品推荐
相关产品推荐

