Recursive TreeStore problem

taintedsushi · March 11, 2009, 12:55pm

I’ve built this recursive bit of code to take an array of arrays and
create a treestore from it. It seems to do what it supposed to do
except, child nodes are not appended to parent nodes. I suspect it has
something to do with passing the “new” (treestore.append()) value. Any
help would be appreciated.

def add_nodes(treestore, parent_id, parent)
0.upto(@gallerybox.length-1) do |i|
if t.to_i == parent_id
new = treestore.append(parent)
new[0] = @gallerybox[i][0].to_i
new[1] = @gallerybox[i][1].to_i
new[2] = @gallerybox[i][2]
new[3] = @gallerybox[i][3]
add_nodes(treestore, @gallerybox[i][0], new)
puts “new node done”
end
end
end

taintedsushi · March 11, 2009, 4:25pm

Ok, I’m an idiot. Trying to make something simple hard…Here’s the
solution :

def populate_tree(node, parentid)
@gallerybox.each { |gallery|
id=gallery[0].to_i
parent=gallery[1].to_i
name=gallery[2]
created = gallery[3]
if parent == parentid
[email protected](node)
child[0] = id
child[1] = parent
child[2] = name
child[3] = created
populate_tree(child, id)
end
}
end

taintedsushi · March 11, 2009, 5:28pm

Miles K. wrote:

Ok, I’m an idiot. Trying to make something simple hard…Here’s the
solution :

def populate_tree(node, parentid)
@gallerybox.each { |gallery|
id=gallery[0].to_i
parent=gallery[1].to_i
name=gallery[2]
created = gallery[3]
if parent == parentid
[email protected](node)
child[0] = id
child[1] = parent
child[2] = name
child[3] = created
populate_tree(child, id)
end
}
end

Though your {{ if parent == parentid }} looks problematic, assuming it
would, when fixed identify parent nodes properly, unless you have
created parents elsewhere, I suggest you do the following:

def populate_tree(node, parentid)
@gallerybox.each do |gallery|
if parent == parentid
[email protected](nil)
child[0] = gallery[0].to_i
child[1] = gallery[1].to_i
child[2] = gallery[2]
child[3] = gallery[3]
populate_tree(child, id)
else
[email protected](node)
child[0] = gallery[0].to_i
child[1] = gallery[1].to_i
child[2] = gallery[2]
child[3] = gallery[3]
populate_tree(child, id)
end
end
end

taintedsushi · March 11, 2009, 6:21pm

Sorry for repeating my post but this is more eligible and better reveals
some issues earlier hidden:

def populate_tree(node, parentid)
@gallerybox.each do |gallery|
if parent_identification == parentid
parent = @treestore.append(nil)
parent[0] = gallery[0].to_i
parent[1] = gallery[1].to_i
parent[2] = gallery[2]
parent[3] = gallery[3]
populate_tree(parent, id)
else
child = @treestore.append(node)
child[0] = gallery[0].to_i
child[1] = gallery[1].to_i
child[2] = gallery[2]
child[3] = gallery[3]
populate_tree(child, id)
end
end
end

However, I still do have an issue with {{ if parent_identification ==
parentid }}. I have tested this recursive method in a full-blown
Ruby/Gtk GUI application and it works fine.

Cheers, Igor

taintedsushi · March 11, 2009, 6:09pm

Igor P. wrote:

Though your {{ if parent == parentid }} looks problematic, assuming it
would, when fixed identify parent nodes properly, unless you have
created parents elsewhere, I suggest you do the following:

def populate_tree(node, parentid)
@gallerybox.each do |gallery|
if parent == parentid
[email protected](nil)
child[0] = gallery[0].to_i
child[1] = gallery[1].to_i
child[2] = gallery[2]
child[3] = gallery[3]
populate_tree(child, id)
else
[email protected](node)
child[0] = gallery[0].to_i
child[1] = gallery[1].to_i
child[2] = gallery[2]
child[3] = gallery[3]
populate_tree(child, id)
end
end
end

I have a mysql table like :

key_id
parent_id
data
created

gallerybox is an array of rows of this table.

parent in the code refers to parent_id from this table
and parentid is the key_id.

Initially I pass ( 0,nil ) to this function so that the inital pass
builds the root level of the tree, the recursive builds all lower
levels.

Perhaps my variable naming is poor but I think the original method
works.

taintedsushi · March 11, 2009, 6:25pm

    [email protected](node)
    child[0] = gallery[0].to_i
    child[1] = gallery[1].to_i
    child[2] = gallery[2]
    child[3] = gallery[3]
    populate_tree(child, id)
 end

end
end

Any reason to duplicate so much code? I routinely hurt my eyes,
nowadays…

def populate_tree(node, parentid)
@gallerybox.each do |gallery|
[email protected](parent == parentid ? nil : node)
child[0] = gallery[0].to_i
child[1] = gallery[1].to_i
child[2] = gallery[2]
child[3] = gallery[3]
populate_tree(child, id)
end
end

–
Guillaume C. - Guillaume Cottenceau

taintedsushi · March 11, 2009, 6:29pm

Miles K. wrote:

Initially I pass ( 0,nil ) to this function so that the inital pass
builds the root level of the tree, the recursive builds all lower
levels.

You may have multiple root levels each with its own children. Look at
the example in Ruby/Gtk tutorial at
http://ruby-gnome2.sourceforge.jp/hiki.cgi?tut-gtk2-treev-trees, where
“Cleaning supplies” and “Food” rows represent root levels. In fact I
have tested your recursive method in this application.

taintedsushi · March 11, 2009, 6:31pm

Guillaume C. wrote:

Any reason to duplicate so much code? I routinely hurt my eyes,
nowadays…

def populate_tree(node, parentid)
@gallerybox.each do |gallery|
[email protected](parent == parentid ? nil : node)
child[0] = gallery[0].to_i
child[1] = gallery[1].to_i
child[2] = gallery[2]
child[3] = gallery[3]
populate_tree(child, id)
end
end

True enough. I should have cleaned that up a bit. Verbosity sometimes
helps me think through things.

Cheers.

taintedsushi · March 11, 2009, 6:34pm

Igor P. wrote:

Look at the example in Ruby/Gtk tutorial at
http://ruby-gnome2.sourceforge.jp/hiki.cgi?tut-gtk2-treev-trees, where
“Cleaning supplies” and “Food” rows represent root levels. In fact I
have tested your recursive method in this application.

Comma, at the end of the link should be avoided, so try this:
http://ruby-gnome2.sourceforge.jp/hiki.cgi?tut-gtk2-treev-trees

taintedsushi · March 11, 2009, 9:00pm

Miles K. wrote:

def populate_tree(node, parentid)
@gallerybox.each do |gallery|
[email protected](parent == parentid ? nil : node)
child[0] = gallery[0].to_i
child[1] = gallery[1].to_i
child[2] = gallery[2]
child[3] = gallery[3]
populate_tree(child, id)
end
end

I was so excited about your “recursive invention” that I wanted to
publish it on Ruby/Gtk2 tutorial web page, and in the process of doing
so I discovered I was not really testing the recursive call with your
populate_tree, which is in fact wrong, because the way you wrote it
makes it an infinite, never-ending recursion. I actually tested the
following strategy:

def populate_tree(parent, parentid)
@gallerybox.each do |gallery|
if parent_identification == parentid
parent = @treestore.append(nil)
parent[0] = gallery[0].to_i
parent[1] = gallery[1].to_i
parent[2] = gallery[2]
parent[3] = gallery[3]
else
child = @treestore.append(parent)
child[0] = gallery[0].to_i
child[1] = gallery[1].to_i
child[2] = gallery[2]
child[3] = gallery[3]
end
end
end

I do believe your code would not work properly even if you take the
recursive call out. You have to retain the value of the last iterator
value across the block iterations and you are loosing that by creating a
block local variable “child”. You need to either use method’s parameter
like in my example (parent), or you need to define {{ parent = child =
nil }} before entering the block.

And most importantly, your “shortened” or as you say “cleaned-up”
version will also not work properly with multiple root rows, because you
are overriding parent iterators by child iterators. Iterators are
references and by doing what you are doing, you make them point to the
same data items.

I do not exactly know how the internals of Gtk::TreeStore work here,
but clearly we have something like the following problem with references
and multi-dimensional arrays:

Again, sorry for my part of the slip.

taintedsushi · March 11, 2009, 9:48pm

Hi Igor,

The recursive function does work given my data set. The mysql table
that I am drawing from already contains the parent/child relationships.

Table :

[ INDEX ] [ PARENT ] [ DATA ]
1 0 food >> ROOT Category
2 1 cheeses >> Sub-Category
3 2 cheddar >> Item 1
4 2 brie >> Item 2
5 0 beverages >> ROOT Category

and so forth.

Does this clear it up at all?

taintedsushi · March 12, 2009, 2:35am

Miles K. wrote:

The recursive function does work given my data set. The mysql table
that I am drawing from already contains the parent/child relationships.

Table :

[ INDEX ] [ PARENT ] [ DATA ]
1 0 food >> ROOT Category
2 1 cheeses >> Sub-Category
3 2 cheddar >> Item 1
4 2 brie >> Item 2
5 0 beverages >> ROOT Category

and so forth.

Does this clear it up at all?

Hi Miles,

After what you have said now it does look that recursion is the best
strategy to solve this algorithm. However you are growing it on me
gradually. First you didn’t even consider multiple root records, and
from your last post it is clear that you have not only multiple root
records but multiple levels of indentation, i.e. not only
two-dimensional Gtk::TreeStore structure but a multi-dimensional one.

And so I come back to my very first objection, which is your condition
that when looked at superficially seemed to only determine the root
nodes, but is actually the controlling mechanism for the recursion. You
should have given more precise definition of what was only a
hypothetical pseudo-code like condition “if t.to_i == parent_id”.

The second issue you have here is the problem which I have already
covered extensively, and would show up only when you actually run a GUI
application, where you would either get root and children nodes properly
indented, or you would only get a two-dimensional layout!

Third minor problem which, indeed, can be programmatically accounted
for, is with your list notation. Your [ INDEX ] [ PARENT ] [ DATA ]
should actually look something like the following:

[ INDEX ] [ PARENT ] [ DATA ]
0, 0, “food” >> ROOT Category
1, 1, “cheeses” >> Sub-Category
2, 1, “cheddar” >> Item 1
3, 1, “brie” >> Item 1
4, 4, “beverages” >> ROOT Category
5, 5, “non-alcohol” >> Sub-Category
6, 5, “pepsi” >> Item 1
7, 5, “coke” >> Item 1
8, 4, “alcoholic” >> Sub-Category
9, 8, “wine” >> Item 1
10, 8, “brandy” >> Item 1

I am really interested to see how you actually handled the problematic
recursion terminating condition.

Cheers, Igor

taintedsushi · March 12, 2009, 3:14am

Igor P. wrote:

Ooops, that’ll do:

[ INDEX ] [ PARENT ] [ DATA ]
0, 0, “food” >> ROOT Category
1, 0, “cheeses” >> Sub-Category
2, 1, “cheddar” >> Item 1
3, 1, “brie” >> Item 2
4, 4, “beverages” >> ROOT Category
5, 4, “non-alcohol” >> Sub-Category
6, 5, “pepsi” >> Item 1
7, 5, “coke” >> Item 2
8, 4, “alcoholic” >> Sub-Category
9, 8, “wine” >> Item 1
10, 8, “brandy” >> Item 2

Hey Igor,

I think I get where you’re coming from now. Let me see if we can’t
straighten this out.

The list notation is purely illustrative and represented the way my data
is stored. It is important to note that the data is derived from a
mysql table. The index is a self incrementing value that is generated
by mysql as the key for the table. It will never begin at zero. If it
were however, you are correct that it would endlessly repeat.

That being said, the above data set should be modified to reflect these
two changes.

[Index] needs to start at 1 and increment from there.
the parent of “beverages” cannot be itself in order to be a Root
Category. The parent of beverages would need to be 0.

Other than that, it would work fine.

–Miles

taintedsushi · March 12, 2009, 10:13am

Miles K. wrote:

I think I get where you’re coming from now. Let me see if we can’t
straighten this out.

The list notation is purely illustrative and represented the way my data
is stored. It is important to note that the data is derived from a
mysql table. The index is a self incrementing value that is generated
by mysql as the key for the table. It will never begin at zero. If it
were however, you are correct that it would endlessly repeat.

That being said, the above data set should be modified to reflect these
two changes.

[Index] needs to start at 1 and increment from there.

the parent of “beverages” cannot be itself in order to be a Root
Category. The parent of beverages would need to be 0.

Other than that, it would work fine.

Hi Miles,

I agree, with your last and second point, namely root for beverages
should be 0 (I made a hasty mistake there), but I do not entirely agree
with your first point though it is not a fatal problem and can be
accommodated in a programmatic way. Strictly speaking index does start
with zero and is logically the top root node, in fact, that is why you
start your recursion with the nil parameter for the first node or
iteration.

It was fun talking to you!
Igor

taintedsushi · March 12, 2009, 2:39am

Ooops, that’ll do:

[ INDEX ] [ PARENT ] [ DATA ]
0, 0, “food” >> ROOT Category
1, 0, “cheeses” >> Sub-Category
2, 1, “cheddar” >> Item 1
3, 1, “brie” >> Item 2
4, 4, “beverages” >> ROOT Category
5, 4, “non-alcohol” >> Sub-Category
6, 5, “pepsi” >> Item 1
7, 5, “coke” >> Item 2
8, 4, “alcoholic” >> Sub-Category
9, 8, “wine” >> Item 1
10, 8, “brandy” >> Item 2