Initialization of Auxillary Property Maps in Boost Graph Library

Question

Objective

Generate a random spanning tree on a randomly generated graph.

Why: because I don't know yet if I can directly generate random trees with specific number of nodes or leaves in BGL.

My problem

I think it boils down to struggling initializing the Auxillary Property Maps to a sensical default.

As you will see I've tried a number of combination of solutions, in the current state the code fails to compile with a cannot form a reference to 'void'.

What I tried

  template<class Graph, class Generator>
  auto generate_random_spanning_tree(int n_vertices, int n_edges, Generator& rng)
  {
    // create empty graph
    Graph g;

    using vertex_t = typename Graph::vertex_descriptor;
    using edge_t = typename Graph::edge_descriptor;

    // The key and value types of the map must both be the graph's vertex type.
    using predecessor_map_t = boost::static_property_map<vertex_t, vertex_t>;
    predecessor_map_t predecessor_map = boost::make_static_property_map<vertex_t,vertex_t>(vertex_t());

    // unweighted version selected by passing an object of type static_property_map<double> as the weight map, so let's go
    using weight_map_t = boost::static_property_map< double >;
    // weight_map_t weight_map = boost::make_transform_value_property_map([](edge_t& e) { return 1.0; }, get(boost::edge_bundle, g)); // nope
    //weight_map_t weight_map = boost::make_static_property_map<double>(1.0); // yes but complicated
    // weight_map_t weight_map;  // nope: why isn't it default constructible?
    double my_constant_weight = 1.0;
    weight_map_t weight_map(my_constant_weight);

    using color_map_t = typename boost::property_map<Graph, boost::vertex_color_t>::type;
    color_map_t color_map ; // i suspect this is faulty

    // mutate graph
    boost::generate_random_graph(g, n_vertices, n_edges, rng);

    // pick root, I guess we could as well pick 1st vertex
    auto root = boost::random_vertex(g, rng);

    boost::random_spanning_tree(g, rng, root, predecessor_map, weight_map, color_map);
    return g;
  }

Answer 1

First: Your own suspect

using color_map_t = typename boost::property_map<Graph, boost::vertex_color_t>::type;
color_map_t color_map; // i suspect this is faulty

Yes. PropertyMaps map properties. They are like references. Here, color_map is essentially an unitialized reference. You need something like

color_map_t color_map = get(boost::vertex_color, g);

This, of course, assumes that a vertex_color_t property map has been associated with the graph by traits. In other words, this assumes that the property is an iternal property of the graph. Internal properties are often used by default.

Second: A constant cannot be modified

You use a static property map:

auto predecessor_map =
    boost::make_static_property_map<vertex_t, vertex_t>(vertex_t());

That just creates a "virtual" property map (without a backing data structure) that returns the construction parameter on every key. Logically, the return value is constant. However, predecessor map is an output parameter:

You will need an LValuePropertyMap there. E.g.

std::map<vertex_t, vertex_t> predecessors;
auto predecessor_map =boost::make_assoc_property_map(predecessors);

Or even

auto vindex          = get(boost::vertex_index, g);
auto predecessors    = std::vector<vertex_t>(num_vertices(g));
auto predecessor_map = boost::make_safe_iterator_property_map(
    predecessors.begin(), predecessors.size(), vindex);

Which uses a vertex index to (optionally) translate descriptors into vector indices. Note that the second is fixed-size, so initialize it after creating all vertices.

Other Points Of Interest

// weight_map_t weight_map;  // nope: why isn't it default constructible?

What would it do? Surely it won't default to what you think is a good default (1.0). So I'd just write

auto weight_map = boost::static_property_map(1.0);

Simplified

I'd write the entire function as:

template <class Graph, class Generator>
auto generate_random_spanning_tree(int n_vertices, int n_edges, Generator& rng) {
    using vertex_t = typename Graph::vertex_descriptor;

    Graph g;
    generate_random_graph(g, n_vertices, n_edges, rng);

    std::map<vertex_t, vertex_t> predecessors;
    random_spanning_tree(g, rng, random_vertex(g, rng),
                         boost::make_assoc_property_map(predecessors),
                         boost::static_property_map(1.0), // unweighted
                         get(boost::vertex_color, g));
    return g;
}

Functional Problems

You're asking some good questions yourself. But let me start with some observations.

1. You have Unspecified/Undefined Behaviour because your input graph doesn't conform to the requirements:

   There must be a path from every non-root vertex of the graph to the root; the algorithm typically enters an infinite loop when given a graph that does not satisfy this property, but may also throw the exception loop_erased_random_walk_stuck if the search reaches a vertex with no outgoing edges

   Indeed, running your code only completes for a few random seeds, and fails or runs infinitely for others (this is even increasing the chance of satisfying the requirements by using undirectedS): Listing

    while true; do (set -x; time ./build/sotest& sleep 3; kill %1); done
   

   

2. You are creating the random spanning tree only to completely forget about it. Did you intend to return the predecessor map as well (or a derived path representation)?

3. Your own questions:

   • "cannot form a reference to 'void'"

     Usually indicates an associated property map could not be found (e.g. what happens if you fail to supply the vertex_color interior property. In this case the remedy is simply to use the default color map:

      random_spanning_tree(
          g, rng,
          boost::root_vertex(random_vertex(g, rng))
              .predecessor_map(boost::make_assoc_property_map(predecessors))
              .weight_map(boost::static_property_map(1.0)) // unweighted
      );
     

   • "I don't know yet if I can directly generate random trees with specific number of nodes or leaves in BGL."

     You can generate random graphs with specific number of nodes and leaves - as you already demonstrate. trees.

     You can also find random spanning trees (given a graph satisfying the preconditions).

     To adhere to the preconditions the simplest way would be to generate undirected graphs, whilst additionally making sure that the result is connected. A simple, possible inefficient(?) way to ensure it would be to explicitly connect components:

      if (int n = boost::connected_components(ug, cmap); n > 1) {
          std::cout << "Connecting " << n << " components:\n";
     
          for (int c = 1; c < n; ++c)
              std::cout << "Added " << add_edge(from(c - 1), from(c), ug).first << "\n";
      }
     

     It might be more effective to write your own generating algorithm.

BONUS EXAMPLE

Showing the use of connected_components to make sure the graph is fully connected, and even building a directed tree from undirected source graph. Also writing graphviz representations of the "raw" (undirected) source and "tree" (directed spanning tree), it seems to work pretty well.

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/random.hpp>
#include <boost/graph/random_spanning_tree.hpp>
#include <boost/property_map/function_property_map.hpp>
#include <iomanip>
#include <random>

namespace detail {
    template <typename T> struct make_undirected { using type = void; };

    template <typename A, typename B, typename C, typename D, typename E, typename F>
    struct make_undirected<boost::adjacency_list<A, B, C, D, E, F>> {
        using type = boost::adjacency_list<A, B, boost::undirectedS, D, E, F>;
    };
} // namespace detail

template <typename T> using Undirect = typename detail::make_undirected<T>::type;

template <class Graph, class Generator>
auto generate_random_spanning_tree(int n_vertices, int n_edges, Generator& rng) {
    using UG = Undirect<Graph>;
    using vertex_t = typename UG::vertex_descriptor;

    // assuming integral vertex index for simplicity
    static_assert(std::is_same_v<vertex_t, size_t>);
    static_assert(std::is_same_v<typename UG::vertex_descriptor,
                                 typename Graph::vertex_descriptor>);

    UG ug;
    generate_random_graph(ug, n_vertices, n_edges, rng);
    vertex_t const root = random_vertex(ug, rng);

    print_graph(ug, std::cout << "Raw root: " << root << ", graph:\n");

    { // make connected
        std::map<vertex_t, int> components;

        auto from = [&](int component) { // just picking the first...
            for (auto& [v, c] : components) if (c == component) return v;
            throw std::range_error("component");
        };

        auto cmap = boost::make_assoc_property_map(components);
        if (int n = connected_components(ug, cmap); n > 1) {
            std::cout << "Connecting " << n << " components:\n";

            for (int c = 1; c < n; ++c)
                std::cout << "Added " << add_edge(from(c - 1), from(c), ug).first << "\n";
        }
    }

    std::map<vertex_t, vertex_t> predecessors;
    random_spanning_tree(
        ug, rng,
        boost::root_vertex(root) //
            .predecessor_map(boost::make_assoc_property_map(predecessors)));

    Graph tree(num_vertices(ug)); // build a tree copy
    for (auto v : boost::make_iterator_range(vertices(ug)))
        if (predecessors.contains(v))
            if (auto pred = predecessors.at(v); ug.null_vertex() != pred)
                add_edge(predecessors.at(v), v, tree);

    auto save = [&predecessors](auto& g, auto name) {
        using edge_t = typename std::decay_t<decltype(g)>::edge_descriptor;
        auto tree_edge = [&predecessors](auto s, auto t) {
            auto it = predecessors.find(s);
            return it != end(predecessors) && it->second == t;
        };

        boost::dynamic_properties dp;
        dp.property("node_id", get(boost::vertex_index, g));
        dp.property("color",
                    boost::make_function_property_map<edge_t>([tree_edge, &g](edge_t e) {
                        auto s = source(e, g), t = target(e, g);
                        return tree_edge(s, t) || tree_edge(t, s) ? "red" : "gray";
                    }));

        std::ofstream os(name);
        write_graphviz_dp(os, g, dp);
    };
    save(ug, "raw.dot");
    save(tree, "tree.dot");

    return std::pair(std::move(tree), root);
}

int main(int argc, char** argv) {
    using G = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS>;

    auto const seed = argc > 1 ? std::stoull(argv[1]) : std::random_device{}();
    std::cout << "seed: " << seed << std::endl;

    std::mt19937 prng(seed);
    auto [tree, root] = generate_random_spanning_tree<G>(10, 20, prng);

    print_graph(tree, std::cout << "From root: " << root << ", tree:\n");
}

Prints the sample seed: 1577455792

Raw root: 7, graph:
0 <--> 7 2 3 7 5 2 8 
1 <--> 
2 <--> 8 0 4 0 4 9 
3 <--> 9 5 0 8 
4 <--> 7 7 2 2 5 
5 <--> 8 3 0 4 
6 <--> 
7 <--> 4 4 0 8 0 
8 <--> 2 5 7 9 0 3 
9 <--> 3 8 2 
Connecting 3 components:
Added (0,1)
Added (1,6)
From root: 7, tree:
0 --> 1 3 
1 --> 6 
2 --> 9 
3 --> 5 
4 --> 2 
5 --> 4 8 
6 --> 
7 --> 0 
8 --> 
9 --> 

Running locally with:

watch './build/sotest; for a in raw tree; do (set -x ; dot -Tpng -o $a.png $a.dot); done'

Shows random solutions like: