Visitorの使い方

参考

Boost Graph Library: Visitor Concepts

Visitorとは

• グラフアルゴリズムを拡張するためのコールバック関数の集まり
  • 使用例）幅優先探索アルゴリズムで訪れる順に頂点を出力する、等
• 各グラフアルゴリズムに対してVisitorコンセプトが定義されている
  • Visitorコンセプト：アルゴリズム中の各ポイントで呼ばれる関数の名前と引数、返り値を定義したもの
  • 例）深さ優先探索(depth_first_search())に対してはDFS Visitorが対応
    • DFS Visitorコンセプトについてはここを参照

Visitorの使い方

• 原理的には、Visitorコンセプトに定義されている関数を全て実装したクラスを定義してグラフアルゴリズムに引数として渡せばOK
• でもイチイチ全部の関数を実装するのは面倒
• より簡単な方法を２通り挙げよう
  • デフォルトのVisitorクラス（default_***_visitor）を継承して、必要な関数のみオーバーライド
  • Event Visitorを利用して必要な関数のみ指定

デフォルトのVisitorクラスを継承する方法

• デフォルトのVisitorクラス（default_***_visitor）： なにもしないVisitor
  • 例） DFS Visitorならdefault_dfs_visitor

#include <iostream>
#include <utility>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
using namespace boost;
using namespace std;

// デフォルトVisitorを継承して独自Visitorを定義
struct print_visitor : public default_dfs_visitor
{
	// DFSで頂点が発見された時に呼ばれる関数
	template<class Vertex, class Graph>
	void discover_vertex(Vertex v, Graph g)
	{
		cout << "discover " <<  v << endl;
	}

};

int main(int, char*[])
{
	typedef adjacency_list<> Graph;
	typedef std::pair<int,int> E;
	E edges[] = { E(0, 4), E(1, 0), E(1, 3),
		E(2, 1), E(2, 3), E(3, 1), E(3, 4),
		E(4, 0), E(4, 1) };  

	Graph G(edges, edges + sizeof(edges)/sizeof(E), 5);
	// 名前つき引数visitorでVisitorオブジェクトを指定
	depth_first_search(G, visitor(print_visitor()));
	return 0;
}

出力

discover 0
discover 4
discover 1
discover 3
discover 2

Event Visitorを利用する方法

• Event Visitorとは
  • Visitorの関数（イベント）一つに対応するファンクタ
  • 詳しくはここを参照

#include <iostream>
#include <utility>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
using namespace boost;
using namespace std;

// Event Visitor
struct print_discover_vertex
{	
	// 実装するイベントに対応するクラス(on_****)をevent_filterとしてtypedefする
	typedef on_discover_vertex event_filter;
	// イベントに対する処理
	template<class Vertex, class Graph>
	void operator()(Vertex v, Graph g)
	{
		cout << "discover " << v << endl;
	}
};

int main(int, char*[])
{
	typedef adjacency_list<> Graph;
	typedef std::pair<int,int> E;
	E edges[] = { E(0, 4), E(1, 0), E(1, 3),
		E(2, 1), E(2, 3), E(3, 1), E(3, 4),
		E(4, 0), E(4, 1) };  

	Graph G(edges, edges + sizeof(edges)/sizeof(E), 5);
	
	// Event Visitorを使ってVisitorを指定
	// make_***_visitorを使う
	depth_first_search(G, visitor(make_dfs_visitor(print_discover_vertex())));
	return 0;
}

出力は上と同じ。