Sample 20. Directed Graphs

>> << 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