Boost Graph Library: Adding vertices with same identification

Question

How can I represent file path using BGL? Consider path like: root/a/a/a/a/a

Corresponding graph would be 'root'->'a'->'a'->...

Is it possible to add multiple vertices sharing the same name? Could not find clear answer.

Answer 1

Sure. As long as the name is not the identifier (identity implies unique).

The whole idea of filesystem paths is that the paths are unique. So, what you would probably want is to have the unique name be the path to the node, and when displaying, choose what part of the path you want to display.

For an elegant demonstration using internal vertex names¹:

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

Now you can add any path to the graph:

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

We'll have to tell BGL to use std::identity to get the internal name from fs::path:

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

Now, demonstrating:

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

To print using the unique node paths:

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

To print using only the local names:

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

Live Demo

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

Prints (on my machine, where test.cpp exists in /home/sehe/Projects/stackoverflow):

 ---- 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/stackoverflow"
"/home/sehe/Projects/stackoverflow" --> "/home/sehe/Projects/stackoverflow/test.cpp"
"/home/sehe/Projects/stackoverflow/test.cpp" -->
 --- local name
"" --> "root" "home"
"root" --> "a"
"a" --> "a"
"a" --> "a"
"a" --> "a"
"a" --> "a"
"a" -->
"home" --> "sehe"
"sehe" --> "Projects"
"Projects" --> "stackoverflow"
"stackoverflow" --> "test.cpp"
"test.cpp" -->

BONUS

Graphviz output:

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

Gives this graphviz

¹ see e.g. How to configure boost::graph to use my own (stable) index for vertices?