Re: Two Steps Forward One Step Back Re: Newbie list traversal

Emre Sevinc <emres@xxxxxxxxxxxx> writes:
> Pascal Bourguignon <pjb@xxxxxxxxxxxxxxxxx> writes:
>
>> Emre Sevinc <emres@xxxxxxxxxxxx> writes:
>>> What am I doing wrong? (I also tried to use cond but
>>> it brings too much semantic confusion to my poor brain
>>> during the early hours of the morning, using if was, I hope,
>>> easier to read, write and understand)
>>
>> A DOT file describes a graph. You start from a list.
>>
>> Why don't you build a graph from your list before generating the DOT
>> from the graph?
>
> I'm a little bit confused and didn't understand what you
> mean exactly.


If you've read the documentation of graphviz, you should know what a
graph is. It's a couple (N,E) where N is a set of nodes, and E is a
relation on N, that is, E is a subset of N×N.

Trees are a special kind of graph: they are acyclic graphs.

Now, since you start from CONSes, you have to define how you read a
tree from this heap of CONSes. There are several way to build trees
with CONSes.

For example if you consider just binary trees with the left child in
the CAR and the right child in the CDR, each CONS being a node:

(defun node-label (node)
"Return the label of the node"
node)

(defun node-children (node)
"Return the list of children to the node."
(when (consp node)
(list (car node) (cdr node))))


In you case, it looks like you're considering LISTs to be the nodes,
the first element being the label and the rest the children:

(defun node-label (node)
"Return the label of the node"
(if (consp node)
(first node)
node))

(defun node-children (node)
"Return the list of children to the node."
(when (consp node)
(cdr node)))


To take the example of your *linear* tree:

(setf *linear*
'(PP (Spec right) (P* (P across) (NP (Spec the) (N* (N bridge))))))


;; rot13'ed to protect the innocents.

(qrsha abqrf (gerr)
"
ERGHEA: Gur yvfg bs abqrf va gur gerr.
"
(apbap (yvfg (abqr-ynory gerr)) ; gur cnerag abqr
(zncpna (shapgvba abqrf) (abqr-puvyqera gerr))))

(qrsha rqtrf (gerr)
"
ERGHEA: Gur yvfg bs rqtrf va gur gerr.
"
(apbap (zncpne (ynzoqn (puvyq) (yvfg (abqr-ynory gerr) (abqr-ynory puvyq)))
(abqr-puvyqera gerr))
(zncpna (shapgvba rqtrf) (abqr-puvyqera gerr))))

(progn
(format t "~&N = { ~{~A~^,~% ~} }~2%" (nodes *linear*))
(format t "~&E = { ~:{( ~8A , ~A ),~% ~} }~2%" (edges *linear*)))

N = { PP,
SPEC,
RIGHT,
P*,
P,
ACROSS,
NP,
SPEC,
THE,
N*,
N,
BRIDGE }

E = { ( PP , SPEC ),
( PP , P* ),
( SPEC , RIGHT ),
( P* , P ),
( P* , NP ),
( P , ACROSS ),
( NP , SPEC ),
( NP , N* ),
( SPEC , THE ),
( N* , N ),
( N , BRIDGE ),
}

If you look closely, you'll notice that the DOT file can be written
directly from N and E. (Perhaps you'll want to add some calls to
node-label).


> Can you explain what you exactly meant? I start
> from a list because that's how linguists write
> their parse trees when they don't have much
> space:
>
> [PP [Spec right] [P' [P ... ...]]]
>
> And then the above structure can be drawn as
> a tree diagram. As far as I know graphviz is good
> for that but in order to draw that tree diagram
> I must first convert it to DOT notation, put
> it in a .dot file and run the dot command on it,
> right?
>
> Am I doing something wrong?

Yes, you're looking it too closely. Back off a little and abstract.

> Did I miss something?

- The input of graphviz is a graph (Nodes, Edges), so you must first
get a graph, not a DOT file. From a graph, you can generate
trivially the DOT file.

- A tree is a graph, so there's no difficulty in obtaining the nodes
and the edges once you have a tree.

- you start from a list representation of a tree, but you need to
explicit your representation. The same list can represent various
different trees:

(a (b c) (d e)) could represent:

T1 = ( N = { (A (B C) (D E)),
A,
(B C),
B,
C,
(D E),
D,
E }

E = { ( (A (B C) (D E)) , A ),
( (A (B C) (D E)) , (B C) ),
( (A (B C) (D E)) , (D E) ),
( (B C) , B ),
( (B C) , C ),
( (D E) , D ),
( (D E) , E ),
} )

or:
T2 = ( N = { (A (B C) (D E)),
A,
((B C) (D E)),
(B C),
B,
(C),
C,
NIL,
((D E)),
(D E),
D,
(E),
E,
NIL,
NIL }

E = { ( (A (B C) (D E)) , A ),
( (A (B C) (D E)) , ((B C) (D E)) ),
( ((B C) (D E)) , (B C) ),
( ((B C) (D E)) , ((D E)) ),
( (B C) , B ),
( (B C) , (C) ),
( (C) , C ),
( (C) , NIL ),
( ((D E)) , (D E) ),
( ((D E)) , NIL ),
( (D E) , D ),
( (D E) , (E) ),
( (E) , E ),
( (E) , NIL ),
} )

or:
T3 = ( N = { A,
B,
C,
D,
E }

E = { ( A , B ),
( A , D ),
( B , C ),
( D , E ),
} )

or:
etc...


http://en.wikipedia.org/wiki/Graph_theory

--
__Pascal Bourguignon__ http://www.informatimago.com/

There is no worse tyranny than to force a man to pay for what he does not
want merely because you think it would be good for him. -- Robert Heinlein
.

Relevant Pages

  • Re: Making trees from branches
    ... Then Make the sub-tree into a tree ... a list containing the label of the from node and the label of the to ... Since we have a tree graph, adjacency lists will be a good ...
    (comp.lang.lisp)
  • Re: A syntax of minimal commitment
    ... It is probably not coincidence that another fairly well-known and popular notation with much the same aims has a form which is only trivially different than sexps, although rather less expressive without special hacks (limited data types, no easy way of expresssing sharing & circularity). ... no one has figured out how to represent an arbitrary graph ... the next best thing to a graph is a tree (or a list of lists) ...
    (comp.lang.lisp)
  • Re: solution to Exercise 6 of Chapter 3, Lisp Primer
    ... I have some difficult when I try to solve the exercise 6 of Chapter 3. ... Look at the prefix expression as a tree where each node in the tree is a ... you replaced them with lists. ... This is an exercise in chapter 3 of an introductory book. ...
    (comp.lang.lisp)
  • Re: eval in bash vs macro in lisp
    ... The first element is the symbol "defun", ... The last two elements are nil, ... is used to end lists. ... The whole thing is a tree formed from pairs. ...
    (comp.lang.lisp)
  • Re: Lisp at sexps length
    ... A tree doesn't look. ... tokens or characters but it's not *the* stream. ... >> parens for grouping and something else for lists. ... it means to construct a syntax object which means addition. ...
    (comp.lang.lisp)