Logic Dice

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

勉強会, 数学

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

adjacency_listのコンストラクタ

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

template <class EdgeIterator>

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と戯れたいかなとも思う次第です。

Permalink | コメント(3) | トラックバック(0) | 21:28

Boost.勉強会#3関西に参加して発表してきました

プログラム, 勉強会

Boost.勉強会#3関西に参加してきました。

http://kokucheese.com/event/index/4335/

当日の発表資料はこちら。

”Boost.GraphとC++初心者な私(pptx)”

”Boost.GraphとC++初心者な私(pdf)”

まあ、色の微調整とネタなどを仕込んだだけなんですけどね。事前資料との差異は。

勉強会参加の感想としては、楽しい異文化コミュニケーションをしてきたような感じでした。

いや、異文化過ぎて全く分からないもの*1もありましたが。

懇親会でも色々と面白い話が出来ました。

あとは、名刺を配りまくってたり、その場にいた魔導書著者の全員にサインを貰ったりとか、結構好きに動いてました。

スピーカーをやる事は自身の勉強のモチベーションに繋がるので非常に有効ですね。

自分のようなC++初心者(学生)でも発表は出来たので、その場に居たC++erな人やustで見てた人なんかもぜひ(勉強して)発表されてはどうでしょうか？

次は関東・関西以外にも、名古屋・北海道あたりでも開催の話がある模様ですので。

勉強会の後、自分の心が闇の軍団方向に進んでいくような気がしましたが、はてさて、今後どうなる事やら。

Permalink | コメント(0) | トラックバック(0) | 21:10