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.
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
