Re: [wanted] automagic generation of graphs

[Jon Wilson]

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