Counting Cycle-Free Paths in a Graph

Description of the problem

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\).

A recurrence relation

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\).

An implementation

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)))

A5

First, 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-VERTEX

Let 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-PATHS

Let us test our implementation on the trivial example A5:

(count-paths A5 0 4)

1

This 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))

2

The 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))

12

Finally, 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