4 ms·
I deal with sparse graph data structures a lot, as molecular graphs, with a maximum degree of about 5. While graphs can be represented as an adjacency matrix, m
by dalke 7y ago
I deal with sparse graph data structures a lot, as molecular graphs, with a maximum degree of about 5. While graphs can be represented as an adjacency matrix, many of the algorithms become suboptimal in that representation, eg, finding the list of 1-away neighbors becomes an O(n) operation rather than O(1), in the number of nodes.
Now, I'm not saying that these graphs or algorithms can't be represented in APL. But, as an example, consider the problem of how to find strongly connected components in a graph, which is something that is not an unreasonable interview topic for an intermediate developer in my field.
An implementation for Dyalog APL is at https://dfns.dyalog.com/c_scc.htm https://dfns.dyalog.com/c_scc.htm with commentary at https://dfns.dyalog.com/n_scc.htm https://dfns.dyalog.com/n_scc.htm . It requires about 30 lines of code, starting:
scc←{⎕ML←1 ⍝ Strongly connected components.
⍝ (Tarjan)
loop←{ ⍝ for each vertex in graph G
vert←{⍺ conn⍣(0=X ⍺⊃⍵)⊢⍵} ⍝ connection of unvisited vertex ⍺
⊃vert/(⌽⍳⍴G),⊂⍵ ⍝ for each vertex in G
} ⍝ :: T ← ∇ T
conn←{v←⍺ ⍝ connection of vertex v
T0←v trace ⍵ ⍝ optional tracing
T1←x1 v push v Lx v Xx T0 ⍝ successor state for x S L and X
T2←↑{w←⍺ ⍝ edge v → w
min_L←{(⍺ w⊃⍵)⌊@(⊂L v)⊢⍵} ⍝ L[v] ⌊← ⍺[w]
0=X w⊃⍵:L min_L w conn ⍵ ⍝ w not connected: depth-first trav
X min_L⍣(w∊S⊃⍵)⊢⍵ ⍝ low-link if w on stack
}/(⌽v⊃G),⊂T1 ⍝ for each edge from vertex v
root←(L v⊃T2)=X v⊃T2 ⍝ is a root vertex?
v comp⍣root⊢T2 ⍝ new component if root
} ⍝ :: T ← v ∇ T
...
The pseuocode on the Tarjan's strongly connected components algorithm Wikipedia page (not counting "end if", "end for", etc. lines) is shorter.
One Python implementation is at https://codereview.stackexchange.com/questions/46832/strongly-connected-components-algorithm https://codereview.stackexchange.com/questions/46832/strongl... where you can see it's slightly shorter than the APL version and - I argue - easier to understand.
Now, the APL commentary page points out:
> Nick Nikolov provides this alternative one-liner, which uses the transitive closure of the adjacency matrix (see →Graphs←).
scc←{(∪⍳⊢)↓∧∘⍉⍨∨.∧⍨⍣≡i∘.∊⍵,¨i←⍳≢⍵}
⍝ · · · · · i←⍳≢⍵ vertex indices
⍝ · · · · ⍵,¨i · consider each vertex a SCC by itself
⍝ · · · i∘.∊ · · neighbour lists to adjacency matrix
⍝ · · ∨.∧⍨⍣≡ · · · transitive closure: g[x;y] ←→ path x → y
⍝ · ∧∘⍉⍨ · · · · · ... and from y to x
⍝ (∪⍳⊢)↓ · · · · · · renumbering of component numbers
> The version is very good for small graphs but its space and time requirements grow rapidly as the size increases.
Which, I believe (not knowing more than a trivial amount of APL) is a consequence of using an array data structure rather than something which is a better fit.
- toolslive 7y agoCan't you use sparse arrays?
- dalke 7y agoI don't understand your question. I think you're asking if APL and/or J supports a sparse matrix representation, such that the one-liner scales as expected for the Tarjan algorithm. As I wrote, I don't know more than a trivial amount of APL, and cannot answer that question. However, I infer that if that were the case then the links I pointed to would use a sparse array implementation and simple one-liner, instead of the 30 or so lines of APL. Perhaps pavlov, as the next Supreme Dictator of Tech, could show us an appropriate whiteboard interview solution for this problem in APL?
- gmfawcett 7y agoI can't speak for APL, but J does have a standardized sparse-array format, and a verb for converting normal arrays to sparse and back. Most operations work on both kinds of arrays transparently, although (in my limited experience) many ops are quite a bit slower on sparse arrays. Perhaps the performance difference is less significant for huge arrays, but for me it was measurably slower when working with a 1000x1000 table. Having said that, the sparse format gives you direct access to its internal index (coordinate) array, as well as the value array. So algorithms that can take advantage of these data structures might benefit significantly.
- yvdriess 7y ago(I also deal with sparse graph data in my dayjob.) A 1-step traversal is the same complexity for both a linear algebra and vertex- or edge-centered representation. However, you do absolutely need a sparse linear algebra representation and operations (cfr. GraphBLAS mathematical foundations paper). With the standardization of linear algebra for large graphs in the form of GraphBLAS, it would be interesting to see a sparse extension to APL or J for dealing with large graph analytics. It's already there for Matlab, Python and Julia.
- robomartin 7y ago