Velocity Reviews > Ruby > tree structures

# tree structures

frank
Guest
Posts: n/a

 02-13-2006
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
Guest
Posts: n/a

 02-13-2006
"just" looked at Bob's work, acts_as_threaded.

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

-Nb

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

> -----Original Message-----
> From: frank [(E-Mail Removed)]
> 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
>
>

David Vallner
Guest
Posts: n/a

 02-13-2006
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
Ruby. (Did I just make a pun?)

# A node of a binary tree.
class Node
attr_accessor :value
attr_accessor arent

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

frank
Guest
Posts: n/a

 02-13-2006
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

David Vallner
Guest
Posts: n/a

 02-13-2006
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

Gene Tani
Guest
Posts: n/a

 02-13-2006

frank wrote:
> Hi,
>
> I have been using ruby for a few months now and am writing a program
> that duplicates portions of a tree structure.
>

this is a good discussion (from Ruby Way, by Hal Fulton)

http://www.informit.com/articles/art...26943&seqNum=5

James Edward Gray II
Guest
Posts: n/a

 02-13-2006
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

frank
Guest
Posts: n/a

 02-13-2006
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

-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] == '(' && 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] == '(' && 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

.......

David Vallner
Guest
Posts: n/a

 02-13-2006
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
>

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

Edward Faulkner
Guest
Posts: n/a

 02-13-2006
--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)

iD8DBQFD8NX6nhUz11p9MSARAsrKAKCSMGR5kwZYnQrMBfWMoX sd1iAgzwCfYoQX
buci5HVx8mznOqcvB3POQ0c=
=NVAw
-----END PGP SIGNATURE-----

--oyUTqETQ0mS9luUI--