Boost.Graphとグラフ理論の補足

発表とか、後のtwitterを見てて気になったことを書いておきます。

adjacency_listのコンストラク

発表資料では(エッジを格納したイテレータの最初、最後、頂点数)の3パラメータから成るコンストラクタを紹介しました。これは以下のコンストラクタです。

template
adjacency_list(EdgeIterator first, EdgeIterator last,
vertices_size_type n,
edges_size_type m = 0,
const GraphProperty& p = GraphProperty())
Creates a graph object with n vertices and with the edges specified in the edge list given by the range [first, last). The EdgeIterator must be a model of InputIterator. The value type of the EdgeIterator must be a std::pair, where the type in the pair is an integer type. The integers will correspond to vertices, and they must all fall in the range of [0, n).

http://www.boost.org/doc/libs/1_44_0/libs/graph/doc/adjacency_list.html

「nの部分の指定がエッジの頂点と一致しない場合はどうなるのか?」という質問がありましたが、まずnが多い場合は非連結のグラフが作られます。
グラフのノードは全て連結していなくてはならないというルールはありません。
極端な話、グラフの辺が空でも、頂点集合との組(V, φ)はグラフと言えます。
問題は、これらをどう使うか、ですね。
一方でnが小さい場合。これは上記引用部の注意に「辺は整数のペアで、その頂点を示す数字は0以上n未満の整数である必要がある」と明記してあります。
なので、この場合は動作を保証しない、あるいはn未満の頂点を指定した辺のみが有効になってグラフが作成される、という動きをすると思われます。

辺の定義

少しプレゼンテーション部分ではつぶれているので補足しておきます。
まず、有向・無向グラフに関わらず、辺は頂点の対によって表現されます。
これ以外の辺はありません。
(v1, v2, v3)は3つの頂点を結ぶ辺ではありません。
と、いうか三つ組みなので、これは辺になれないデータとなります。
そのため、家系図などは表現を考えなければグラフとしては表現出来ません。
これらの3つが繋がっていることは、例えば「(v1, v2), (v2, v3), (v3, v1)の3つの辺が全てあることの省略である」として記述するのであれば、それは許可されます。
こういった話をする場合、定義が大事に成ってくるわけです。

需要はあるのかな...?

ところでBoost.Graphとかグラフ理論とかの話は需要があるのでしょうか?
グラフ理論とかは結構Wikipediaに充実している気もしますが。
もし需要があるなら、まだまだBoost.Graphと戯れたいかなとも思う次第です。