You need to enable JavaScript to run this app. Boost planar_face_traversal未正确识别外层面节点的问题
优惠活动
大模型
产品
解决方案
定价
更多

Boost planar_face_traversal未正确识别外层面节点的问题

问题根因定位
  • 图的出边容器类型不兼容平面嵌入要求
    你定义的图用setS作为出边列表容器,该容器会自动对存储的邻接边按字典序固定排序,无法修改邻居的排布顺序。而boyer_myrvold_planarity_test生成平面嵌入时,需要按圆周旋转顺序存储每个顶点的邻居序列,这个顺序不一定和字典序匹配。
    之前节点数小于8时,刚好所有顶点的邻接字典序和算法需要的旋转顺序一致,因此没有暴露问题;节点数升高后,核心连接点的邻居数量增多,算法生成的旋转顺序和setS的固定字典序不匹配,直接导致嵌入结果失效。

  • embedding类型未正确定义
    代码中使用的vec_t是未定义的类型,算法无法正确把生成的邻居旋转顺序写入embedding数组,直接导致后续面遍历的顺序混乱,你看到的单独输出6、7的单顶点碎片面,就是遍历被错误顺序打断的结果。

  • 外层面判定逻辑完全错误
    代码中通过if (c>3)判断是否保存为外层面,这个逻辑没有任何平面几何依据:

    1. 当图存在较大的内部面(比如四边形、五边形内部面)时,会被错误识别为外层面,覆盖之前的正确结果;
    2. 当图大部分内部面是三角形(边数=3)、外层面边数大于3时,这个判断才会偶然在小图上生效,图结构稍复杂就会失效。
      你本次的示例图中,中心顶点6连接所有外围顶点,形成6个三角形内部面,这些面的c值都是3,被代码排除在外,剩下的碎片面因为c值过小根本不会被保存,最终拿到的面序列和预期完全不符。
修正方案
  1. 调整图的出边容器类型,把setS替换为vecS,允许邻接边的顺序按照平面旋转排布,适配嵌入遍历要求:
    typedef adjacency_list <
        vecS,  // 替换原setS
        vecS, 
        undirectedS, 
        property<vertex_index_t, int>, 
        property<edge_index_t, int> 
    > SimpleGraph;
    
  2. 显式定义合法的embedding类型,不要使用未声明的vec_t:
    using vertex_desc = SimpleGraph::vertex_descriptor;
    std::vector<std::vector<vertex_desc>> embedding(num_vertices(tempGSN));
    
  3. 调整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 ++;
        }
    };
    
  4. 遍历完成后直接取最后一个存储的面作为外层面:
    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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.03 21:15:10