Kopiowanie z grid_graph do adjacency_list z boost :: copy_graph

Question

Używam biblioteki wykresów boost i próbuję zainicjować MutableGraph, aby rozpocząć życie jako siatka. Krawędzie zostaną dodane i usunięte w późniejszym okresie życia, więc myślę, że adjacency_list<vecS,listS,undirectedS> jest właściwym wyborem.

Moje czytanie o BGL wskazano, że rozsądny sposób initalise go z tych krawędzi byłoby wykorzystać boost::grid_graph za pomocą boost::copy_graph skopiować z boost::grid_graph że można dokonać wszystkich początkowych krawędzie dla mnie za darmo. Myślałem, że ma to sens - copy_graph egzemplarzy z modelu VertexListGraph do modelu MutableGraph, który jest dokładnie tym, co mam.

Początkowo próbowałem użyć 2-argumentowej wersji copy_graph, z niejasną nadzieją, że stanie się coś sensownego z domyślnymi ustawieniami dla reszty. Tak się nie stało, grid_graph (z powodów, których nie mogłem dokładnie wymyślić) nie wydaje się mieć możliwości używania PropertyMap s z żadną krawędzią lub wierzchołkiem, więc domyślne vertex_copy i edge_copy zawiodły (z kompilatorem błąd) kopiowanie właściwości.

Ponieważ wersja 2-argumentowa najwyraźniej nie wydawała się odpowiednia, przechodzę dalej i próbuję zaimplementować własnego operatora binarnego do kopiowania wierzchołków i krawędzi. Nawet z kopią "no-op" nie działa tak dobrze, jak mam nadzieję (to znaczy, że się nie kompiluje).

Mam ułożyła minimalnej pracy przykład, który ilustruje 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)); 
} 

Ten przykład nie kompiluje:

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

Moja analiza tego błędu jest to, że wydaje się być próba domyślnego skonstruowania części wewnętrznych z grid_graph, które nie mogą być domyślnie skonstruowane, z jakiegoś powodu, który nie jest dla mnie strasznie jasny. (clang tak naprawdę nie mówi mi nic, czego nie mogę zobaczyć z g ++ tutaj).

Pytania:

1. Czy to jest właściwa droga o initalising jest zmienny wykres, aby uruchomić jako zwykły siatki? Początkowo myślałem, że to dużo łatwiejsze niż pisanie funkcji, aby to zrobić sam, ale teraz nie jestem tego taki pewien!
2. Dlaczego domyślna wartość orig_to_copy i/lub vertex_index nie jest tutaj odpowiednia? Zakładam, że te dwa są przyczyną błędu. (Które, jeśli jakiekolwiek, faktycznie powodują problem? Nie mogę odczytać przyczyny głównej błędu).
3. Co to jest "poprawny" sposób naprawy?

Answer 1

Jesteś na dobrej drodze, ale w kodzie trzeba zmienić dwie rzeczy. Po pierwsze, istnieje specjalna metoda definiowania niestandardowych właściwości wierzchołków. Po drugie, istnieje inna składnia (bardziej preferowana i prawdopodobnie jedyna, która jest poprawna) dla parametrów nazwanych BGL.

Pierwsza pozycja dostępna pod numerem the section of the documentation titled Custom Vertex Properties.Zasadniczo, w celu zdefiniowania niestandardowej właściwości wierzchołków, trzeba najpierw zdefiniować „typ zmiennej” (A struct z nazwiskiem kończącym się _t):

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

Wtedy to rodzaj tag gdzieś w szablonie boost::property który określa wewnętrznie przechowywane właściwości wierzchołków:

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

powyższy typedef definiuje dwa wewnętrznie przechowywane właściwości: wskaźnik i „położenia” użytkownika.

Drugim elementem, the preferred way na użycie nazwanych parametrów, jest składnia "metoda łańcuchowa". Jeśli na przykład funkcja akceptuje dwa nazwane parametry: named_param1 i named_param2, w obszarze nazw named_param1 i named_param2 istnieją dwie funkcje o nazwach named_param1 i named_param2. Funkcja boost::named_param1 przyjmuje wartość parametru named_param1 i zwraca przedmiot posiadający named_param2sposób (Podobnie, funkcja boost::named_param2 przyjmuje wartość parametru named_param2 i zwraca przedmiot posiadający named_param1sposób). Wywołujesz metodę, aby ustawić wartość dla tego nazwanego parametru (który z kolei zwraca inny obiekt mający metody dla innych obsługiwanych parametrów nazwanych).

W celu przekazania wartości val1 i val2 nazwanych parametrów named_param1 i named_param2, Można użyć:

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

czyli

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

 

Dla porównania, tutaj jest kompletny program, który kopiuje siatkę do obiektu Graph Typ:

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

Kiedy wpadłem to, otrzymałem następujący wynik:

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