Boost Graph Libraryメモ②
Boost Graph Library (BGL)
1つ前の記事
でBGLについて少し触れた．
この記事では隣接行列の形でグラフを表現するadjacency_matrixを紹介する．
上の記事で紹介したadjacency_listクラスは，隣接リストグラフ構造を表現するために使用するインターフェースである．
adjacency_matrix
adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>
adjacency_matrixの利点としては，辺の削除や追加が定数時間で終了するという点が挙げられる．
しかし，行列はn×nであり，メモリ消費量が大きいという欠点がある（nはノード数とする）．
adjacency_matrixはグラフの密度が高い（辺の本数が多い）場合に向いていて，adjacency_listは密度が低い場合に向いている．
パラメータ
adjacency_matrixにはDirected, VertexProperty, EdgeProperty, GraphProperty, Allocatorという5つのパラメータが存在する．
Directedは有向か無向かを決定し，VertexProperty，EdgeProperty，GraphPropertyはプロパティを設定する．
Allocatorには特に記述がなかったが，おそらくメモリの確保や割り当てを行うオブジェクトのことを意味していると思う．
使用例
例が紹介されていた．
enum { A, B, C, D, E, F, N };
const char* name = "ABCDEF";
typedef boost::adjacency_matrix<boost::directedS> Graph;
Graph g(N);
add_edge(B, C, g);
add_edge(B, F, g);
add_edge(C, A, g);
add_edge(C, C, g);
add_edge(D, E, g);
add_edge(E, D, g);
add_edge(F, A, g);
std::cout << "vertex set: ";
boost::print_vertices(g, name);
std::cout << std::endl;
std::cout << "edge set: ";
boost::print_edges(g, name);
std::cout << std::endl;
std::cout << "out-edges: " << std::endl;
boost::print_graph(g, name);
std::cout << std::endl;
The output is:
vertex set: A B C D E F
edge set: (B,C) (B,F) (C,A) (C,C) (D,E) (E,D) (F,A)
out-edges:
A -->
B --> C F
C --> A C
D --> E
E --> D
F --> A
addEdge()で辺を追加し，boost::print_graph()でedge setを出力する．
他にもnum_vertices()で頂点数を，num_edges()で辺の数を得る関数などが用意されている．
さいごに
今後もBGLを使用したプログラムの例などを記事にしたいと思います．PageRank計算を行うプログラムなど，具体的な例を紹介できればと思います．
