20. 指向圖

指向圖 為一群節點與聯結任兩節點的連線或弧線所組成。它可以用來描述諸如一群步驟的優先順序 (裝信封必須優先於封口)，或者樹狀結構。

路徑可以布林連接矩陣 取弧線，而連接矩陣可由一系列的弧線所決定。

連接矩陣便於決定圖的各種性質，如進-度數 (到達一節點的弧線)、出-度數、最近下家與終點，或某些路徑所有的弧線。例如：

   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'         轉換成顯示
DHCFFHBFFFCGBCDHHEHCHE
FGACGCHGAHDDCBHAECDAAD

   CM=: #. e.~ [: i. [ , [              由弧線得到的連接矩陣
   ]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|
+---------------+---------------+--+--+--+

前述結果為進、出與總度數；接著為弧線個數與相異弧線個數。布林向量 b 用來代表節點，而內積 b +./ . *. cm 得到它們可達到的節點。因此近親族群 (包括原來節點)由函數imfam得到：

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

下個 • 前個 • 字彙 • 索引 • 主選單