使用boost :: copy_graph從grid_graph複製到adjacency_list

Question

我正在使用boost圖庫並嘗試初始化MutableGraph以啓動網格生命。 邊緣將被添加和刪除生活後期，所以我認爲adjacency_list<vecS,listS,undirectedS>是正確的選擇。

我對BGL讀數表明，合理的方式與這些邊緣initalise這將是通過使用 boost::copy_graph從boost::grid_graph，可以使一切對我最初的邊緣免費拷貝到利用boost::grid_graph。 我認爲這是有道理的 - copy_graph從模型VertexListGraph複製到MutableGraph，這正是我所擁有的模型。

我最初嘗試使用copy_graph的雙參數版本，並且模糊地希望其餘的默認值會發生一些明智的事情。事實證明，情況並非如此，grid_graph（由於我無法弄清楚的原因）似乎沒有使用PropertyMap s的邊或頂點的功能，所以默認vertex_copy和edge_copy失敗（使用編譯器錯誤）複製屬性。

由於2個參數的版本顯然不合適，我繼續嘗試實現自己的二元運算符來複制頂點和邊。即使使用'no-op'副本，這也不會像我希望的那樣工作（即它不會編譯）。

我已經把最低工作的例子，說明了這個問題：

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

這個例子不能編譯：

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

我是錯誤的分析是，它似乎是試圖默認構建grid_graph的內部部分，這不能被默認構建，出於某種原因，這對我來說不是很清楚。 （clang並沒有真正告訴我任何我在g ++裏看不到的東西）。

問題：

1. 這是去了解initalising一個可變圖開始作爲常規電網的正確方法？我最初認爲這比自己寫一個函數要容易得多，但現在我不太確定！
2. 爲什麼默認值orig_to_copy和/或vertex_index在這裏不合適？我假設這兩個是錯誤的原因。 （如果有的話，這實際上是造成這個問題的原因？我無法破譯當前錯誤的根本原因是什麼）。
3. 解決此問題的「正確」方法是什麼？

Answer 1

您現在處於正確的軌道上，但在代碼中需要更改兩件事情。首先是有一種定義自定義頂點屬性的特殊方法。第二個是BGL命名參數有不同的語法（更優選，也可能是唯一正確的語法）。請參考the section of the documentation titled Custom Vertex Properties。從本質上講，爲了定義一個定製頂點屬性，你需要首先定義「標籤式」（一個struct在_t結尾的名稱）：

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

然後你的地方包括標籤類型的boost::property模板限定內部存儲頂點屬性：

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

上面typedef定義了兩個內部存儲的屬性：指數和定製的「位置」。

關於第二項，the preferred way使用命名參數是一種「方法鏈式」的語法。例如，如果一個函數接受兩個命名參數named_param1和named_param2，則分別名爲named_param1和named_param2的boost名稱空間中有兩個函數。所述boost::named_param1函數接受用於named_param1參數值，並返回具有named_param2方法（類似地，boost::named_param2函數接受用於named_param2參數值，並返回具有named_param1方法的對象）的對象。您可以調用該方法來設置該指定參數的值（然後返回另一個具有其他受支持命名參數方法的對象）。

爲了傳遞值val1和val2命名參數named_param1和named_param2，你可以使用：

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

或：

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

 

供參考，在這裏是一個完整的程序，將網格複製到Graph的對象類型：

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

當我跑了這一點，我收到了以下的輸出：

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