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