Adjacency List functions

General APL language issues

Adjacency List functions

Postby paulmansour on Wed Jul 04, 2018 2:19 pm

I'm writing some functions to operate on adjacency lists, which are used for representing hierarchies. I assume this code has been written many times before me, but I cannot find any articles in Vector on it, and the dfns functions deal with trees in two other formats, tree view and nested arrays.


Here is a crude attempt at finding the list of ancestors for each item, quadIo 0, quad ML 3. Note that I am returning indices back into the original arguments:
Code: Select all
adjacencyListAncestors←{
     ⍝ ⍺ ←→ Parent
     ⍝ ⍵ ←→ key
     p←⍵⍳⍺
     r←≢⍵
     q←p,r
     z←⍬{
         ⍵∧.=r:⍺
         (⍺,⊂⍵)∇ q[⍵]
     }p
     (↓⍉⊃z)~¨r
 }

k←'Merlot' 'Beer' 'Wine' 'Red' 'White' 'Rose' 'Lager' 'Stout' 'Cab'
       p←'Red' '' '' 'Wine' 'Wine' 'Wine' 'Beer' 'Beer' 'Red'
      k,[0.5 ] p
 Merlot  Red 
 Beer         
 Wine         
 Red     Wine
 White   Wine
 Rose    Wine
 Lager   Beer
 Stout   Beer
 Cab     Red 
    ]display  p adjacencyListAncestors k
┌→────────────────────────────────────────┐
│ ┌→──┐ ┌⊖┐ ┌⊖┐ ┌→┐ ┌→┐ ┌→┐ ┌→┐ ┌→┐ ┌→──┐ │
│ │3 2│ │0│ │0│ │2│ │2│ │2│ │1│ │1│ │3 2│ │
│ └~──┘ └~┘ └~┘ └~┘ └~┘ └~┘ └~┘ └~┘ └~──┘ │
└∊────────────────────────────────────────┘


There are obviously a bunch of other functions that suggest themselves, including converting to tree view format, etc.

Specific questions:

1. In the above case, is there a better way? I get the feeling there might be some grade up technique that does it without recursion.

2. Is there any literature on this out there that I have missed?

Thanks.
paulmansour
 
Posts: 302
Joined: Fri Oct 03, 2008 4:14 pm

Re: Adjacency List functions

Postby Roger|Dyalog on Wed Jul 04, 2018 11:09 pm

For the specific problem of computing the list of ancestors, search for the phrase "transitive closure". More generally, an adjacency list is just one way (although usually the most efficient way) to represent a graph. In the initial stages of grappling with the problem it may be helpful to work with the Boolean matrix representation.

I will come up with a solution of transitive closure for Boolean matrices in a bit.
Roger|Dyalog
 
Posts: 139
Joined: Thu Jul 28, 2011 10:53 am

Re: Adjacency List functions

Postby Roger|Dyalog on Thu Jul 05, 2018 2:37 am

A solution using an adjacency matrix representation:

Code: Select all
      ⊢ u←∪k,p              ⍝ the list of unique nodes   
┌──────┬────┬────┬───┬─────┬────┬─────┬─────┬───┬┐
│Merlot│Beer│Wine│Red│White│Rose│Lager│Stout│Cab││
└──────┴────┴────┴───┴─────┴────┴─────┴─────┴───┴┘
      B←(2⍴≢u)⍴0            ⍝ adjacency matrix           
      B[↓u⍳p,⍪k]←1          ⍝ populate adjacency matrix   
      B
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0
0 0 0 1 1 1 0 0 0 0
1 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
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 1 1 0 0 0 0 0 0 0
      ⊢ C← {⍵∨∨.∧⍨⍵}⍣≡ B    ⍝ transitive closure         
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0
1 0 0 1 1 1 0 0 1 0
1 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
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
1 1 1 1 1 1 1 1 1 0
      ⍸¨ ↓ ⍉C               ⍝ list of lists of ancestors 
┌─────┬─┬─┬───┬───┬───┬───┬───┬─────┬┐
│2 3 9│9│9│2 9│2 9│2 9│1 9│1 9│2 3 9││
└─────┴─┴─┴───┴───┴───┴───┴───┴─────┴┘
      ⍸¨ ↓C                 ⍝ list of lists of descendants
┌┬───┬─────────┬───┬┬┬┬┬┬─────────────────┐
││6 7│0 3 4 5 8│0 8││││││0 1 2 3 4 5 6 7 8│
└┴───┴─────────┴───┴┴┴┴┴┴─────────────────┘

In this case the 9, "the mother of all drinks", is lousing things up. We can exclude it from the final results, but it's neater to remove it at the beginning.

Code: Select all
      u1←u~⊂''              ⍝ the list of unique nodes
      B1←(2⍴≢u1)⍴0          ⍝ adjacency matrix
      B1[↓u1⍳(~p∊⊂'')⌿p,⍪k]←1
      B1
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0
0 0 0 1 1 1 0 0 0
1 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 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
      ⊢ C1← {⍵∨∨.∧⍨⍵}⍣≡ B1    ⍝ transitive closure
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0
1 0 0 1 1 1 0 0 1
1 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 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
      ⍸¨ ↓ ⍉C1                ⍝ list of lists of ancestors 
┌───┬┬┬─┬─┬─┬─┬─┬───┐
│2 3│││2│2│2│1│1│2 3│
└───┴┴┴─┴─┴─┴─┴─┴───┘
      ⍸¨ ↓ C1                 ⍝ list of lists of descendants 
┌┬───┬─────────┬───┬┬┬┬┬┐
││6 7│0 3 4 5 8│0 8││││││
└┴───┴─────────┴───┴┴┴┴┴┘

A solution using lists which avoids blowing it up into a matrix. Unless the graph is dense using lists is more efficient.

Code: Select all
      f←(≢u1)⍴⊂⍬            ⍝ list of fathers       
      f[u1⍳b/k],←u1⍳b/p     ⍝ populate list of fathers
      f
┌─┬┬┬─┬─┬─┬─┬─┬─┐
│3│││2│2│2│1│1│3│
└─┴┴┴─┴─┴─┴─┴─┴─┘
      {∪¨ ⍵,¨⍵∘{∊⍺[⍵]}¨⍵}⍣≡ f  ⍝ transitive closure
┌───┬┬┬─┬─┬─┬─┬─┬───┐
│3 2│││2│2│2│1│1│3 2│
└───┴┴┴─┴─┴─┴─┴─┴───┘

A final example using lists:

Code: Select all
      f←100⍴⊂⍬
      f[2*1+⍳6],←2*⍳6            ⍝ each number 2*k has 2*k-1 as its father
      f[3*1+⍳4],←3*⍳4            ⍝ each number 3*k has 3*k-1 as its father
      f
┌┬┬─┬─┬─┬┬┬┬─┬─┬┬┬┬┬┬┬─┬┬┬┬┬┬┬┬┬┬┬─┬┬┬┬┬──┬┬┬┬
│││1│1│2││││4│3│││││││8│││││││││││9│││││16││││...
└┴┴─┴─┴─┴┴┴┴─┴─┴┴┴┴┴┴┴─┴┴┴┴┴┴┴┴┴┴┴─┴┴┴┴┴──┴┴┴┴

      a ← {∪¨ ⍵,¨⍵∘{∊⍺[⍵]}¨⍵}⍣≡f  ⍝ list of ancestors

      (⍸~a∊⊂⍬),⍪(~a∊⊂⍬)/a         ⍝ list of ancestors with labels
┌──┬─────────────┐
│2 │1            │
├──┼─────────────┤
│3 │1            │
├──┼─────────────┤
│4 │2 1          │
├──┼─────────────┤
│8 │4 2 1        │
├──┼─────────────┤
│9 │3 1          │
├──┼─────────────┤
│16│8 4 2 1      │
├──┼─────────────┤
│27│9 3 1        │
├──┼─────────────┤
│32│16 8 4 2 1   │
├──┼─────────────┤
│64│32 16 8 4 2 1│
├──┼─────────────┤
│81│27 9 3 1     │
└──┴─────────────┘
Roger|Dyalog
 
Posts: 139
Joined: Thu Jul 28, 2011 10:53 am

Re: Adjacency List functions

Postby paulmansour on Thu Jul 05, 2018 12:27 pm

Roger,

Thankyou! Digesting it all...

Paul
paulmansour
 
Posts: 302
Joined: Fri Oct 03, 2008 4:14 pm


Return to Language

Who is online

Users browsing this forum: No registered users and 1 guest