Compressed Sparse Row (CSR) CSR は疎なグラフの効率的な表現方法である．adjacency_list といった他のフォーマットよりもオーバヘッドが小さいという特徴がある． BGL にも CSR 方式に基づいたクラスが用意されているが，adjacency_list と使い方が大きく…

疎行列 非零要素数がn2（nはグラフのノード数）よりも著しく少ない行列を疎行列という．要するに，ほとんどの要素が0である行列を指す． グラフの隣接行列はたいてい疎行列となる． n×n行列はn2個の記憶領域を必要とするが，疎行列は非零要素の値と座標のみ…

boostjp.github.io を参考にさせていただいた．とても分かりやすかった． 任意のプロパティの設定 BGLのグラフ構造（adjacency_listやadjacency_matrix）は，ノードやエッジのプロパティを自分で設定することができる．プロパティはstruct構造体で設定する．…

グラフの可視化 BGLとGraphvizを用いてグラフを可視化します． Boost Graph Library: write graphviz - 1.61.0 を参考にしました． macの場合，Graphvizのinstallはbrewで簡単に行うことができます（それ以外の方法は調査していません..）． brew install gr…

Boost Graph Library (BGL) 1つ前の記事 tomov3.hatenablog.com でBGLについて少し触れた． この記事では隣接行列の形でグラフを表現するadjacency_matrixを紹介する． 上の記事で紹介したadjacency_listクラスは，隣接リストグラフ構造を表現するために使用…

Boost Graph Library (BGL) C++でグラフを扱うプログラムを作成するために，BGLの勉強を始める． Table of Contents: Boost Graph Libraryを参考にする． BGLはグラフの構造へどのようにアクセスするかを定めた インタフェースである。グラフ構造はadjacency…