Implementing basic graph theory functions in APL with matrices

Question

I had to solve three problems on graph theory that I solved by implementing a utility function and 3 functions, one for each of the problems.

The problem set defines the input for all my functions as a E+1 x 2 matrix (they call this an edge list) where the first row V E contains the number of vertices V in the graph and the number E of edges. The other E rows contain the endpoints of edges, so a row a b means there's an edge between vertices a and b.

• Degrees is a function that retrieves the degree of a given vertex; e.g. Graphs.Degrees 8 2 ⍴ 6 7 1 2 2 3 6 3 5 6 2 5 2 4 1 4 gives 2 4 2 2 2 2;

• DoubleDegrees is a function that, given a vertex v, retrieves the sum of the degrees of the neighbours of v (i.e. the vertices connected to v by an edge); e.g. Graphs.DoubleDegrees 5 2⍴ 5 4 1 2 2 3 4 3 2 4 gives 3 5 5 5 0;

• ConnectedComponents is a function that counts the number of connected components in the graph; e.g. Graphs.ConnectedComponents 14 2⍴12 13 1 2 1 5 5 9 5 10 9 10 3 4 3 7 3 8 4 8 7 11 8 11 11 12 8 12 gives 3.

The functions work as expected.

I'm particularly interested in feedback on the AdjacencyMatrix and on the ConnectedComponents functions. Also, 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?

:Namespace Graphs
    ⍝ This particular namespace contains functions related to graphs.
    ⍝ For this namespace, an 'EdgeList' is a (v+1)×2 integer matrix, with v≥0, that encodes an undirected graph:
    ⍝   The first row (v e) is the number of vertices and edges in the graph;
    ⍝   The remaining e rows have two integers ≤v representing the end points of an edge.

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

        vertices ← ⊃1↑⍵
        edges ← (↓⌽⍪⊢) 1↓⍵
        mat ← 0⍴⍨ 2⍴ vertices
        (1@edges) mat
    }

    Degrees ← {
        ⍝ Compute the degree of a vertex of a graph.
        ⍝ Dyadic function expecting integer on the left and 'EdgeList' on the right.
        ⍝   If the left integer is missing, return the degrees of all vertices.

        ⍺ ← ⍬
        adj ← AdjacencyMatrix ⍵
        ⍺⊃+/adj
    }

    DoubleDegrees ← {
        ⍝ Compute the double degree of a vertex of a graph.
        ⍝ Dyadic function expecting an integer on the left and 'EdgeList' on the right.
        ⍝   If the left integer is missing, return the double degrees of all vertices.

        ⍺ ← ⍬
        adj ← AdjacencyMatrix ⍵
        ⍺⊃+/ +.×⍨ adj
    }

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

        adj ← AdjacencyMatrix ⍵
        v ← ⊃⍴ adj
        (1 1⍉adj) ← v⍴1     ⍝ Assign 1s to the main diagonal to accumulate all paths.
        accum ← (+.×)⍣(v-1)⍨ adj
        ≢∪ (1@(≠∘0)) accum
    }  

:EndNamespace

Answer 1

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
}