Generating random regular graphs

Description of the problem

An undirected graph \(G=(V,E)\) is called regular if all of the vertices \(v\in V\) has the same degree. For the purposes of today’s post, I will allow loops on vertices, and multiple edges between any pair of vertices.

A solution implementation in Common Lisp

First, I am going to need a helper function that will generate \(k\)-copies of each vertex numbered from \(1\) to \(n\):

(defun pool (n k)
   (loop for i from 1 to n append
       (loop repeat k collect i)))

POOL

This is going to needed to generate a random \(k\)-regular graph on \(n\)-vertices.

I am also going to need an helper function that takes the difference of two lists like set-difference but one that works for lists:

(defun list-difference (xs ys)
  (cond ((null ys) xs)
        ((member (car ys) xs) (list-difference (remove (car ys) xs :count 1) 
                                               (cdr ys)))
        (t (list-difference xs (cdr ys)))))

LIST-DIFFERENCE

Here is the function that generates that random graph

(defun graph (xs &optional es)
  (labels ((random-elt (ys) (elt ys (random (length ys))))
           (random-edge (xs)  
             (let* ((x (random-elt xs))
                    (y (random-elt (remove x xs :count 1))))
               (if (> x y)
                   (list y x)
                   (list x y)))))
    (if xs
        (let ((e (random-edge xs)))
          (graph (list-difference xs e) (push e es)))
        es)))

GRAPH

Let us test it. Here is a random 5-regular graph on 20-vertices:

(defvar G (graph (pool 20 5)))

G