• 1.1k
• 5
• 18

• 1.1k
• 5
• 18

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. Maths.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. Maths.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