Generating Uniformly Random Connected Graphs
Description of the problem
Today, I’d like to expand on an old post. In that post I gave a simple algorithm and the corresponding lisp code that generates a uniformly random tree on nn vertices. Today, I’ll extend the code to generate a uniformly random connected graph on n vertices.
The main idea
The main idea is to get a uniformly random edge from the whole list of unused edges after we get a uniformly random tree on n vertices.
An implementation
First, I need a utility function that gets the first nn terms in a list.
(defun take (xs n &optional res)
(if (or (zerop n) (null xs))
(reverse res)
(take (cdr xs) (1- n) (cons (car xs) res))))
TAKEThe following function creates all possible edges on the vertex set \({0,\ldots,n−1}\) and then randomly sorts them.
(defun get-the-pool (n)
(mapcar #'cdr
(sort (loop for i from 0 below (1- n) append
(loop for j from (1+ i) below n collect
(list (random 1.0) i j)))
#'<
:key #'car)))
GET-THE-POOLI am re-using the following code from my earlier random tree post:
(defun random-tree (n)
(loop for i from 1 below n collect
(list (random i) i)))
RANDOM-TREENow, the code for the uniformly random connected graph:
(defun get-random-connected-graph (n)
(let ((pool (get-the-pool n))
(tree (random-tree n))
(k (random (floor (- (* n (1- n)) (1- n)) 2))))
(do* ((xs pool (remove (car ys) xs :test #'equal))
(ys tree (cdr ys)))
((null ys) (append tree (take xs k))))))
GET-RANDOM-CONNECTED-GRAPHWe first get the pool of edges in random order. Then we generate a random tree. This is the key for connectedness since every connected graph has a spanning tree. Then we remove the edges in the randomly generated tree from the pool of edges, and finally we get a random number of edges from the pool to finalize our random graph. I set that number to be between 0 and the half of the remaining edges to get something that I can display.
Let us test our code: a random connected graph on 14 vertices.
(defparameter G (get-random-connected-graph 14))
G