[wanted] automagic generation of graphs

[wanted] automagic generation of graphs

[Marco Maggi]

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

--
Marco Maggi

"Now feel the funk blast!"
Rage Against the Machine - "Calm like a bomb"




_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-user

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



_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-user

Here's the attachment...

[Jon Wilson]

[-- Attachment #1: Type: text/plain, Size: 1664 bytes --]

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



[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: make-graph.scm --]
[-- Type: text/x-scheme; name=make-graph.scm, Size: 906 bytes --]

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


[-- Attachment #3: Type: text/plain, Size: 140 bytes --]

_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-user

Re: [wanted] automagic generation of graphs

[Thien-Thi Nguyen]

() "Marco Maggi" <marco.maggi-ipsu@poste.it>
() Fri, 20 Jul 2007 18:09:54 +0200

   suggest ideas.

it just so happens i'm experimenting w/ reading (simple) lisp syntax
into guile[0].  perhaps you can grep the net for lisp callgraphs and use
`read-sexp' to convert them...

another idea is to instrument (scripts lint) from guile 1.4.x [1] to
emit such graphs from scanning scheme code (it has to do the requisite
tree crawling internally, anyway).

note to future mailing-list archive browsers: the snapshots referenced
below will disappear in a few days.

thi

_________________________________________________________
[0] EXPERIMENTAL PRE-RELEASE
    http://www.gnuvola.org/tmp/read-sexp.scm

[1] PRE-RELEASE
    http://www.gnuvola.org/tmp/lint


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-user

Re: [wanted] automagic generation of graphs

[Marco Maggi]

Thanks to all. Am I correct in saying that with a form like:

  (a . body)

if the symbol 'a' appears in 'body' the graph is cyclic,
while if the symbol does not appear in its own body the
graph is Acyclic?

--
Marco Maggi

"Now feel the funk blast!"
Rage Against the Machine - "Calm like a bomb"




_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-user

Re: [wanted] automagic generation of graphs

[Jon Wilson]

Marco Maggi wrote:
> Thanks to all. Am I correct in saying that with a form like:
>
>   (a . body)
>
> if the symbol 'a' appears in 'body' the graph is cyclic,
> while if the symbol does not appear in its own body the
> graph is Acyclic?
Well, it is immediately obvious that any graph (or digraph) which has 
such a form has a cycle.  So if a graph is acyclic, then no such form 
appears.  But you also want the converse or its contrapositive: if no 
such form appears, then the graph is acyclic; if a graph is cyclic, then 
such a form appears.

Are you trying to represent graphs or digraphs?


I. you are representing graphs

The answer is no.  (a (b c) c) contains a cycle a-b-c-a, but does not 
contain an (a . body) with a in body form.


II. you are representing digraphs

The answer is provisionally no.  (a (b c) (c b)) contains a cycle 
b->c->b, but no form (a . body) with a in body.  However, this graph 
could also be represented as (a (b (c b)) c), which does contain such a 
form.  Notice that in this latter representation, the first time a node 
appears, its edge list is given.

So, if we do not require the edge list to be given at the first 
appearance of a node, the answer is definitely no.  OTOH, if we do make 
such a requirement, the answer seems to be yes, but I have not proven 
this to be so.

Regards,
Jon


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-user