SunQuest
           Python Programming
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
User Name:
Password:
Remember me
Go Back   Dev Shed ForumsProgramming LanguagesPython Programming

Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Rate Thread Display Modes
 
Unread Dev Shed Forums Sponsor:
Get inside! Sample the range of functionality easily built with JMSL Library for Time Series Data Analysis, Heat Maps, Portfolio Optimization, Monte Carlo Simulation, Stock Price Charting and more. Download Now!
  #1  
Old March 26th, 2004, 10:57 PM
roypython roypython is offline
Contributing User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Feb 2004
Posts: 71 roypython User rank is Lance Corporal (50 - 100 Reputation Level)roypython User rank is Lance Corporal (50 - 100 Reputation Level)roypython User rank is Lance Corporal (50 - 100 Reputation Level) 
Time spent in forums: 1 h 20 m 49 sec
Reputation Power: 5
finding node in a tree

Hi.
I have a question that might be a bit silly.
I have a tree structure ( not binary), and a pointer to the root node.
How do I write a function that looks for a node with a certain name and returns the node ( if found), or None.
( python has no static variables, which makes it a bit more difficult)
thank you very much
Roy

Reply With Quote
  #2  
Old March 26th, 2004, 11:05 PM
Strike Strike is offline
Contributing User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Dec 2001
Location: Houston, TX
Posts: 383 Strike User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 1 h 41 m 27 sec
Reputation Power: 7
Send a message via ICQ to Strike Send a message via AIM to Strike Send a message via Yahoo to Strike
We need more info on the data structure. The generic answer is "walk the tree", with more specific (but still generic) answers like, "do a depth-first traversal".
__________________
Debian - because life's too short for worrying.
Best. (Python.) IRC bot. ever.

Reply With Quote
  #3  
Old March 26th, 2004, 11:14 PM
roypython roypython is offline
Contributing User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Feb 2004
Posts: 71 roypython User rank is Lance Corporal (50 - 100 Reputation Level)roypython User rank is Lance Corporal (50 - 100 Reputation Level)roypython User rank is Lance Corporal (50 - 100 Reputation Level) 
Time spent in forums: 1 h 20 m 49 sec
Reputation Power: 5
Thank you for your quick reply.
Every node consists of:
Node:
name=the name of the node
and variable number of attributes

I want to compare the Node.name to the name that was recieved as
parameter, if it is equal then return the node (self)
if not, keep on looking or return None ( if no nodes left to look in)

Reply With Quote
  #4  
Old March 27th, 2004, 06:05 AM
DevCoach DevCoach is offline
Contributing User
Dev Shed Beginner (1000 - 1499 posts)
 
Join Date: Feb 2004
Location: London, England
Posts: 1,196 DevCoach User rank is Captain (20000 - 30000 Reputation Level)DevCoach User rank is Captain (20000 - 30000 Reputation Level)DevCoach User rank is Captain (20000 - 30000 Reputation Level)DevCoach User rank is Captain (20000 - 30000 Reputation Level)DevCoach User rank is Captain (20000 - 30000 Reputation Level)DevCoach User rank is Captain (20000 - 30000 Reputation Level)DevCoach User rank is Captain (20000 - 30000 Reputation Level)DevCoach User rank is Captain (20000 - 30000 Reputation Level)DevCoach User rank is Captain (20000 - 30000 Reputation Level) 
Time spent in forums: 1 Week 5 Days 13 h 42 m 7 sec
Reputation Power: 252
That still doesn't tell us how you walk the tree - how do you get from one node to the next?

What you describe is not a tree, unless the 'variable list of attributes' can also contain nodes. Is this the case, or are the nodes linked in some other way?


Dave - The Developers' Coach

Reply With Quote
  #5  
Old March 27th, 2004, 05:49 PM
roypython roypython is offline
Contributing User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Feb 2004
Posts: 71 roypython User rank is Lance Corporal (50 - 100 Reputation Level)roypython User rank is Lance Corporal (50 - 100 Reputation Level)roypython User rank is Lance Corporal (50 - 100 Reputation Level) 
Time spent in forums: 1 h 20 m 49 sec
Reputation Power: 5
You right Dave, my apology ( thinks for your patience )
Every Node has some linking info as well:
children =[]
parent = None

children is a list that contains all the direct children of the node.
parent contains None ( if it is the root node) or reference to another node, which it is his it's parent.

Reply With Quote
  #6  
Old March 28th, 2004, 04:08 AM
DevCoach DevCoach is offline
Contributing User
Dev Shed Beginner (1000 - 1499 posts)
 
Join Date: Feb 2004
Location: London, England
Posts: 1,196 DevCoach User rank is Captain (20000 - 30000 Reputation Level)DevCoach User rank is Captain (20000 - 30000 Reputation Level)DevCoach User rank is Captain (20000 - 30000 Reputation Level)DevCoach User rank is Captain (20000 - 30000 Reputation Level)DevCoach User rank is Captain (20000 - 30000 Reputation Level)DevCoach User rank is Captain (20000 - 30000 Reputation Level)DevCoach User rank is Captain (20000 - 30000 Reputation Level)DevCoach User rank is Captain (20000 - 30000 Reputation Level)DevCoach User rank is Captain (20000 - 30000 Reputation Level) 
Time spent in forums: 1 Week 5 Days 13 h 42 m 7 sec
Reputation Power: 252
There are several ways to do it. If you are using 2.2 or above then you could use generators to add an iterator to the class that would allow you to treat the tree as a sequence of nodes. If you also added a comparison function for the name attribute you could use the 'in' operator to test for the presence of a node with a give name.

e.g.

Code:
#this import is only needed for 2.2
from __future__ import generators

class Node:
    def __init__(self, name, *nodes):
        self.name = name
        self.children = list(nodes)
        
    def addChild(self, kid):
        self.children.append(nodes)
        
    def __iter__(self):
        yield self
        for child in self.children:
            for node in child:
                yield node

    def __eq__(self, name):
        return self.name == name


if __name__ == '__main__':
    #create some sample data
    a = Node('a')
    b = Node('b')
    c = Node('c', a, b)
    d = Node('d', c)
    e = Node('e')
    f = Node('f')
    g = Node('g', d, e, f)
    h = Node('h')
    i = Node('i', g, h)
    j = Node('j', i)
    k = Node('k')
    l = Node('l', k, j)
    root = Node('root', l)

    #print out the nodes (depth first)
    for node in root: print node.name,
    print
    #test for node with the given name
    print 'x' in root
    print 'i' in root


The output from the above script:
Code:
E:\prj\sandbox>python test2.py
root l k j i g d c a b e f h
False
True


Dave - The Developers' Coach

Reply With Quote
  #7  
Old March 28th, 2004, 06:47 PM
roypython roypython is offline
Contributing User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Feb 2004
Posts: 71 roypython User rank is Lance Corporal (50 - 100 Reputation Level)roypython User rank is Lance Corporal (50 - 100 Reputation Level)roypython User rank is Lance Corporal (50 - 100 Reputation Level) 
Time spent in forums: 1 h 20 m 49 sec
Reputation Power: 5
Thank you very much Dave for your solution.
it helped me heaps!!!
There is one more issue though...
1. How to delete an item (and all it's children as well)?
2. How can I use built in operator overloading method to invoke
deletion (like __delitem__)?
Thank you very much
Roy

Reply With Quote
  #8  
Old March 29th, 2004, 12:28 AM
theperfectsoup theperfectsoup is offline
Contributing User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Jul 2003
Posts: 35 theperfectsoup User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: < 1 sec
Reputation Power: 5
In all honesty, it sounds like you're prying for answers to a HW assignment. Rather than give you code, here are some hints:

1. How to delete an item (and all it's children as well)?

Traverse the tree until you find the parent of the node to delete; you will know that you are at the parent of the node to delete when its "children" array contains the node to delete. Just call children.remove() on that node.

2. How can I use built in operator overloading method to invoke
deletion (like __delitem__)?


Just call the above code __delitem__, I believe (haven't done any operator overloading myself -- never had the need -- so someone else correct me if I'm wrong).

- tps

Reply With Quote
Reply

Viewing: Dev Shed ForumsProgramming LanguagesPython Programming > finding node in a tree


Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Rate This Thread:


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump


Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
  
 





© 2003-2008 by Developer Shed. All rights reserved. DS Cluster 5 hosted by Hostway