hi,
figure I have following tree:
A
/ | \
B C D
|
E
that I will represent with a list like this (A (B (C (E)) (D))
Now, what I want to do is to get the path from root node to E, that is
(A C E)
I'm not sure how to do that, maybe using backtracking...
any hints are welcome
thanks in advance
I don't know how to write it in lisp, but the idea is this:
You need something that would associate a parent with each node (a
reverse tree). Here is some pseudo-python:
compute_parent(node,parent):
parent_of[node]=parent
for child in node.children:
compute_parent(child,node)
>From there, given E, parent_of(E) would be C, parent_of(C) would be A,
and parent_of(A) would be null.
From: Rahul Jain
Subject: Re: return path in a tree search
Date:
Message-ID: <87brb3y2mc.fsf@nyct.net>
bmsv <····@hotmail.com> writes:
> Now, what I want to do is to get the path from root node to E, that is
> (A C E)
> I'm not sure how to do that, maybe using backtracking...
> any hints are welcome
Do a recursive search and then when you find the desired end point,
return a list containing that end point. From the recirsive calls,
return the current point consed in front of the remainder of the path
list.
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
bmsv wrote:
> hi,
> figure I have following tree:
> A
> / | \
> B C D
> |
> E
>
> that I will represent with a list like this (A (B (C (E)) (D))
> Now, what I want to do is to get the path from root node to E, that is
> (A C E)
> I'm not sure how to do that, maybe using backtracking...
> any hints are welcome
homework? if so, most cll denizens will gladly help fix any brave
attempt you make. if not, what have you tried so far?
kt
--
Cells? Cello? Cells-Gtk?: http://www.common-lisp.net/project/cells/
Why Lisp? http://lisp.tech.coop/RtL%20Highlight%20Film
"Doctor, I wrestled with reality for forty years, and I am happy to
state that I finally won out over it." -- Elwood P. Dowd
Someone referred to as: bmsv <····@hotmail.com>
has comitted the herein quoted text :
> hi,
> figure I have following tree:
> A
> / | \
> B C D
> |
> E
>
> that I will represent with a list like this (A (B (C (E)) (D))
> Now, what I want to do is to get the path from root node to E, that is
> (A C E)
> I'm not sure how to do that, maybe using backtracking...
> any hints are welcome
I figure you could read the chapter 13 of peter Seibel's book, or your
teachers recommended reader or paper.
http://www.gigamonkeys.com/book/beyond-lists-other-uses-for-conses.html
Cor
--
To really make a mess of things one should use a computer
bmsv <····@hotmail.com> wrote:
> hi,
> figure I have following tree:
> A
> / | \
> B C D
> |
> E
>
> that I will represent with a list like this (A (B (C (E)) (D))
I assume you mean (A (B) (C (E)) (D)) (note the missing '(' after 'B'),
then it is easy:
(defun get-path (tree element)
(nreverse (funcall
(funcall
#'(lambda (m)
((lambda (u)
(funcall m #'(lambda (&rest arg)
(apply (funcall u u) arg) )))
#'(lambda (u)
(funcall m #'(lambda (&rest arg)
(apply (funcall u u) arg) ))) ))
#'(lambda (fun)
#'(lambda (tree element path)
(let ((value (car tree))
(children (cdr tree)))
(push value path)
(if (eql element value)
path
(if children
(dolist (child children)
(let ((next-path (funcall fun child
element path)))
(when next-path (return next-path))))
nil))))))
tree
element
nil)))
You can call it like this:
CL-USER > (get-path '(A (B) (C (E)) (D)) 'e)
(A C E)
PS: If this is a homework, perhaps your teacher is reading this
newsgroup, too.
--
Frank Bu�, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
On 2 Feb 2005, ··@frank-buss.de wrote:
> bmsv <····@hotmail.com> wrote:
[...]
>> figure I have following tree:
>> A
>> / | \
>> B C D
>> |
>> E
[...]
> I assume you mean (A (B) (C (E)) (D)) (note the missing '(' after 'B'),
> then it is easy:
[Code]
>
> You can call it like this:
>
> CL-USER > (get-path '(A (B) (C (E)) (D)) 'e)
> (A C E)
>
> PS: If this is a homework, perhaps your teacher is reading this
> newsgroup, too.
I'm only an amateur in Lisp but if you meant the above code serious (I
think also that it sounds like homework) I'm not sure if it's not a bit
too complicated. I played a bit (found some solutions) and here is one
I like (maybe I overlooked somehting simple then forget that code):
(defun get-path (tree element)
(let (found)
(labels ((walker (node)
(let ((left (car node)) (right (cdr node)))
(cond ((consp left)
(let ((lpath (unless found (walker left)))
(rpath (unless found (walker right))))
(or (and lpath rpath (cons lpath rpath))
lpath rpath)))
((not left) left)
((eql left element) (setf found t) (cons left nil))
(t
(let ((path (walker right)))
(and path (cons left path))))))))
(walker tree))))
Maybe with some destructive operations instead of `cons' the code would
cons less but I don't think that should be a problem.
KP
On 2005-02-02 09:02:55 -0500, ······@12move.de (Karl
=?iso-8859-1?Q?Pfl=E4sterer?=) said:
>> CL-USER > (get-path '(A (B) (C (E)) (D)) 'e)
>> (A C E)
> (maybe I overlooked somehting simple then forget that code):
With this representation of trees, something like
(defun get-path (tree element &key (test 'eql))
(labels ((walk (tree)
(acond ((null tree) nil)
((funcall test (car tree) element)
(list element))
((some #'walk (cdr tree)) (cons (car tree) it)))))
(walk tree)))
will do what you want. Whether this is simpler than your solution is
questionable, but it is more compact.
^L
······@12move.de (Karl Pfl�sterer) wrote:
> I'm only an amateur in Lisp but if you meant the above code serious (I
> think also that it sounds like homework) I'm not sure if it's not a
> bit too complicated.
you are right, I forgot the smiley, but I was hoping that "bmsv" uses this
solution and the teacher asks him about the Y operator :-)
> I played a bit (found some solutions) and here
> is one I like (maybe I overlooked somehting simple then forget that
> code):
yes, that's more like a student would write it. It can be simplified,
because I think that lpath is always an atom.
--
Frank Bu�, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
bmsv wrote:
> hi,
> figure I have following tree:
> A
> / | \
> B C D
> |
> E
>
> that I will represent with a list like this (A (B (C (E)) (D))
> Now, what I want to do is to get the path from root node to E, that is
> (A C E)
> I'm not sure how to do that, maybe using backtracking...
> any hints are welcome
>
> thanks in advance
>
Go crazy ....
(defun find-path (map end)
(cond
((null map) nil)
((eql (first map) end) (list end))
(t
(map nil
(lambda (submap)
(let ((result (find-path submap end)))
(when result
(return-from find-path (cons (first map) result)))))
(rest map)))))
CL-USER 2 > (find-path '(A (B) (C (E)) (D)) 'e)
(A C E)
Wade