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 <kwess...@gmail.com> wrote:
> 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
