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

CodePudding user response：

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,

You will need an