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)))))))
--
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
