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