Given a graph \(G = (V,E)\) and a pair of vertices \(x\) and \(y\), we would like to count the number of (cycle-free) paths between and \(x\) and \(y\).
Let \(N(G,x)\) be the set of neighbors of \(x\) in \(G\) and let \(G/x\) be the graph obtained from \(G\) by removing the vertex \(x\) and all edges incident to \(x\). Let us use \(P(G;x,y)\) to denote the number of paths between \(x\) and \(y\) in \(G\). Then \[ P(G;x,y) = \sum_{z\in N(G,x)} P(G/x;z,y) \] We treat the special case \(x=y\) as \(P(G;x,x)=1\).
We are going to represent a graph by listing set of neighbors of each vertex. This is called the adjacency list representation of a graph. For example, the line graph \(A_5\) is going to described as an association list of set of neighbors as
(defparameter A5 '((0 1) (1 0 2) (2 1 3) (3 2 4) (4 3 5)))A5First, I need a function that removes a vertex and all edges incident to it.
(defun remove-vertex (G x)
(mapcar (lambda (xs) (remove x xs))
(remove-if (lambda (xs) (equal x (car xs))) G)))REMOVE-VERTEXLet us test:
(remove-vertex A5 0)((1 2) (2 1 3) (3 2 4) (4 3 5))Next, we write the implementation:
(defun count-paths (G x y)
(cond ((or (null (assoc x G)) (null (assoc y G))) 0)
((equal x y) 1)
(t (let ((G-prime (remove-vertex G x)))
(loop for z in (cdr (assoc x G)) sum (count-paths G-prime z y))))))COUNT-PATHSLet us test our implementation on the trivial example A5:
(count-paths A5 0 4)1This was easy, let us test a slightly more complicated example: C5
(let ((C5 '((0 1 4) (1 0 2) (2 1 3) (3 2 4) (4 3 0))))
(count-paths C5 0 4))2The wheel graph W5:
(let ((W5 '((0 1 4 5) (1 0 2 5) (2 1 3 5) (3 2 4 5) (4 3 0 5) (5 0 1 2 3 4))))
(count-paths W5 0 4))12Finally, a random 4-regular graph on 20 vertices and two random points
(let* ((N 20)
(d 4)
(x (random N))
(y (random N))
(G (loop for i from 0 below N collect
(cons i (remove i (loop repeat d collect (random N)))))))
(count-paths G x y))201364