グラフの基本的な操作を定義したモジュール。
独自のグラフクラスを作る場合は、下の「必要なメソッド」を定義した上で、 このモジュールをインクルードします。
self[ v, w ]頂点 v と頂点 w を結ぶ辺の重み。
辺の重みは、アルゴリズムによって辺の長さや辺の容量として使われる値です。
v と w が隣接でない場合は、 parameter(:default)
の値(デフォルトでは nil )を返します。
each_vertex{ |v| ... }directed?()有向グラフなら true 、無向グラフなら false を返します。
無向グラフとは、全ての頂点について self[v, w]==self[w, v]
となるグラフです。
adjacent?(v, w)頂点 v と頂点 w が隣接(つまり辺 [v, w] が存在する)なら
true を返します。
隣接かどうかは、 self[v, w]!=parameter(:default) で判定します。
有向グラフでは、 adjacent?(v, w) と adjacent?(w, v) が
一致するとは限りません。
each_successing_vertex(v){ |w| ... }each_edge(uniq= false){ |v, w| ... }グラフの各辺に対して繰り返します。
無向グラフでも、 v, w と w, v に対して個別に
繰り返されます。これを防ぐには、 uniq に true を
指定します。
有向グラフでは uniq を指定しても無視されます。
out_degree(v)verticesedges(uniq= false)グラフの全ての辺を配列として返します。
uniq の働きは each_edge と同じです。
parameter(name)グラフについてのパラメータ。 GraphAlgorithm のメソッドで指定するパラメータのデフォルト値として使われます。
また、 parameter(:default) は、 v と w が隣接でない場合の
self[v, w] の戻り値になります。
デフォルトでは常に nil を返すようになっています。
必要に応じて再定義してください。