Search code examples
c++boost-graph

How to use boost graph to traverse a planar graph ( representing a tree ) to simulate walking around the edge of the graph

I have the following graph on the XY plane. Vertices are numbered. I have

struct Point {
  double x;
  double y;
}

std::vector<Point> points;
std::vector<std::pair<size_t, size_t> edges;

For example I may have 6 vertices and 5 edges

enter image description here

I wish to choose any vertex to start my traversal. Let's choose vertex 1. The traversal would be.

  • 1
  • 3
  • 6
  • 4
  • 6
  • 5
  • 6
  • 3
  • 2
  • 3
  • 1

This is equivalent to treating the graph like a fence in a field and walking along the fence clockwise keeping the wall to your right hand side.

enter image description here

I believe this is the planar traversal as described in

https://www.boost.org/doc/libs/1_51_0/libs/graph/doc/planar_face_traversal.html#:~:text=A%20traversal%20of%20the%20faces,the%20border%20of%20the%20face.

However boost graph requires a precalculated planar embedding which requires pre-sorting all the edges around each vertex. I didn't see a way within the boost library to perform this sorting automatically. Is there one?

Solution

  • The way to automatically get the planar embedding is as the output from a planarity test. So you could wrap that in your own function:

    template <typename G> void walk_faces(G const& g) {
    using V = G::vertex_descriptor;
    using E = G::edge_descriptor;

    // edge index
    std::map<E, size_t> e_index;
    for (size_t edge_count = 0; auto e : make_iterator_range(edges(g)))
        e_index[e] = edge_count++;

    // compute the planar embedding
    using Edges = std::vector<E>;
    std::vector<Edges> embedding(num_vertices(g));
    auto embedmap = make_safe_iterator_property_map( //
        embedding.begin(), embedding.size(), get(boost::vertex_index, g));

    namespace P = boost::boyer_myrvold_params;
    if (!boyer_myrvold_planarity_test(P::graph = g, P::embedding = embedmap))
        std::runtime_error("not a planar graph");

    struct : boost::planar_face_traversal_visitor {
        void begin_face()     const { std::cout << "New face: "; }
        void end_face()       const { std::cout << std::endl; }
        void next_vertex(V v) const { std::cout << v << " "; }
    } vis;

    planar_face_traversal(g, embedmap, vis, make_assoc_property_map(e_index));
}

    Demo: Live On Coliru:

    New face: 1 3 2 3 6 5 6 4 6 3

    UPDATE: Clockwise ordering

    After reading the comments, I figured out a way to apply a siilar clock-wise ordering:

    for (auto v : boost::make_iterator_range(vertices(g)))
    std::ranges::sort( //
        g.out_edge_list(v), std::less{}, [src = g[v], &g](auto const& out) {
            auto& dst = g[out.get_iter()->m_target];
            return atan2(dst.y - src.y, dst.x - src.x);
        });

    Note how I didn't take the angle from a fixed starting point¹, instead actually sorting by the angle of each individual edge. I'll leave it to you to decide whether that's okay for you. It seemed to be enough for the given example.

    Live On Coliru

    #include <boost/core/demangle.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boyer_myrvold_planar_test.hpp>
#include <boost/graph/planar_face_traversal.hpp>
#include <cmath>
#include <iostream>
#include <ranges>

template <typename G>
void walk_faces(G const& g) {
    using V = G::vertex_descriptor;
    using E = G::edge_descriptor;

    // edge index
    std::map<E, size_t> e_index;
    for (size_t edge_count = 0; auto e : make_iterator_range(edges(g)))
        e_index[e] = edge_count++;

    // compute the planar embedding
    using Edges = std::vector<E>;
    std::vector<Edges> embedding(num_vertices(g));
    auto embedmap = make_safe_iterator_property_map( //
        embedding.begin(), embedding.size(), get(boost::vertex_index, g));

    namespace P = boost::boyer_myrvold_params;
    if (!boyer_myrvold_planarity_test(P::graph = g, P::embedding = embedmap))
        std::runtime_error("not a planar graph");

    struct : boost::planar_face_traversal_visitor {
        void begin_face()     const { std::cout << "New face: "; }
        void end_face()       const { std::cout << std::endl; }
        void next_vertex(V v) const { std::cout << v << " "; }
    } vis;

    planar_face_traversal(g, embedmap, vis, make_assoc_property_map(e_index));
}

int main() {
    struct Point {
        double x, y;
    };
    using G = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Point>;
    G g;

    add_edge(1, 3, g);
    add_edge(3, 6, g);
    add_edge(3, 2, g);
    add_edge(6, 4, g);
    add_edge(6, 5, g);

    g[1] = {-1, -1};
    g[2] = {+1, -1};
    g[3] = {+0, +0};
    g[4] = {-1, +3};
    g[5] = {+1, +3};
    g[6] = {+0, +2};

    std::cout << "Before: ";
    walk_faces(g);

    for (auto v : boost::make_iterator_range(vertices(g)))
        std::ranges::sort( //
            g.out_edge_list(v), std::less{}, [src = g[v], &g](auto const& out) {
                auto& dst = g[out.get_iter()->m_target];
                return atan2(dst.y - src.y, dst.x - src.x);
            });

    std::cout << "After:  ";
    walk_faces(g);
}

    Which now prints:

    #include <boost/core/demangle.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boyer_myrvold_planar_test.hpp>
#include <boost/graph/planar_face_traversal.hpp>
#include <cmath>
#include <iostream>
#include <ranges>

template <typename G>
void walk_faces(G const& g) {
    using V = G::vertex_descriptor;
    using E = G::edge_descriptor;

    // edge index
    std::map<E, size_t> e_index;
    for (size_t edge_count = 0; auto e : make_iterator_range(edges(g)))
        e_index[e] = edge_count++;

    // compute the planar embedding
    using Edges = std::vector<E>;
    std::vector<Edges> embedding(num_vertices(g));
    auto embedmap = make_safe_iterator_property_map( //
        embedding.begin(), embedding.size(), get(boost::vertex_index, g));

    namespace P = boost::boyer_myrvold_params;
    if (!boyer_myrvold_planarity_test(P::graph = g, P::embedding = embedmap))
        std::runtime_error("not a planar graph");

    struct : boost::planar_face_traversal_visitor {
        void begin_face()     const { std::cout << "New face: "; }
        void end_face()       const { std::cout << std::endl; }
        void next_vertex(V v) const { std::cout << v << " "; }
    } vis;

    planar_face_traversal(g, embedmap, vis, make_assoc_property_map(e_index));
}

int main() {
    struct Point {
        double x, y;
    };
    using G = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Point>;
    G g;

    add_edge(1, 3, g);
    add_edge(3, 6, g);
    add_edge(3, 2, g);
    add_edge(6, 4, g);
    add_edge(6, 5, g);

    g[1] = {-1, -1};
    g[2] = {+1, -1};
    g[3] = {+0, +0};
    g[4] = {-1, +3};
    g[5] = {+1, +3};
    g[6] = {+0, +2};

    std::cout << "Before: ";
    walk_faces(g);

    for (auto v : boost::make_iterator_range(vertices(g)))
        std::ranges::sort( //
            g.out_edge_list(v), std::less{}, [src = g[v], &g](auto const& out) {
                auto [x, y] = g[out.get_iter()->m_target];
                return atan2(y - src.y, x - src.x);
            });

    std::cout << "After:  ";
    walk_faces(g);
}

    Now prints:

    Before: New face: 1 3 2 3 6 5 6 4 6 3 
After:  New face: 1 3 6 4 6 5 6 3 2 3

    ¹ I suppose the selection using min_element may be ambiguous, by the way. It seems that in your question example both points 1 and 4 have equally minimal x?