CODEWITHSUNDEEP
c++boostboost-graph
Logan Byers
Logan Byers

Reputation: 1573

Copy adjacency_list to different VertexList and EdgeList template

I am having trouble converting or copying a boost::adjacency_list<setS, setS, undirectedS, int, float> to a boost::adjacency_list<vecS, vecS, undirectedS, int, float> so I can use it for boost::connected_components. I cannot control the VertexList and EdgeList template arguments being boost::setS from the outside API so I am trying to work around that.

Minimal example

#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++ error truncated

/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]),
                                   ~~~^~~~~~~~~~~~~~~~~~~~

Upvotes: 3

Views: 284

Answers (2)

sehe
sehe

Reputation: 392911

The vertex map is not specified. It's easy to create one:

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

Upvotes: 3

mindriot
mindriot

Reputation: 5668

From the 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.

Looking at the documentation for adjacency_list, we see:

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.

In other words, your limiting factor is that the alternative vertex list representations do not play well with the default vertex index map. The edge list representation is not affected. Indeed, using setS only for the OutEdgeList works just fine, i.e. the following works:

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

If your VertexList has to be setS, then you will have to provide your own vertex index map that can handle it. Unfortunately I cannot help you there, but the following related SO questions might help you:

Upvotes: 2

Related Questions