APL/J言語:グラフ理論

APL/J言語:グラフ理論

以下、よくわかりません。

      • -

グラフ理論における、有向グラフ(向き有りグラフ、directed graph)とは結線(connection)やアーク(arc)によって結ばれたノード(接点)の集合である。ツリー構造や、手順における前工程(封筒を糊付けする前に、中身を入れる、等)を示すために用いられる。

結線はアークのかわりにブール型結合マトリックスで示すことができる。逆に結合マトリックスはアークのリストによって決定することができる。

結合マトリックスはグラフの様々な特性を決定するのに便利である。たとえばノードに入るアークの数(インディグリー)やアウトディグリー、直接の継承先、クロージャー、あるパスを通じて到達できるすべてのノードへの結合、等である。

   from=: 3 7 2 5 5 7 1 5 5 5 2 6 1 2 3 7 7 4 7 2 7 4
     to=: 5 6 0 2 6 2 7 6 0 7 3 3 2 1 7 0 4 2 3 0 0 3
   $ arcs=: from,.to
22 2       
   |: arcs { nodes=: 'ABCDEFGH'   NB.表示の都合上トランスポーズしてある
DHCFFHBFFFCGBCDHHEHCHE
FGACGCHGAHDDCBHAECDAAD
   CM=: #. e.~ [: i. [ , [        NB.アークからの結合マトリックス
   ]cm=: (>:>./,arcs) CM arcs
0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1
1 1 0 1 0 0 0 0
0 0 0 0 0 1 0 1
0 0 1 1 0 0 0 0
1 0 1 0 0 0 1 1
0 0 0 1 0 0 0 0
1 0 1 1 1 0 1 0
   (+/cm);(+/"1 cm);  (+/+/cm);(#arcs);(#~.arcs)
 +---------------+---------------+--+--+--+
 |3 1 4 4 1 1 2 3|0 2 3 2 2 4 1 5|19|22|19|
 +---------------+---------------+--+--+--+

上記の結果は、イン、アウト、トータルのディグリーの数と、アークの数、それから重複を除いた(distinct)アークの数である。ブール型ベクトルbをノードを表すベクトルとすると、内積b+./ . *.cmはそこから到達できるノードの同じ表現になる。直接のファミリー(オリジナルポイントを含む)は従って次のinfam関数になる。

   imfam=: [ +. +./ . *.
   (b=: 1 0 0 0 0 0 0 1) imfam cm
1 0 1 1 1 0 1 1