|
35. Transitive Closure The transitive closure of a set of directed edges is the set of reachable nodes. If the edges are represented as a matrix, its transitive closure can be computed as in the following example: i←⍳19 b←i∘.=2+i ⍝ edges are (i,2+i) t←(⊢∨∨.∧⍨)⍣≡b ⍝ transitive closure of b '.∘'[b] '.∘'[t] ................... ................... ................... ................... ∘.................. ∘.................. .∘................. .∘................. ..∘................ ∘.∘................ ...∘............... .∘.∘............... ....∘.............. ∘.∘.∘.............. .....∘............. .∘.∘.∘............. ......∘............ ∘.∘.∘.∘............ .......∘........... .∘.∘.∘.∘........... ........∘.......... ∘.∘.∘.∘.∘.......... .........∘......... .∘.∘.∘.∘.∘......... ..........∘........ ∘.∘.∘.∘.∘.∘........ ...........∘....... .∘.∘.∘.∘.∘.∘....... ............∘...... ∘.∘.∘.∘.∘.∘.∘...... .............∘..... .∘.∘.∘.∘.∘.∘.∘..... ..............∘.... ∘.∘.∘.∘.∘.∘.∘.∘.... ...............∘... .∘.∘.∘.∘.∘.∘.∘.∘... ................∘.. ∘.∘.∘.∘.∘.∘.∘.∘.∘.. b records that there is an edge from node i to node 2+i . t is the transitive closure of b ; ⍸i⌷t are the nodes reachable from node i . A matrix is usually an inefficient representation for a graph and therefore the above is usually an inefficient computation of the transitive closure. There is a limited version of transitive closure with an efficient representation and computation [49b, 51e]: Each node has exactly one outgoing edge. All edges go to a higher-numbered node, except for the last node, whose edge goes to itself. The graph can be represented as an integer vector. Such a graph arises in several practical problems such as paragraphing, nested multiple quotation marks, record length and data, etc.
x← 1 4 5 5 7 6 9 9 10 12 11 14 14 15 16 18 18 18 20 20 20
(⍳≢x) ,[¯0.5] x
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 4 5 5 7 6 9 9 10 12 11 14 14 15 16 18 18 18 20 20 20
tc←{⍺←0 ⋄ (⊃⍵)=⊃⌽⍵:∪⍺ ⋄ (⍺,⍵[⍺]) ∇ ⍵[⍵]}
tc x
0 1 4 7 9 12 14 16 18 20
At the j-th function call, ⍵[i] represents the node reachable from node i in 2*j steps. tc x are the nodes reachable from node 0 and terminates in at most ⌈2⍟≢x function calls. The transitive closure of x can be computed in at least two other ways: ⍸ 0⌷⍤1 (⊢∨∨.∧⍨)⍣≡(⍳≢x)∘.=x 1 4 7 9 12 14 16 18 20 ⍸ ((≢x)↑1)⌹(∘.=⍨⍳≢x)-(⍳≢x)∘.=x+x=⊃⌽x 0 1 4 7 9 12 14 16 18 The first is the repeated squaring method on the adjacency matrix presented above. The second is due to Bob Smith [103], and is based on the infinite series equation ÷1-x ←→ (x*0)+(x*1)+(x*2)+ … for numbers translated into the matrix realm,
using the identity matrix instead of 1 , ⌹
instead of ÷ ,
and +.× instead of × (implicit in *).
|