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

[gennari]

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

"fogh" <cad_support@skipthisandunderscores.catena.nl> wrote in message
news:416ad23d$0$135$e4fe514c@dreader19.news.xs4all.nl...

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