Forum: Ruby tree structures

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
26bbdb609f9c721b929204fdbe123a1e?d=identicon&s=25 frank (Guest)
on 2006-02-13 03:38
(Received via mailing list)
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
00e3a96684ab390a350b0271e98741d3?d=identicon&s=25 Nshbrown Nshbrown (nshb)
on 2006-02-13 03:44
(Received via mailing list)
"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-a...

-Nb

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 Nathaniel S. H. Brown                           http://nshb.net
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
430ea1cba106cc65b7687d66e9df4f06?d=identicon&s=25 David Vallner (Guest)
on 2006-02-13 04:12
(Received via mailing list)
Hmm. To be very, very, very frank, If I wanted binary trees for
something, I'd
let the Berkeley DB do this for me. There's people way better at making
efficient data structures out there.

DÅ?a Pondelok 13 Február 2006 03:38 frank napísal:
> 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
shouldn't matter anyway. Ruby has by-reference semantics, variables hold
references to objects. Which isn't -quite- true, but let's say it is for
now.

Classes are your friends. But I'll let the code do the talking. If you
find
you don't understand something, I recommend you read the Pickaxe book,
available for free online in the first edition, which is probably enough
for
now. As a matter of fact, you should read it anyway, with nothing
insulting
in mind, you have a little to learn about this gem of a language that is
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=(node)
			@left = node
			left.parent = self
		end

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

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

		def initialize(new_value = nil)
			self.value = 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
26bbdb609f9c721b929204fdbe123a1e?d=identicon&s=25 frank (Guest)
on 2006-02-13 04:33
(Received via mailing list)
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
430ea1cba106cc65b7687d66e9df4f06?d=identicon&s=25 David Vallner (Guest)
on 2006-02-13 04:43
(Received via mailing list)
DÅ?a Pondelok 13 Február 2006 04:33 frank napísal:
> 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
by-value semantics into a strongly OO, interpreted, dynamically typed
one
with by-reference ones?

Yah right.

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

David Vallner
9dfe8c734b0f9b37a4e218425c0a2138?d=identicon&s=25 Gene Tani (Guest)
on 2006-02-13 06:03
(Received via mailing list)
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/article.asp?p=269...
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2006-02-13 14:56
(Received via mailing list)
On Feb 12, 2006, at 8:38 PM, frank wrote:

> 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
26bbdb609f9c721b929204fdbe123a1e?d=identicon&s=25 frank (Guest)
on 2006-02-13 19:13
(Received via mailing list)
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] == '(' && 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



.......
430ea1cba106cc65b7687d66e9df4f06?d=identicon&s=25 David Vallner (Guest)
on 2006-02-13 19:46
(Received via mailing list)
DÅ?a Pondelok 13 Február 2006 19:13 frank napísal:
> 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
procedural and OO, except with encapsulation applying in the simpler
cases,
and abstract interfaces in the more complicated ones - the actual
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
data you will be storing, the standard Ruby Array will work well - it
does
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.

Now this is a tricky one. I could give my personal list of "recommended"
reading to see just where OO is significantly different from procedural,
but
I think that is a little out of your scope just now, and the basics,
which
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
> 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.
>

Actually, I don't think it's related to that. The code I posted, nearly
identical to the Ruby Way one, wasn't that advanced, it was just
granular -
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
pore over it to find out what's happening - if I'm correct, you're
trying to
read the tree structure from a string.

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

David Vallner
036a1b88dafaab8ffd73a8b0a74b5b38?d=identicon&s=25 Edward Faulkner (Guest)
on 2006-02-13 19:56
(Received via mailing list)
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".

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
26bbdb609f9c721b929204fdbe123a1e?d=identicon&s=25 frank (Guest)
on 2006-02-13 19:58
(Received via mailing list)
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
1affa5f0b72a1a76c8b72bc0ccc6f552?d=identicon&s=25 Alan Chen (Guest)
on 2006-02-13 23:24
(Received via mailing list)
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
D63c268960051bc17a310aa29fffd979?d=identicon&s=25 Dave Cantrell (Guest)
on 2006-02-15 06:36
(Received via mailing list)
> 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
26bbdb609f9c721b929204fdbe123a1e?d=identicon&s=25 frank (Guest)
on 2006-02-15 15:19
(Received via mailing list)
Thanks Dave,  I'll look this over as I continue to modify my code.

-
D63c268960051bc17a310aa29fffd979?d=identicon&s=25 Dave Cantrell (Guest)
on 2006-02-15 19:23
(Received via mailing list)
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
This topic is locked and can not be replied to.