[Top][All Lists]

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

Re: [wanted] automagic generation of graphs

From: Jon Wilson
Subject: Re: [wanted] automagic generation of graphs
Date: Tue, 24 Jul 2007 13:49:14 -0400
User-agent: Thunderbird (X11/20070604)

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.


reply via email to

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