Here's the attachment...

[Jon Wilson]

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
> address@hidden
> 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)))