CADForums.net

fogh · Guest

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

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:

fogh · Guest

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:

Andrew Beckett · Guest

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:

Jim Newton · Guest

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:

Duncan Barclay · Guest

fogh wrote:

fogh · Guest

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:

Jim Newton · Guest

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:

fogh · Guest

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:

fogh · Guest

Duncan Barclay wrote:

fogh · Guest

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:

Jean-Marc Bourguet · Guest

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

Jim Newton · Guest

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

Jean-Marc Bourguet wrote:

fogh · Guest

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:

	CADForums.net Forum Index -> Cadence	All times are GMT Goto page 1, 2 Next
Page 1 of 2