复制 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

来自documentation to boost::copy_graph:

Named parameters

[…]

IN: vertex_index_map(VertexIndexMap i_map)

The vertex index map type must be a model of Readable Property Map and must map the vertex descriptors of G to the integers in the half-open range [0,num_vertices(G)).

Default: get(vertex_index, G).
Note: if you use this default, make sure your graph has an internal vertex_index property. For example, adjacency_list with VertexList=listS does not have an internal vertex_index property.

查看 documentation for adjacency_list，我们看到：

If the VertexList of the graph is vecS, then the graph has a builtin vertex indices accessed via the property map for the vertex_index_t property.

换句话说，您的限制因素是替代顶点列表表示不能很好地与默认顶点索引映射配合使用。边列表表示不受影响。实际上，仅对 OutEdgeList 使用 setS 就可以正常工作，即以下工作：

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

如果您的 VertexList 有为 setS，那么您将必须提供自己的可以处理它的顶点索引图。很遗憾，我无法在这方面为您提供帮助，但以下相关的 SO 问题可能会对您有所帮助：

Dijkstra Shortest Path with VertexList = ListS in boost graph
BGL dijkstra_shortest_path algorithm method does not accept my color map exterior property

Answer 2

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

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

复制 adjacency_list 到不同的 VertexList 和 EdgeList 模板

Copy adjacency_list to different VertexList and EdgeList template

c++

boost

boost-graph

最小示例

g++ 错误截断

Named parameters