如何使用boost graph遍历平面图（代表一棵树）来模拟沿着图的边缘行走

Question

我在 XY 平面上有以下图形。顶点已编号。我有

struct Point {
  double x;
  double y;
}

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

例如我可能有 6 个顶点和 5 条边

我希望选择任何顶点来开始我的遍历。我们选择顶点 1。遍历将是。

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

这相当于将图表视为田野中的栅栏，并顺时针沿着栅栏行走，保持墙位于您的右侧。

我相信这是

中描述的平面遍历

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 %20脸.

然而，Boost 图需要预先计算的平面嵌入，这需要对每个顶点周围的所有边进行预排序。我没有在 boost 库中看到自动执行此排序的方法。有吗

Answer 1

自动获取平面嵌入的方法与平面性测试的输出一样。所以你可以将其包装在你自己的函数中：

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

演示：在 Coliru 上直播：

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

更新：顺时针排序

阅读评论后，我找到了一种应用类似顺时针排序的方法：

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

请注意，我没有从固定的起点 1 获取角度，而是实际上按每个单独边缘的角度进行排序。我会让你决定这是否适合你。对于给定的例子来说这似乎已经足够了。

住在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);
}

现在打印：

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

现在打印：

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 

---

顺便说一句，我认为使用

min_element

 进行的选择可能不明确。看来在你的问题示例中，点 1 和点 4 都有同样最小的 x？