Boost Graph Library：添加具有相同标识的顶点

Question

如何使用 BGL 表示文件路径？考虑如下路径：root/a/a/a/a/a

对应的图表是'root'->'a'->'a'->...

是否可以添加多个同名的顶点？找不到明确的答案。

Answer 1

当然可以。只要名称不是标识符（标识意味着唯一）。

文件系统路径的整体思想是路径是唯一的。因此，您可能想要的是将唯一名称作为节点的路径，并在显示时选择要显示的路径部分。

使用内部顶点名称的优雅演示¹：

using G = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, fs::path>;
using V = G::vertex_descriptor;

现在您可以向图表添加任何路径：

void add_path(fs::path p, G& g) {
    if (p.empty()) return;
    if (!p.has_root_path()) p = fs::absolute(p);

    std::optional<V> prev;
    fs::path curr;
    for (auto const& el : p) {
        curr /= el;
        auto v = add_vertex(curr, g);
        if (prev)
            add_edge(*prev, v, g);
        prev = v;
    }
}

我们必须告诉 BGL 使用 std::identity 从 fs::path:

获取内部名称

template <> struct boost::graph::internal_vertex_name<fs::path> {
    struct type : std::identity {
        using result_type = fs::path;
    };
};

现在，演示：

G g;

add_path("/root/a/a/a/a/a", g);
add_path("test.cpp", g);

要使用顶点 ID 进行打印：

print_graph(g);

要使用唯一节点路径进行打印：

auto paths = get(boost::vertex_bundle, g);
print_graph(g, paths);

仅使用本地名称进行打印：

auto filename = std::mem_fn(&fs::path::filename);
auto local    = make_transform_value_property_map(filename, paths);
print_graph(g, local);

现场演示

Live On Compiler Explorer

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <filesystem>
using std::filesystem::path;

template <>
struct boost::graph::internal_vertex_name<path> {
    struct type : std::identity {
        using result_type = path;
    };
};

using G =
    boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, path>;
using V = G::vertex_descriptor;

void add_path(path p, G& g) {
    if (p.empty()) return;
    if (!p.has_root_path()) p = absolute(p);

    std::optional<V> prev;
    path curr;
    for (auto const& el : p) {
        curr /= el;
        auto v = add_vertex(curr, g);
        if (prev) add_edge(*prev, v, g);
        prev = v;
    }
}

int main() {
    G g;

    add_path("/root/a/a/a/a/a", g);
    add_path("test.cpp", g);

    // To print using the vertex ids:
    print_graph(g, std::cout << " ---- vertex index\n");

    // To print using the unique node paths:
    auto paths = get(boost::vertex_bundle, g);
    print_graph(g, paths, std::cout << " --- node path\n");

    // To print using only the local names:
    auto filename = std::mem_fn(&path::filename);
    auto local = make_transform_value_property_map(filename, paths);
    print_graph(g, local, std::cout << " --- local name\n");
}

打印（在我的机器上，test.cpp 存在于 /home/sehe/Projects/Whosebug 中）：

 ---- vertex index
0 --> 1 7
1 --> 2
2 --> 3
3 --> 4
4 --> 5
5 --> 6
6 -->
7 --> 8
8 --> 9
9 --> 10
10 --> 11
11 -->
 --- node path
"/" --> "/root" "/home"
"/root" --> "/root/a"
"/root/a" --> "/root/a/a"
"/root/a/a" --> "/root/a/a/a"
"/root/a/a/a" --> "/root/a/a/a/a"
"/root/a/a/a/a" --> "/root/a/a/a/a/a"
"/root/a/a/a/a/a" -->
"/home" --> "/home/sehe"
"/home/sehe" --> "/home/sehe/Projects"
"/home/sehe/Projects" --> "/home/sehe/Projects/Whosebug"
"/home/sehe/Projects/Whosebug" --> "/home/sehe/Projects/Whosebug/test.cpp"
"/home/sehe/Projects/Whosebug/test.cpp" -->
 --- local name
"" --> "root" "home"
"root" --> "a"
"a" --> "a"
"a" --> "a"
"a" --> "a"
"a" --> "a"
"a" -->
"home" --> "sehe"
"sehe" --> "Projects"
"Projects" --> "Whosebug"
"Whosebug" --> "test.cpp"
"test.cpp" -->

奖金

Graphviz 输出：

write_graphviz(std::cout, g, boost::label_writer{local});

给予this graphviz

¹ 参见示例

Boost Graph Library：添加具有相同标识的顶点

Boost Graph Library: Adding vertices with same identification

c++

boost

boost-graph

现场演示

奖金