SKILL q: how do I reorder a tree represented as nested lists

[fogh]

Hi all,

I would like a function that does a bit what a "make" does, listing the dependencies first. I for instance takes this input:
'(1
(11 12
(121 122)
13)
2
3
(31
(311
(3111)
)
)
)
and returns
( (3111 121 122 13 11 2)
(311 12)
(31 1)
(3)
)

I am sure there is a clever way to do this in lisp, and maybe it is even in some classic books, but I did not read those books and I don t feel so clever on this friday.
So if you know this procedure, please post.

TIA,
--
Frederic

[Jim Newton]

sorry, i do not understand what kind of rule you are using to
order the list? why does 121 come after 3111?

-jim


fogh wrote:

Hi all,

I would like a function that does a bit what a "make" does, listing the
dependencies first. I for instance takes this input:
'(1
(11 12
(121 122)
13)
2
3
(31
(311
(3111)
)
)
)
and returns
( (3111 121 122 13 11 2)
(311 12)
(31 1)
(3)
)

I am sure there is a clever way to do this in lisp, and maybe it is even
in some classic books, but I did not read those books and I don t feel
so clever on this friday.
So if you know this procedure, please post.

TIA,

[fogh]

The rule is just dependency. Leaves firts. Then leaves + 1 , but the
depth of leaves is not the same.
You can switch 121 and 3111, order doesn t matter inside this list.

Jim Newton wrote:

sorry, i do not understand what kind of rule you are using to
order the list? why does 121 come after 3111?

-jim


fogh wrote:

Hi all,

I would like a function that does a bit what a "make" does, listing
the dependencies first. I for instance takes this input:
'(1
(11 12
(121 122)
13)
2
3
(31
(311
(3111)
)
)
)
and returns
( (3111 121 122 13 11 2)
(311 12)
(31 1)
(3)
)

I am sure there is a clever way to do this in lisp, and maybe it is
even in some classic books, but I did not read those books and I don t
feel so clever on this friday.
So if you know this procedure, please post.

TIA,

[Andrew Beckett]

That's exactly what I thought! I couldn't figure out what the original
list meant, which is probably one step towards understanding what is
required.

Andrew.

On Fri, 08 Oct 2004 19:08:46 +0200, Jim Newton <jimka@rdrop.com>
wrote:

sorry, i do not understand what kind of rule you are using to
order the list? why does 121 come after 3111?

-jim


fogh wrote:
Hi all,

I would like a function that does a bit what a "make" does, listing the
dependencies first. I for instance takes this input:
'(1
(11 12
(121 122)
13)
2
3
(31
(311
(3111)
)
)
)
and returns
( (3111 121 122 13 11 2)
(311 12)
(31 1)
(3)
)

I am sure there is a clever way to do this in lisp, and maybe it is even
in some classic books, but I did not read those books and I don t feel
so clever on this friday.
So if you know this procedure, please post.

TIA,

[Jim Newton]

why do you want 121 122 and 11 in the same sublist of the return
value but 12 in a differnt list in the return value?

sorry but it is still not clear to me what the mapping is
that you are looking for.

-jim

fogh wrote:

The rule is just dependency. Leaves firts. Then leaves + 1 , but the
depth of leaves is not the same.
You can switch 121 and 3111, order doesn t matter inside this list.


'(1
(11 12
(121 122)
13)
2
3
(31
(311
(3111)
)
)
)
and returns
( (3111 121 122 13 11 2)
(311 12)
(31 1)
(3)
)

I am sure there is a clever way to do this in lisp, and maybe it is
even in some classic books, but I did not read those books and I don
t feel so clever on this friday.
So if you know this procedure, please post.

TIA,

[Duncan Barclay]

fogh wrote:

Hi all,

I would like a function that does a bit what a "make" does, listing the
dependencies first. I for instance takes this input:
'(1
(11 12
(121 122)
13)
2
3
(31
(311
(3111)
)
)
)
and returns
( (3111 121 122 13 11 2)
(311 12)
(31 1)
(3)
)

I am sure there is a clever way to do this in lisp, and maybe it is even
in some classic books, but I did not read those books and I don t feel
so clever on this friday.
So if you know this procedure, please post.

What you are looking for is a procedure to traverse a "direct acyclic
graph" or DAG. I would guess it is in most text books, certainly in
Sedgewick's. If you can read TCL, I have some routines that I could
email to you.

Duncan

> TIA,

[fogh]

The first list in the return value is leaves. The second list is one
level above leaves. And so on.

In the input list, 12 has children. It is immediatly followed by the
list of children (121 122). Whereas 11 has no children.
I have used numbers that show what the parent is, but in practice it is
not so. You could have
trunc (leaf1 branch (apple1 apple2 leaf2) leaf3)
And I would expect this return:
(apple1 leaf2 apple2 leaf3 leaf1)
(branch)
(trunc)

Judging from Andrew's reaction and yours, you quite dislike this
reprensentation. It is not important. You can use that one instead:
(trunc leaf1 (branch apple1 apple2 leaf2) leaf3)
Where the parent is the car.
You can use any representation, but I am looking for a list with leaves,
leaves+1, leaves+2, .. until exhaustion.

Jim Newton wrote:

why do you want 121 122 and 11 in the same sublist of the return
value but 12 in a differnt list in the return value?

sorry but it is still not clear to me what the mapping is
that you are looking for.

-jim

fogh wrote:

The rule is just dependency. Leaves firts. Then leaves + 1 , but the
depth of leaves is not the same.
You can switch 121 and 3111, order doesn t matter inside this list.


'(1
(11 12
(121 122)
13)
2
3
(31
(311
(3111)
)
)
)
and returns
( (3111 121 122 13 11 2)
(311 12)
(31 1)
(3)
)

I am sure there is a clever way to do this in lisp, and maybe it is
even in some classic books, but I did not read those books and I don
t feel so clever on this friday.
So if you know this procedure, please post.

TIA,

[Jim Newton]

what are the leaves in the list you give?

I don't understand why you think that
(3111 121 122 13 11 2) are leaves and 12
is not. 12 is at the same depth in the
hierarchy as 11 and 13.

please give me a definition of leaf in your example
and explain why 13 and 11 fit that definition
but 12 does not.

-jim

fogh wrote:

You can use any representation, but I am looking for a list with leaves,
leaves+1, leaves+2, .. until exhaustion.



'(1
(11 12
(121 122)
13)
2
3
(31
(311
(3111)
)
)
)
and returns
( (3111 121 122 13 11 2)
(311 12)
(31 1)
(3)
)

[fogh]

Jim,

12 is directly followed by a list. That list is children. So 12 is not a leaf.

You can change this representation if you dont like it. For instance you can represent it as
(12 121 122)
with the parent being the car , instead of what I put in my example
12 (121 122)

The question is really : how do you enumerate a tree from the leaves up ?
The representation of the tree is up to you. You can use any another representation. You can also assume headers that contain info about depth, number of children, or whatever. As long as the supplementary info can be generated rather easily.

Jim Newton wrote:

what are the leaves in the list you give?

I don't understand why you think that
(3111 121 122 13 11 2) are leaves and 12
is not. 12 is at the same depth in the
hierarchy as 11 and 13.

please give me a definition of leaf in your example
and explain why 13 and 11 fit that definition
but 12 does not.

-jim

fogh wrote:

You can use any representation, but I am looking for a list with
leaves, leaves+1, leaves+2, .. until exhaustion.



'(1
(11 12
(121 122)
13)
2
3
(31
(311
(3111)
)
)
)
and returns
( (3111 121 122 13 11 2)
(311 12)
(31 1)
(3)
)

[fogh]

Duncan Barclay wrote:

fogh wrote:

Hi all,

I would like a function that does a bit what a "make" does, listing
the dependencies first. I for instance takes this input:
'(1
(11 12
(121 122)
13)
2
3
(31
(311
(3111)
)
)
)
and returns
( (3111 121 122 13 11 2)
(311 12)
(31 1)
(3)
)

I am sure there is a clever way to do this in lisp, and maybe it is
even in some classic books, but I did not read those books and I don t
feel so clever on this friday.
So if you know this procedure, please post.


What you are looking for is a procedure to traverse a "direct acyclic
graph" or DAG. I would guess it is in most text books, certainly in
Sedgewick's. If you can read TCL, I have some routines that I could
email to you.

Duncan

Duncan,
TCL is readable enough. Can you post the DAG traversal algorithm here or send me a mail ?

[fogh]

Andrew,

there is no order in
(3111 121 122 13 11 2)
it can be in any other order, all that matters is that they are all leaves. In the example I made, a leaf is an element that is not followed by a opening parenthesis.

If you state the problem like a parallel build, consider that you have the dependency tree and an infinity of hosts available. You want to first submit all the leaves. Not only the deepest.

A stupid way of doing this would be using a "height" property. Just to illustrate:

while(not(all nodes have a height property)
for each node N,
if N is a leaf
set N->height=0
else if all children C have a height property
set N->height=add1(max(C~>height))
else
all nodes have a heigth property = false
endif
endfor
endwhile

And then simply list by height.

Cfor height=0 ; return!=nil ; height++
return=set of nodes with height
end Cfor


Do you know a proper way to do this in lisp ?

Andrew Beckett wrote:

That's exactly what I thought! I couldn't figure out what the original
list meant, which is probably one step towards understanding what is
required.

Andrew.

On Fri, 08 Oct 2004 19:08:46 +0200, Jim Newton <jimka@rdrop.com
wrote:


sorry, i do not understand what kind of rule you are using to
order the list? why does 121 come after 3111?

-jim


fogh wrote:

Hi all,

I would like a function that does a bit what a "make" does, listing the
dependencies first. I for instance takes this input:
'(1
(11 12
(121 122)
13)
2
3
(31
(311
(3111)
)
)
)
and returns
( (3111 121 122 13 11 2)
(311 12)
(31 1)
(3)
)

I am sure there is a clever way to do this in lisp, and maybe it is even
in some classic books, but I did not read those books and I don t feel
so clever on this friday.
So if you know this procedure, please post.

TIA,

[Jean-Marc Bourguet]

fogh <cad_support@skipthisandunderscores.catena.nl> writes:

I would like a function that does a bit what a "make" does, listing
the dependencies first. I for instance takes this input:

'(1
(11 12
(121 122)
13)
2
3
(31
(311
(3111)
)
)
)
and returns
( (3111 121 122 13 11 2)
(311 12)
(31 1)
(3)
)

What make does is a topological sort. You seem to want something more
constrained (linearizing your result give a topological sort). More
or less like a BFS (a BFS would return
((1 2 3)
(11 12 13 31)
(121 122 311)
(3111))
which is different (but still can be linearized to give a topological
sort)

Does this solve your problem? It seems on your test case but I don't
get precisely what are your additional constraints (or maybe they are
just side effect of your choice of example)

(defun merge (l1 l2)
(cond
((eq l1 nil)
l2)
((eq l2 nil)
l1)
(t
(cons (append (car l1) (car l2)) (merge (cdr l1) (cdr l2))))))

(defun depthfirst (l)
(cond
((eq l nil)
nil)
((eq (cdr l) nil)
(list l))
((listp (cadr l))
(merge (append (depthfirst (cadr l)) (list (list (car l))))
(depthfirst (cddr l))))
(t
(merge (list (list (car l)))
(depthfirst (cdr l))))))

Yours,

--
Jean-Marc

[Jim Newton]

do you simply want a bredth first search in bottom up order?
If so, here is some code to do that for you.

;; RECURSIVE FUNCTION
;; bredth first traversal of a list
;; returns a list of pairs of the form ( N elem)
;; where N represents the depth at which the elem was found
(defun bfs ( node @key ( depth 0 ) conc_list)
(when (zerop depth)
conc_list = (list nil))
(cond
((null node)
nil)

((atom node)
(tconc conc_list (list depth node)))

(t
(foreach item node
;; RECURSIVE CALL
(bfs item ?depth ( 1 + depth) ?conc_list conc_list))))

(car conc_list))


;; returns unique elements in reverse order
(defun uniq_list ( l_list)
(let ( uniq )
(foreach x l_list
(unless (member x uniq)
(push x uniq)))
uniq))

;; returns a list of sublists.
;; the lowest level elements are in the first sublist
;; the second lowest level elements at the next sublist
;; ...
;; the highest level elements are in the last sublist
(defun collect_bfs ( node)
(let (( coll (bfs node)))
(foreach mapcar x (uniq_list (mapcar 'car coll))
(mapcar 'cadr (setof sub coll
((car sub) == x))))))


top = '(1
(11 12
(121 122)
13)
2
3
(31
(311
(3111)
)
)
)


(collect_bfs top)

fogh wrote:

Hi all,

I would like a function that does a bit what a "make" does, listing
the dependencies first. I for instance takes this input:
'(1
(11 12
(121 122)
13)
2
3
(31
(311
(3111)
)
)
)
and returns
( (3111 121 122 13 11 2)
(311 12)
(31 1)
(3)
)

--
+------------------------------------------------------------------------+
| Jim E. Newton (jimka@cadence.com) desk +49-(0)89-4563-1918 |
| Methodology Services Europe fax +49-(0)89-4563-1819 |
| Cadence Design Systems GmbH Munich Germany |
| |
| If you won't do it in the rain, you won't do it. |
+------------------------------------------------------------------------+

[fogh]

Jean-Marc Bourguet wrote:

fogh <cad_support@skipthisandunderscores.catena.nl> writes:


I would like a function that does a bit what a "make" does, listing
the dependencies first. I for instance takes this input:

'(1
(11 12
(121 122)
13)
2
3
(31
(311
(3111)
)
)
)
and returns
( (3111 121 122 13 11 2)
(311 12)
(31 1)
(3)
)


What make does is a topological sort. You seem to want something more
constrained (linearizing your result give a topological sort). More
or less like a BFS (a BFS would return
((1 2 3)
(11 12 13 31)
(121 122 311)
(3111))
which is different (but still can be linearized to give a topological
sort)

Does this solve your problem? It seems on your test case but I don't
get precisely what are your additional constraints (or maybe they are
just side effect of your choice of example)

(defun merge (l1 l2)
(cond
((eq l1 nil)
l2)
((eq l2 nil)
l1)
(t
(cons (append (car l1) (car l2)) (merge (cdr l1) (cdr l2))))))

(defun depthfirst (l)
(cond
((eq l nil)
nil)
((eq (cdr l) nil)
(list l))
((listp (cadr l))
(merge (append (depthfirst (cadr l)) (list (list (car l))))
(depthfirst (cddr l))))
(t
(merge (list (list (car l)))
(depthfirst (cdr l))))))

Jean Marc,

Oops. Desole. If that what make is doing, this is not what I meant. Imagine instead what parallel make should do if there was an infinity of build hosts available. It would not keep so many machines idle while one machine is building 3111, it would also submit all the others chunks that do not have a dependency.
So the first parallel step would be to build (3111 121 122 13 11 2).

[fogh]

Jim,
almost, but it is not really the deepest node that I want in the first list. It is all nodes that have no children.

I would like it sorted on a quantity for a node N like
Q(N)=max(depth(children(N)))-depth(N)


Jim Newton wrote:

do you simply want a bredth first search in bottom up order?
If so, here is some code to do that for you.

;; RECURSIVE FUNCTION
;; bredth first traversal of a list
;; returns a list of pairs of the form ( N elem)
;; where N represents the depth at which the elem was found
(defun bfs ( node @key ( depth 0 ) conc_list)
(when (zerop depth)
conc_list = (list nil))
(cond
((null node)
nil)

((atom node)
(tconc conc_list (list depth node)))

(t
(foreach item node
;; RECURSIVE CALL
(bfs item ?depth ( 1 + depth) ?conc_list conc_list))))

(car conc_list))


;; returns unique elements in reverse order
(defun uniq_list ( l_list)
(let ( uniq )
(foreach x l_list
(unless (member x uniq)
(push x uniq)))
uniq))

;; returns a list of sublists.
;; the lowest level elements are in the first sublist
;; the second lowest level elements at the next sublist
;; ...
;; the highest level elements are in the last sublist
(defun collect_bfs ( node)
(let (( coll (bfs node)))
(foreach mapcar x (uniq_list (mapcar 'car coll))
(mapcar 'cadr (setof sub coll
((car sub) == x))))))


top = '(1
(11 12
(121 122)
13)
2
3
(31
(311
(3111)
)
)
)


(collect_bfs top)



fogh wrote:

Hi all,

I would like a function that does a bit what a "make" does, listing
the dependencies first. I for instance takes this input:
'(1
(11 12
(121 122)
13)
2
3
(31
(311
(3111)
)
)
)
and returns
( (3111 121 122 13 11 2)
(311 12)
(31 1)
(3)
)