Copying from grid_graph to adjacency_list with boost::copy_graph

Question

I'm using the boost graph library and trying to initalise a MutableGraph to start life as a grid. Edges will be added and removed later in life, so I think adjacency_list<vecS,listS,undirectedS> is the right choice.

My reading about BGL indicated that the sensible way to initalise it with these edges would be to take advantage of boost::grid_graph by using boost::copy_graph to copy from a boost::grid_graph that can make all the initial edges for me for free. I thought that made sense - copy_graph copies from a model of VertexListGraph to a model of a MutableGraph, which is exactly what I have.

I initially tried using the 2-argument version of copy_graph, with the vague hope that something sensible would happen with the defaults for the rest. That turned out not to be the case, grid_graph (for reasons I couldn't quite figure out) doesn't seem to have a facility for using PropertyMaps with either edges or vertices, so the default vertex_copy and edge_copy failed (with a compiler error) copying the properties.

Since the 2-argument version clearly didn't seem appropriate I move on and tried to implement my own binary operator for copying vertices and edges. Even with a 'no-op' copy this doesn't work as well as I'd hope (i.e. it doesn't compile).

I've put together a minimum working example that illustrates the problem:

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

struct Position {
  int x, y;
};

struct VertexProperties {
  Position pos;
};

typedef boost::adjacency_list<boost::vecS, boost::listS, boost::undirectedS, 
                      VertexProperties> Graph;

struct MyCopy {
  template <typename S, typename D>
  void operator()(const S& /*src*/, D& /*dest*/) {
    // Nothing for now, deduced types to try and just make it compile
    // TODO: set values for pos to reflect position on grid.
  }
};

int main() {
    boost::array<std::size_t, 2> lengths = { { 3, 3 } };
    boost::grid_graph<2> grid(lengths);

    Graph graph;
    MyCopy copier;
    // Using 3-Arg version of copy_graph so we can specify a custom way of copying to create the properties
    boost::copy_graph(grid,graph,boost::bgl_named_params<MyCopy,boost::vertex_copy_t,
                                 boost::bgl_named_params<MyCopy,boost::edge_copy_t> >(copier));
}

This example doesn't compile:

g++ -Wextra -Wall -O2 -g -o copytest.o -c copytest.cc
In file included from /usr/include/boost/graph/grid_graph.hpp:24:0,
                 from copytest.cc:2:
/usr/include/boost/iterator/transform_iterator.hpp: In constructor ‘boost::transform_iterator<UnaryFunction, Iterator, Reference, Value>::transform_iterator() [with UnaryFunc = boost::detail::grid_graph_vertex_at<boost::grid_graph<2u> >, Iterator = boost::counting_iterator<unsigned int, boost::use_default, boost::use_default>, Reference = boost::use_default, Value = boost::use_default]’:
/usr/include/boost/graph/copy.hpp:115:55:   instantiated from ‘static void boost::detail::copy_graph_impl<0>::apply(const Graph&, MutableGraph&, CopyVertex, CopyEdge, Orig2CopyVertexIndexMap, IndexMap) [with Graph = boost::grid_graph<2u>, MutableGraph = boost::adjacency_list<boost::vecS, boost::listS, boost::undirectedS, VertexProperties>, CopyVertex = MyCopy, CopyEdge = MyCopy, IndexMap = boost::grid_graph_index_map<boost::grid_graph<2u>, boost::array<unsigned int, 2u>, unsigned int>, Orig2CopyVertexIndexMap = boost::iterator_property_map<__gnu_cxx::__normal_iterator<void**, std::vector<void*, std::allocator<void*> > >, boost::grid_graph_index_map<boost::grid_graph<2u>, boost::array<unsigned int, 2u>, unsigned int>, void*, void*&>]’
/usr/include/boost/graph/copy.hpp:327:5:   instantiated from ‘void boost::copy_graph(const VertexListGraph&, MutableGraph&, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = boost::grid_graph<2u>, MutableGraph = boost::adjacency_list<boost::vecS, boost::listS, boost::undirectedS, VertexProperties>, P = MyCopy, T = boost::vertex_copy_t, R = boost::bgl_named_params<MyCopy, boost::edge_copy_t>]’
/mnt/home/ajw/code/hpcwales/copytest.cc:31:66:   instantiated from here
/usr/include/boost/iterator/transform_iterator.hpp:100:26: error: no matching function for call to ‘boost::detail::grid_graph_vertex_at<boost::grid_graph<2u> >::grid_graph_vertex_at()’
/usr/include/boost/graph/grid_graph.hpp:104:7: note: candidates are: boost::detail::grid_graph_vertex_at<Graph>::grid_graph_vertex_at(const Graph*) [with Graph = boost::grid_graph<2u>]
/usr/include/boost/graph/grid_graph.hpp:100:33: note:                 boost::detail::grid_graph_vertex_at<boost::grid_graph<2u> >::grid_graph_vertex_at(const boost::detail::grid_graph_vertex_at<boost::grid_graph<2u> >&)

My analysis of that error is that it seems to be trying to default construct part of the internals of grid_graph, which can't be default constructed, for some reason that isn't terribly clear to me. (clang doesn't really tell me anything I can't see from g++ here).

Questions:

1. Is this the right way to go about initalising a mutable graph to start as a regular grid? I initially thought it was much easier than writing a function to do so myself, but now I'm not so sure!
2. Why is the default value of orig_to_copy and/or vertex_index not appropriate here? I'm assuming that those two are the cause of the error. (Which, if any, of those is actually causing the problem? I can't decipher what the root cause of the current error is).
3. What is the "correct" way of fixing this?

Answer 1

You are on the right track, but there are two things that need to be changed in your code. The first is that there is a special method of defining custom vertex properties. The second is that there is a different syntax (more preferred and probably the only one that is correct) for BGL named parameters.

On the first item, please refer to the section of the documentation titled Custom Vertex Properties. Essentially, in order to define a custom vertex property, you need to first define a "tag type" (a struct with a name ending in _t):

struct vertex_position_t {
    typedef boost::vertex_property_tag kind;
};

Then you include the tag type somewhere in the boost::property template that defines internally-stored vertex properties:

typedef boost::property<boost::vertex_index_t, std::size_t,
        boost::property<vertex_position_t, Position> > VertexProperties;

The above typedef defines two internally-stored properties: index and the custom "position".

On the second item, the preferred way to use named parameters is a "method chaining-like" syntax. For example, if a function accepts two named parameters, named_param1 and named_param2, there are two functions in the boost namespace named named_param1 and named_param2, respectfully. The boost::named_param1 function accepts the value for the named_param1 parameter and returns an object having a named_param2 method (similarly, the boost::named_param2 function accepts the value for the named_param2 parameter and returns an object having a named_param1 method). You call the method to set the value for that named parameter (which in turn returns another object having methods for other supported named parameters).

In order to pass values val1 and val2 for named parameters named_param1 and named_param2, you can either use:

boost::named_parameter1(val1).named_param2(val2)

or:

boost::named_parameter2(val2).named_param1(val1)

 

For reference, here is a complete program that copies a grid to an object of the Graph type:

#include <cassert>
#include <cstddef>
#include <cstdlib>
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/copy.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/grid_graph.hpp>
#include <boost/property_map/property_map.hpp>

struct vertex_position_t {
    typedef boost::vertex_property_tag kind;
};

struct Position {
    std::size_t x, y;

    Position()
        : x(0), y(0)
    {
    }
};

typedef boost::property<boost::vertex_index_t, std::size_t, boost::property<vertex_position_t, Position> > VertexProperties;
typedef boost::adjacency_list<boost::vecS, boost::listS, boost::undirectedS, VertexProperties> Graph;
typedef boost::graph_traits<Graph> GraphTraits;

namespace detail {
typedef boost::grid_graph<2> Grid;
typedef boost::graph_traits<Grid> GridTraits;

struct grid_to_graph_vertex_copier {
    typedef boost::property_map< Grid, boost::vertex_index_t>::type grid_vertex_index_map;
    typedef boost::property_map< ::Graph, boost::vertex_index_t>::type graph_vertex_index_map;
    typedef boost::property_map< ::Graph, ::vertex_position_t>::type graph_vertex_position_map;

    const Grid& grid;
    grid_vertex_index_map grid_vertex_index;
    graph_vertex_index_map graph_vertex_index;
    graph_vertex_position_map graph_vertex_position;

    grid_to_graph_vertex_copier(const Grid& grid_, Graph& graph)
        : grid(grid_), grid_vertex_index(get(boost::vertex_index_t(), grid_)),
        graph_vertex_index(get(boost::vertex_index_t(), graph)),
        graph_vertex_position(get(::vertex_position_t(), graph))
    {
    }

private:
    Position grid_vertex_index_to_position(std::size_t idx) const {
        unsigned num_dims = grid.dimensions();
        assert(grid.dimensions() == 2);

        idx %= grid.length(0) * grid.length(1);

        Position ret;
        ret.x = idx % grid.length(0);
        ret.y = idx / grid.length(0);

        return ret;
    }

public:
    void operator()(GridTraits::vertex_descriptor grid_vertex, ::GraphTraits::vertex_descriptor graph_vertex) const {
        std::size_t idx = get(grid_vertex_index, grid_vertex);
        put(graph_vertex_index, graph_vertex, idx);
        Position pos = grid_vertex_index_to_position(idx);
        std::cout << "grid_vertex = " << idx << ", pos.x = " << pos.x << ", pos.y = " << pos.y << std::endl;
        put(graph_vertex_position, graph_vertex, pos);
    }
};

struct grid_to_graph_edge_copier {
    void operator()(GridTraits::edge_descriptor grid_edge, ::GraphTraits::edge_descriptor graph_edge) const {
    }
};
}

int main()
{
    boost::array<std::size_t, 2> lengths = { { 3, 5 } };
    detail::Grid grid(lengths);

    Graph graph;

    boost::copy_graph(grid, graph, boost::vertex_copy(detail::grid_to_graph_vertex_copier(grid, graph))
            .edge_copy(detail::grid_to_graph_edge_copier()));

    std::cout << std::endl;
    boost::write_graphviz(std::cout, graph);

    return EXIT_SUCCESS;
}

When I ran this, I received the following output:

grid_vertex = 0, pos.x = 0, pos.y = 0
grid_vertex = 1, pos.x = 1, pos.y = 0
grid_vertex = 2, pos.x = 2, pos.y = 0
grid_vertex = 3, pos.x = 0, pos.y = 1
grid_vertex = 4, pos.x = 1, pos.y = 1
grid_vertex = 5, pos.x = 2, pos.y = 1
grid_vertex = 6, pos.x = 0, pos.y = 2
grid_vertex = 7, pos.x = 1, pos.y = 2
grid_vertex = 8, pos.x = 2, pos.y = 2
grid_vertex = 9, pos.x = 0, pos.y = 3
grid_vertex = 10, pos.x = 1, pos.y = 3
grid_vertex = 11, pos.x = 2, pos.y = 3
grid_vertex = 12, pos.x = 0, pos.y = 4
grid_vertex = 13, pos.x = 1, pos.y = 4
grid_vertex = 14, pos.x = 2, pos.y = 4

graph G {
0;
1;
2;
3;
4;
5;
6;
7;
8;
9;
10;
11;
12;
13;
14;
0--1 ;
1--2 ;
3--4 ;
4--5 ;
6--7 ;
7--8 ;
9--10 ;
10--11 ;
12--13 ;
13--14 ;
1--0 ;
2--1 ;
4--3 ;
5--4 ;
7--6 ;
8--7 ;
10--9 ;
11--10 ;
13--12 ;
14--13 ;
0--3 ;
1--4 ;
2--5 ;
3--6 ;
4--7 ;
5--8 ;
6--9 ;
7--10 ;
8--11 ;
9--12 ;
10--13 ;
11--14 ;
3--0 ;
4--1 ;
5--2 ;
6--3 ;
7--4 ;
8--5 ;
9--6 ;
10--7 ;
11--8 ;
12--9 ;
13--10 ;
14--11 ;
}