tree structures

Discussion in 'Ruby' started by frank, Feb 13, 2006.

  1. frank

    frank Guest

    Hi,

    I have been using ruby for a few months now and am writing a program
    that duplicates portions of a tree structure.

    For example, take the following tree:

    ((A,B),C)

    Where ( represents a node, each letter represents a leaf. I am
    currently using a very clunky set of arrays to hold all the
    information.

    leaf = Array.new
    node = Array.new
    left = Array.new #represents the child to the left
    right = Array.new #represents the child to the right
    parent = Array.new

    I number each element in the array based on moving up the tree and
    reading either a left or right node or leaf.
    left = i*2
    right = i*2+1

    thus node[2] represents the node subtending the edges leading to the
    left child A and the right child B.

    So to traverse this tree
    ( = node 1
    ( = move up a node to 2
    A = move up to left leaf 4
    , = move down to node 2
    B = move up to the right leaf 5
    ) = move down to node 2
    , = move down to node 1
    C = move up to right child 3
    ) = move down to node 1 and end of tree

    Using the above tree and information in the array elements, I want to
    be able to duplicate portions of the tree, such that I could get
    something like:

    (((A,B),(A,B)), C)

    So moving up from node 1 to node 2 I have a duplication in A and B. I
    can indicate where I have duplications but ultimately need to write
    this back out into the parenthetical notation that I am using to
    describe a tree. I am afraid that I should be using struct or they may
    be a better way to describe my tree structures rather than using
    numbered and linked lists. Any information on using struct in ruby or
    pointer equivalents would be appreciated. I am trying to come up with
    a way of doing this such that I could use it on trees of any size.
    Right now I am using arrays and the bookkeeping is getting tricky.

    Thanks for any help!
    frank
     
    frank, Feb 13, 2006
    #1
    1. Advertising

  2. "just" looked at Bob's work, acts_as_threaded.

    I am fairly certain it is exactly what you are after.

    http://www.railtie.net/articles/2006/02/05/rails-acts_as_threaded-plugin

    -Nb

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Nathaniel S. H. Brown http://nshb.net
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


    > -----Original Message-----
    > From: frank [mailto:]
    > Sent: February 12, 2006 6:38 PM
    > To: ruby-talk ML
    > Subject: tree structures
    >
    > Hi,
    >
    > I have been using ruby for a few months now and am writing a
    > program that duplicates portions of a tree structure.
    >
    > For example, take the following tree:
    >
    > ((A,B),C)
    >
    > Where ( represents a node, each letter represents a leaf. I
    > am currently using a very clunky set of arrays to hold all
    > the information.
    >
    > leaf = Array.new
    > node = Array.new
    > left = Array.new #represents the child to the left right =
    > Array.new #represents the child to the right parent = Array.new
    >
    > I number each element in the array based on moving up the
    > tree and reading either a left or right node or leaf.
    > left = i*2
    > right = i*2+1
    >
    > thus node[2] represents the node subtending the edges
    > leading to the left child A and the right child B.
    >
    > So to traverse this tree
    > ( = node 1
    > ( = move up a node to 2
    > A = move up to left leaf 4
    > , = move down to node 2
    > B = move up to the right leaf 5
    > ) = move down to node 2
    > , = move down to node 1
    > C = move up to right child 3
    > ) = move down to node 1 and end of tree
    >
    > Using the above tree and information in the array elements, I
    > want to be able to duplicate portions of the tree, such that
    > I could get something like:
    >
    > (((A,B),(A,B)), C)
    >
    > So moving up from node 1 to node 2 I have a duplication in A
    > and B. I can indicate where I have duplications but
    > ultimately need to write this back out into the parenthetical
    > notation that I am using to describe a tree. I am afraid
    > that I should be using struct or they may be a better way to
    > describe my tree structures rather than using numbered and
    > linked lists. Any information on using struct in ruby or
    > pointer equivalents would be appreciated. I am trying to
    > come up with a way of doing this such that I could use it on
    > trees of any size.
    > Right now I am using arrays and the bookkeeping is getting tricky.
    >
    > Thanks for any help!
    > frank
    >
    >
     
    Nathaniel S. H. Brown, Feb 13, 2006
    #2
    1. Advertising

  3. Hmm. To be very, very, very frank, If I wanted binary trees for something, =
    I'd=20
    let the Berkeley DB do this for me. There's people way better at making=20
    efficient data structures out there.

    D=C5=88a Pondelok 13 Febru=C3=A1r 2006 03:38 frank nap=C3=ADsal:
    > I am afraid that I should be using struct or they may
    > be a better way to describe my tree structures rather than using
    > numbered and linked lists. Any information on using struct in ruby or
    > pointer equivalents would be appreciated. I am trying to come up with
    > a way of doing this such that I could use it on trees of any size.
    > Right now I am using arrays and the bookkeeping is getting tricky.
    >


    I smell C.

    There are no pointer equivalents. Or rather, there's nothing else, but it=20
    shouldn't matter anyway. Ruby has by-reference semantics, variables hold=20
    references to objects. Which isn't -quite- true, but let's say it is for no=
    w.

    Classes are your friends. But I'll let the code do the talking. If you find=
    =20
    you don't understand something, I recommend you read the Pickaxe book,=20
    available for free online in the first edition, which is probably enough fo=
    r=20
    now. As a matter of fact, you should read it anyway, with nothing insulting=
    =20
    in mind, you have a little to learn about this gem of a language that is=20
    Ruby. (Did I just make a pun?)

    # A node of a binary tree.
    class Node
    attr_reader :left
    attr_reader :right
    attr_accessor :value
    attr_accessor :parent

    def left=3D(node)
    @left =3D node
    left.parent =3D self
    end

    def right=3D(node)
    @right =3D node
    right.parent =3D self
    end

    # Recursively duplicate a node.
    def initialize_copy(node)
    self.value =3D node.value
    self.left =3D node.left.dup if node.left
    self.right =3D node.right.dup if node.right
    end

    def initialize(new_value =3D nil)
    self.value =3D new_value
    end

    # The recursive string conversion.
    def to_s
    "(" + [left, value, right].join(", ") + ")"
    end

    end

    Calling Node#dup should duplicate a (sub) tree properly.

    David Vallner
     
    David Vallner, Feb 13, 2006
    #3
  4. frank

    frank Guest

    David,

    Thank you for the help! Yes, some of my code is translated from C. I
    am trying to migrate to Ruby with this project. I also figured this
    would be a straight forward project....

    frank
     
    frank, Feb 13, 2006
    #4
  5. D=C5=88a Pondelok 13 Febru=C3=A1r 2006 04:33 frank nap=C3=ADsal:
    > David,
    >
    > Thank you for the help! Yes, some of my code is translated from C. I
    > am trying to migrate to Ruby with this project. I also figured this
    > would be a straight forward project....
    >
    > frank


    Migration from a fully procedural, compiled, statically typed language with=
    =20
    by-value semantics into a strongly OO, interpreted, dynamically typed one=20
    with by-reference ones?

    Yah right.

    You technically can code procedural in Ruby, it just hurts so much when it=
    =20
    comes to custom data structures. Learning to (ab)use the features of Ruby=20
    will make your life easier than just one-to-one porting.

    David Vallner
     
    David Vallner, Feb 13, 2006
    #5
  6. frank

    Gene Tani Guest

    Gene Tani, Feb 13, 2006
    #6
  7. On Feb 12, 2006, at 8:38 PM, frank wrote:

    > For example, take the following tree:
    >
    > ((A,B),C)
    >
    > Where ( represents a node, each letter represents a leaf. I am
    > currently using a very clunky set of arrays to hold all the
    > information.
    >
    > leaf = Array.new
    > node = Array.new
    > left = Array.new #represents the child to the left
    > right = Array.new #represents the child to the right
    > parent = Array.new
    >
    > I number each element in the array based on moving up the tree and
    > reading either a left or right node or leaf.
    > left = i*2
    > right = i*2+1


    Is there any reason not to use a simpler approach (my opinion), like:

    [ ["A", "B"], "C" ]

    ?

    Seems like traversing that with first(), last(), and is_a?(Array)
    ought to be pretty simple. You can wrap it in a class to make it
    even easier.

    > Using the above tree and information in the array elements, I want to
    > be able to duplicate portions of the tree, such that I could get
    > something like:
    >
    > (((A,B),(A,B)), C)


    branch = ["A", "B"]
    [ branch, branch, "C" ]

    ?

    James Edward Gray II
     
    James Edward Gray II, Feb 13, 2006
    #7
  8. frank

    frank Guest

    Okay, so I need to approach this head on from an OO standpoint. I have
    Ruby Way and Programming Ruby.

    With the program I have written so far, I parsed the tree information
    into a set of linked lists (see below). I realize this may not be the
    best way to begin this program. I need to embrace classes and
    represent the tree as an object. I am looking over the example in the
    Ruby Way on binary trees. I get what is going on with Hal Fultons
    examples. But it seems like there is a huge gulf between my procedural
    thinking and an OO thinking with regard to this tree structure. How
    would you represent a linked list in Ruby?

    In other words, would it be possible to convert the following
    procedural Ruby code into OO ruby so that I would be able to "get it".
    Or are there equivalent examples procedural to OO. I mean, what I have
    written is awful looking compared to the class Node you posted
    earlier...and while I understand the ideas of instance variables and
    self and classes methods etc. I am struggling to get them right in my
    head.

    -frank

    This is not the full program but enough to see what I am trying to
    accomplish.
    #!/usr/bin/ruby -w

    class Integer
    def odd?
    self % 2 == 0
    end
    end

    #class Integer
    # def even?() self.[](0) == 0 end
    # def odd?() self.[](0) == 1 end
    #end

    tree =
    "(((aa:0.490,bb:0.50):0.70,cc:0.85):0.90,(ee:0.95,dd:0.99):0.100);"
    print "here is the tree", tree, "\n"

    tree_array = tree.scan(/[a-z]+|\d+\.\d+|[(,);]/)

    tree_array_size = tree_array.size # want to use this but need to parse
    the tree file better
    #initializing an array for a linked list so that I can begin traversing
    nodes

    leaf = Array.new
    node = Array.new
    left = Array.new
    right = Array.new
    ancestor = Array.new
    branch = Array.new

    m = 0 # a counter used for assigning numbers to nodes
    i = 0 #counter for reading through all the elements of a newick tree
    while i < tree_array_size

    if tree_array == '(' && i == 0

    print "ROOT", "\n"


    i += 1
    m += 1

    left_m = m*2
    right_m = m*2+1


    node[m] =[]
    left[left_m] = []
    right[right_m] = []

    elsif tree_array == '(' && i != 0

    print " UP_PASS", "\n"

    i += 1
    m = m*2


    if node[m] == nil

    left_m = m*2
    right_m = m*2+1



    node[m] = []
    left[left_m] = []
    right[right_m] = []
    ancestor[m] == node[m/2]


    print "node is ", m, "\n"
    print "left ", left_m, "\n"
    print "right ", right_m, "\n"

    if m.odd? != true

    print "ancestor odd is ", (m-1)/2, "\n"
    else

    print "ancestor is ", m/2, "\n"
    end

    elsif node[m] != nil

    m = m/2


    print "node already defined looking RIGHT on the tree", "\n"

    m = m*2+1

    left_m = m*2
    right_m = m*2+1


    node[m] = []
    left[left_m] = []
    right[right_m] = []
    ancestor[m] == node[m/2]


    print "node is ", m, "\n"
    print "left ", left_m, "\n"
    print "right ", right_m, "\n"

    if m.odd? != true

    print "ancestor odd is ", (m-1)/2, "\n"
    else

    print "ancestor is ", m/2, "\n"
    end

    else

    print "NO doesn't work", "\n"
    end



    .......
     
    frank, Feb 13, 2006
    #8
  9. D=C5=88a Pondelok 13 Febru=C3=A1r 2006 19:13 frank nap=C3=ADsal:
    > But it seems like there is a huge gulf between my procedural
    > thinking and an OO thinking with regard to this tree structure.


    Oh, it gets worse. Data structures are actually more or less the same thing=
    in=20
    procedural and OO, except with encapsulation applying in the simpler cases,=
    =20
    and abstract interfaces in the more complicated ones - the actual=20
    implementation of the algorithms is identical.

    > How would you represent a linked list in Ruby?
    >


    Usually not at all. If you can place a reasonable upper bound on the amount=
    of=20
    data you will be storing, the standard Ruby Array will work well - it does=
    =20
    support the necessary operations.

    > In other words, would it be possible to convert the following
    > procedural Ruby code into OO ruby so that I would be able to "get it".
    > Or are there equivalent examples procedural to OO.=20


    Now this is a tricky one. I could give my personal list of "recommended"=20
    reading to see just where OO is significantly different from procedural, bu=
    t=20
    I think that is a little out of your scope just now, and the basics, which=
    =20
    are well enough documented in the books you mentioned, will do for now.

    > I mean, what I have written is awful looking compared to the class Node=20
    > you posted earlier...and while I understand the ideas of instance variabl=

    es
    > and self and classes methods etc. I am struggling to get them right in my
    > head.
    >


    Actually, I don't think it's related to that. The code I posted, nearly=20
    identical to the Ruby Way one, wasn't that advanced, it was just granular -=
    =20
    more on that a bit below.

    > This is not the full program but enough to see what I am trying to
    > accomplish.


    Not quite. I can't really see the intent of the code clearly, and I have to=
    =20
    pore over it to find out what's happening - if I'm correct, you're trying t=
    o=20
    read the tree structure from a string.=20

    I'll give you an additional small exercise: You're doing everything in the=
    =20
    toplevel scope with up to four levels of nested "if"s, mostly communicating=
    =20
    via three more or less global variables. Try to break up the script into=20
    small bits. Stay with procedural for now, but break it up into functions of=
    =20
    at most 10 lines each, preferrably only around five. And try to give them=20
    some informative names, though not too long ones. The way your script is no=
    w,=20
    it's easy to forget which of those counters was doing what after I scroll=20
    past the comments describing that, and so on.

    David Vallner
     
    David Vallner, Feb 13, 2006
    #9
  10. --oyUTqETQ0mS9luUI
    Content-Type: text/plain; charset=us-ascii
    Content-Disposition: inline
    Content-Transfer-Encoding: quoted-printable

    On Tue, Feb 14, 2006 at 03:13:25AM +0900, frank wrote:
    > But it seems like there is a huge gulf between my procedural
    > thinking and an OO thinking with regard to this tree structure. How
    > would you represent a linked list in Ruby?


    Why do you really want a "linked list"? Just use an Array and stop
    worrying about how it's implemented. This is an example of thinking
    too low-level.

    But more importantly, why use lists at all to represent a tree? Why
    not just build a tree? Trees are recursive. Your data structure
    isn't. No wonder the code to navigate it is complicated. I would go
    farther and say that your parser should probably be recursive too.

    Your problem is not with "OO" vs "procedural" thinking. I'd say it's
    more "low-level abstractions" vs "high-level abstractions". =20

    And even if this code was translated to C, I'd still consider it
    wrong, because you've chosen the wrong structures. It's just that
    Ruby is such a clear languages it makes bad choices more painfully
    obvious.

    Learning to think recursively isn't easy, but it's incredibly valuable
    for solving problems like this.

    best regards,
    Ed

    --oyUTqETQ0mS9luUI
    Content-Type: application/pgp-signature; name="signature.asc"
    Content-Description: Digital signature
    Content-Disposition: inline

    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.4.1 (GNU/Linux)

    iD8DBQFD8NX6nhUz11p9MSARAsrKAKCSMGR5kwZYnQrMBfWMoXsd1iAgzwCfYoQX
    buci5HVx8mznOqcvB3POQ0c=
    =NVAw
    -----END PGP SIGNATURE-----

    --oyUTqETQ0mS9luUI--
     
    Edward Faulkner, Feb 13, 2006
    #10
  11. frank

    frank Guest

    Okay, I'll break the code into small bits. Thanks for the guidance.
    If you don't mind me keeping you posted that would be great.

    Best,
    Frank
     
    frank, Feb 13, 2006
    #11
  12. frank

    Alan Chen Guest

    You might look at the Ruby Graph Library
    (http://rubyforge.org/projects/rgl/) for inspiration, or just to use as
    a library to implement your algorithm. The RGL takes a lot of OO design
    cues from the C++ Boost Graph Library. The BGL is pretty robust, but
    unless you're into C++, the code can be difficult to read -- especially
    if you're trying to extract some understanding of the design.

    Good luck,
    - alan
     
    Alan Chen, Feb 13, 2006
    #12
  13. > How would you represent a linked list in Ruby?

    Like David said, probably not at all, using Array.

    BUT... just for grins (and to actually, honest to god, learn about one
    of those nifty data structures I always had abstracted out for me in
    other languages) when I first picked up Ruby a few weeks back I decided
    to implement a non-Array-based linked list.

    Looking back over it, it's ugly as hell and I'd probably do quite a bit
    of it differently now. But as a learning exercise in Ruby it taught me a
    fair bit. Especially when I pulled the node traversal out into a
    separate method to pass blocks into.

    (Speaking of ugly, it appears in my haste I made a node traversal nested
    inside a node traversal, for absolutely no good reason. Ick.)

    So, purely for BS fun, here's my crappy non-Array linked list, in all
    it's ugly glory.

    -dave

    =====linkedlist.rb
    #########################################################
    class Node
    attr_reader :name
    attr_accessor :next

    def initialize(name)
    @name = name
    end

    def to_s
    @name
    end

    end


    #########################################################
    class LinkedList

    attr_reader :length

    def initialize()
    @headNode = nil
    @tailNode = nil
    @length = 0
    end

    # Returns the first node in the list.
    def head
    @headNode
    end

    # Returns the last node in the list.
    def tail
    @tailNode
    end

    # Adds a new node to the list.
    # If no nodes exist, sets the root node and last
    # node to the new node.
    # If nodes exist, appends to the last node and
    # resets the last node to the new node.
    def add(aNode)
    if !@headNode
    @headNode = aNode
    @tailNode = @headNode
    else
    @tailNode.next = aNode
    @tailNode = @tailNode.next
    end
    @length += 1
    end

    # Deletes the node from the list that matches
    # the node passed in, and return it.
    # Match is based on object.id equality.
    def delete(aNode)
    prev, curr = nil
    traverse do |node|
    prev, curr = curr, node
    if node === aNode
    # need to rewire the prev/next if they exist
    if prev and curr.next
    prev.next = curr.next
    else
    prev = nil # deleting head node
    end
    # reset head and tail nodes
    # TODO: This is SLOPPY and should be re-written
    # TEST: Run this way with 1m nodes, then re-write
    # and re-run test, checking performance gain
    # from not re-iterating over all nodes with
    # each delete
    traverse do |node|

    end
    @length -= 1
    return curr
    end
    end
    end

    # Iterates over all nodes starting at root
    # and yields each node encountered.
    def traverse
    currNode = @headNode
    yield(currNode) # have to yeild the first node first
    if !(@headNode === @tailNode)
    while currNode.next
    currNode = currNode.next
    yield(currNode)
    end
    end
    end

    def shownodes
    traverse { |node| print node, (node.next ? " -> " : "\n") }
    end

    end # LinkedList



    ########################################################


    list = LinkedList.new

    n1 = Node.new("node1")
    n2 = Node.new("node2")
    n3 = Node.new("node3")
    n4 = Node.new("node4")

    puts "adding nodes"
    p list.length
    list.add n1
    list.add n2
    list.add n3
    list.add n4
    p list.length

    list.shownodes


    puts "deleting nodes"
    puts list.delete(n3)
    puts list.delete(n1)
    puts list.delete(n2)
    puts list.delete(n4)

    list.shownodes
     
    Dave Cantrell, Feb 15, 2006
    #13
  14. frank

    frank Guest

    Thanks Dave, I'll look this over as I continue to modify my code.

    -
     
    frank, Feb 15, 2006
    #14
  15. frank wrote:
    > Thanks Dave, I'll look this over as I continue to modify my code.
    >


    I really wouldn't use that for anything other than what it was: my first
    real attempt to write a linked list that was exactly that, not
    implemented as an array. Arrays are native (and I presume implemented in
    C?) and will have *far* better performance than anything we create
    ourselves.

    As others said, I think you'd be better off approaching the problem
    domain from scratch using The Ruby Way(tm) rather than trying to port C
    code into Ruby. Ugly C code makes ugly Ruby code, or ugly any other
    code, regardless. :(

    Good luck!
    -dave
     
    Dave Cantrell, Feb 15, 2006
    #15
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    2
    Views:
    529
  2. shawn

    tree structures

    shawn, Mar 7, 2006, in forum: Java
    Replies:
    3
    Views:
    432
    shawn
    Mar 7, 2006
  3. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,200
  4. tweak
    Replies:
    14
    Views:
    2,814
    Eric Sosman
    Jun 11, 2004
  5. Alfonso Morra
    Replies:
    11
    Views:
    740
    Emmanuel Delahaye
    Sep 24, 2005
Loading...

Share This Page