未正确访问外边的加速平面面遍历

Question

我想保存我的图的外部节点。为此，我有以下代码(我显示了我认为与问题相关的部分，我确实有所有的#include头文件等)：

typedef adjacency_list <
    setS, 
    vecS, 
    undirectedS, 
    property<vertex_index_t, int>, 
    property<edge_index_t, int> 
    > SimpleGraph;

struct output_visitor : public planar_face_traversal_visitor{
    int c = 0;
    vector<int> vertexOuter;
    vector<int> save_vertexOuter;
    void begin_face(){cout << "New face: ";};
    void end_face(){
        if (c>3){
            save_vertexOuter = vertexOuter; 
        }
        cout << "End face "<< endl;
        vertexOuter.clear();
        c = 0;
    };
};

struct vertex_output_visitor : public output_visitor
{
    template <typename Vertex>

    void next_vertex(Vertex v){
        cout << v << " ";
        vertexOuter.push_back(v);
        c ++;
    }
};

SimpleGraph BuildGraph(int i, vector<vector<int>> structureInfo){
    
    // arguments of the function are not relevant here
    // I am just passing graphs from a dataset

    int j;
    SimpleGraph g;
    vector <int> adjList = structureInfo[i];

    for(int j =0; j<adjList.size(); j++){
        cout << adjList[j] << " ";
    }
    
    for (j = 0; j<adjList.size()-1; j+=2){
        add_edge(adjList[j], adjList[j+1], g);
    }

    return g;
}

SimpleGraph tempGSN = BuildGraph(i, gs_N);
vector<vec_t> embedding(num_vertices(tempGSN));
bool is_planar = boost::boyer_myrvold_planarity_test(tempGSN, boost::boyer_myrvold_params::embedding = &embedding[0]);

if (is_planar){
        
            vertex_output_visitor v_vis;
            planar_face_traversal(tempGSN, &embedding[0], v_vis);
           
            for (int j = 0; j < v_vis.save_vertexOuter.size()-1; j+=1 ){
                 Do something;}
}

到目前为止，代码在小图(节点数< 8)上工作正常，但在n=9时开始失败，我不知道为什么。例如，对于邻接列表

0 3 0 4 0 6 0 7 1 3 1 5 1 6 2 4 2 5 2 6 3 6 3 7 4 6 5 6

它返回

New face: 0 3 1 5 2 4 End face 
New face: 6 End face 
New face: 7 End face 

这是不合理的。正确的外表面应该是0 7 3 1 5 2 4。

如果能帮助我发现问题，我将不胜感激。谢谢!

Answer 1

将您的图解释为边列表(不是邻接表，因为这似乎没有意义)：

​

​

我计算出您的0 7 3 1 5 2 4序列源于平面图形表示：

​

​

所以我同意有些地方不对劲。我清理/简化了你的代码，并将其扩展为潜在的原因，但这些偏离都不会导致任何行为的改变。

我得到的唯一的洞察力-从上面的平面图和原始嵌入的输出中都有直观的意义-是第7点造成了问题。

v = 0: (0,3) (0,7) (0,6) (0,4)
v = 1: (1,5) (1,6) (3,1)
v = 2: (2,4) (2,6) (5,2)
v = 3: (3,1) (3,6) (3,7) (0,3)
v = 4: (0,4) (4,6) (2,4)
v = 5: (5,2) (5,6) (1,5)
v = 6: (0,6) (3,6) (1,6) (5,6) (2,6) (4,6)
v = 7: (0,7) (3,7)

如果您查看顶点0的边的顺序，您将注意到它们不是一致的顺时针顺序(再次参考图像)。

这可能是个bug，也可能是我误解了平面性测试算法的全部前提条件。我建议你在Boost devs上回答这个问题。

完整列表

这包括：

使用原始embedding

• attempted规范排序和绘制代码的调试转储，允许从输入和原始代码中移除特定折点的行选项中列出的可选行选项和可选的行步骤(最终只是确认嵌入未正确生成)

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/planar_face_traversal.hpp>
#include <boost/graph/boyer_myrvold_planar_test.hpp>
#include <boost/graph/make_connected.hpp>
#include <boost/graph/make_biconnected_planar.hpp>
#include <boost/graph/make_maximal_planar.hpp>
#include <boost/graph/planar_canonical_ordering.hpp>
#include <boost/graph/chrobak_payne_drawing.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/fusion/adapted.hpp> // parsing
#include <boost/spirit/home/x3.hpp> // parsing
#include <iostream>

using SimpleGraph =
    boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS,
                          boost::property<boost::vertex_index_t, int>,
                          boost::property<boost::edge_index_t, int>>;

using V  = SimpleGraph::vertex_descriptor;
using E  = SimpleGraph::edge_descriptor;
using Vs = std::vector<V>;
using Es = std::vector<E>;
using Structures = std::vector<Vs>;
using Embedding  = std::vector<Es>;

struct Point { int x, y; };
using Drawing = std::vector<Point>;

struct output_visitor : public boost::planar_face_traversal_visitor {
    void begin_traversal() const { std::cout << "Planar traversal:\n"; } 
    void begin_face()            { std::cout << "Face:";               } 
    void end_face()   const      { std::cout << "\n";                  } 
    void next_vertex(V v)        { std::cout << " " << v;              } 
    void next_edge(E e) const    { std::cout << " " << e;              } 
    void end_traversal() const   { std::cout << "Done\n";              } 
};

SimpleGraph BuildGraph(std::string_view input){
    SimpleGraph g;

    namespace x3 = boost::spirit::x3;
    static const auto edge_
        = x3::rule<E, std::pair<V,V> >{}
        = x3::uint_ >> x3::uint_;

    std::vector<std::pair<size_t, size_t> > edgeList;
    if (not phrase_parse(input.begin(), input.end(),
                         +edge_ >> x3::eoi, // grammar
                         x3::space,         // skipper
                         edgeList))
        throw std::runtime_error("BuildGraph");

    for (auto [src, tgt] : edgeList)
        if (not add_edge(src, tgt, g).second)
            throw std::runtime_error("BuildGraph");
    return g;
}

auto parse_cli(std::set<std::string_view> cli) {
    auto extract = [&] (std::string_view name) {
        bool yn = cli.count(name);
        cli.erase(name);
        return yn;
    };

    struct {
        bool make_bi, make_max, traverse, dump, draw, dot;
        std::set<V, std::greater<V> > to_remove; // descending!
    } parsed{extract("--make_bi"),
        extract("--make_max"),
        extract("--traverse"),
        extract("--dump"),
        extract("--draw"),
        extract("--dot"),
        {}};

    extract(""); // prevent zero-length options
    for (auto opt : cli)
        if (opt.front() != '-')
            parsed.to_remove.insert(std::stoul(opt.data()));

    return parsed;
}

int main(int argc, char** argv) {
    auto const opts = parse_cli({ argv+1, argv+argc });

    namespace P = boost::boyer_myrvold_params;

    SimpleGraph g =
        BuildGraph("0 3 0 4 0 6 0 7 1 3 1 5 1 6 2 4 2 5 2 6 3 6 3 7 4 6 5 6");

    // remove some vertices?
    for (auto removal : opts.to_remove) {
        clear_vertex(removal, g);
    }
    for (auto removal: opts.to_remove) { // DESCENDING ORDER
        remove_vertex(removal, g);
    }

    std::cout << "Input: ";
    for (auto e : boost::make_iterator_range(edges(g))) {
        std::cout << " " << e;
    }
    std::cout << "\n";

    // some optional tests/preprocessing, didn't improve for given inputs
    if (opts.make_bi || opts.make_bi) {
        make_connected(g);
        Embedding embedding(num_vertices(g));
        boyer_myrvold_planarity_test(g, P::embedding = &embedding[0]);

        make_biconnected_planar(g, embedding.data());
    }
    if (opts.make_max) {
        Embedding embedding(num_vertices(g));
        boyer_myrvold_planarity_test(g, P::embedding = &embedding[0]);

        make_maximal_planar(g, embedding.data());
    }

    if (opts.dot) {
        boost::write_graphviz(std::cout, g);
    }

    Embedding embedding(num_vertices(g));
    auto emap = boost::make_iterator_property_map(
        embedding.begin(), get(boost::vertex_index, g));
    bool planar = boyer_myrvold_planarity_test(g, P::embedding = emap);

    if (planar) {
        if (opts.traverse) {
            output_visitor v_vis;
            planar_face_traversal(g, emap, v_vis);
        }

        if (opts.dump) {
            std::cout << "Raw embedding:\n";
            for (auto v : boost::make_iterator_range(vertices(g))) {
                std::cout << "v = " << v << ":";
                for (auto e : embedding.at(v)) {
                    std::cout << " " << e;
                }
                std::cout << "\n";
            }
        }

        if (opts.draw) {
            Vs ordering;
            planar_canonical_ordering(g, emap, std::back_inserter(ordering));
            for (auto v : ordering) {
                std::cout << " " << v;
            }
            std::cout << "\n";

            Drawing drawing(num_vertices(g));

            // Compute the straight line drawing
            chrobak_payne_straight_line_drawing(g,
                    emap,
                    ordering.begin(), ordering.end(),
                    &drawing[0]);

            std::cout << "The straight line drawing is: " << std::endl;
            
            for (auto v : boost::make_iterator_range(vertices(g))) {
                auto [x,y] =  drawing.at(v);
                std::cout << v << " -> (" << x << ", " << y << ")\n";
            }
        }
    } else {
        std::cout << "Not planar\n";
    }

    return planar? 0 : 1;
}

原文：(--dump --traverse --make_bi)：

Input:  (0,3) (0,4) (0,6) (0,7) (1,3) (1,5) (1,6) (2,4) (2,5) (2,6) (3,6) (3,7) (4,6) (5,6)
Planar traversal:
Face: 0 (0,3) 3 (3,1) 1 (1,5) 5 (5,2) 2 (2,4) 4 (0,4)
Face: 6 (0,6)
Face: 7 (0,7)
Done
Raw embedding:
v = 0: (0,3) (0,7) (0,6) (0,4)
v = 1: (1,5) (1,6) (3,1)
v = 2: (2,4) (2,6) (5,2)
v = 3: (3,1) (3,6) (3,7) (0,3)
v = 4: (0,4) (4,6) (2,4)
v = 5: (5,2) (5,6) (1,5)
v = 6: (0,6) (3,6) (1,6) (5,6) (2,6) (4,6)
v = 7: (0,7) (3,7)

移除顶点7：(--traverse 7)

Input:  (0,3) (0,4) (0,6) (1,3) (1,5) (1,6) (2,4) (2,5) (2,6) (3,6) (4,6) (5,6)
Planar traversal:
Face: 0 (0,3) 3 (3,1) 1 (1,5) 5 (5,2) 2 (2,4) 4 (0,4)
Face: 6 (0,6)
Done

一些高级远足：--traverse --make_max 7 --draw

Input:  (0,3) (0,4) (0,6) (1,3) (1,5) (1,6) (2,4) (2,5) (2,6) (3,6) (4,6) (5,6)
Planar traversal:
Face: 0 (0,3) 3 (0,3)
Face: 4 (0,4)
Face: 6 (0,6)
Face: 1 (1,3)
Face: 5 (1,5)
Face: 2 (2,4)
Done
 0 1 5 2 4 6 3
The straight line drawing is: 
0 -> (0, 0)
1 -> (10, 0)
2 -> (6, 2)
3 -> (5, 5)
4 -> (5, 3)
5 -> (7, 1)
6 -> (5, 4)