Generating random regular graphs

[Tiemo]

Hi,

I need to implement an algorithm to generate large random d-regular
graphs. A d-regular graph is a graph in which all vertices have degree
d. Specifically I need to generate large (1000+ vertices) 4-regular
graphs. The algorithm I need to use is as follows:

let V be a set of n vertices with d legs
while |legs| > 0
find a random leg and connect with it
done

A leg is an edge that is not yet connected. It is important that the
algorithm iterates over the free legs in order, and then connects them
to a random leg on some edge. Edges that connect a vertex with itself
(tadpoles) are allowed.

To implement this simple algorithm in Java didn't take long, but I
want to try implementing it in Clojure, the problem is that, as a
clojure noob, I end up with imperative looking code. So how can I
tackle this problem such that the algorithm is followed precisely
(it's important because this algorithm ensures certain properties) and
I end up with efficient code?

The representation of the graph is currently a vector of vertex
structs:
(defstruct vertex :id :neighbours)

The id is there just for drawing. Neighbours is a d-sized vector. A
adjacency matrix is out of the question here because I'm concerned
with large sparsely connected graphs.

Any help is appreciated.

- Tiemo.

[Ken Wesson]

I took a stab at it:

(defn make-verts [n]
(zipmap (range n) (repeat [])))

(defn free-legs? [m i d]
(< (count (m i)) d))

(defn free-leg-indices [m n d]
(filter #(free-legs? m % d) (range n)))

(defn first-free-leg [m n d]
(first (free-leg-indices m n d)))

(defn random-free-leg [m n d]
(let [fli (free-leg-indices m n d)
fl-counts (zipmap fli (map #(- d (count (m %))) fli))
fli2 (mapcat #(repeat (fl-counts %) %) fli)]
(nth fli2 (rand-int (count fli2)))))

(defn add-random-edge [m n d]
(let [i1 (first-free-leg m n d)
i2 (random-free-leg (update-in m [i1] conj 'dummy) n d)]
(update-in (update-in m [i1] conj i2) [i2] conj i1)))

(defn d-regular-graph-edges [n d]
(/ (* n d) 2))

(defn random-d-regular-graph [n d]
(nth
(iterate #(add-random-edge % n d) (make-verts n))
(d-regular-graph-edges n d)))

It seems to work and looks pretty functional to me.

user=> (random-d-regular-graph 5 2)
{4 [0 0],
3 [1 1],
2 [2 2],
1 [3 3],
0 [4 4]}
user=> (random-d-regular-graph 5 2)
{4 [1 3],
3 [1 4],
2 [2 2],
1 [3 4],
0 [0 0]}
user=> (random-d-regular-graph 5 2)
{4 [0 2],
3 [0 1],
2 [1 4],
1 [2 3],
0 [3 4]}
user=> (random-d-regular-graph 4 3)
{3 [0 1 2],
2 [0 1 3],
1 [0 2 3],
0 [1 3 2]}
user=> (random-d-regular-graph 4 3)
{3 [0 0 1],
2 [1 2 2],
1 [0 3 2],
0 [1 3 3]}

Obviously it b0rks if the product of the number of vertices and the
degree isn't even:

user=> (random-d-regular-graph 3 3)
{2 [1 1],
1 [0 2 2],
0 [1 0 0]}

As you can see there's one free leg left over.

The only slightly tricky bit in the code is the (update-in ...
'dummy). It's there to avoid this:

user=> (random-d-regular-graph 5 2)
{4 [0 0],
3 [1],
2 [1 2 2],
1 [3 2],
0 [4 4]}

In this example, for the final random edge it took a free leg on 2 and
saw that 2 and 3 still had free legs and randomly picked 2. So, when
it goes to pick the other leg to join it has to view the leg already
chosen as already taken.

Now, this picks one leg for each new edge to be the first in a fixed
traversal order of verts-then-legs and the other randomly and
uniformly from all of the other free legs remaining. If that's not
what you wanted, say if in particular having two edges from the same
node to the same other node is verboten, I hope at least that the
outline of the code shows you how this kind of thing can be done
without mutables or even loop/recur and that you can adapt your own
algorithm to the same basic structure -- that you can see where the
random selection of the second leg of a new edge occurs and where you
might make it pick in a different way or avoid parallel pairs of
edges, etc.

If you want global properties such as connectedness, that's more
complicated; my first inclination would be to wrap the whole thing in
a (first (remove is-bad-in-some-way? (repeatedly
#(random-d-regular-graph n d)))) but I expect that would slow to a
crawl if is-bad-in-some-way? is usually true for a fully general
random graph and either n or d is at all large.

[Mark Engelberg]

I think the simplest and most efficient way to simulate the random connection process in a functional manner is to start by generating a shuffled list of d copies of each vertices (this represents the d legs for each vertex), and then pair them up using partition.  At this point you have a list of all the undirected edges, so you just add them to your graph.  This process should work with any graph representation.

So if your vertices are numbered 0 through 3, and you want 3 edges coming out from each vertex, you begin by shuffling the list:
[0 1 2 3 0 1 2 3 0 1 2 3]
into something like:
[2 1 3 0 3 0 2 2 0 3 1 1]
Then partition this into:
[[2 1] [3 0] [3 0] [2 2] [0 3] [1 1]]
These are your 6 undirected edges which you store in your graph however you like.

For demonstration purposes, consider a graph representation where an undirected edge is stored as two directed edges, vertex ids are numbers in (range number-of-nodes), and the graph is just a vector that associates vertex ids with vectors of ids you can get to via outgoing directed edges.

A straightforward implementation of graph-building functions:

(defn empty-graph [number-of-nodes]
 (vec (repeat number-of-nodes [])))

(defn add-directed-edge [graph node1 node2]
 (let [node1-neighbors (graph node1)]
   (assoc graph node1 (conj node1-neighbors node2))))

(defn add-edge [graph [node1 node2]]
 (-> graph
     (add-directed-edge node1 node2)
     (add-directed-edge node2 node1)))

And the random generation is easy:

(defn random-graph [number-of-nodes number-of-edges]
 (reduce add-edge (empty-graph number-of-nodes)
         (partition 2 (shuffle (take (* number-of-nodes number-of-edges)
                                     (cycle (range number-of-nodes)))))))

[Tiemo]

That is really nice thank you. I'd have to take a real hard look at
it, to see whether or not it's the exact algorithm I need, but
nonetheless, you pointed me in the right direction. The code I
produced was a mess of mutable state and loops. Thank you very much!

[Tiemo]

This is also a nice idea. I will take a look at both implementations.