Jon Wilson wrote:
Hi Marco,
I cobbled something together for you real quick. Attached. The
function you want to call is make-graph. node-count is obvious*.
edge-density is the probability that any given node has an edge to any
other given node. Symbol names are read from /usr/share/dict/words.
* if you set edge-density low, then you are likely to get a graph with
fewer nodes than node-count. This could be fixed, but not without
either allowing for disconnect graphs (which it didn't look like you
were interested in, nor did you give a notation for), or making it so
that edge-density didn't actually mean edge-density. Generating a
50-node graph with edge-density 0.03125, I got graphs with node counts
in the upper 30s.
HTH,
Jon
Marco Maggi wrote:
Ciao,
I need to test some module that handles graphs and
constraint networks; I would like to automatically
generate test graphs, both cyclic and acyclic. I wonder
if someone has already written some code for it and
is willing to share it or to suggest ideas.
It should be "enough" to build something like a
pseudo-random mega-scheme-function-call like:
(a
(b c (d e a))
(f (c g) (h c))
(g (e b)))
in which:
* all the elements in the lists are symbols;
* each symbol appears once and only once as
first element in a list;
* each symbol appears at least once as first
element in a list.
TIA
_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-user
(use-modules (srfi srfi-1) (srfi srfi-8))
(define (binomial p)
(> p (random:uniform)))
(define (make-edge-list name nodes p used-nodes)
(set! used-nodes (cons name used-nodes))
(let ((edge-list '()))
(for-each
(λ (node)
(if (binomial p) ; add an edge going to this node. Else, don't do anything.
(set! edge-list (xcons edge-list
(if (member node used-nodes)
node
(receive (edges used) (make-edge-list node nodes p used-nodes)
(set! used-nodes (append used used-nodes))
(cons node edges)))))))
nodes)
(values edge-list used-nodes)))
(define words (open-input-file "/usr/share/dict/words"))
(define (make-graph node-count edge-density)
(let* ((nodes (map (λ (x) (read words)) (iota node-count))))
(receive (graph used-nodes)
(make-edge-list (car nodes) nodes edge-density '())
graph)))
_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-user
