c++ - 将 adjacency_list 复制到不同的 VertexList 和 EdgeList 模板

Question

我在转换或复制 boost::adjacency_list<setS, setS, undirectedS, int, float> 时遇到问题到 boost::adjacency_list<vecS, vecS, undirectedS, int, float>所以我可以将它用于 boost::connected_components .我无法控制 VertexList和 EdgeList模板参数为 boost::setS来自外部 API，所以我正在尝试解决这个问题。

最小示例

#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>
#include <boost/graph/copy.hpp>

typedef boost::adjacency_list<boost::setS, boost::setS, boost::undirectedS, uint32_t, float> AdjacencyList;
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, uint32_t, float> AdjacencyListWithVec;


typedef AdjacencyList::vertex_descriptor VertexID;


int main(int argc, char** argv)
{
    AdjacencyList adj;
    VertexID id_0 = boost::add_vertex(adj);
    VertexID id_1 = boost::add_vertex(adj);
    VertexID id_2 = boost::add_vertex(adj);
    VertexID id_3 = boost::add_vertex(adj);
    boost::add_edge(id_0, id_1, 1.0f, adj);
    boost::add_edge(id_2, id_3, 2.0f, adj);

    AdjacencyListWithVec adj_vec;
  
    boost::copy_graph(adj, adj_vec); // won't compile
  
    std::vector<uint32_t> component(4);
    size_t num_components = boost::connected_components (adj_vec, &component[0]);
  
}

g++ 错误截断

/usr/include/boost/graph/detail/adjacency_list.hpp: In instantiation of 'struct boost::adj_list_any_vertex_pa::bind_<boost::vertex_index_t, boost::adjacency_list<boost::setS, boost::setS, boost::undirectedS, int, float>, int>':
/usr/include/boost/graph/detail/adjacency_list.hpp:2613:12:   required from 'struct boost::detail::adj_list_choose_vertex_pa<boost::vertex_index_t, boost::adjacency_list<boost::setS, boost::setS, boost::undirectedS, int, float>, int>'
/usr/include/boost/graph/detail/adjacency_list.hpp:2750:12:   required from 'struct boost::adj_list_vertex_property_selector::bind_<boost::adjacency_list<boost::setS, boost::setS, boost::undirectedS, int, float>, int, boost::vertex_index_t>'
/usr/include/boost/graph/properties.hpp:201:12:   required from 'struct boost::detail::vertex_property_map<boost::adjacency_list<boost::setS, boost::setS, boost::undirectedS, int, float>, boost::vertex_index_t>'
/usr/include/boost/graph/properties.hpp:212:10:   required from 'struct boost::property_map<boost::adjacency_list<boost::setS, boost::setS, boost::undirectedS, int, float>, boost::vertex_index_t, void>'
/usr/include/boost/graph/detail/adjacency_list.hpp:1733:5:   required by substitution of 'template<class Config, class Base, class Property> typename boost::property_map<typename Config::graph_type, Property>::const_type boost::get(Property, const boost::adj_list_helper<Config, Base>&) [with Config = boost::detail::adj_list_gen<boost::adjacency_list<boost::setS, boost::setS, boost::undirectedS, int, float>, boost::setS, boost::setS, boost::undirectedS, int, float, boost::no_property, boost::listS>::config; Base = boost::undirected_graph_helper<boost::detail::adj_list_gen<boost::adjacency_list<boost::setS, boost::setS, boost::undirectedS, int, float>, boost::setS, boost::setS, boost::undirectedS, int, float, boost::no_property, boost::listS>::config>; Property = boost::vertex_index_t]'
/usr/include/boost/graph/copy.hpp:353:38:   required from 'void boost::copy_graph(const VertexListGraph&, MutableGraph&) [with VertexListGraph = boost::adjacency_list<boost::setS, boost::setS, boost::undirectedS, int, float>; MutableGraph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, int, float>]'
/my/file/and/line/num:   required from here
/usr/include/boost/graph/detail/adjacency_list.hpp:2543:29: error: forming reference to void
         typedef value_type& reference;
                             ^~~~~~~~~
/usr/include/boost/graph/detail/adjacency_list.hpp:2544:35: error: forming reference to void
         typedef const value_type& const_reference;
                                   ^~~~~~~~~~~~~~~
/usr/include/boost/graph/detail/adjacency_list.hpp:2547:47: error: forming reference to void
           <Graph, value_type, reference, Tag> type;
                                               ^~~~
/usr/include/boost/graph/detail/adjacency_list.hpp:2549:53: error: forming reference to void
           <Graph, value_type, const_reference, Tag> const_type;
                                                     ^~~~~~~~~~
...

In file included from/my/file:5:0:
/usr/include/boost/graph/copy.hpp: In instantiation of 'void boost::copy_graph(const VertexListGraph&, MutableGraph&) [with VertexListGraph = boost::adjacency_list<boost::setS, boost::setS, boost::undirectedS, int, float>; MutableGraph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, int, float>]':
/my/file/and/line/num:   required from here
/usr/include/boost/graph/copy.hpp:353:38: error: no matching function for call to 'get(boost::vertex_index_t, const boost::adjacency_list<boost::setS, boost::setS, boost::undirectedS, int, float>&)'
                                   get(vertex_index, g_in), orig2copy[0]),
                                   ~~~^~~~~~~~~~~~~~~~~~~~

Answer 1

未指定顶点映射。创建一个很容易:

std::map<AdjacencyList::vertex_descriptor, int> index;
for (auto v : boost::make_iterator_range(boost::vertices(adj))) {
    index.insert(std::make_pair(v, index.size()));
}

AdjacencyListWithVec adj_vec;
boost::copy_graph(adj, adj_vec, boost::vertex_index_map(boost::make_assoc_property_map(index)));