Logan Byers Logan Byers - 1 month ago 13
C++ Question

How does boost::copy_graph's vertex_copy work?

I am using

boost::copy_graph
to copy an
adjacency_list
into another
adjacency_list
with a different
VertexProperties
template. To do this, I am trying to use the
vertex_copy
parameter (doc here). I am running into a compiler error that tells the I have a wrong type for the vertex properties of the second (to-be-copied) graph.

Minimal Example



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

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

typedef AdjacencyList::vertex_descriptor VertexID;

struct custom_property
{
uint32_t label;
float f;
};

typedef boost::adjacency_list<boost::vecS,
boost::vecS,
boost::undirectedS,
custom_property,
float> AdjacencyListCustom;

struct vertex_copier
{
void operator() (uint32_t &input, custom_property &output)
{
output.label = input;
output.f = 0.;
}
};


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

AdjacencyListCustom adj_custom;
boost::copy_graph(adj, adj_custom, boost::vertex_copy(vertex_copier()));

}


g++ compilation error



...
/usr/include/boost/graph/copy.hpp:164:22: error: no match for call to '(vertex_copier) (boost::iterators::detail::iterator_facade_base<boost::range_detail::integer_iterator<long unsigned int>, long unsigned int, boost::iterators::random_access_traversal_tag, long unsigned int, long int, false, false>::reference, boost::graph_traits<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, custom_property, float> >::vertex_descriptor&)'
copy_vertex(*vi, new_v);
~~~~~~~~~~~^~~~~~~~~~~~
/path/to/file.cpp: note: candidate: void vertex_copier::operator()(uint32_t&, custom_property&)
void operator() (uint32_t &input, custom_property &output)
^~~~~~~~
/path/to/file.cpp: note: no known conversion for argument 2 from 'boost::graph_traits<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, custom_property, float> >::vertex_descriptor {aka long unsigned int}' to 'custom_property&'


This tells me that that
vertex_copy
is actually trying to copy the
vertex_descriptor
, which is a
long unsigned int
, not a
custom_property
. This seems to go against what is stated in the docs:

This is a Binary Function that copies the properties of a vertex in the original graph into the corresponding vertex in the copy.

How does
vertex_copy
work? Can it be used to set/define vertex properties in the copied graph that are not in the original? If not, do these properties have to be set after the copying by iterating through the graph? Can I apply a mapping en masse or does each vertex have to be visited and updated?


EDIT:
If I attempt to use
copy_graph
without specifying
vertex_copy
, then there is an error because the
=
operator does not exist between
custom_property
and
uint32_t
.

Answer

Sidestepping the question for a second, the simplest way to achieve things would be to add the appropriate conversion constructor to the custom property:

struct custom_property {
    custom_property(uint32_t label = 0, float f = 0) : label(label), f(f) {}
    uint32_t label;
    float f;
};

In which case, a simple copy will work:

boost::copy_graph(adj, adj_custom);

See it Live On Coliru


Regarding the vertex copier, it receives the vertex decriptors. To access the vertex properties, you need to have the graph reference:

struct vertex_copier {
    AdjacencyList& from;
    AdjacencyListCustom& to;

    void operator()(AdjacencyList::vertex_descriptor input, AdjacencyListCustom::vertex_descriptor output) const {
        to[output] = { from[input], 0.f };
    }
};

In which case you'd invoke things:

boost::copy_graph(adj, adj_custom, boost::vertex_copy(vertex_copier{adj, adj_custom}));

Again, Live On Coliru

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

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

typedef AdjacencyList::vertex_descriptor VertexID;

    struct custom_property {
        //custom_property(uint32_t label = 0, float f = 0) : label(label), f(f) {}
        uint32_t label;
        float f;
    };

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, custom_property, float> AdjacencyListCustom;

struct vertex_copier {
    AdjacencyList& from;
    AdjacencyListCustom& to;

    void operator()(AdjacencyList::vertex_descriptor input, AdjacencyListCustom::vertex_descriptor output) const {
        to[output] = { from[input], 0.f };
    }
};

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

    AdjacencyListCustom adj_custom;
    boost::copy_graph(adj, adj_custom, boost::vertex_copy(vertex_copier{adj, adj_custom}));
}