>>  <<  Ndx  Usr  Pri  Phr  Dic  Rel  Voc  !:  wd  Help  Dictionary

20. Directed Graphs

A directed graph is a collection of nodes with connections or arcs specified between certain pairs of nodes. It can be used to specify matters such as the precedences in a set of processes (stuffing of envelopes must precede sealing), or the structure of a tree.

The connections can be specified by a boolean connection matrix instead of by arcs, and the connection matrix can be determined from the list of arcs.

The connection matrix is convenient for determining various properties of the graph, such as the in-degrees (number of arcs entering a node), the out-degrees, immediate descendants, and the closure, or connection to every node reachable through some path. For example:
   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'         Transposed for display
DHCFFHBFFFCGBCDHHEHCHE
FGACGCHGAHDDCBHAECDAAD

   CM=: #. e.~ [: i. [ , [              Connection matrix from arcs
   ]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|
+---------------+---------------+--+--+--+
The foregoing results are the in, out, and total degrees; followed by the number of arcs, and the number of distinct arcs. A boolean vector b may be used to represent the nodes, and the inner product b +./ . *. cm gives the same representation of the nodes reachable from them. The immediate family (which includes the original points themselves) is therefore given by the function imfam :
   imfam=: [ +. +./ . *.
   (b=: 1 0 0 0 0 0 0 1) imfam cm
1 0 1 1 1 0 1 1


>>  <<  Ndx  Usr  Pri  Phr  Dic  Rel  Voc  !:  wd  Help  Dictionary