Using boost graph library to obtain induced subgraph reachable from vertex v with distance d

Question

I'm having problems in filtering the subgraphs using boost libraries, I want to obtain induced subgraph reachable from v with distance d. Here is the python code using networkx library:

def reachable_subgraph(G, v, d):
    E = nx.bfs_edges(G, v, depth_limit=d)
    N = set([n for e in E for n in e])
    return nx.induced_subgraph(G, N)

How can I do it using Boost library? Should I use bfs_visitors? I am not very familiar with the visitor concepts so it would be helpful to know it can be done using the visitor or any other Boost approaches.

Thanks!

Should I use bfs_visitors?

Answer 1

You might use the filtered_graph adaptor.

I like to push c++20 features to get as close to Pythonesque as I can:

#include <boost/graph/filtered_graph.hpp>

template <typename Graph, typename Nodes, typename V = typename Graph::vertex_descriptor>
auto induced_subgraph(Graph& g, Nodes nodes) {
    std::function f{[n = std::move(nodes)](V v) { return n.contains(v); }};
    return boost::filtered_graph(g, boost::keep_all{}, f);
}

Now, let's write your reachable_subgraph function:

#include <boost/graph/breadth_first_search.hpp>
template <typename Graph, typename V = typename Graph::vertex_descriptor>
auto reachable_subgraph(Graph& g, V source, unsigned depth) {
    std::vector<unsigned> dist(num_vertices(g));

    auto vis = make_bfs_visitor(record_distances(dist.data(), boost::on_tree_edge{}));
    breadth_first_search(g, source, visitor(vis));

    std::set<V> N;
    for (auto [b, e] = vertices(g); b != e; ++b)
        if (auto d = dist[*b]; d && d < depth)
            N.insert(*b);

    return induced_subgraph(g, std::move(N));
}

DEMONSTRATION

See it Live On Coliru

int main() {
    boost::adjacency_list g;
    std::mt19937 prng(77); // manually selected for example
    generate_random_graph(g, 100, 150, prng);

    // print_graph(g);
    fmt::print("g has vertices [0..{}]\n", num_vertices(g) - 1);

    auto sub = reachable_subgraph(g, 5, 3);
    //fmt::print("nodes reachable < 3 from 5: {}\n", boost::make_iterator_range(vertices(sub)));

    print_graph(sub);
}

Prints

g has vertices [0..99]
8 --> 
13 --> 22 
14 --> 22 8 
22 --> 
27 --> 22 
31 --> 13 63 72 
35 --> 
50 --> 90 
63 --> 
72 --> 
90 --> 
97 --> 35 27