grid_graph öğesinden comacency_list'e kopyalama ile kopyalama :: copy_graph

Question

Destek grafiği kitaplığını kullanıyorum ve hayatı bir kılavuz olarak başlatmak için MutableGraph numaralı telefonu kullanmaya çalışıyorum. Kenarlar hayata daha sonra eklenecek ve kaldırılacak, bu yüzden adjacency_list<vecS,listS,undirectedS> doğru seçim olduğunu düşünüyorum.

BGL hakkında My okuma

mantıklı yolu benim için ücretsiz tüm başlangıç ​​kenarları yapabilir boost::grid_graph kopyalamak boost::copy_graph kullanarak boost::grid_graph yararlanmak olacaktır bu kenarları ile initalise için belirtti. Bu,modelinden MutableGraph modeline göre, copy_graph kopyaları yaptığımı düşündüm.

Başlangıçta, copy_graph'un 2-argüman sürümünü kullanmaya çalıştım ve geri kalanın varsayılanları ile ilgili mantıklı bir şey olacağını belirsiz belirttim. Durumun böyle olmadığı ortaya çıktı, grid_graph (tam olarak anlayamadığım nedenlerden dolayı) PropertyMap s kenarlarından veya köşe noktalarından yararlanabilme özelliği yok gibi görünüyor, bu nedenle varsayılan vertex_copy ve edge_copy başarısız oldu (bir derleyici ile birlikte) hata) özellikleri kopyalamak.

2-argümanı sürümü açıkça uygun görünse, köşeleri ve kenarları kopyalamak için kendi ikili operatörümüzü uygulamaya devam ettim. Bir 'no-op' kopyasıyla bile, bu umduğum kadar işe yaramıyor (yani derleme yapmıyor).

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

Bu örnek derleme değil:

ben birlikte sorunu göstermektedir minimum çalışma örneği koyduk

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

o hatanın analizim gibi görünüyor olmasıdır varsayılan olarak, grid_graph dahili içeriğinin bir kısmını yapılandırmaya çalışmak, varsayılan olarak yapılamamaktadır, çünkü bu durum bana açık değildir. (clang bana g ++ 'dan göremediğim bir şey söylemiyor).

Sorular:

1. bu normal bir ızgara olarak başlamak için değişken grafiği initalising hakkında en doğru yol var mı? Başlangıçta kendim yapmak için bir işlev yazmaktan çok daha kolay olduğunu düşündüm, ama şimdi o kadar emin değilim!
2. Neden varsayılan değer orig_to_copy ve/veya vertex_index burada uygun değil? Bu ikisinin hatanın sebebi olduğunu varsayıyorum. (Hangi, aslında, bu sorunu neden olan nedir? Geçerli hatanın kök nedenini deşifre edemiyorum).
3. Bunu düzeltmenin "doğru" yolu nedir?

Answer 1

Doğru yoldasınız, ancak kodunuzda değiştirilmesi gereken iki şey var. Birincisi, özel köşe özelliklerini tanımlamak için özel bir yöntem olmasıdır. İkincisi, BGL adlı parametreler için farklı bir sözdizimi (daha çok tercih edilen ve muhtemelen doğru olan tek) olmasıdır.

İlk üründe, lütfen the section of the documentation titled Custom Vertex Properties'a bakın.Sonra

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

Eğer boost::property şablonunda bir yere etiket türünü içerir: Esasen, özel bir köşe özellik tanımlamak amacıyla, önce (_t biten bir adla bir struct) bir "etiket türü" tanımlamanız gerekir bu dahili depolanmış tepe özelliklerini tanımlar: bir dizin ve özel "pozisyon":

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

yukarıda typedef iki dahili depolanmış özelliklerini tanımlar.

İkinci öğede, adlandırılmış parametreler kullanmak için the preferred way bir "yöntem zincirleme benzeri" sözdizimidir. Örneğin, bir işlev named_param1 ve named_param2 olarak adlandırılan iki işlevi kabul ederse, named_param1 ve named_param2 adında boost ad alanında iki işlev vardır. boost::named_param1 fonksiyonu named_param1 parametresinin değeri kabul eder ve (benzer şekilde, boost::named_param2 fonksiyonu named_param2 parametresinin değeri kabul eder ve bir named_param1yöntem sahip olan bir nesne döner) bir named_param2yöntem sahip olan bir nesne döndürür. Bu adlandırılmış parametrenin değerini ayarlamak için yöntemi çağırırsınız (bu da diğer desteklenen adlandırılmış parametreler için yöntemlere sahip başka bir nesneyi döndürür). adlandırılmış parametreleri named_param1 ve named_param2 için

değerlerini val1 geçmek için

ve val2 yapabilirsiniz kullanım ya:

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

ya:

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

Başvuru için

 

, burada Bir ızgarayı Graph nesnesine kopyalayan tam bir program Türü:

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

bu koştum

, aşağıdaki çıktıyı aldım:

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