The Kitchen Sink and Other Oddities

Atabey Kaygun

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)=zN(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 A5 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