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
gives2 4 2 2 2 2
;DoubleDegrees
is a function that, given a vertexv
, retrieves the sum of the degrees of the neighbours ofv
(i.e. the vertices connected tov
by an edge); e.g.Graphs.DoubleDegrees 5 2⍴ 5 4 1 2 2 3 4 3 2 4
gives3 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
gives3
.
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