プロパティとプロパティ・マップ
参考→Quick Tour of Boost Graph Library, Boost Graph Library: Using Property Maps,
- グラフの辺や頂点にプロパティ（重みや名前、色などの情報）を付けるためにはプロパティ・マップを使う。
- プロパティの管理方法には2種類ある
- 内部プロパティ：グラフ・オブジェクトの内部にプロパティを持たせる。
- 外部プロパティ：グラフ・オブジェクトとは別にプロパティを管理する。
以下それぞれ説明。
内部プロパティ
グラフ・オブジェクト(adjacency_listとか）の内部にプロパティを持たせる方法。adjacency_listの場合はテンプレート引数にプロパティを指定する。
#include <string> #include <iostream> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/foreach.hpp> using namespace std; using namespace boost; int main() { // プロパティの型 typedef property<vertex_name_t, string> VertexProperty; // 頂点のプロパティ型 //（頂点の名前をstd::stringで） typedef property<edge_capacity_t, int, property<edge_weight_t, float> > EdgeProperty; // 辺のプロパティ型 //（辺の容量をint、重みをfolatで） typedef property<graph_name_t, string> GraphProperty; // グラフ自体のプロパティ型 // (グラフ自体の名前をstd::stringで) // グラフ型（隣接リスト） typedef adjacency_list<listS, // 辺を格納するデータ構造 std::list listS, // 頂点を格納するデータ構造 std::list undirectedS, // 無向グラフ VertexProperty, // 頂点のプロパティ EdgeProperty, // 辺のプロパティ GraphProperty // グラフ自体のプロパティ > Graph; const int nV = 5; // 頂点数 string v_name_array[] = { "ant", "bee", "cat", "dog", "elephant" }; // 頂点名 typedef pair<int, int> Pair; Pair edge_array[] = { Pair(0, 1), Pair(0, 2), Pair(1, 2), Pair(2, 3), Pair(3, 4) }; // 辺 const int nE = sizeof(edge_array) / sizeof(Pair); // 辺数 int capacity_array[] = { 3, 5, 9, 10, 11 }; // 辺の容量 float weight_array[] = { 1.0, 2.0, 1.5, 3.0, 2.5 }; // 辺の重み // グラフオブジェクトの生成 // コンストラクタで辺、辺の第一プロパティの値(edge_capacity_t), 頂点数を指定可能 Graph G(edge_array, edge_array + nE, capacity_array, nV); // 記述子の型 typedef graph_traits<Graph>::vertex_descriptor Vertex; // 頂点 typedef graph_traits<Graph>::edge_descriptor Edge; // 辺 // プロパティ・マップ typedef property_map<Graph, edge_weight_t>::type EdgeWeightMap; // 辺記述子→重みのプロパティ・マップ型 EdgeWeightMap e_weight = get(edge_weight, G); // 辺記述子→重み のプロパティ・マップオブジェクト // ************************ // * プロパティ値の設定 // ************************ // グラフに対して set_property(G, graph_name, string("MyGraph")); // グラフに対してはset_property関数で // 頂点に対して for(int i = 0; i < nV; i++){ Vertex v = vertex(i, G); put(vertex_name, G, v, v_name_array[i]); // 名前を設定(put関数で) } // 辺に対して for(int i = 0; i < nE; i++){ bool is_edge; Edge e; Vertex v1 = vertex(edge_array[i].first, G); Vertex v2 = vertex(edge_array[i].second, G); tie(e, is_edge) = edge(v1, v2, G); e_weight[e] = weight_array[i]; // 重みを設定(プロパティマップオブジェクトで) } // ************************* // *プロパティ値の参照 // ************************* // グラフ cout << "graph name: " << get_property(G, graph_name) << endl; // グラフに対してはget_property関数で // 頂点 cout << "vertex name:" << endl; BOOST_FOREACH(const Vertex &v, vertices(G)){ cout << "\t" << get(vertex_name, G, v) << endl; // 名前を参照(get関数で) } cout << endl; // 辺 cout << "edge capacity weight:" << endl; BOOST_FOREACH(Edge &e, edges(G)){ cout << "\t" << get(edge_capacity, G, e)// 容量を参照(get関数で) << "\t" << e_weight[e] << endl;; // 重みを参照(プロパティ・マップオブジェクトで) } cout << endl; return 0; }
で、出力はこれ↓
graph name: MyGraph
vertex name:
ant
bee
cat
dog
elephant
edge capacity weight:
3 1
5 2
9 1.5
10 3
11 2.5
- プロパティの型はproperty<(プロパティ識別用のタグ), (プロパティの型), (次のプロパティ)>で指定する。
- プロパティ識別用のタグは予め用意された型があるし、自作もできる。
- 予め用意されたタグの一覧や自作の仕方はUsing the Boost Graph Libraryを参照
- 上の辺の時のようにpropertyクラスの第3テンプレート引数を使ってpropertyクラスをネストすることで複数のプロパティを指定できる
- プロパティの設定や参照
- グラフ自体に対してはset_property()/get_property()関数で
- 辺や頂点に対してはプロパティ・マップオブジェクトを作るか、直接put()/get()関数で
- プロパティ識別用のタグ型は辺ならedge_***_t, 頂点ならvertex_***_tだが、コードでput()/get()関数の第1引数に渡しているのは"_t"の取れたedge_***やvertex_***である。これは、対応するタグ型に対して予め生成されているオブジェクトの名前である
外部プロパティ
疲れたのでまた今度。
