グラフ・インタフェイスについて

参考→Boost Graph Concepts
要点と考えたこと：

• データ構造とアルゴリズムの独立性を高めるためにインタフェイスを通じてグラフのデータへアクセスする
  • グラフのデータ：頂点、辺、ある頂点の隣接頂点や接続辺など
  • インタフェイスの条件を満たすような自作のデータ構造はBGLのアルゴリズムに食わせることができる
  • が、普通はBGLのadjacency_listとかadjacency_matrix使えば間に合う
• インタフェイスはいくつかのコンセプトで表現される

• コンセプトとは
  • あるデータ構造に対して要求される型と関数の集まり
  • コンセプトの一覧とその関係は上記参考サイトの図１を参照
  • 図１中の矢印はいわば継承関係のようなもので、矢印元は矢印先の要件を全て満たしていなきゃいけない
    • 例えば、AdjacencyGraphコンセプトはGraphコンセプトの要件を全てみたしている
  • 最初、純粋仮想関数使ってインタフェイス定義したらええんちゃうの？と思ったが、よく考えると仮想関数は実行時のオーバーヘッドがあるので、テンプレートを用いてコンパイル時にそこらへんは解決しとけばええやん、ということか（多分）

• 各コンセプトの概要（実際に必要な型とか関数とかは上記参考サイトの表１にあるので、なんのためのコンセプトかっていうこと）
  • Graph：グラフの基本コンセプト。頂点/辺の型、有向/無向、多重辺の許可/不許可、グラフ上の頂点と辺を巡回するための方法を要求
  • IncidenceGraph ： 頂点からの出辺を扱うための型と関数を要求
  • BidirectionalGraph ： 頂点の入出辺を扱うための型と関数を要求
  • AdjacencyGraph ： 隣接頂点を扱うための型と関数を要求
  • VertexListGraph ： 頂点集合を扱うための型と関数を要求
  • EdgeListGragh ： 辺集合を扱うための型と関数を要求
  • AdjacencyMatrix ： 隣接行列のためのコンセプト
  • MutableGraph ： 頂点や辺の追加や削除のための関数を要求
  • PropertyGraph ： 頂点/辺に付随するプロパティ（重みや色など）を扱うための型と関数を要求
  • MutablePropertyGraph ： プロパティ付きの頂点や辺を追加するための関数を要求

• 無向グラフの扱い
  • 有向グラフと同じインタフェイスを使うが、辺の向きが無視される

グラフ・インタフェイスについては、単にadjacency_listとBGLのアルゴリズム使うだけなら意識する必要なさそうだけどもね。自分でBGLのグラフ・インタフェイスに対応したアルゴリズム書いたり、自作のデータ構造をBGLのアルゴリズムに食わせるときには必要かと思われる。