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)))
POOLThis 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-DIFFERENCEHere 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)))
GRAPHLet us test it. Here is a random 5-regular graph on 20-vertices:
(defvar G (graph (pool 20 5)))
G