CODEWITHSUNDEEP
graph-theoryapldyalog
justin2004
justin2004

Reputation: 305

transitive edges in APL

Say we have a rank 2 vector that represents edges in a graph:

      m←3 2⍴3 5 5 9 6 3
      m
3 5
5 9
6 3

And we want to compute the transitive edges.

e.g. Since we have the edge from node 3 to 5 and the edge from node 5 to 9 then transitively we also have the edge from node 3 to 9.

I have implemented a function to do that like this:

transitive_edges_one_step←{idx←⍸⍵[;2]∘.=⍵[;1] ⋄ 0=⍴idx:⍵ ⋄ ∪⍵⍪↑⍵∘{⍺[1⌷⍵;1],⍺[2⌷⍵;2]}¨idx}

Running it 'till quiescence produces the desired result:

      (transitive_edges_one_step⍣≡) m
3 5
5 9
6 3
3 9
6 5
6 9

What are some more terse solutions?

Does this problem require a recursive approach (here with the power operator)?

Also, for larger rank 2 vectors (20,000 rows) I get WS FULL in Dyalog. Are there solutions that use less memory?

Upvotes: 3

Views: 94

Answers (4)

Josh D
Josh D

Reputation: 53

Adam's solution showcases the classic transitive closure idiom in APL. I just want to share some more excellent write ups by Roger Hui around this, which also includes an implementation using lists instead of a matrix (more efficient if your graph is sparse)

https://forums.dyalog.com/viewtopic.php?f=13&t=1376&hilit=transitive+closure

https://forums.dyalog.com/viewtopic.php?f=30&t=1636&p=6468

Upvotes: 2

Adám
Adám

Reputation: 7671

Here's a shorter and more efficient version of B. Wilson's answer:

First, the adjacency matrix is computed simply by checking which of all possible edges exist in the list of edges:

      ⎕←a←(↓∊⍨∘⍳2⍴⌈⌿∘,)m
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

Then we compute the transitive closure of that using Boolean functions instead of arithmetic ones:

      ⎕←e←(∨.∧⍨∨⊢)⍣≡a
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 1
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1
0 0 1 0 1 0 0 0 1
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

Finally, as in the original, we get the indices of the edges:

      ↑⍸e
3 5
3 9
5 9
6 3
6 5
6 9

This is brief enough that we can put it all together in a single line:

      ↑⍸(∨.∧⍨∨⊢)⍣≡(↓∊⍨∘⍳2⍴⌈⌿∘,)m
3 5
3 9
5 9
6 3
6 5
6 9

We can even define this as a function:

      TE←↑∘⍸(∨.∧⍨∨⊢)⍣≡∘(↓∊⍨∘⍳2⍴⌈⌿∘,)
      TE m
3 5
3 9
5 9
6 3
6 5
6 9

Try it online!

Upvotes: 3

B. Wilson
B. Wilson

Reputation: 131

The power series of the adjacency matrix gives the transitive closure:

      a←{(2⍴1+⌈⌿,⍵)↑⍸⍣¯1↓⍵}m  ⍝ Adjacency matrix
      ↑⍸(×⊢+a+.×⊢)⍣≡a
 3 5
 3 9
 5 9
 6 3
 6 5
 6 9

Granted, memory usage is quadratic in node count.

Upvotes: 2

LdBeth
LdBeth

Reputation: 421

An only slightly better answer:

    z←{∪⍵⍪↑⊃,/f,¨¨t((t←⊢/⍵)/⍨⊢)⍤=¨⊂f←⊣/⍵}
    z⍣≡⊢ m
3 5
5 9
6 3
3 9
6 5
6 9

Upvotes: 1

Related Questions