Copia da grid_graph a adjacency_list con boost :: copy_graph

Question

Sto utilizzando la libreria del grafico boost e sto provando initalamente un MutableGraph per iniziare la vita come una griglia. I bordi saranno aggiunti e rimossi più tardi nella vita, quindi penso che adjacency_list<vecS,listS,undirectedS> sia la scelta giusta.

La mia lettura su BGL ha indicato che il modo sensato initalise con questi bordi sarebbe di sfruttare boost::grid_graph utilizzando boost::copy_graph copiare da un boost::grid_graph che può fare tutti i bordi iniziali per me gratuitamente. Ho pensato che fosse logico - copy_graph copie da un modello di a un modello di un MutableGraph, che è esattamente quello che ho.

Inizialmente ho provato a utilizzare la versione a 2 argomenti di copy_graph, con la vaga speranza che qualcosa di sensato sarebbe accaduto con le impostazioni predefinite per il resto. Non è questo il caso, grid_graph (per ragioni che non riuscivo a capire) non sembra avere una funzionalità per l'utilizzo di PropertyMap s con bordi o vertici, quindi il default vertex_copy e edge_copy non riuscito (con un compilatore errore) copiando le proprietà.

Poiché la versione a 2 argomenti chiaramente non sembra appropriata, passo avanti e ho cercato di implementare il mio operatore binario per copiare vertici e spigoli. Anche con una copia 'no-op' questo non funziona come spero (cioè non si compila).

Ho messo insieme un esempio di lavoro minima che illustra il problema:

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

questo esempio non può essere compilato:

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

La mia analisi di tale errore è che sembra essere cercando di default costruisci parte dell'intero interno di grid_graph, che non può essere costruito in modo predefinito, per qualche ragione che non mi è molto chiaro. (clang in realtà non mi dice nulla che non riesco a vedere da g ++ qui).

Domande:

1. È questo il modo giusto per andare su un grafico, inizializzazione mutabile per iniziare come una griglia regolare? Inizialmente pensavo che fosse molto più facile che scrivere una funzione per farlo da solo, ma ora non ne sono così sicuro!
2. Perché il valore predefinito di orig_to_copy e/o vertex_index non è appropriato qui? Suppongo che quei due siano la causa dell'errore. (Che, se del caso, di quelli in realtà sta causando il problema? Non riesco a decifrare quale sia la causa principale dell'errore corrente).
3. Qual è il modo "corretto" per risolvere questo problema?

Answer 1

Sei sulla strada giusta, ma ci sono due cose che devono essere cambiate nel codice. Il primo è che esiste un metodo speciale per definire le proprietà dei vertici personalizzate. Il secondo è che esiste una sintassi diversa (più preferita e probabilmente l'unica corretta) per i parametri con nome BGL.

Sul primo elemento, fare riferimento a the section of the documentation titled Custom Vertex Properties.In sostanza, al fine di definire una proprietà custom vertex, è necessario definire prima un "tipo di tag" (un struct con un nome che termina con _t):

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

Poi si includono il tipo di tag da qualche parte nel modello boost::property che definisce proprietà vertici internamente memorizzati:

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

Quanto sopra typedef definisce due proprietà internamente memorizzati: index e la "posizione" personalizzato.

Sul secondo elemento, the preferred way per utilizzare i parametri denominati è una sintassi "metodo concatenato". Ad esempio, se una funzione accetta due parametri denominati, named_param1 e named_param2, ci sono due funzioni nello spazio dei nomi boost denominato named_param1 e named_param2, rispettosamente. La funzione boost::named_param1 accetta il valore per il parametro named_param1 e restituisce un oggetto avente un metodonamed_param2(analogamente, la funzione boost::named_param2 accetta il valore per il parametro named_param2 e restituisce un oggetto avente un metodo named_param1). Si chiama il metodo per impostare il valore per quel parametro denominato (che a sua volta restituisce un altro oggetto che ha metodi per altri parametri denominati supportati).

Per passare valori val1 e val2 per parametri denominati named_param1 e named_param2, è possibile utilizzare:

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

o:

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

 

Per riferimento, ecco un programma completo che copia una griglia su un oggetto dello Graph Tipo:

#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; 
} 

Quando ho eseguito questo, ho ricevuto il seguente 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 ; 
}