| Author |
Message |
Jean-Marc Bourguet
Guest
|
 Posted:
Tue Oct 12, 2004 3:16 pm Post subject:
Re: SKILL q: how do I reorder a tree represented as nested l |
|
|
fogh <cad_support@skipthisandunderscores.catena.nl> writes:
| Quote: | 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))))))
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).
|
Did you try my function? Its result on your test case is
| Quote: | (depthfirst '(1 (11 12 (121 122) 13) 2 3 (31 (311 (3111)))))
((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
|
|
| Back to top |
|
 |
fogh
Guest
|
| Posted:
Tue Oct 12, 2004 8:42 pm Post subject:
TADA: the answer (Re: SKILL q: how do I reorder a tree repre |
|
|
Jean-Marc Bourguet wrote:
| Quote: | fogh <cad_support@skipthisandunderscores.catena.nl> writes:
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))))))
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).
Did you try my function? Its result on your test case is
(depthfirst '(1 (11 12 (121 122) 13) 2 3 (31 (311 (3111)))))
((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).
|
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. |
|
| Back to top |
|
|
Jean-Marc Bourguet
Guest
|
| Posted:
Wed Oct 13, 2004 10:40 am Post subject:
Re: TADA: the answer (Re: SKILL q: how do I reorder a tree r |
|
|
fogh <cad_support@skipthisandunderscores.catena.nl> writes:
| Quote: |
Jean-Marc, this solves my problem. I will now better read your
function. What do you mean by "linearising BFS to a topological
sort" ?
|
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).
| Quote: | 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.
|
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,
--
Jean-Marc
|
|
| Back to top |
|
|
gennari
Guest
|
| Posted:
Sat Oct 16, 2004 12:40 am Post subject:
Re: SKILL q: how do I reorder a tree represented as nested l |
|
|
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...
| Quote: | 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)
)
|
|
|
| Back to top |
|
|
fogh
Guest
|
| Posted:
Sun Oct 17, 2004 8:18 pm Post subject:
Re: SKILL q: how do I reorder a tree represented as nested l |
|
|
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.
gennari wrote:
| Quote: | 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)
) |
|
|
| Back to top |
|
|
Jean-Marc Bourguet
Guest
|
| Posted:
Mon Oct 18, 2004 11:43 am Post subject:
Re: SKILL q: how do I reorder a tree represented as nested l |
|
|
fogh <adff_at@xs4all_dot.nl> writes:
| Quote: | 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,
--
Jean-Marc |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in