Today, I would like to develop a simple algorithm and the accompanying lisp code to calculate the number of components of a simple undirected graph. A component is a maximally connected subgraph of a given graph.
The algorithm will start from an arbitrary vertex, and then starts visiting all of its neighbors recursively marking them visited in the process. If all vertices are visited, the graph is connected, thus k(G) is 1. Otherwise, increase k(G) by 1, pick an unvisited vertex in random and repeat the process.
Algorithm ConnectedComponents
Input: An undirected simple graph G = (V,E)
Output: The number of connected components k(G)
Initialize: k <- 0
Visited <- {}
Begin
While V \ Visited is non-empty do
Pick a vertex v from V \ Visited
Let N <- N(v)
Do
For any x in N
Add N(x) to N
End
Until N(x) is a subset of N for every x in N
Add N to Visited
Increase k by 1
End
Return k
EndAs before, a graph is represented by a list of edges:
(defvar G '((0 1) (1 2) (1 3) (2 4) (3 4) (5 6) (6 7)
(8 9) (8 10) (10 9) (9 11)
(12 13) (13 14) (13 15) (14 15)))GLet me start with two important functions.
(defun vertices (G)
(remove-duplicates (reduce #'union G)))
(defun neighbors (xs G &optional carry)
(if (null xs)
carry
(neighbors (cdr xs)
G
(union carry (vertices (remove-if-not (lambda (e) (member (car xs) e)) G))))))VERTICES
NEIGHBORSLet us test:
(vertices G)
(neighbors '(0 2) G)(13 12 10 5 2 0 1 3 4 6 7 8 9 11 14 15)
(4 2 0 1)Now, the implementation:
(defun component (G N)
(let ((M (neighbors N G)))
(if (equal N M)
N
(component G M))))
(defun connected-components (G)
(let ((V (vertices G)))
(labels ((helper (k visited)
(let ((W (set-difference V visited)))
(if (null W)
k
(helper (1+ k)
(union visited (component G (list (car W)))))))))
(helper 0 (list (car V))))))COMPONENT
CONNECTED-COMPONENTSNow, let us test:
(component G '(0))
(component G '(5))
(component G '(8))
(component G '(13))
(connected-components G)(1 0 2 3 4)
(5 6 7)
(10 8 9 11)
(12 13 14 15)
4