Implementing basic graph theory functions in APL with matrices
I believe the DoubleDegrees and ConnectedComponents functions are sub-optimal since they use simple algorithms but make use of matrix multiplications and search algorithms would be faster (in other languages). Is this still efficient code for APL? Or would a search-based solution be more efficient?


Many APL implementations, especially Dyalog's, are heavily optimized around array operations using hardware SIMD instructions and parallel processing. Matrix multiplication is one of them.

Classical algorithms say that matrix multiplication is heavy, and a search algorithm will definitely do better. However, the uniqueness of APL gives very low constant factor to matrix multiplication (possibly even cutting down a dimension with enough parallelism), while it likely gives a high cost to a recursive search (interpreting a function over and over, and digging through a nested array).

In conclusion, I'd say matrix multiplication is the preferred way to solve such a task in APL. If in doubt, you can always implement both and compare the timings.


  I'm particularly interested in feedback on the AdjacencyMatrix and on the ConnectedComponents functions.


AdjacencyMatrix

AdjacencyMatrix ← {
    ⍝ Compute the adjacency matrix of a graph.
    ⍝ Monadic function expecting an 'EdgeList'.

    vertices ← ⊃1↑⍵          ⍝ can be simplified to `vertices ← ⊃⍵`
    edges ← (↓⌽⍪⊢) 1↓⍵       ⍝ consider putting atop `↓` outside of the train
                             ⍝ to clarify the intent:
                             ⍝ edges ← ↓ (⌽⍪⊢) 1↓⍵
    mat ← 0⍴⍨ 2⍴ vertices
    (1@edges) mat            ⍝ `1@edges⊢ mat` is more common way to split
                             ⍝ right operand from right arg
}


ConnectedComponents

ConnectedComponents ← {
    ⍝ Computes the number of connected components of a graph.
    ⍝ Monadic function expecting 'EdgeList' as argument.

    adj ← AdjacencyMatrix ⍵
    v ← ⊃⍴ adj                 ⍝ can be simplified to `v ← ≢adj`
    (1 1⍉adj) ← v⍴1            ⍝ can be simplified to `(1 1⍉adj) ← 1`
    accum ← (+.×)⍣(v-1)⍨ adj   ⍝ more on two last lines below
    ≢∪ (1@(≠∘0)) accum
}


Plain \$n\$th matrix power of an adjacency matrix \$M\$ gives the count of all length-\$n\$ paths between given two vertices. Adding the 1 to the diagonal of \$M\$ has the effect of adding loops to the graph, and its power gives the count of all length-\$≤n\$ paths. To describe the inner workings: For each pair of vertices \$(p, r)\$, +.× counts the paths \$p \rightarrow q \rightarrow r\$ for every intermediate vertex \$q\$ by multiplying × paths for \$p \rightarrow q\$ and \$q \rightarrow r\$, and collects all of them by sum +.

But right now we don't need the counts, we just need to know whether such a path exists. This gives rise to the Boolean matrix product ∨.∧. Analogously to +.×, ∨.∧ checks if any path \$p \rightarrow q \rightarrow r\$ exists by ∧-ing \$p \rightarrow q\$ and \$q \rightarrow r\$, and collects them by ∨ to indicate if some path exists. This has several benefits:


Boolean arrays and operations on them are more time- and space-efficient over integer arrays.
Finding all connected pairs is easier with the fixed point ⍣≡, while it can't be done with +.×.
You don't need an extra step (1@(≠∘0), though it can be simplified to 0≠or simply ×) to extract the exists from the counts.


Finally, if we change ∨.∧⍣≡⍨ to ∨.∧⍨⍣≡, we double the number of steps instead of advancing only one step every iteration (thus reducing the number of matmul operation from \$O(n)\$ to \$O(\log{n})\$). If we were calculating precisely the \$n\$th power, we would need repeated squaring that refers to \$n\$'s bit pattern. We don't need to care about it because we'll be iterating until it converges anyway.

Now the code looks like: (the variable v is removed since it is no longer used)

ConnectedComponents ← {
    adj ← AdjacencyMatrix ⍵
    (1 1⍉adj) ← 1
    accum ← ∨.∧⍨⍣≡ adj    ⍝ (f.g)⍣≡⍨ is same as f.g⍣≡⍨ due to parsing rule
    ≢∪ accum
}