[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Here's the attachment...

From: Jon Wilson
Subject: Here's the attachment...
Date: Fri, 20 Jul 2007 13:44:28 -0400
User-agent: Thunderbird (X11/20070604)

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.

Marco Maggi wrote:

  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:

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


Guile-user mailing list

(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 '()))
          (λ (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)
(receive (edges used) (make-edge-list node nodes p used-nodes)
         (set! used-nodes (append used used-nodes))
         (cons node edges)))))))
        (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 '())

reply via email to

[Prev in Thread] Current Thread [Next in Thread]