Hello,
I am trying to traverse the list (A (B (D E) C)) in a way that the
print output should be in the following order D, E, B, C, A aka depth
first traversal.
So far, I have come up with this code but it seems to have some
strange problem.
[code](setq start (list 'a (list 'b (list 'd 'e) 'c )))
====> gives ====> (A (B (D E) C))
(defun depth-first (start)
(cond
((null start) 0)
((listp (first start)) (setq start (first start))
(depth-first (first start)))
((not (eq nil (car start))) (print (car start))
(setq start (rest start))
(depth-first (start)))
(t "Go home")))[/code]
Can someone please help me out.
(defun depth-first (arg)
(cond
; when list is empty rekursion will end
((not arg)
())
; first case: 1th element is a list
; example: ((b (d e) c))
; result from rekursion will be ()
((listp (first arg))
(append (depth-first (first arg)) (depth-first (rest arg))))
; second case: 1th element is an element
; example: (a (b (d e) c))
; result from rekursion: (d e b c)
(t
(append (depth-first (rest arg)) (list (first arg))))))
hi this is not a final solution to your problem but it might give you
a few pointers on how to to do it.
it should return a list with the elements ordered by depth i.e. (a (b
(d e) c)) will return (e d c b a)
don't know if it is usefull for you
Oh what the hell...
(defun myblah (x)
(if (null x) nil
(append
(myblah
(reduce #'append
(remove-if-not #'listp x)
:initial-value nil))
(remove-if-not #'atom x))))
This isn't an implementation of the algorithm I showed above, but this
feels nicer anyway.
It does the example asked for, but I'd welcome bug fixes.
Ali wrote:
> Oh what the hell...
>
> (defun myblah (x)
> (if (null x) nil
> (append
> (myblah
> (reduce #'append
> (remove-if-not #'listp x)
> :initial-value nil))
> (remove-if-not #'atom x))))
>
> This isn't an implementation of the algorithm I showed above, but this
> feels nicer anyway.
> It does the example asked for, but I'd welcome bug fixes.
What if the bug is you? Can we fix that? You did what the OP asked,
which was completely daft. So you failed to realize they had no clue
what is depth-first, and this happened because you pulled a c.l.l
classic, you obediently did what someone clueless specified.
hth, kenny
ps. Now stop trying to give them what they asked for. k
On Sep 11, 4:49 am, Kenny <·········@gmail.com> wrote:
> Ali wrote:
> > Oh what the hell...
>
> > (defun myblah (x)
> > (if (null x) nil
> > (append
> > (myblah
> > (reduce #'append
> > (remove-if-not #'listp x)
> > :initial-value nil))
> > (remove-if-not #'atom x))))
>
> > This isn't an implementation of the algorithm I showed above, but this
> > feels nicer anyway.
> > It does the example asked for, but I'd welcome bug fixes.
>
> What if the bug is you? Can we fix that? You did what the OP asked,
> which was completely daft. So you failed to realize they had no clue
> what is depth-first, and this happened because you pulled a c.l.l
> classic, you obediently did what someone clueless specified.
>
> hth, kenny
>
> ps. Now stop trying to give them what they asked for. k
Originally I was obediently _not_ doing someone else's homework. After
the first 2 solutions came, I felt that the obedience not to do his
homework was now irrelevant, since it was already done. Then I started
trying to see how I would do it, embarrassed that all I could think of
was a crappy algorithm. Having found a solution, I liked it for its
simplicity and hoped that it would help persuade "crashoverride111" to
get a new email address.
If Pascal and tkrumh had not already posted the solution, I assure
you, I would not have even found one to post.
In fact, I have no clue what depth-first is, I'll go and look that up
now.
> ps. Now stop trying to give them what they asked for. k
Excellent philosophy.
>>ps. Now stop trying to give them what they asked for. k
>
>
> Originally I was obediently _not_ doing someone else's homework.
No, I meant they must have the spec wrong cuz that is not "depth first".
I was not worried aboot homeworkness, I was concerned about the usual
c.l.l slavish, well, following in the footsteps of those who begin by
saying they are lost.
k
On Sep 11, 4:03 pm, Kenny <·········@gmail.com> wrote:
> >>ps. Now stop trying to give them what they asked for. k
>
> > Originally I was obediently _not_ doing someone else's homework.
>
> No, I meant they must have the spec wrong cuz that is not "depth first".
> I was not worried aboot homeworkness, I was concerned about the usual
> c.l.l slavish, well, following in the footsteps of those who begin by
> saying they are lost.
>
> k
So what you really mean is that I've provided a confused and incorrect
breadth-first function. neat.
On Sep 11, 4:46 pm, Ali <·············@gmail.com> wrote:
> So what you really mean is that I've provided a confused and incorrect
> breadth-first function. neat.
(defun breadth-first (x)
(if (null x) nil
(join (atoms-only x) (breadth-first (join-lists (lists-only
x))))))
Well here's my bug-fixed breadth-first then FWIW.
On Sep 11, 11:03 am, Kenny <·········@gmail.com> wrote:
> >>ps. Now stop trying to give them what they asked for. k
>
> > Originally I was obediently _not_ doing someone else's homework.
>
> No, I meant they must have the spec wrong cuz that is not "depth first".
> I was not worried aboot homeworkness, I was concerned about the usual
> c.l.l slavish, well, following in the footsteps of those who begin by
> saying they are lost.
>
> k
Kenny, apart from trying to be hypocritical about "helping the lost",
I could not see any point helpful in anyways to my OP. Not that I
dislike to work, and was asking a completely spoon fed solution, I
gave my code whatever I could write after two days of getting familiar
with LISP. You could very well call me lost, but I would disagree.
I don't see much point for this forum if people (like you) stop
helping out others (includes those who are lost for a reason) and
calling others "daft" and acting two-faced. Who do you think ask for
help?
- People who try working out what the problem is and then ask for help
(including students, professionals).
- People who don't try working out what the problem is and ask for
help straightaway (could also include students, professionals).
I can hardly think of anyone who is not a student or working
professionally, wants to learn LISP out of the blue and would come
here and ask for help. Now if you don't want to help students, what's
the "logical" reason to help professionals? If you want me to believe
that apart from professionals and students, there are enough LISP
lovers who would keep this forum alive, it's time to wake up.
Going by your two times off-topic reply, unlike all the others who
helped me suggesting problems with my own ways of interpreting tree
lists etc, I would expect you to keep your brilliant philosophies with
you and not to spread them in anyway.
Carla wrote:
> On Sep 11, 11:03 am, Kenny <·········@gmail.com> wrote:
>
>>>>ps. Now stop trying to give them what they asked for. k
>>
>>>Originally I was obediently _not_ doing someone else's homework.
>>
>>No, I meant they must have the spec wrong cuz that is not "depth first".
>>I was not worried aboot homeworkness, I was concerned about the usual
>>c.l.l slavish, well, following in the footsteps of those who begin by
>>saying they are lost.
>>
>>k
>
>
> Kenny, apart from trying to be hypocritical about "helping the lost",
> I could not see any point helpful in anyways to my OP. Not that I
> dislike to work, and was asking a completely spoon fed solution, I
> gave my code whatever I could write after two days of getting familiar
> with LISP. You could very well call me lost, but I would disagree.
>
> I don't see much point for this forum if people (like you) stop
> helping out others (includes those who are lost for a reason) and
> calling others "daft" and acting overly "hypocritical". Who do you
> think ask for help?
> - People can try working out what the problem is and then ask for help
> (including students, professionals).
> - People who don't try working out what the problem is and ask for
> help straightaway (could also include students, professionals).
>
> I can hardly think of anyone who is not a student or working
> professionally, wants to learn LISP out of the blue and would come
> here and ask for help. Now if you don't want to help students, what's
> the "logical" reason to help professionals? If you want me to believe
> that apart from professionals and students, there are enough LISP
> lovers who would keep this forum alive, it's time to wake up.
>
Jeez, you love the sound of your own voice, don't you.
Anyway, you are a complete ass. I have given more better help to noobs
than anyone on this NG.
You are so clueless you do not even realize I was trying to help you by
saving you from those who would help you by helping you do what you were
trying to do when you should not be.
Generally once I get involved the noob finally figures out they
misunderstood their problem entirely and we begin to solve their problem
while the other clowns on this NG start fighting over whose solution to
the wrong problem was better.
> Going by your two times off-topic reply, unlike all the others who
> helped me suggesting problems with my own ways of interpreting tree
> lists etc, I would expect you not to keep your brilliant philosophies
> with you and not to spread them in anyway.
I feel a naggum coming on, one having to do with what an ignorant dolt
like you expects, but you butchered the English language so badly in
that last sentence that the moment passed.
Where do I send the T-shirt?
kt
················@gmail.com wrote:
> Hello,
> I am trying to traverse the list (A (B (D E) C)) in a way that the
> print output should be in the following order D, E, B, C, A aka depth
> first traversal.
>
> So far, I have come up with this code but it seems to have some
> strange problem.
Well, what strange problem exactly? And why do you think it's strange?
> [code](setq start (list 'a (list 'b (list 'd 'e) 'c )))
You know you can write (setq start '(a b (d e) c)), right? Strictly
speaking a SETQ at top level has undefined behavior, you should declare
start as a global variable first (with DEFVAR, for example), but that's
not something you should be concerned about for now.
> (defun depth-first (start)
> (cond
> ((null start) 0)
> ((listp (first start)) (setq start (first start))
> (depth-first (first start)))
> ((not (eq nil (car start))) (print (car start))
> (setq start (rest start))
> (depth-first (start)))
> (t "Go home")))
While waiting to hear from you if this is homework or not, I'll point
out a few initial things:
1. Why are you returning a number (0) in some cases, and a string ("Go
home") in others, when all you want from your function is the side
effect of printing the elements out?
2. (eq nil something) is true if something is NIL. Therefore (not (eq
nil something)) will be NIL if something is NIL, and true otherwise. So
why not use just something by itself? In Lisp, everything that is not
NIL is considered true.
3. The second recursive call to DEPTH-FIRST has as its argument (start),
that looks like a function call, but there's no function called start...
Alberto
To answer the most important question, yes it is my homework question
and it entails developing a full blown depth first search algorithm
for such alphabetical binary trees. The reason I am struggling with
Lisp is that I have never worked on Lisp nor seen its coding style.
I have modified my code to accommodate the changes you suggested, but
still it only prints A and before printing B, pops an error "*** -
FIRST: B is not a list
" and breaks out.
(defun depth-first (start)
(cond
((listp (first start)) (setq start (first start))
(depth-first
(first start)))
((not (eq nil (car start))) (print (car start))
(setq start (rest start))
(depth-first (start)))
(t "End of List")))
The third point was totally silly mistake as I didn't realize leaving
start within (). I have corrected that.
I am not asking anyone to post the corrected code but if you can post
these kinda questions, I can work it out. It is the first program in
Lisp, I am learning.
> (A (B (D E) C))
1: ((B (D E) C) A)
2: (((D E) B C) A)
3: (D E B C A)
Above is probably an inefficient way to do it, but should work,
provided you merge any two lists which appear on the same level.
Again, probably inefficient, but I'm not gonna do your homework too
carefully!
Really I just posted to say you should get yourself a decent email
address. It would definitely not be cool even if you were just
crashoverride. Being a runner-up for crashoverride is just lame and
won't get you any respect.
················@gmail.com writes:
> To answer the most important question, yes it is my homework question
> and it entails developing a full blown depth first search algorithm
> for such alphabetical binary trees. The reason I am struggling with
> Lisp is that I have never worked on Lisp nor seen its coding style.
What should happen for a tree such as:
(a (b (c d) e) (f (g (h i) j) k) l)
Should "c d" be written before "h i"?
h and i are at a deeper depth, so in a depth first, shouldn't they go first?
(defstruct node label depth)
(defun collect-depths (tree depth)
(mapcan (lambda (child)
(if (atom child)
(list (make-node :label child :depth depth))
(collect-depths child (1+ depth))))
tree))
(let ((tree '(a (b (c d) e) (f (g (h i) j) k) l)))
(collect-depths tree 1))
(defun deepest-first (tree)
(mapcar (function node-label)
(stable-sort (collect-depths tree 1)
(function >)
:key (function node-depth))))
(let ((tree '(a (b (c d) e) (f (g (h i) j) k) l)))
(format t "~{~A~^ ~}~%" (deepest-first tree)))
--
__Pascal Bourguignon__ http://www.informatimago.com/
Nobody can fix the economy. Nobody can be trusted with their finger
on the button. Nobody's perfect. VOTE FOR NOBODY.
Nopes, we start with the first node on the left and prints out the
deepest node within all the child nodes from the leftmost node. after
we cover all of the leaf nodes for leftmost node according to their
respective depths, we then move to the adjacent node and so on.
················@gmail.com writes:
> Nopes, we start with the first node on the left and prints out the
> deepest node within all the child nodes from the leftmost node. after
> we cover all of the leaf nodes for leftmost node according to their
> respective depths, we then move to the adjacent node and so on.
Then it has nothing to do with depth first walk.
It's a kind of suffix walk, where we consider that all leaves
constitute the label of the node.
(defun strange-suffix-walk (tree action)
(loop
:with leaves = '()
:for child :in tree
:do (if (atom child)
(push child leaves)
(strange-suffix-walk child action))
:finally (loop
:for leaf :in (reverse leaves)
:do (funcall action leaf))))
(dolist (tree '( (a (b (c d) e) (f (g (h i) j) k) l)
(A (B (D E) C)) ) (values))
(prin1 tree) (princ " -> ")
(strange-suffix-walk tree (lambda (x) (prin1 x) (princ " ")))
(terpri))
(A (B (C D) E) (F (G (H I) J) K) L) -> C D B E H I G J F K A L
(A (B (D E) C)) -> D E B C A
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
On Sep 11, 1:56 am, ····@informatimago.com (Pascal J. Bourguignon)
wrote:
> ················@gmail.com writes:
> > Nopes, we start with the first node on the left and prints out the
> > deepest node within all the child nodes from the leftmost node. after
> > we cover all of the leaf nodes for leftmost node according to their
> > respective depths, we then move to the adjacent node and so on.
>
> Then it has nothing to do with depth first walk.
>
> It's a kind of suffix walk, where we consider that all leaves
> constitute the label of the node.
>
> (defun strange-suffix-walk (tree action)
> (loop
I don't think that loop is necessary.
> :with leaves = '()
> :for child :in tree
> :do (if (atom child)
> (push child leaves)
> (strange-suffix-walk child action))
> :finally (loop
> :for leaf :in (reverse leaves)
> :do (funcall action leaf))))
>
> (dolist (tree '( (a (b (c d) e) (f (g (h i) j) k) l)
> (A (B (D E) C)) ) (values))
> (prin1 tree) (princ " -> ")
> (strange-suffix-walk tree (lambda (x) (prin1 x) (princ " ")))
> (terpri))
>
> (A (B (C D) E) (F (G (H I) J) K) L) -> C D B E H I G J F K A L
> (A (B (D E) C)) -> D E B C A
Ruby:
# Convert string to array. Example: "(A (B (D E) C))"
# becomes [:A, [:B, [:D, :E], :C]]
def rubify str
eval str.strip.gsub(/\( */,"[").gsub(/ *\)/,"]").
gsub(/ +/,",").upcase.gsub(/[A-Z]+/, ':\&')
end
def strange_suffix_walk tree, action
leaves = []
tree.each{ |child|
if child.class == Array
strange_suffix_walk child, action
else
leaves << child
end
}
leaves.each{ |leaf| action[ leaf ] }
end
## Test it.
[ "(A (B (D E) C))",
"(A (B (C D) E) (F (G (H I) J) K) L)"
].each{|s|
print "#{ s } -> "
strange_suffix_walk rubify( s ), proc{|x| print "#{x} " }
puts
}
--- output ---
(A (B (D E) C)) -> D E B C A
(A (B (C D) E) (F (G (H I) J) K) L) -> C D B E H I G J F K A L
--
57. Whether he whose luxury consumeth foreign products, and whose
industry produceth nothing domestic to exchange for them, is not
so far forth injurious to his country?
--- George Berkeley, _The Querist_, 1737
William James <·········@yahoo.com> writes:
> Ruby:
If you want to keep writing Ruby in cll, at least you could have the
decency of not doing it filthly.
With some nice parentheses, ruby becomes almost usable:
(def rubify(str)
(eval str.strip.gsub(/\( */,"[").gsub(/ *\)/,"]").gsub(/ +/,",").upcase.gsub(/[A-Z]+/, ':\&'))
end)
(def strange_suffix_walk(tree,action)
(leaves = [])
(tree.each { |child|
(if (child.class == Array)
(strange_suffix_walk(child,action))
else
(leaves << child)
end)})
(leaves.each { |leaf| action[leaf] })
end)
([ "(A (B (D E) C))",
"(A (B (C D) E) (F (G (H I) J) K) L)"].each {|s|
(print "#{ s } -> ")
(strange_suffix_walk((rubify(s)),(proc{|x| (print "#{x} ")})))
(puts)})
(A (B (D E) C)) -> D E B C A
(A (B (C D) E) (F (G (H I) J) K) L) -> C D B E H I G J F K A L
["(A (B (D E) C))", "(A (B (C D) E) (F (G (H I) J) K) L)"]
--
__Pascal Bourguignon__
On Sep 12, 6:51 am, ····@informatimago.com (Pascal J. Bourguignon)
wrote:
> William James <·········@yahoo.com> writes:
> > Ruby:
>
> If you want to keep writing Ruby in cll,
I don't want to, but I feel that it is important
to make the superiority of COMOL-LISP glaringly
evident to all window-shoppers who read this group.
This will be done simply by showing that Ruby code
is always more prolix, more convoluted, less elegant,
and less readable to a normal human than CLISP code.
Admittedly, my attempts so far have been rather
unsuccessful. I hope to improve with practice.
--
Government is not reason, it is not eloquence; it is force; like
fire, a troublesome servant and a fearful master. Never for a
moment should it be left to irresponsible action.
--- George Washington, speech of January 7, 1790
William James schrieb:
> On Sep 12, 6:51 am, ····@informatimago.com (Pascal J. Bourguignon)
> wrote:
>> William James <·········@yahoo.com> writes:
>>> Ruby:
>> If you want to keep writing Ruby in cll,
>
> I don't want to, but I feel that it is important
> to make the superiority of COMOL-LISP glaringly
> evident to all window-shoppers who read this group.
>
> This will be done simply by showing that Ruby code
> is always more prolix, more convoluted, less elegant,
> and less readable to a normal human than CLISP code.
>
> Admittedly, my attempts so far have been rather
> unsuccessful. I hope to improve with practice.
To be successful you should show algorithms to solve the problem
which can�t be expressed with the same ease in Lisp.
In all of your examples you only made use of facilities which Ruby
got from Lisp (like loops, blocks, injects, ...). Of course this can
not impress anyone here, because all this stuff already is in Lisp.
A Haskell fan can at least bring in implicit currying and pattern
matching. This can of course also be done in Lisp, but at least such
attempts make much more sense, because these techniques can indeed
reduce program complexity.
By saving three keystrokes with Rubys map vs Lisps mapcar no piece
of software becomes easier to understand (nor can it be written faster
in any meaningful way).
As long you show only some functions calls, a bit imperative style here
some funky functional style there you won�t be able to beat Lisp, as it
can be done the same way. Bring in abstractions. Look at Haskell or
Prolog or Mercury. They offer abstractions which are not always so
very easy to implement in Lisp.
Andr�
--
On Sep 10, 7:25 pm, ····@informatimago.com (Pascal J. Bourguignon)
wrote:
> ················@gmail.com writes:
> > To answer the most important question, yes it is my homework question
> > and it entails developing a full blown depth first search algorithm
> > for such alphabetical binary trees. The reason I am struggling with
> > Lisp is that I have never worked on Lisp nor seen its coding style.
>
> What should happen for a tree such as:
>
> (a (b (c d) e) (f (g (h i) j) k) l)
>
> Should "c d" be written before "h i"?
> h and i are at a deeper depth, so in a depth first, shouldn't they go first?
>
> (defstruct node label depth)
>
> (defun collect-depths (tree depth)
> (mapcan (lambda (child)
> (if (atom child)
> (list (make-node :label child :depth depth))
> (collect-depths child (1+ depth))))
> tree))
>
> (let ((tree '(a (b (c d) e) (f (g (h i) j) k) l)))
> (collect-depths tree 1))
>
> (defun deepest-first (tree)
> (mapcar (function node-label)
> (stable-sort (collect-depths tree 1)
I don't think that sorting is necessary.
> (function >)
> :key (function node-depth))))
>
> (let ((tree '(a (b (c d) e) (f (g (h i) j) k) l)))
> (format t "~{~A~^ ~}~%" (deepest-first tree)))
Ruby:
def _depth_first list, accum, depth
list.each{|x|
if x.class == Array
accum << [] if accum.size < depth + 2
_depth_first x, accum, depth + 1
else
accum[depth] << x
end
}
end
def depth_first list
result = [[]]
_depth_first list, result, 0
result.reverse.flatten
end
p depth_first [:a,[:b,[:c,:d],:e],[:f,[:g,[:h,:i],:j],:k],:l]
--- output ---
[:h, :i, :c, :d, :g, :j, :b, :e, :f, :k, :a, :l]
--
Let the tutor make his charge pass everything through a seive and
lodge
nothing in his head on mere authority and trust.
--- Montaigne
??>> To answer the most important question, yes it is my homework question
??>> and it entails developing a full blown depth first search algorithm
??>> for such alphabetical binary trees. The reason I am struggling with
??>> Lisp is that I have never worked on Lisp nor seen its coding style.
PJB> What should happen for a tree such as:
PJB> (a (b (c d) e) (f (g (h i) j) k) l)
PJB> Should "c d" be written before "h i"?
PJB> h and i are at a deeper depth, so in a depth first, shouldn't they go
PJB> first?
are you trying to confuse him? DFS is a pretty concrete thing:
http://en.wikipedia.org/wiki/Depth-first_search
"Alex Mizrahi" <········@users.sourceforge.net> writes:
> ??>> To answer the most important question, yes it is my homework question
> ??>> and it entails developing a full blown depth first search algorithm
> ??>> for such alphabetical binary trees. The reason I am struggling with
> ??>> Lisp is that I have never worked on Lisp nor seen its coding style.
>
> PJB> What should happen for a tree such as:
>
> PJB> (a (b (c d) e) (f (g (h i) j) k) l)
>
> PJB> Should "c d" be written before "h i"?
> PJB> h and i are at a deeper depth, so in a depth first, shouldn't they go
> PJB> first?
>
> are you trying to confuse him? DFS is a pretty concrete thing:
>
> http://en.wikipedia.org/wiki/Depth-first_search
The confusion is between a "search" and a "walk".
Notice that in a depth-first-search, the node a would be "searched" first.
Here we are asked to walk the tree, and ordering the leaves according
to their depth. This is different than a depth-first-search.
This is not a prefix, an infix, nor a suffix walk either. It's quite
specific a kind of walk.
--
__Pascal Bourguignon__
It looks like I represented the binary tree incorrectly in the list-
form. It is a simple binary tree with
A
B C
D E
Shouldn't we be representing this as (A (B (D E) C))?
Also, I have modified the code suggested by ········@gmx
==========================================================
(setq start '(a (b (d e) c) ))
(defun depth-first (list-arg leaf-arg)
(cond
; when list is empty recursion will end
((not list-arg)
())
; first case: 1th element is a list
((listp (first list-arg))
(append (depth-first (first list-arg) leaf-arg) (depth-
first (rest list-arg) leaf-arg)))
; second case: 1th element is an element
(t
(when (eq (first list-arg) leaf-arg) "Found"
(append (depth-first (rest list-arg) leaf-arg)
(list (first list-arg)))))))
==========================================================
Say, we give
(depth-first start 'a)
It'll return (a)
Say, we give
(depth-first start 'f)
It'll return nil
Still the question remains did I incorrectly represented the binary
tree, because if I did, I need to modify this depth-first search again
to suit the corrected list-form.
On Sep 11, 6:59 am, ················@gmail.com wrote:
> It looks like I represented the binary tree incorrectly in the list-
> form. It is a simple binary tree with
>
> A
> B C
> D E
>
> Shouldn't we be representing this as (A (B (D E) C))?
Or another form could be (A (B (D) (E)) C)? I am trying to modify the
above code for this form too.
On 11 Sep., 13:35, ················@gmail.com wrote:
> On Sep 11, 6:59 am, ················@gmail.com wrote:
>
> > It looks like I represented the binary tree incorrectly in the list-
> > form. It is a simple binary tree with
>
> > A
> > B C
> > D E
>
> > Shouldn't we be representing this as (A (B (D E) C))?
>
> Or another form could be (A (B (D) (E)) C)? I am trying to modify the
> above code for this form to
I dont think you have the correct representation of a tree in list. in
my opinion it should look something like this:
(root (lefttree) (rigthtree))
so your tree in a list representation would be:
> > A
> > B C
> > D E
(a (b (d) (e)) (c))
now lets say you want to ad an F as the left child of C
> > A
> > B C
> > D E F
your list representation would change to:
(a (b (d) (e)) (c (f)))
with the general representation:
(rootnode (sublist containing the left child tree) (sublist containg
the right child tree))
another simple example would be
A
B C
(A (B) (C))
i hope this helps
Carla wrote:
> For a tree-list (a (b d e) c), this code is working
...
> But as I said earlier, given my zero familiarity about Lisp structure
> until this Monday - I still find (a (b (d) (e)) (c)) more concise.
The first representation is more concise but not quite right:
it can't represent a null tree. The second one is correct and
can be easily generalized to an N-ary tree, where (car list)
is a node's value, (cdr list) its children.
A na�ve implementation for what you want is something like this:
(defun foo (tree)
(if tree
(append (reduce #'append (mapcar #'foo (cdr tree)))
(list (car tree)))
()))
(foo '(a (b (c) (d) (e)) (f) (g (h))) => (C D E B F H G A)
But this has at least O(N^2) complexity. You should be able
to do better! [BTW, the example tree is not a binary tree.]
·········@gmx.de writes:
> I dont think you have the correct representation of a tree in list.
> [...]
Obviously not, but neither do you. The point here is that there is no
"THE" correct representation. There are an infinity of
representations of (an infinity of variety of) trees using lists.
What should be done first is to define the functionnal abstraction
used to access and manipulate the tree.
Have a look at:
http://groups.google.com/group/comp.lang.lisp/msg/b8d9376744b4ebb1
http://groups.google.com/group/comp.lang.lisp/msg/0c66e597e08be90d
--
__Pascal Bourguignon__
C> ========================================================================
C> (setq start '(a (b d e) c))
C> (defun depth-first (list-arg leaf-arg)
C> (cond
C> ; when list is empty recursion will end
C> ((not list-arg)
C> ())
C> ; first case: 1th element is a list
C> ((listp (first list-arg))
C> (append (depth-first (first list-arg) leaf-arg) (depth-
C> first (rest list-arg) leaf-arg)))
C> ; second case: 1th element is an element
C> (t
C> (when (eq (first list-arg) leaf-arg) "Found"
this condition make it recursing only for leaf-arg
C> (append (depth-first (rest list-arg) leaf-arg)
C> (list (first list-arg)))))))
so output of (depth-first start 'a) is (A).
other than that, it sort of works, but there is easier way to do.
first case works on half-processed list, like ((b d e) c) -- i'd
say it's not very elegant, it's better to do processing at once rather than
leave it for
next recursion iteration.
actually there are just two cases -- when arg is list, and when it's not.
if it is a list, you should fully process it. if it's not a list -- just
return it.
something like that:
(defun depth-first (node)
(cond
;; rare case -- empty tree
((null node) ())
;; node is list -- has children
((listp node)
(append
;; recurse into children appending results in order
(depth-first (second node)) ; recurse left subtree
(depth-first (third node)) ; recurse rigth subtree
(list (first node)))) ; add node's sign itself
;; node is symbol -- return it listified
(t (list node))))
??>> It looks like I represented the binary tree incorrectly in the list-
??>> form. It is a simple binary tree with
??>>
??>> A
??>> B C
??>> D E
??>>
??>> Shouldn't we be representing this as (A (B (D E) C))?
i can't see how it could. you have B, (D E) and C in one list.
here B and C are childs of A, but (D E) is not -- it's child of B.
how is that?
c> Or another form could be (A (B (D) (E)) C)? I am trying to modify the
c> above code for this form too.
this makes more sense, but if you mark leaf nodes as singleton lists, this
should be:
(A (B (D) (E)) (C))
if we agree on form of list, now please write your algorithm in plain
english.
what cases do we see here? i see two cases -- one when node has childs, and
one when it has not.
so probably your recursion has two branches.
as for coding, i'll suggest you one thing:
for case when node has children, we might want to decode list into three
elements -- node name,
left child and right child.
to make code less weird, you might want to do it with LET:
(if (node-has-children node)
(let ((node-name (first node))
(left-child (second node))
(right-child (third node)))
;;within the let we can refer to this things by name, i.e.:
(print "node-name:") (print node-name)
(print "left-child:") (print left-child)
(print "right-child:") (print right-child)))
now you need to insert proper check in place of node-has-children, and
implement
your algorithm in terms of node-name, left-child and right-child. once
you've done
with algorithm -- you see it works -- you can remove LET and insert (first
node) etc into
the code directly.
??>> It looks like I represented the binary tree incorrectly in the list-
??>> form. It is a simple binary tree with
??>>
??>> A
??>> B C
??>> D E
??>>
??>> Shouldn't we be representing this as (A (B (D E) C))?
c> Or another form could be (A (B (D) (E)) C)? I am trying to modify the
c> above code for this form too.
alternatively you can represent leaf nodes with just symbols, then
representation will be
(A (B D E) C)
??>> are you trying to confuse him? DFS is a pretty concrete thing:
??>>
??>> http://en.wikipedia.org/wiki/Depth-first_search
PJB> The confusion is between a "search" and a "walk".
what is "walk" and how is it different from normal dfs traversal?
PJB> Notice that in a depth-first-search, the node a would be "searched"
PJB> first.
check the link i gave, there are preordering, postordering and reverse
postordering (later makes sense only for a DAG).
i guess what he needs is postordering, he just messed list representation.
PJB> Here we are asked to walk the tree, and ordering the leaves according
PJB> to their depth. This is different than a depth-first-search.
no, he did not. you've just mis-interpreted his messy description of
depth-first algorithm.
PJB> This is not a prefix, an infix, nor a suffix walk either. It's quite
PJB> specific a kind of walk.
if it is that specific, he won't call it "depth-first", right? note that
"depth first traversal" probably comes from task description itself -- that
is,
authoriative source, while algorithm description comes from his
understanding --
that is, not so authoriative. if he knew how it works he won't ask, would
he?
First, it's not a "he" - rather a "she". Thought I would share this
bit. :)
Alex, I find (A (B (D) (E)) (C)) this to be more comfortable for me to
understand the tree structure.
Everyone else, I am working on an algorithm right now to incorporate
this representation into a depth-first-search code. Once I'll have
something concrete to post, in about 20 minutes - I'll post it here.
On Thu, 11 Sep 2008 15:10:47 +0300, "Alex Mizrahi"
<········@users.sourceforge.net> wrote:
> ??>> are you trying to confuse him? DFS is a pretty concrete thing:
> ??>>
> ??>> http://en.wikipedia.org/wiki/Depth-first_search
>
> PJB> The confusion is between a "search" and a "walk".
>
>what is "walk" and how is it different from normal dfs traversal?
A walk touches every node of the tree, a search partitions the tree to
avoid touching every node.
> PJB> Notice that in a depth-first-search, the node a would be "searched"
> PJB> first.
>
>check the link i gave, there are preordering, postordering and reverse
>postordering (later makes sense only for a DAG).
>i guess what he needs is postordering, he just messed list representation.
Yes, the OP's belated explanation appears to match post-ordering.
> PJB> Here we are asked to walk the tree, and ordering the leaves according
> PJB> to their depth. This is different than a depth-first-search.
>
>no, he did not. you've just mis-interpreted his messy description of
>depth-first algorithm.
But the OP still wants a walk rather than a search.
George
From: Kaz Kylheku
Subject: Re: Depth First Search traversal of this list
Date:
Message-ID: <20080911161556.424@gmail.com>
On 2008-09-11, George Neuner <········@comcast.net> wrote:
> On Thu, 11 Sep 2008 15:10:47 +0300, "Alex Mizrahi"
><········@users.sourceforge.net> wrote:
>
>> ??>> are you trying to confuse him? DFS is a pretty concrete thing:
>> ??>>
>> ??>> http://en.wikipedia.org/wiki/Depth-first_search
>>
>> PJB> The confusion is between a "search" and a "walk".
>>
>>what is "walk" and how is it different from normal dfs traversal?
>
> A walk touches every node of the tree, a search partitions the tree to
> avoid touching every node.
Partitioning can be done if the tree is organized for searching. In other
words, if the tree is a search tree!
Generally, the DFS is understood to be an exhaustive search of a general tree
which is not organized for searching. The depth-first-search performs a
depth-first-traversal (or walk). An unsuccessful search performs the complete
walk.
I apologize for having misread the assignment problem and asking you
to help me implement that "strange" walk. Even knowing its
strangeness, people still helped me out, and I can not be more
thankful to them.
I have to implement a pre-order DFS assignment and I have confirmed
this with my Prof.
For the same tree (A (B (D) (E)) (C)), the output will be A, B, D, E,
C.
Carla wrote:
> I apologize for having misread the assignment problem and asking you
> to help me implement that "strange" walk. Even knowing its
> strangeness, people still helped me out, and I can not be more
> thankful to them.
>
> I have to implement a pre-order DFS assignment and I have confirmed
> this with my Prof.
> For the same tree (A (B (D) (E)) (C)), the output will be A, B, D, E,
> C.
I love happy endings!
:)
kzo
Carla wrote:
> I have to implement a pre-order DFS assignment and I have confirmed
> this with my Prof.
> For the same tree (A (B (D) (E)) (C)), the output will be A, B, D, E,
> C.
You could implement it like this:
(defun traverse (list)
(when list
(let ((first (first list))
(rest (rest list)))
(if (atom first)
(format t "~a " first)
(traverse first))
(traverse rest))))
But this has the drawback that the stack depth is limited in most Lisp
implementations, so (traverse (for i from 0 to 1000000 collect i)) would
stop with a stack overflow error or even crash in some Lisp
implementations.
But you can convert the recursion with a explicit stack to a loop:
(defun traverse (list)
(let ((stack '()))
(push list stack)
(loop while (first stack) do
(let ((list (pop stack)))
(let ((first (first list))
(rest (rest list)))
(when rest
(push rest stack))
(if (atom first)
(format t "~a " first)
(when first
(push first stack))))))))
This works even for very large trees and is limited by the available memory
of the Lisp system, only.
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Frank Buss wrote:
> Carla wrote:
>
>
>>I have to implement a pre-order DFS assignment and I have confirmed
>>this with my Prof.
>>For the same tree (A (B (D) (E)) (C)), the output will be A, B, D, E,
>>C.
>
>
> You could implement it like this:
>
> (defun traverse (list)
> (when list
> (let ((first (first list))
> (rest (rest list)))
> (if (atom first)
> (format t "~a " first)
> (traverse first))
> (traverse rest))))
>
> But this has the drawback that the stack depth is limited in most Lisp
> implementations, so (traverse (for i from 0 to 1000000 collect i)) would
> stop with a stack overflow error or even crash in some Lisp
> implementations.
>
> But you can convert the recursion with a explicit stack to a loop:
>
> (defun traverse (list)
> (let ((stack '()))
> (push list stack)
> (loop while (first stack) do
> (let ((list (pop stack)))
> (let ((first (first list))
> (rest (rest list)))
> (when rest
> (push rest stack))
> (if (atom first)
> (format t "~a " first)
> (when first
> (push first stack))))))))
>
> This works even for very large trees and is limited by the available memory
> of the Lisp system, only.
>
Wow, talk about large trees. What is wrong with my bonsai?:
(defun tv (x)
(if (consp x)
(loop for y in x do (tv y))
(format t "~a " x)))
kt
Kenny wrote:
> Wow, talk about large trees. What is wrong with my bonsai?:
>
> (defun tv (x)
> (if (consp x)
> (loop for y in x do (tv y))
> (format t "~a " x)))
That's the same problem: It uses a recursion, so you can get a stack
overflow error with large lists.
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Frank Buss wrote:
> Kenny wrote:
>
>
>>Wow, talk about large trees. What is wrong with my bonsai?:
>>
>> (defun tv (x)
>> (if (consp x)
>> (loop for y in x do (tv y))
>> (format t "~a " x)))
>
>
> That's the same problem: It uses a recursion, so you can get a stack
> overflow error with large lists.
>
Grasshopper cannot see forest for bonsai.
kzo
Frank Buss <··@frank-buss.de> writes:
> Kenny wrote:
>
>> Wow, talk about large trees. What is wrong with my bonsai?:
>>
>> (defun tv (x)
>> (if (consp x)
>> (loop for y in x do (tv y))
>> (format t "~a " x)))
>
> That's the same problem: It uses a recursion, so you can get a stack
> overflow error with large lists.
For deep trees.
Each node can have as many children you want, they're processed by loop.
--
__Pascal Bourguignon__ http://www.informatimago.com/
ATTENTION: Despite any other listing of product contents found
herein, the consumer is advised that, in actuality, this product
consists of 99.9999999999% empty space.
From: Kaz Kylheku
Subject: Re: Depth First Search traversal of this list
Date:
Message-ID: <20080912143902.723@gmail.com>
On 2008-09-11, Carla <················@gmail.com> wrote:
> I apologize for having misread the assignment problem and asking you
> to help me implement that "strange" walk.
Next time, just quote the assignment problem verbatim rather than
paraphrasing it.
You learned a valuable software engineering lesson here, though: Development is
driven by requirement specifications. Requirement specifications can be
incomplete, imprecise and inconsistent. In spite of that, people can somehow
still write code, rather than go back to fix the requirements.
Kaz Kylheku wrote:
> On 2008-09-11, Carla <················@gmail.com> wrote:
>
>>I apologize for having misread the assignment problem and asking you
>>to help me implement that "strange" walk.
>
>
> Next time, just quote the assignment problem verbatim rather than
> paraphrasing it.
>
> You learned a valuable software engineering lesson here, though: Development is
> driven by requirement specifications. Requirement specifications can be
> incomplete, imprecise and inconsistent. In spite of that, people can somehow
> still write code, rather than go back to fix the requirements.
Doesn't anyone want to point out that Doctor K was... nahhh, even I am
getting tired of being right all the time.
Really, is there one chance in Hell you dorks will ever learn to listen
to noobs when they ask for help?
Hi, I am new to Lisp. I need to you all to step in front of a high-speed
locomotive... no, wait, we'll lose half the NG...
<sigh>
kzo
PJB>>> The confusion is between a "search" and a "walk".
??>>
??>> what is "walk" and how is it different from normal dfs traversal?
GN> A walk touches every node of the tree, a search partitions the tree to
GN> avoid touching every node.
partitions??
do you mean it exists as soon as it finds something, while "walk"
visits all node?
this actually makes sense, but people historically(?) refer to it as dfs
even if they are not going to find anything.
for example, NISTS's "Dictionary of Algorithms and Data Structures"
only has an entry for depth-first-search (no depth first walk or whatever):
----
(1) Any search algorithm that considers outgoing edges (children) of a
vertex before any of the vertex's siblings, that is, outgoing edges of the
vertex's predecessor in the search. Extremes are searched first. This is
easily implemented with recursion. (2) An algorithm that marks all vertices
in a directed graph in the order they are discovered and finished,
partitioning the graph into a forest.
Specialization (... is a kind of me.)
preorder traversal, in-order traversal, postorder traversal.
Note: Depth-first search doesn't specify if a vertex is considered before,
during, or after its outgoing edges or children. Thus it can be preorder,
in-order, or postorder traversal.
----
note that specializations are called traversals rather than searches -- i
guess that's later, more precies terminology comparing to original term dfs.
and it's used like that almost everywhere. in wikipedia:
http://en.wikipedia.org/wiki/Depth-first_search
Depth-first search (DFS) is an algorithm for traversing or searching a tree,
tree structure, or graph.
http://en.wikipedia.org/wiki/Topological_sorting
An alternative algorithm for topological sorting is based on depth-first
search. Loop through the vertices of the graph, in any order, initiating a
depth-first search for any vertex that has not already been visited by a
previous search. The desired topological sorting is the reverse postorder of
these searches.
Boost C++ libraries:
The depth_first_search() function performs a depth-first traversal of the
vertices in a directed graph.
also note, wherever they do not use word "search", they use word
"traversal".
so it seems like "walk" is unofficial rarely-used term (try google searches
for depth-first search, traversal and walk, and see the difference), but
Pascal used it as if everybody
should know what "walk" is and how is it different from search.
"Alex Mizrahi" <········@users.sourceforge.net> writes:
> PJB>>> The confusion is between a "search" and a "walk".
> ??>>
> ??>> what is "walk" and how is it different from normal dfs traversal?
>
> GN> A walk touches every node of the tree, a search partitions the tree to
> GN> avoid touching every node.
>
> partitions??
> do you mean it exists as soon as it finds something, while "walk"
> visits all node?
>
> this actually makes sense, but people historically(?) refer to it as dfs
> even if they are not going to find anything.
>
> for example, NISTS's "Dictionary of Algorithms and Data Structures"
> only has an entry for depth-first-search (no depth first walk or whatever):
Of course, there's no such thing as a depth first walk. You have
prefix walks, infix walks, suffix walks. Qualifying a walk of depth
first could be interpreted as I proposed, by displaying first the
deepest nodes, tree-wide, then going up depth by depth, independently
of the parent/child relationships.
What is requested apparently is some strange traversal where the
leaves are displayed after the subtrees. Well if that's what was
asked, ok.
> also note, wherever they do not use word "search", they use word
> "traversal".
> so it seems like "walk" is unofficial rarely-used term (try google searches
> for depth-first search, traversal and walk, and see the difference), but
> Pascal used it as if everybody
> should know what "walk" is and how is it different from search.
"tree walking algorithm" is an expression that is used too.
--
__Pascal Bourguignon__ http://www.informatimago.com/
WARNING: This product warps space and time in its vicinity.
From: Kaz Kylheku
Subject: Re: Depth First Search traversal of this list
Date:
Message-ID: <20080911163141.779@gmail.com>
On 2008-09-11, Pascal J. Bourguignon <···@informatimago.com> wrote:
> "Alex Mizrahi" <········@users.sourceforge.net> writes:
>
>> PJB>>> The confusion is between a "search" and a "walk".
>> ??>>
>> ??>> what is "walk" and how is it different from normal dfs traversal?
>>
>> GN> A walk touches every node of the tree, a search partitions the tree to
>> GN> avoid touching every node.
>>
>> partitions??
>> do you mean it exists as soon as it finds something, while "walk"
>> visits all node?
>>
>> this actually makes sense, but people historically(?) refer to it as dfs
>> even if they are not going to find anything.
>>
>> for example, NISTS's "Dictionary of Algorithms and Data Structures"
>> only has an entry for depth-first-search (no depth first walk or whatever):
>
> Of course, there's no such thing as a depth first walk. You have
> prefix walks, infix walks, suffix walks. Qualifying a walk of depth
> first could be interpreted as I proposed, by displaying first the
> deepest nodes, tree-wide, then going up depth by depth, independently
> of the parent/child relationships.
That is not understood in computer science literature as a depth-first
traversal. It's a breadth-first traversal (the ``tree-wide'' part) in a reverse
order of depth.
The term ``depth-first'' doesn't mean ``visit lower depths before the current
depth''. It means ``probe depth before breadth''.
If you want depth-first to mean ``visit lower depths first, in breadth-major
order across the tree'', you have to be clear about htis usage, since you are
redefining a generally understood computer science term to have a different
local meaning.
> What is requested apparently is some strange traversal where the
> leaves are displayed after the subtrees. Well if that's what was
> asked, ok.
Based on the OP's desired output in relation to the given input, it's in fact a
breadth-first traversal, but in reverse order of depth.
Kaz Kylheku <········@gmail.com> writes:
> On 2008-09-11, Pascal J. Bourguignon <···@informatimago.com> wrote:
>> "Alex Mizrahi" <········@users.sourceforge.net> writes:
>>
>>> PJB>>> The confusion is between a "search" and a "walk".
>>> ??>>
>>> ??>> what is "walk" and how is it different from normal dfs traversal?
>>>
>>> GN> A walk touches every node of the tree, a search partitions the tree to
>>> GN> avoid touching every node.
>>>
>>> partitions??
>>> do you mean it exists as soon as it finds something, while "walk"
>>> visits all node?
>>>
>>> this actually makes sense, but people historically(?) refer to it as dfs
>>> even if they are not going to find anything.
>>>
>>> for example, NISTS's "Dictionary of Algorithms and Data Structures"
>>> only has an entry for depth-first-search (no depth first walk or whatever):
>>
>> Of course, there's no such thing as a depth first walk. You have
>> prefix walks, infix walks, suffix walks. Qualifying a walk of depth
>> first could be interpreted as I proposed, by displaying first the
>> deepest nodes, tree-wide, then going up depth by depth, independently
>> of the parent/child relationships.
>
> That is not understood in computer science literature as a depth-first
> traversal. It's a breadth-first traversal (the ``tree-wide'' part) in a reverse
> order of depth.
>
> The term ``depth-first'' doesn't mean ``visit lower depths before the current
> depth''. It means ``probe depth before breadth''.
>
> If you want depth-first to mean ``visit lower depths first, in breadth-major
> order across the tree'', you have to be clear about htis usage, since you are
> redefining a generally understood computer science term to have a different
> local meaning.
Yes, that's exactly what I'm saying.
>> What is requested apparently is some strange traversal where the
>> leaves are displayed after the subtrees. Well if that's what was
>> asked, ok.
>
> Based on the OP's desired output in relation to the given input, it's in fact a
> breadth-first traversal, but in reverse order of depth.
That's what I understood. And in this context, I wanted the OP to
clarify with the "trick" tree, (a (b (c d) e) (f (g (h i) j) k) l),
which according to her answer, implied an even stranger walk that what
we agree she said she wanted first.
--
__Pascal Bourguignon__ http://www.informatimago.com/
The world will now reboot. don't bother saving your artefacts.
On Thu, 11 Sep 2008 15:10:47 +0300, "Alex Mizrahi"
<········@users.sourceforge.net> wrote:
> ??>> are you trying to confuse him? DFS is a pretty concrete thing:
> ??>>
> ??>> http://en.wikipedia.org/wiki/Depth-first_search
>
> PJB> The confusion is between a "search" and a "walk".
>
>what is "walk" and how is it different from normal dfs traversal?
Incidentally, the reason for the violent agreement with Pascal is that
you brought up depth first _search_ without specifying that it was the
traversal order that you were referring to.
George
c> To answer the most important question, yes it is my homework question
c> and it entails developing a full blown depth first search algorithm
c> for such alphabetical binary trees.
what are "such alphabetically binary trees"? you did not specify what your
format
means, but i'm pretty sure list (A (B (D E) C)) cannot be a binary tree.
if your format is like in Lisp expressions (parent child child child ..),
then your
list (A (B (D E) C)) will be rather weird tree:
A
B
D C
E
here node A has only one child -- B, so it is not binary. the postordering
of this
tree will be E D C B A but not D E B C A as you wrote. (check article:
http://en.wikipedia.org/wiki/Depth-first_search
to understand what postordering means).
on the other hand, postordering D E B C A could be produced with a binrary
tree:
A
B C
D E
this tree can be represented as a list (A (B D E) C). maybe this is what you
mean?
c> The reason I am struggling with Lisp is that I have never worked on
c> Lisp nor seen its coding style.
your problem is not in lisp but in that you do not really understand format
you're working with
and recursive process. start with specifying format. then write down
recursive process
in plain English -- that is what cases are, and what do you do in each case.
only then you can start coding that with lisp.
P� Thu, 11 Sep 2008 01:05:13 +0200, skrev <················@gmail.com>:
> Hello,
> I am trying to traverse the list (A (B (D E) C)) in a way that the
> print output should be in the following order D, E, B, C, A aka depth
> first traversal.
>
> So far, I have come up with this code but it seems to have some
> strange problem.
>
> [code](setq start (list 'a (list 'b (list 'd 'e) 'c )))
> ====> gives ====> (A (B (D E) C))
>
> (defun depth-first (start)
> (cond
> ((null start) 0)
> ((listp (first start)) (setq start (first start))
> (depth-first (first start)))
> ((not (eq nil (car start))) (print (car start))
> (setq start (rest start))
> (depth-first (start)))
> (t "Go home")))[/code]
>
> Can someone please help me out.
Something like this? (Nore that node-left and node-right return nil also
when the list contains only node-data.)
(defstruct (node (:type list)) data left right)
(defun depth-first-traversal (tree)
"Traverse a tree depth first and collect the data into a list."
(let (result)
(labels ((traverse (tree)
(when (node-left tree) (traverse (node-left tree)))
(push (node-data tree) result)
(when (node-right tree) (traverse (node-right tree)))))
(nreverse (traverse tree)))))
CL-USER 23 > (depth-first-traversal '(1 (2 (3) (4)) (5)))
(3 2 4 1 5)
--------------
John Thingstad
From: Kaz Kylheku
Subject: Re: Depth First Search traversal of this list
Date:
Message-ID: <20080911151148.135@gmail.com>
On 2008-09-10, ················@gmail.com <················@gmail.com> wrote:
> Hello,
> I am trying to traverse the list (A (B (D E) C)) in a way that the
> print output should be in the following order D, E, B, C, A aka depth
> first traversal.
This isn't depth-first traversal.
Depth first means: A B D E C, in other words, the left-to-right order in
which the nodes appear.
Breadth first means: A B C D E. The tree is traversed down to level N,
before proceeding to level N + 1.
What you are asking for is to visit level N + 1 before visiting level N.
This is not what is generally understood, in computer science, as
depth first.
This is almost like the output of a breadth-first traversal in reverse,
except that you still want to process each level left-to-right.
So we can start by coding a breadth-first traversal. This algorithm
works by iterating over the items at one level in the tree. Atoms
at the current level are visited in left-to-right order. Subtrees (i.e. conses)
are deferred into a queue, which is processed after the atoms are visited.
We append the list together, so for instance if we are processing
(A (B C) D (E F)) the algorithm will visit A, append (B C) to the queue, then
visit D, and append (E F) to the queue, so the queue holds (B C E F).
It will then recurse over the queue, visiting B C E F.
(defun breadth-first-map (function tree)
(loop for item in tree
if (consp item)
append item into queue
else
do (funcall function item)
finally
(unless (null queue)
(breadth-first-map function queue))))
Test cases:
(breadth-first-map #'print '(1 2 (3 (9 10) 4) 5 (6 7)))
-> NIL
[output]
1
2
5
3
4
6
7
9
10
[/output]
(breadth-first-map #'print '(A (B (D E) C)))
-> NIL
[output]
A
B
C
D
E
[/output]
So that is breadth-first traversal. What you are looking for is a traversal
which visits the levels in the reverse order: lower levels first. At each
level, it still visits the atoms in the left-to-right order.
To visit the lower level first, we cannot process the current level items
immediately as we see them. We must collect them into a list.
And we must still maintain a queue for visiting the next lower depth.
After collecting both the queue and current level items, we do the recursion to
the next depth first, and then map the saved current level items through the
function to visit them:
(defun breadth-first-map-bottom-up (function tree)
(loop for item in tree
if (consp item)
append item into queue
else
collect item into current-level-items
finally
;; recurse to lower depths first---
;; ---not to be confused with ``depth-first traversal''!!!
(unless (null queue)
(breadth-first-map-bottom-up function queue))
;; then process items at this level
(mapc function current-level-items)))
(breadth-first-map-right-left-bottom-up #'print '(A (B (D E) C)))
[output]
D
E
B
C
A
[/output]
So there is your so-called ``depth first'' traversal.
It doesn't appear to be a particularly useful invention.
One last note. Notice that the original breadth-first traversal is tail
recursive; it can be trivially rewritten as a loop. The last thing it does is
call itself, and doesn't do anything with the return value, other
than pass it up.
This means we can replace the recursive call by assigning to the parameters and
looping backwards. The null queue test which terminates the recursion becomes a
termination test for our loop. For the sake of variety, let's use DO, and move
the termination test into its termination clause:
(defun breadth-first-map (function tree)
(do () ((null tree)) ;; loop until tree is null
(loop for item in tree
if (consp item)
append item into queue
else
do (funcall function item)
finally
;; process next level by treating the
;; queue as the tree
(setf tree queue))))
Homework for you: is the bottom-up version of the traversal tail recursive?
Can we easily rewrite it to use iteration?
KK> Depth first means: A B D E C, in other words, the left-to-right order
in
KK> which the nodes appear.
not really.
http://www.nist.gov/dads/HTML/depthfirst.html
Note: Depth-first search doesn't specify if a vertex is considered before,
during, or after its outgoing edges or children. Thus it can be preorder,
in-order, or postorder traversal.