Boost Graph Libraryメモ

Boost Graph Library (BGL)

C++でグラフを扱うプログラムを作成するために，BGLの勉強を始める． Table of Contents: Boost Graph Libraryを参考にする．

BGLはグラフの構造へどのようにアクセスするかを定めた インタフェースである。グラフ構造はadjacency_listクラスで実装する．

adjacency_list

adjacency_listの詳細は

Boost Graph Library: Adjacency List

に，使い方は

Using the Boost Graph Library

に詳しい記述がある．

adjacency_list<EdgeList, VertexList, Directed, VertexProperties, EdgeProperties, GraphProperties>

• EdgeList, VertexListはそれぞれどの種類のコンテナを用いて辺と頂点を表現するかを決定する．

std::vectorを使用する場合はvecS，std::listを使用する場合はlistSを選択する．

• Directedは有向か無向か，または双方向の辺アクセス (出辺と入辺の両方にアクセス する) の有向かを選ぶ．

有向グラフを選ぶには directedS か bidirectionalS を使い、無向グラフを選ぶには undirectedS を使う。

あとの3つはプロパティを設定する．
それぞれデフォルトはvecS，vecS，directedS，no_property，no_property，no_propertyである．

使用例

family treeをグラフで表現した例が以下に挙げられていた．

http://boost.cppll.jp/HEAD/libs/graph/example/family-tree-eg.cpp

後日実際に実装して新たに記事にしたい．

追記 (2016/6/22)

とても分かりやすいスライドを見つけました．

bgl design and shortest path from Akira Takahashi

www.slideshare.net

BGLについて学びたい方にとてもオススメです．