nanocのソースを読む(DirectedGraph)

nanocのDirectedGraphクラスのソースを読んだときのメモ。
このクラスが表現していることを理解するには、"有向グラフ"を検索してグラフの形を見ておくとわかりやすいかも。
irbでDirectedGraphインスタンスを作って、ソースのコメントに載っているサンプルの動作を確認してみる。

>> require 'pp'
>> require 'nanoc3'
?> g = Nanoc3::DirectedGraph.new(%w( a b c d ))
>> pp g
#<Nanoc3::DirectedGraph:0xfc0
 @from_graph={},
 @predecessors={},
 @successors={},
 @to_graph={},
 @vertice_indexes={"a"=>0, "b"=>1, "c"=>2, "d"=>3},
 @vertices=["a", "b", "c", "d"]>

add_edge

add_edge('a', 'b')は、有向グラフで言えばaからbに線を引くようなもの。

>> g.add_edge('a', 'b')
=> {}
>> pp g
#<Nanoc3::DirectedGraph:0xfc0
 @from_graph={"a"=>#<Set: {"b"}>},
 @predecessors={},
 @successors={},
 @to_graph={"b"=>#<Set: {"a"}>},
 @vertice_indexes={"a"=>0, "b"=>1, "c"=>2, "d"=>3},
 @vertices=["a", "b", "c", "d"]>
=> nil
>> g.add_edge('b', 'c')
=> {}
>> pp g
#<Nanoc3::DirectedGraph:0xfc0
 @from_graph={"a"=>#<Set: {"b"}>, "b"=>#<Set: {"c"}>},
 @predecessors={},
 @successors={},
 @to_graph={"b"=>#<Set: {"a"}>, "c"=>#<Set: {"b"}>},
 @vertice_indexes={"a"=>0, "b"=>1, "c"=>2, "d"=>3},
 @vertices=["a", "b", "c", "d"]>
=> nil
>> g.add_edge('c', 'd')
=> {}
>> pp g
#<Nanoc3::DirectedGraph:0xfc0
 @from_graph={"a"=>#<Set: {"b"}>, "b"=>#<Set: {"c"}>, "c"=>#<Set: {"d"}>},
 @predecessors={},
 @successors={},
 @to_graph={"b"=>#<Set: {"a"}>, "c"=>#<Set: {"b"}>, "d"=>#<Set: {"c"}>},
 @vertice_indexes={"a"=>0, "b"=>1, "c"=>2, "d"=>3},
 @vertices=["a", "b", "c", "d"]>
=> nil

direct_predecessors_of

direct_predecessors_of('d')は、dへ直接線を引いている要素の集合を返す。
いまの場合、add_edge('c', 'd')でcからdへ線を引いたので、cが返る。
predecessors_of('d')は、dへたどりつける線が存在する要素の集合を返す。
たとえば、add_edge('a', 'b')、add_edge('b', 'c')、add_edge('c', 'd')としていたので、
a→b→c→dで、aはpredecessors_of('d')で返される要素の１つとなっている。
これと対応するような、direct_successors_of、successors_ofというメソッドもある。

>> g.direct_predecessors_of('d').sort
=> ["c"]
>> g.predecessors_of('d').sort
=> ["a", "b", "c"]

remove_edge

remove_edge("a", "b")は、add_edge("a", "b")を取り消す。aからbへの線を消すことに値する。

>> g.remove_edge('a', 'b')
=> {}
>> pp g
#<Nanoc3::DirectedGraph:0xfc0
 @from_graph={"a"=>#<Set: {}>, "b"=>#<Set: {"c"}>, "c"=>#<Set: {"d"}>},
 @predecessors={},
 @successors={},
 @to_graph={"b"=>#<Set: {}>, "c"=>#<Set: {"b"}>, "d"=>#<Set: {"c"}>},
 @vertice_indexes={"a"=>0, "b"=>1, "c"=>2, "d"=>3},
 @vertices=["a", "b", "c", "d"]>
=> nil

これぐらい概要を書いておけば、あとで思い出すときもすぐ思い出せるかな。