BOOST Planar Face Traversal not visiting outer edges correctly

Question

I want to save what are the outer nodes of my graph. For that, I have the following code (I am showing the parts I believe are relevant for the problem, I do have all the #include headers etc...):

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;}
}

So far, the code has worked correctly on small graphs (num nodes < 8), but it has started to fail at n = 9 and I don't understand why. For instance, for an adjacency list

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

it returns

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

which does not make sense. The correct outer face would be 0 7 3 1 5 2 4.

I would be grateful for any help spotting the problem. Thanks!

Answer 1

Interpreting your graph as an edgelist (not an adjacency list, because that didn't seem to make sense):

I worked out that your 0 7 3 1 5 2 4 sequence stems from the plane drawing representation:

So I concur that there is something amiss. I cleaned up/simplified your code and extended it with excursions into potential causes, but none of the excursions lead to any change in behaviour.

The only insight I gained - which makes intuitive sense from both the planar drawing above and the output of the raw embedding is the point 7 is creating the problem.

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)

If you look at the ordering of the edges for vertex 0, you will notice that they are not in consistent clockwise order (referring to the image again).

This could either be a bug, or me misunderstanding the full preconditions for the planarity-test algorithm. I suggest you take the question up at the Boost devs.

Complete Listing

This includes:

• optional make_connected/make_biconnected_planar/make_maximum_planar steps as outlined in various docs
• command line options that allow removal of specific vertices from the input
• the original code with debug dump of raw embedding
• attempted canonical ordering and drawing code (that ended up just confirming that the embedding isn't correctly produced)

Live On Compiler Explorero

#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;
}

Original: (--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)

Removing vertex 7: (--traverse 7) https://godbolt.org/z/7e3Mfx:

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

Some advanced excursions: --traverse --make_max 7 --draw https://godbolt.org/z/bbdba5:

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)