如何在boost graph 属性中使用reference？

Question

我正在尝试定义一个包含对属性的引用的增强邻接列表在外部容器中定义（不一定基于 0！）。

因为我想在运行时过滤结果图，所以我尝试添加所有启动时的顶点并将所有顶点相互连接（无循环）。

但是编译器总是抱怨某些东西不是默认构造的，我不清楚为什么？有什么办法可以实现我想做的事情吗？

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

编辑：

我刚刚看到（根据文档）属性必须是默认可构造的。所以问题是：我怎样才能解决这个要求？（不退回到指针？）

Answer 1

限制是属性必须是可默认构造的。 std::reference_wrapper 不是。其实一个简单的

AdjLst graph(4);

会运行陷入同样的麻烦。原因是 add_edge 能够增长顶点 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);
}

一个不太明显的解决方法是将 vecS 替换为基于节点的容器选择器。原因是 BGL 没有 know/try 来帮助添加顶点，因为顶点描述符不是隐式的顶点索引。看到 Live On Coliru

其他选项：
您可以使用 boost::optional<vertex_t&>。 Live Demo
纯粹主义者会建议std::optional<std::reference_wrapper<vertex_t> >, but at that point I'd simply store a vertex_t*
更高级一点的是，您可以将所有权完全转移到图表中，并在顶部使用侵入式容器：

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

最简单的清单

在上述中，我建议 vertex_t* 作为捆绑包类型：

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

如何在boost graph 属性中使用reference？

How to use reference in boost graph property?

c++

boost

graph

boost-graph

最简单的清单