Sao chép từ grid_graph sang adjacency_list với boost :: copy_graph

Question

Tôi đang sử dụng thư viện đồ thị tăng cường và cố gắng đầu tư một số MutableGraph để bắt đầu cuộc sống dưới dạng lưới. Các cạnh sẽ được thêm và xóa sau này trong cuộc sống, vì vậy tôi nghĩ rằng adjacency_list<vecS,listS,undirectedS> là lựa chọn đúng đắn.

đọc của tôi về BGL chỉ ra rằng cách hợp lý để initalise nó với những cạnh sẽ tận dụng lợi thế của boost::grid_graph bằng cách sử dụng boost::copy_graph để sao chép từ một boost::grid_graph có thể làm cho tất cả các cạnh ban đầu cho tôi miễn phí. Tôi nghĩ rằng có ý nghĩa - copy_graph các bản sao từ một mô hình VertexListGraph đến một mô hình của một MutableGraph, đó là chính xác những gì tôi có.

Ban đầu tôi đã thử sử dụng phiên bản 2 đối số copy_graph, với hy vọng mơ hồ rằng một điều gì đó hợp lý sẽ xảy ra với các giá trị mặc định cho phần còn lại. Điều đó hóa ra không phải là trường hợp, grid_graph (vì lý do tôi không thể tìm ra) dường như không có cơ sở để sử dụng PropertyMap s với một trong hai cạnh hoặc đỉnh, do đó, mặc định vertex_copy và edge_copy không thành công (với trình biên dịch lỗi) sao chép các thuộc tính.

Vì phiên bản 2 đối số rõ ràng dường như không thích hợp nên tôi tiếp tục và cố gắng triển khai toán tử nhị phân của riêng mình để sao chép các đỉnh và cạnh. Ngay cả với bản sao 'no-op', nó không hoạt động tốt như tôi mong đợi (tức là nó không biên dịch).

tôi đã đặt cùng một ví dụ làm việc tối thiểu mà minh họa các vấn đề:

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

Ví dụ này không biên dịch:

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

phân tích của tôi về lỗi đó là nó có vẻ là cố gắng để mặc định xây dựng một phần của các bên trong của grid_graph, không thể được xây dựng mặc định, vì một số lý do không rõ ràng đối với tôi. (clang không thực sự cho tôi biết bất cứ điều gì tôi không thể nhìn thấy từ g + + ở đây).

Câu hỏi:

1. Đây có phải là cách đúng đắn để đi về initalising một đồ thị có thể thay đổi để bắt đầu như một mạng lưới thường xuyên? Ban đầu tôi nghĩ rằng nó dễ dàng hơn nhiều so với việc viết một hàm để tự làm như vậy, nhưng bây giờ tôi không chắc lắm!
2. Tại sao giá trị mặc định là orig_to_copy và/hoặc vertex_index không phù hợp ở đây? Tôi giả định rằng hai nguyên nhân đó là nguyên nhân gây ra lỗi. (Mà, nếu có, trong số đó thực sự gây ra vấn đề? Tôi không thể giải mã nguyên nhân gốc rễ của lỗi hiện tại).
3. Cách sửa lỗi này "đúng" là gì?

Answer 1

Bạn đang đi đúng hướng, nhưng có hai thứ cần được thay đổi trong mã của bạn. Đầu tiên là có một phương pháp đặc biệt để xác định các thuộc tính vertex tùy chỉnh. Thứ hai là có một cú pháp khác (được ưa thích hơn và có lẽ là một cú pháp duy nhất đúng) cho các tham số có tên BGL.

Trên mục đầu tiên, vui lòng tham khảo the section of the documentation titled Custom Vertex Properties.Về cơ bản, để xác định một tài sản đỉnh tùy chỉnh, bạn cần phải đầu tiên xác định một "loại thẻ" (một struct với một tên kết thúc bằng _t):

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

Sau đó, bạn bao gồm các loại thẻ ở đâu đó trong boost::property mẫu xác định các thuộc tính vertex được lưu trữ nội bộ:

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

xác định hai thuộc tính được lưu trữ bên trong: chỉ mục và "vị trí" tùy chỉnh.

Trên mục thứ hai, the preferred way để sử dụng tham số được đặt tên là cú pháp "giống như phương thức". Ví dụ: nếu hàm chấp nhận hai tham số được đặt tên, named_param1 và named_param2, có hai hàm trong không gian tên boost có tên là named_param1 và named_param2, một cách tôn trọng. Chức năng boost::named_param1 chấp nhận giá trị cho tham số named_param1 và trả về một đối tượng có một phương phápnamed_param2(tương tự, các boost::named_param2 chức năng chấp nhận giá trị cho tham số named_param2 và trả về một đối tượng có một named_param1phương pháp). Bạn gọi phương thức để đặt giá trị cho tham số được đặt tên đó (mà lần lượt trả về một đối tượng khác có các phương thức cho các tham số có tên được hỗ trợ khác).

Để vượt qua giá trị val1 và val2 cho tên thông số named_param1 và named_param2, bạn có thể sử dụng:

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

hay:

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

 

Để tham khảo, đây là một chương trình hoàn chỉnh sao chép một lưới vào một đối tượng của Graph loại:

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

Khi tôi chạy này, tôi nhận được kết quả như sau:

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