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
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]
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
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!
On Nov 16, 6:29 pm, Ken Wesson
This is also a nice idea. I will take a look at both implementations.
On Nov 16, 8:16 pm, Mark Engelberg mark.engelb...@gmail.com wrote:
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
