SKILL q: how do I reorder a tree represented as nested lists intobottom-up ?

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,

 

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

-jim

 

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.

 

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.

 

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

 

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.

 

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

 

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.

 

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

 

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 ?

 

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,

 

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)




--
+------------------------------------------------------------------------+
| Jim E. Newton () 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. |
+------------------------------------------------------------------------+

 

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

 

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)

 

Did you try my function? Its result on your test case is

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

Which looks like what you want exected ordering in the sublists (and
you wrote that it didn't matter).

Yours,

 

Jean-Marc, this solves my problem. I will now better read your function.

What do you mean by "linearising BFS to a topological sort" ? Sorry for the candid question, but I did not study CS. BTW, if you have french or english references that I can use in less than a year of bedtime reading, please send them.

 

A topological sort of a graph is a list of the nodes of the graph in
such an ordrer than no node is before other nodes on which it depends
(this assume a directed graph obviously). If you ignore the structure
of your result

11 121 122 13 2 3111 12 311 1 31 3

that's a topological sort. But ignoring the structure of the other
possible result I gave (reversed in that case)

3111 121 122 311 11 12 13 31 1 2 3

is another. You can still get other sort (for example using a DFS):

11 121 122 12 13 1 2 3111 311 31 3

BFS and DFS are order in which one can traverse a graph (bread first
and depth first).

About any book on algorithm and datastructure which include graph
should be enough for that kind of problems. For example Robert
Sedgewick's one (graph is handled in part 5, the second book, but if
you have no background abording it directly could be hard).

I don't have good reference in French on hand, but if you prefer to
communicate in french, just send me a personal email with a subject
not easily mistaken for spam or it could be dropped silently.

Yours,

 

I don't have time to write the SKILL code at the moment, but here is the
general idea:
1. Create a mapping (array?) to map each element in your hierarchical list
to a unique number, and set all entries to "unused"
2. Create a queue of items to be processed, maybe represented as a list of
these unique numbers
3. Start a new output list for the return elements
4. Add all leaf elements to both the queue and output list by finding
elements in the hierarchical list that have no children, and set the unique
numbers associated with these elements to "used"
5. While the queue is not empty, iterate over all elements in it:
For each element, if all of it's children are "used", then add its
parents to the queue (might require an inverse mapping from element to
parent's unique number), add it to the output list, mark it as "used", and
remove the element from the queue

When the queue is empty your output list will be complete and in reverse
hierarchical order (leaves first, root last).
It seems complex but I think you need all of the steps for an efficient and
correct implementation.

Frank

list. It is all nodes that have no children.

 

Thanks Gen,

This solution has the advantage of being intuitive. I though of a
simplified version of it, first copy the tree, then list the leaves of
the copy, then delete those leaves, and iterate until the copied tree is
has become nil. I don t know if this is the most efficient algorithm,
but it looks like some things I found when doing A google on topological
sort and depth-first-sort.
I can now kinda-understand the recursive solution posted by Jean Marc
Bourguet (that is: I understand how it works but not how to write such.)
, but I did not try to evaluate its complexity. It is not too important
for my particular application at this moment even if it has O(n**2) growth.

 

I think it would be linear in the number of node if I didn't use
append. Replace the use of append by tconc (but tconc can't be
substitued for append without modifications) and that should do the
trick.

Your,