プロパティとプロパティ・マップ２

前回の続き。

参考

Quick Tour of Boost Graph Library
Boost Graph Library: Using Property Maps

内部プロパティ(adjacency_matrix)

adjacency_matrixの内部プロパティもテンプレート引数で指定する。

typedef adjacency_matrix<undirectedS,
			 property<vertex_index_t, int>,		// vertex property
			 property<edge_capacity_t, double>,	// edge property
			 property<graph_name_t, string>		// graph property
			>
			Graph;

指定の仕方はadjacency_listと一緒。

外部プロパティ

• 外部プロパティ：グラフオブジェクトとは別に管理するプロパティ
• 一時的にしか必要でないプロパティは外部プロパティとした方がメモリを節約できる
  • 例：深さ優先探索時に既に訪れた頂点かを判定するために使われる色プロパティ
• 外部プロパティ・マップを作成する方法は様々だが、ここでは2つの方法が紹介されている
  • adjacency_listでテンプレートパラメータVertexListがvecSで指定されてる場合は、vertex_descripterは整数型である事が保証されるので、頂点に対する外部プロパティマップとして配列やvectorがそのまま使える

	typedef adjacency_list<vecS, vecS> Graph;	// グラフ型
	Graph g(2);	// 頂点数2のグラフ
	int props[] = {10, 20};	// 頂点の外部プロパティ
	// 頂点のプロパティを表示。
	BOOST_FOREACH(graph_traits<Graph>::vertex_descriptor v , vertices(g)){
		cout << props[v] << endl;
	}

出力

10
20

• • VertexListがvecS以外の場合や、辺の外部プロパティの場合は、頂点/辺のインデックスを内部プロパティとして持たせた上でアダプタクラスboost::iterator_property_mapを使ってプロパティマップを作れる

#include <iostream>
#include <boost/foreach.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/property_map/property_map.hpp>	// for boost::iterator_property_map

using namespace std;
using namespace boost;

int main(int , char* []) {

	// グラフ型
	typedef adjacency_list<
		vecS,
		listS, 
		undirectedS,
		property<vertex_index_t, size_t>
	> Graph;
	Graph g;	// 空のグラフオブジェクト
	// インデックスを指定しながらグラフに頂点を追加
	add_vertex(0, g);
	add_vertex(1, g);

	int props[2] = {10, 20};	// 頂点のプロパティ
	// 頂点インデックスへのプロパティマップ
	typedef property_map<Graph, vertex_index_t>::type VertexIndexMap;
	VertexIndexMap vertex_id = get(vertex_index, g);
	// 外部プロパティマップの型
	typedef iterator_property_map<
		int*,	// プロパティに対するrandom accessイテレータ型の指定(今回は配列なのでポインタ)
		VertexIndexMap,
		int,	// プロパティの型(省略可)
		int&	// プロパティの参照型の指定(省略可)
	> IterMap;
	// 外部プロパティマップのオブジェクト
	// 外部プロパティを指定するための配列、頂点→インデックスのプロパティマップを指定
	IterMap v_prop_map(props, vertex_id);
	// 頂点プロパティの出力
	BOOST_FOREACH(graph_traits<Graph>::vertex_descriptor v , vertices(g)){
		cout << v_prop_map[v] << endl;
	}
	return 0;
}

出力

10
20