How to use reference in boost graph property?

Question

I'm trying to define a boost adjacency list which holds a reference to a property defined in an external container (not necessarily 0 based!).

As I want to filter the resulting graph at runtime I'm trying to add all vertices at startup and connect all of them with each other (no loops).

However the compiler always complains that something is not default constructable which is not clear to me why? Is there any way to achieve what I want to do?

#include <boost/graph/adjacency_list.hpp>

struct vertex_t
{
    uint32_t num1;
    uint32_t num2;
};

using MyVec = std::vector<vertex_t>;
using AdjLst = boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS, std::reference_wrapper<vertex_t> >;

int main()
{
    MyVec vc;
    // Some sample data
    vc.push_back({123, 456});
    vc.push_back({23, 46 });
    vc.push_back({3, 6 });
    vc.push_back({12, 4 });

    AdjLst graph;
    for (auto it = vc.begin(); it != vc.end(); ++it)
    {
        add_vertex(*it, graph);
    }

    AdjLst::vertex_iterator vi, vend;
    for (boost::tie(vi, vend) = vertices(graph); vi != vend; ++vi)
    {
        auto vi2 = vi;
        while (++vi2 != vend)
        {
            add_edge(*vi, *vi2, graph); // <--------FAIL!
        }
    }

    return 1;
}

EDIT:

I just saw that (according to the docs) the property MUST be default constructible. So the question is: How can I work around that requirement? (Without falling back to pointers?)

Answer 1

The restriction is that properties need to be default-constructible. std::reference_wrapper is not. In fact, a simple

AdjLst graph(4);

would run into the same trouble. The reason is that add_edge is able to grow the vertex space:

// Here we override the directed_graph_helper add_edge() function
// so that the number of vertices is automatically changed if
// either u or v is greater than the number of vertices.
template < class Graph, class Config, class Base >
inline std::pair< typename Config::edge_descriptor, bool > add_edge(
    typename Config::vertex_descriptor u, typename Config::vertex_descriptor v,
    const typename Config::edge_property_type& p,
    vec_adj_list_impl< Graph, Config, Base >& g_)
{
    BOOST_USING_STD_MAX();
    typename Config::vertex_descriptor x
        = max BOOST_PREVENT_MACRO_SUBSTITUTION(u, v);
    if (x >= num_vertices(g_))
        g_.m_vertices.resize(x + 1);
    adj_list_helper< Config, Base >& g = g_;
    return add_edge(u, v, p, g);
}

1. One slightly non-obvious workaround is to replace vecS with a node-based container selector. The reason is that BGL doesn't know/try to help adding vertices because the vertex descriptor isn't implicitly the vertex index. See that Live On Coliru

   Other options:

2. You could use boost::optional<vertex_t&>. Live Demo

3. Purists would suggest std::optional<std::reference_wrapper<vertex_t> >, but at that point I'd simply store a vertex_t*

4. Getting mildly fancier you can move the ownership to the graph altogether and use an intrusive container on top:

Live On Coliru

    namespace bi = boost::intrusive;

    using Hook = bi::list_base_hook<bi::link_mode<bi::auto_unlink>>;
    using MyList = bi::list<struct vertex_t, bi::constant_time_size<false>>;

    struct vertex_t : Hook {
        uint32_t num1;
        uint32_t num2;

        vertex_t() = default;
        vertex_t(uint32_t a, uint32_t b) : num1(a), num2(b) {}
    };

    using AdjLst = boost::adjacency_list<boost::setS, boost::vecS,
        boost::undirectedS, vertex_t>;

    int main()
    {
        MyList vc;
        AdjLst graph;

        for (auto node : { vertex_t
                { 123, 456 },
                { 23, 46 },
                { 3, 6 },
                { 12, 4 },
             }) 
        {
            auto v = add_vertex(node, graph);
            vertex_t& stored_node = graph[v]; // note: intermediate variable for
                                              // exposition purposes only
            vc.push_back(stored_node);
        }

Simplest Listing

Of the above, I'd suggest vertex_t* as the bundle type:

Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iostream>

struct vertex_t {
    uint32_t num1;
    uint32_t num2;
};

using MyVec = std::vector<vertex_t>;
using AdjLst = boost::adjacency_list<
    boost::setS,
    boost::vecS,
    boost::undirectedS,
    vertex_t*
>;

int main()
{
    MyVec vc {
        { 123, 456 },
        { 23, 46 },
        { 3, 6 },
        { 12, 4 },
    };

    AdjLst graph;
    for (auto it = vc.begin(); it != vc.end(); ++it) {
        add_vertex(&*it, graph);
    }

    for (auto v : boost::make_iterator_range(vertices(graph)))
    {
        auto& [num1,num2] = *graph[v];
        std::cout << v << " {" << num1 << ", " << num2 << "}\n";
    }

    for (auto [src, e] = vertices(graph); src != e; ++src)
        for (auto dest = src; ++dest != e;)
            boost::add_edge(*src, *dest, graph);
}