displaying categories/subcategories using modified preorder tree transversal

[hornedw]

I have been working on a ecommerce website for myself. What I needed
some assistance on was when i was trying to display the
categories/subcategories for the different products.
I decided to use the modified preorder tree transversal algorithm. What
I wanted was on the first page is to display the catogories as follows

Books (35)
Electronics(23)

The number inside the parenthesis being the number of products in that
category. When Books is clicked on, it would display the following

Books(35)
Fiction(18)
Nonfiction(17)
Electronics(23)

In my MYSQL database table, I have the fields catid, name, lft and
rgt. For example for the three categories mentioned above I have the
following entries

catid name lft rgt
1 home 1 1
2 books 2 17
4 fiction 3 10
5 nonfiction 11 16
3 electronics 18 37


The first category home was just used to represent the main root of the
whole tree. If anyone could give me some assistance, it would be much
appreciated. Thank you in advance.

[hornedw]

Re: displaying categories/subcategories using modified preorder tree transversal

the category table should look like the following. it did not display
very well in the first message

catid, name,lft,rgt
1, home,1,1
2, books,2,17
4, fiction,3,10
5, nonfiction, 11,16
3, electronics,18, 37






hornedw wrote:

I have been working on a ecommerce website for myself. What I needed
some assistance on was when i was trying to display the
categories/subcategories for the different products.
I decided to use the modified preorder tree transversal algorithm. What
I wanted was on the first page is to display the catogories as follows
>
Books (35)
Electronics(23)
>
The number inside the parenthesis being the number of products in that
category. When Books is clicked on, it would display the following
>
Books(35)
Fiction(18)
Nonfiction(17)
Electronics(23)
>
In my MYSQL database table, I have the fields catid, name, lft and
rgt. For example for the three categories mentioned above I have the
following entries
>
catid name lft rgt
1 home 1 1
2 books 2 17
4 fiction 3 10
5 nonfiction 11 16
3 electronics 18 37
>
>
The first category home was just used to represent the main root of the
whole tree. If anyone could give me some assistance, it would be much
appreciated. Thank you in advance.

[Jerry Stuckle]

Re: displaying categories/subcategories using modified preorder treetransversal

hornedw wrote:

the category table should look like the following. it did not display
very well in the first message
>
catid, name,lft,rgt
1, home,1,1
2, books,2,17
4, fiction,3,10
5, nonfiction, 11,16
3, electronics,18, 37
>
>
>
>
>
>
hornedw wrote:
>

>>I have been working on a ecommerce website for myself. What I needed
>>some assistance on was when i was trying to display the
>>categories/subcategories for the different products.
>>I decided to use the modified preorder tree transversal algorithm. What
>>I wanted was on the first page is to display the catogories as follows
>>
>>Books (35)
>>Electronics(2 3)
>>
>>The number inside the parenthesis being the number of products in that
>>category. When Books is clicked on, it would display the following
>>
>>Books(35)
> Fiction(18)
> Nonfiction(17)
>>Electronics(2 3)
>>
>>In my MYSQL database table, I have the fields catid, name, lft and
>>rgt. For example for the three categories mentioned above I have the
>>following entries
>>
>>catid name lft rgt
>>1 home 1 1
>>2 books 2 17
>>4 fiction 3 10
>>5 nonfiction 11 16
>>3 electronics 18 37
>>
>>
>>The first category home was just used to represent the main root of the
>>whole tree. If anyone could give me some assistance, it would be much
>>appreciated . Thank you in advance.

>
>

I guess I'm confused. How do you link from "fiction" or "nonfiction " to
books?

This way of doing it looks quite confusing to me.


--
=============== ===
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstucklex@attgl obal.net
=============== ===

[hornedw]

Re: displaying categories/subcategories using modified preorder tree transversal

Jerry

I was trying to set it up where when a person clicks on books the page
would reload and then display Books and then Nonfiction and Fiction
would appear under it. Like below
Books (35)
Electronics(23)

The number inside the parenthesis being the number of products in that
category. When Books is clicked on, it would display the following
Books(35)
Fiction(18)
Nonfiction(17)
Electronics(23)

It does not necessaryly have to be spaced over. I may use bulleted list
or something like that. The main two things I was trying to do was use
the modfied preorder tree algorithm and to have it display the main
category and then display the main category and its subcategories and
then the rest of the categories on the page. I was debating on whether
doing it this way or something similar to the way it is done at
Amazon.com on their categories.

David
Jerry Stuckle wrote:

hornedw wrote:

the category table should look like the following. it did not display
very well in the first message

catid, name,lft,rgt
1, home,1,1
2, books,2,17
4, fiction,3,10
5, nonfiction, 11,16
3, electronics,18, 37






hornedw wrote:

>I have been working on a ecommerce website for myself. What I needed
>some assistance on was when i was trying to display the
>categories/subcategories for the different products.
>I decided to use the modified preorder tree transversal algorithm. What
>I wanted was on the first page is to display the catogories as follows
>
>Books (35)
>Electronics(23 )
>
>The number inside the parenthesis being the number of products in that
>category. When Books is clicked on, it would display the following
>
>Books(35)
Fiction(18)
Nonfiction(17)
>Electronics(23 )
>
>In my MYSQL database table, I have the fields catid, name, lft and
>rgt. For example for the three categories mentioned above I have the
>following entries
>
>catid name lft rgt
>1 home 1 1
>2 books 2 17
>4 fiction 3 10
>5 nonfiction 11 16
>3 electronics 18 37
>
>
>The first category home was just used to represent the main root of the
>whole tree. If anyone could give me some assistance, it would be much
>appreciated. Thank you in advance.

>
I guess I'm confused. How do you link from "fiction" or "nonfiction " to
books?
>
This way of doing it looks quite confusing to me.
>
>
--
=============== ===
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstucklex@attgl obal.net
=============== ===

[Jerry Stuckle]

Re: displaying categories/subcategories using modified preorder treetransversal

hornedw wrote:

Jerry
>
I was trying to set it up where when a person clicks on books the page
would reload and then display Books and then Nonfiction and Fiction
would appear under it. Like below
Books (35)
Electronics(23)
>
The number inside the parenthesis being the number of products in that
category. When Books is clicked on, it would display the following
Books(35)
Fiction(18)
Nonfiction(17)
Electronics(23)
>
It does not necessaryly have to be spaced over. I may use bulleted list
or something like that. The main two things I was trying to do was use
the modfied preorder tree algorithm and to have it display the main
category and then display the main category and its subcategories and
then the rest of the categories on the page. I was debating on whether
doing it this way or something similar to the way it is done at
Amazon.com on their categories.
>
David
Jerry Stuckle wrote:
>

>>hornedw wrote:
>>

>>>the category table should look like the following. it did not display
>>>very well in the first message
>>>
>>>catid, name,lft,rgt
>>>1, home,1,1
>>>2, books,2,17
>>>4, fiction,3,10
>>>5, nonfiction, 11,16
>>>3, electronics,18, 37
>>>
>>>
>>>
>>>
>>>
>>>
>>>hornedw wrote:
>>>
>>>
>>>>I have been working on a ecommerce website for myself. What I needed
>>>>some assistance on was when i was trying to display the
>>>>categorie s/subcategories for the different products.
>>>>I decided to use the modified preorder tree transversal algorithm. What
>>>>I wanted was on the first page is to display the catogories as follows
>>>>
>>>>Books (35)
>>>>Electronics (23)
>>>>
>>>>The number inside the parenthesis being the number of products in that
>>>>category. When Books is clicked on, it would display the following
>>>>
>>>>Books(35)
>>>Fiction(18 )
>>>Nonfiction(1 7)
>>>>Electronics (23)
>>>>
>>>>In my MYSQL database table, I have the fields catid, name, lft and
>>>>rgt. For example for the three categories mentioned above I have the
>>>>following entries
>>>>
>>>>catid name lft rgt
>>>>1 home 1 1
>>>>2 books 2 17
>>>>4 fiction 3 10
>>>>5 nonfiction 11 16
>>>>3 electronics 18 37
>>>>
>>>>
>>>>The first category home was just used to represent the main root of the
>>>>whole tree. If anyone could give me some assistance, it would be much
>>>>appreciated . Thank you in advance.
>>>
>>>

>>I guess I'm confused. How do you link from "fiction" or "nonfiction " to
>>books?
>>
>>This way of doing it looks quite confusing to me.
>>
>>
>>--
>>============= =====
>>Remove the "x" from my email address
>>Jerry Stuckle
>>JDS Computer Training Corp.
>>jstucklex@att global.net
>>============= =====

>
>

Yes, I'm aware of what you're trying to do. What I'm confused about is
how, from the information you provided, the system is supposed to know
that fiction and nonfiction fall under books. The example you have
doesn't show any way to determine if something is a top level category
or a subcategory - and if the latter, which is its parent category.

P.S. Please don't top post.

--
=============== ===
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstucklex@attgl obal.net
=============== ===

[hornedw]

Re: displaying categories/subcategories using modified preorder tree transversal


Jerry Stuckle wrote:

hornedw wrote:

Jerry

I was trying to set it up where when a person clicks on books the page
would reload and then display Books and then Nonfiction and Fiction
would appear under it. Like below
Books (35)
Electronics(23)

The number inside the parenthesis being the number of products in that
category. When Books is clicked on, it would display the following
Books(35)
Fiction(18)
Nonfiction(17)
Electronics(23)

It does not necessaryly have to be spaced over. I may use bulleted list
or something like that. The main two things I was trying to do was use
the modfied preorder tree algorithm and to have it display the main
category and then display the main category and its subcategories and
then the rest of the categories on the page. I was debating on whether
doing it this way or something similar to the way it is done at
Amazon.com on their categories.

David
Jerry Stuckle wrote:

>hornedw wrote:
>
>>the category table should look like the following. it did not display
>>very well in the first message
>>
>>catid, name,lft,rgt
>>1, home,1,1
>>2, books,2,17
>>4, fiction,3,10
>>5, nonfiction, 11,16
>>3, electronics,18, 37
>>
>>
>>
>>
>>
>>
>>hornedw wrote:
>>
>>
>>>I have been working on a ecommerce website for myself. What I needed
>>>some assistance on was when i was trying to display the
>>>categories/subcategories for the different products.
>>>I decided to use the modified preorder tree transversal algorithm. What
>>>I wanted was on the first page is to display the catogories as follows
>>>
>>>Books (35)
>>>Electronics( 23)
>>>
>>>The number inside the parenthesis being the number of products in that
>>>category. When Books is clicked on, it would display the following
>>>
>>>Books(35)
>>Fiction(18)
>>Nonfiction(17 )
>>>Electronics( 23)
>>>
>>>In my MYSQL database table, I have the fields catid, name, lft and
>>>rgt. For example for the three categories mentioned above I have the
>>>following entries
>>>
>>>catid name lft rgt
>>>1 home 1 1
>>>2 books 2 17
>>>4 fiction 3 10
>>>5 nonfiction 11 16
>>>3 electronics 18 37
>>>
>>>
>>>The first category home was just used to represent the main root of the
>>>whole tree. If anyone could give me some assistance, it would be much
>>>appreciate d. Thank you in advance.
>>
>>
>I guess I'm confused. How do you link from "fiction" or "nonfiction " to
>books?
>
>This way of doing it looks quite confusing to me.
>
>
>--
>============== ====
>Remove the "x" from my email address
>Jerry Stuckle
>JDS Computer Training Corp.
>jstucklex@attg lobal.net
>============== ====

>
Yes, I'm aware of what you're trying to do. What I'm confused about is
how, from the information you provided, the system is supposed to know
that fiction and nonfiction fall under books. The example you have
doesn't show any way to determine if something is a top level category
or a subcategory - and if the latter, which is its parent category.
>
P.S. Please don't top post.
>
--
=============== ===
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstucklex@attgl obal.net
=============== ===

I got most of my information from

http://dev.mysql.com/tech-resources/articles/hierarchical-data.html

Under the section where it says "Nested Set"

I will try to explain using the example I gave.

I noticed on my example that the rgt value for home should have been 38
Here is the datbase values I had in my previous post


catid, name,lft,rgt

>>1, home,1,38
>>2, books,2,17
>>4, fiction,3,10
>>5, nonfiction, 11,16
>>3, electronics,18, 37

Basically this algorithm sets up the data you are working in as a tree
diagram.Each block has a left and right value. You start on the left of
the root of the tree and go around the diagram and number the blocks. .
If the item has a child, you will number the parent's left value and
the child's left value. If the item is a child, you wll number the left
value and then go to the right value of the child. The difference
between the right and left value of a child is always 1. Once you have
given the child its right value, you will go back up the tree and give
the parent its right value Once you have reached the main parent under
the root, you go to the next main parent that is under the root. You
continue this until you have given the last main parent its right value
and then you give the root its right value.

In the example above, Home has the biggest difference between its right
and left values and therefore is the root. Books is the first main
parent category. The left and right values of fiction and nonfiction
fall between the left and right values of books. That is how books is
the parent category of fiction and nonfiction. Electronics is another
main category in the table. The list I gave above is not a full list
of al the categories and subcategories For example, I do not have any
child subcategories listed. I know this not a very good explanation,
but the website listed above may be of greater help of explaining what
I am trying to do.

David

[Jerry Stuckle]

Re: displaying categories/subcategories using modified preorder treetransversal

hornedw wrote:

Jerry Stuckle wrote:
>

>>hornedw wrote:
>>

>>>Jerry
>>>
>>>I was trying to set it up where when a person clicks on books the page
>>>would reload and then display Books and then Nonfiction and Fiction
>>>would appear under it. Like below
>>>Books (35)
>>>Electronics( 23)
>>>
>>>The number inside the parenthesis being the number of products in that
>>>category. When Books is clicked on, it would display the following
>>>Books(35)
>> Fiction(18)
>> Nonfiction(17)
>>>Electronics( 23)
>>>
>>>It does not necessaryly have to be spaced over. I may use bulleted list
>>>or something like that. The main two things I was trying to do was use
>>>the modfied preorder tree algorithm and to have it display the main
>>>category and then display the main category and its subcategories and
>>>then the rest of the categories on the page. I was debating on whether
>>>doing it this way or something similar to the way it is done at
>>>Amazon.com on their categories.
>>>
>>>David
>>>Jerry Stuckle wrote:
>>>
>>>
>>>>hornedw wrote:
>>>>
>>>>
>>>>>the category table should look like the following. it did not display
>>>>>very well in the first message
>>>>>
>>>>>catid, name,lft,rgt
>>>>>1, home,1,1
>>>>>2, books,2,17
>>>>>4, fiction,3,10
>>>>>5, nonfiction, 11,16
>>>>>3, electronics,18, 37
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>hornedw wrote:
>>>>>
>>>>>
>>>>>
>>>>>>I have been working on a ecommerce website for myself. What I needed
>>>>>>some assistance on was when i was trying to display the
>>>>>>categorie s/subcategories for the different products.
>>>>>>I decided to use the modified preorder tree transversal algorithm. What
>>>>>>I wanted was on the first page is to display the catogories as follows
>>>>>>
>>>>>>Books (35)
>>>>>>Electroni cs(23)
>>>>>>
>>>>>>The number inside the parenthesis being the number of products in that
>>>>>>categor y. When Books is clicked on, it would display the following
>>>>>>
>>>>>>Books(3 5)
>>>>>>Fiction(1 8)
>>>>>>Nonfictio n(17)
>>>>>>Electroni cs(23)
>>>>>>
>>>>>>In my MYSQL database table, I have the fields catid, name, lft and
>>>>>>rgt. For example for the three categories mentioned above I have the
>>>>>>followi ng entries
>>>>>>
>>>>>>catid name lft rgt
>>>>>>1 home 1 1
>>>>>>2 books 2 17
>>>>>>4 fiction 3 10
>>>>>>5 nonfiction 11 16
>>>>>>3 electronics 18 37
>>>>>>
>>>>>>
>>>>>>The first category home was just used to represent the main root of the
>>>>>>whole tree. If anyone could give me some assistance, it would be much
>>>>>>appreciat ed. Thank you in advance.
>>>>>
>>>>>
>>>>I guess I'm confused. How do you link from "fiction" or "nonfiction " to
>>>>books?
>>>>
>>>>This way of doing it looks quite confusing to me.
>>>>
>>>>
>>>>--
>>>>=========== =======
>>>>Remove the "x" from my email address
>>>>Jerry Stuckle
>>>>JDS Computer Training Corp.
>>>>jstucklex@a ttglobal.net
>>>>=========== =======
>>>
>>>

>>Yes, I'm aware of what you're trying to do. What I'm confused about is
>>how, from the information you provided, the system is supposed to know
>>that fiction and nonfiction fall under books. The example you have
>>doesn't show any way to determine if something is a top level category
>>or a subcategory - and if the latter, which is its parent category.
>>
>>P.S. Please don't top post.
>>
>>--
>>============= =====
>>Remove the "x" from my email address
>>Jerry Stuckle
>>JDS Computer Training Corp.
>>jstucklex@att global.net
>>============= =====

>
>
I got most of my information from

http://dev.mysql.com/tech-resources/articles/hierarchical-data.html

Under the section where it says "Nested Set"
>
I will try to explain using the example I gave.
>
I noticed on my example that the rgt value for home should have been 38
Here is the datbase values I had in my previous post
>
>
catid, name,lft,rgt
>

>>>>>1, home,1,38
>>>>>2, books,2,17
>>>>>4, fiction,3,10
>>>>>5, nonfiction, 11,16
>>>>>3, electronics,18, 37

>
>
>
Basically this algorithm sets up the data you are working in as a tree
diagram.Each block has a left and right value. You start on the left of
the root of the tree and go around the diagram and number the blocks. .
If the item has a child, you will number the parent's left value and
the child's left value. If the item is a child, you wll number the left
value and then go to the right value of the child. The difference
between the right and left value of a child is always 1. Once you have
given the child its right value, you will go back up the tree and give
the parent its right value Once you have reached the main parent under
the root, you go to the next main parent that is under the root. You
continue this until you have given the last main parent its right value
and then you give the root its right value.
>
In the example above, Home has the biggest difference between its right
and left values and therefore is the root. Books is the first main
parent category. The left and right values of fiction and nonfiction
fall between the left and right values of books. That is how books is
the parent category of fiction and nonfiction. Electronics is another
main category in the table. The list I gave above is not a full list
of al the categories and subcategories For example, I do not have any
child subcategories listed. I know this not a very good explanation,
but the website listed above may be of greater help of explaining what
I am trying to do.
>
David
>

David,

All I can say is - that has got to be one of the WORST implementations
I've ever seen. Talk about making a simple problem complex - this takes
the cake.

I wouldn't even try implementing something like this.

Rather, keep it simple:

id parent description
1 null books
2 1 nonfiction
3 1 fiction
4 null electronics

The only thing I'm not sure of is if MySQL will support recursive
queries - haven't tried it. If so, you can get your info in one sql
statement. Otherwise you'll have to do a little recursion in your PHP code.

--
=============== ===
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstucklex@attgl obal.net
=============== ===

[frothpoker]

Re: displaying categories/subcategories using modified preorder tree transversal

OK, back to the original problem....

I presume that when you select a node, you are actually having trouble
writing the SQL query to correctly return the higher level nodes as
showing....

Books
-->Fiction
-->-->Classic
-->-->Sci-Fi
-->NonFiction
Video

This is a perfect example of where javascript and CSS would be handy.
Why not return all the elements and contain each one within a <DIV>
with the visible poperty set to false and an onClick() event for the
parent category that sets the visible property of the child div to true
or false.

Obiron

[mootmail-googlegroups@yahoo.com]

Re: displaying categories/subcategories using modified preorder tree transversal

Jerry Stuckle wrote:

All I can say is - that has got to be one of the WORST implementations
I've ever seen. Talk about making a simple problem complex - this takes
the cake.
>
I wouldn't even try implementing something like this.
>
Rather, keep it simple:
>
id parent description
1 null books
2 1 nonfiction
3 1 fiction
4 null electronics
>

At first glance, something like a preorder-tree traversal setup is
needlessly complex. I agree that the example you provided is much
easier to visualize conceptually.

I agree because I have made that mistake in the past. We had a project
that involved massive trees (we're talking the bill of materials for an
entire automobile down to an individual screw), and went with the
simple 'parent' scheme, but were too deep into the project before we
suddenly regretted it. A scheme like that is easy to set up, but a
nightmare to use and maintain.

To get a node and its children from the example you gave (known as the
Adjacency model), you have to rely either on recursion or knowing
exactly how many levels exist. The former introduces significant
overhead while the latter is just bad hard-coding. Using a more
advanced tree algorithm allows for a much easier time working with
nodes and children. The link provided earlier
(http://dev.mysql.com/tech-resources/...ical-data.html)
is a great resource for seeing the different queries required to work
with either scheme.

I doubt the OP will be dealing with trees quite as large as the ones I
needed to use, but if you can deal with a bit of complexity up front,
you can save yourself a lot of extra work later on.

And speaking of the original post...I didn't quite understand what you
were asking. If you were asking for advice on getting the # of items
in each category, perhaps you could use the examples on that page
linked to for getting all the children of a node, and then WHERE'ing it
to include only those nodes whose lft & rgt are 1 apart (meaning they
have no children).

[Jerry Stuckle]

Re: displaying categories/subcategories using modified preorder treetransversal

mootmail-googlegroups@ya hoo.com wrote:

Jerry Stuckle wrote:
>

>>All I can say is - that has got to be one of the WORST implementations
>>I've ever seen. Talk about making a simple problem complex - this takes
>>the cake.
>>
>>I wouldn't even try implementing something like this.
>>
>>Rather, keep it simple:
>>
> id parent description
> 1 null books
> 2 1 nonfiction
> 3 1 fiction
> 4 null electronics
>>

>
>
At first glance, something like a preorder-tree traversal setup is
needlessly complex. I agree that the example you provided is much
easier to visualize conceptually.
>
I agree because I have made that mistake in the past. We had a project
that involved massive trees (we're talking the bill of materials for an
entire automobile down to an individual screw), and went with the
simple 'parent' scheme, but were too deep into the project before we
suddenly regretted it. A scheme like that is easy to set up, but a
nightmare to use and maintain.
>

Interesting. I've implemented this for things like a flight database -
all scheduled flights throughout the world, with each departure and
destination airport, etd and eta, etc. And been able to use recursive
queries to find possible flight combinations to get from one destination
to another - one single query would get it. And although there are a
lot of parts in an automobile, there are also a lot of scheduled flights
in the world for a year.

If you can do recursive queries, it works quite well. And this was with
DB2, which handles recursive queries quite well.

To get a node and its children from the example you gave (known as the
Adjacency model), you have to rely either on recursion or knowing
exactly how many levels exist. The former introduces significant
overhead while the latter is just bad hard-coding. Using a more
advanced tree algorithm allows for a much easier time working with
nodes and children. The link provided earlier

Not that much overhead if you can do the recursion in SQL. One query
can get everything.

(http://dev.mysql.com/tech-resources/...ical-data.html)
is a great resource for seeing the different queries required to work
with either scheme.
>
I doubt the OP will be dealing with trees quite as large as the ones I
needed to use, but if you can deal with a bit of complexity up front,
you can save yourself a lot of extra work later on.
>

And if you can do your recursion in your SQL statements you don't even
need the complexity.

And speaking of the original post...I didn't quite understand what you
were asking. If you were asking for advice on getting the # of items
in each category, perhaps you could use the examples on that page
linked to for getting all the children of a node, and then WHERE'ing it
to include only those nodes whose lft & rgt are 1 apart (meaning they
have no children).
>

--
=============== ===
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstucklex@attgl obal.net
=============== ===

[mootmail-googlegroups@yahoo.com]

Re: displaying categories/subcategories using modified preorder tree transversal

Jerry Stuckle wrote:

>
If you can do recursive queries, it works quite well. And this was with
DB2, which handles recursive queries quite well.
>

Hmm. The DB we were using didn't support recursive queries, so I never
got to explore that path, unfortunately. I suspect that, as you say,
it would handle well enough performance-wise, seeing that all the
recursing is done on the DB itself rather than via recursive queries
coming from the code. Still, though, even the most efficient recursion
carries along with it some degree of overhead. That's just the nature
of recursion.

If I had the time spare time, I would love to implement a number of
tree algorithms and see how they scale in performance as the size of
the tree increases. That is the kind of assignment I WISH they had
given back in college. Practical and educational.

[hornedw]

Re: displaying categories/subcategories using modified preorder tree transversal


mootmail-googlegroups@ya hoo.com wrote:

Jerry Stuckle wrote:

If you can do recursive queries, it works quite well. And this was with
DB2, which handles recursive queries quite well.

>
Hmm. The DB we were using didn't support recursive queries, so I never
got to explore that path, unfortunately. I suspect that, as you say,
it would handle well enough performance-wise, seeing that all the
recursing is done on the DB itself rather than via recursive queries
coming from the code. Still, though, even the most efficient recursion
carries along with it some degree of overhead. That's just the nature
of recursion.
>
If I had the time spare time, I would love to implement a number of
tree algorithms and see how they scale in performance as the size of
the tree increases. That is the kind of assignment I WISH they had
given back in college. Practical and educational.

Thanks everyone for your help. I probably will either use Javascript or
CSS in displaying the child categories or set it up similar to
Amazon.com's categories(main categories display on one page, and the
category selected and its subcategories on the second page. Thanks
mootmail--I will look back at the link I provided earlier as to display
the number of items.

David

[onembk]

Re: displaying categories/subcategories using modified preorder tree transversal

On 2006-09-01 22:48:44 -0600, "hornedw" <hornedw@yahoo. comsaid:

>
mootmail-googlegroups@ya hoo.com wrote:

>Jerry Stuckle wrote:

>>>
>>If you can do recursive queries, it works quite well. And this was with
>>DB2, which handles recursive queries quite well.
>>>

>>
>Hmm. The DB we were using didn't support recursive queries, so I never
>got to explore that path, unfortunately. I suspect that, as you say,
>it would handle well enough performance-wise, seeing that all the
>recursing is done on the DB itself rather than via recursive queries
>coming from the code. Still, though, even the most efficient recursion
>carries along with it some degree of overhead. That's just the nature
>of recursion.
>>
>If I had the time spare time, I would love to implement a number of
>tree algorithms and see how they scale in performance as the size of
>the tree increases. That is the kind of assignment I WISH they had
>given back in college. Practical and educational.

>
Thanks everyone for your help. I probably will either use Javascript or
CSS in displaying the child categories or set it up similar to
Amazon.com's categories(main categories display on one page, and the
category selected and its subcategories on the second page. Thanks
mootmail--I will look back at the link I provided earlier as to display
the number of items.
>
David

What if your result set is in the thousands? Tens of thousands?
JavaScript probably wouldn't do so well with that.

Here's a way to do it, ugly proof of concept but it works while letting
you control how much data is loaded into memory:

Tables:
=============== =============== ==

Table 1: categories
cat_id cat_parent cat_name
1 0 books
2 1 fiction
3 2 classic
4 2 sci-fi
5 1 non-fiction

Table 2: Items
item_id item_cat item_name item_descriptio n
1 3 'hamlet' 'shakespeare'
2 3 'romeo & juliet' 'shakespeare'
3 4 'episode 1' 'star wars'
4 4 'episode 2' 'star wars'

PHP:
=============== =============== ==

<pre>
<?php

//
// usage: array load_tree(int cat_id, int child depth);
//
function load_tree($cat_ id, $depth, $cur_level = 0) {
if ($cur_level $depth) {return;}

$ret = array();
$cats = mysql_fetch_ass oc(mysql_query( "SELECT * FROM categories WHERE
cat_id='$cat_id '"));
$ret[$cats['cat_name']] = array();

$sub_cats = mysql_query("SE LECT * FROM categories WHERE
cat_parent='".$ cats['cat_id']."'");

$cur_level++;
while ($cats2 = mysql_fetch_ass oc($sub_cats)) {
$ret[$cats['cat_name']][] = load_tree($cats 2['cat_id'], $depth, $cur_level);
}
$cur_level--;

$items = mysql_query("SE LECT * FROM items WHERE item_cat='$cat_ id'");
while ($item = mysql_fetch_ass oc($items)) {
$ret[$cats['cat_name']][] = $item;
}
return $ret;
}

function print_tree($tre e, $indent = ' ') {
if (!is_array($tre e)) {return;}
if (isset($tree['item_name'])) {
echo $indent.$tree['item_name'].' '.$tree['item_descripti on'].'<br />';
} else {
foreach ($tree as $key =$val) {
echo $indent.$key.'< br />';
if (count($val) 0) {
foreach ($val as $val2) {
print_tree($val 2, $indent.$indent );
}
}
}
}
}

$tree = load_tree(1, 3);

//print_r($tree);
echo "\n\n";
print_tree($tre e);
?>

Output:
=============== =============== ==

books
fiction
classic
hamlet (shakespeare)
romeo & juliet (shakespeare)
sci-fi
episode 1 (star wars)
episode 2 (star wars)
non-fiction
=============== =============== ==

You could do the same thing in reverse, recursively querying for the
parent instead of the children, but you would only end up with a single
main category (categories other than 'books' would be ignored).

Hope this gives you another idea. I've used this method many times to
create download pages and other things, works quite well (even though
the '$tree' array is ugly).

[hornedw]

Re: displaying categories/subcategories using modified preorder tree transversal


onembk wrote:

On 2006-09-01 22:48:44 -0600, "hornedw" <hornedw@yahoo. comsaid:
>

mootmail-googlegroups@ya hoo.com wrote:

Jerry Stuckle wrote:
>>
>If you can do recursive queries, it works quite well. And this was with
>DB2, which handles recursive queries quite well.
>>
>
Hmm. The DB we were using didn't support recursive queries, so I never
got to explore that path, unfortunately. I suspect that, as you say,
it would handle well enough performance-wise, seeing that all the
recursing is done on the DB itself rather than via recursive queries
coming from the code. Still, though, even the most efficient recursion
carries along with it some degree of overhead. That's just the nature
of recursion.
>
If I had the time spare time, I would love to implement a number of
tree algorithms and see how they scale in performance as the size of
the tree increases. That is the kind of assignment I WISH they had
given back in college. Practical and educational.

Thanks everyone for your help. I probably will either use Javascript or
CSS in displaying the child categories or set it up similar to
Amazon.com's categories(main categories display on one page, and the
category selected and its subcategories on the second page. Thanks
mootmail--I will look back at the link I provided earlier as to display
the number of items.

David

>
What if your result set is in the thousands? Tens of thousands?
JavaScript probably wouldn't do so well with that.
>
Here's a way to do it, ugly proof of concept but it works while letting
you control how much data is loaded into memory:
>
Tables:
=============== =============== ==
>
Table 1: categories
cat_id cat_parent cat_name
1 0 books
2 1 fiction
3 2 classic
4 2 sci-fi
5 1 non-fiction
>
Table 2: Items
item_id item_cat item_name item_descriptio n
1 3 'hamlet' 'shakespeare'
2 3 'romeo & juliet' 'shakespeare'
3 4 'episode 1' 'star wars'
4 4 'episode 2' 'star wars'
>
PHP:
=============== =============== ==
>
<pre>
<?php
>
//
// usage: array load_tree(int cat_id, int child depth);
//
function load_tree($cat_ id, $depth, $cur_level = 0) {
if ($cur_level $depth) {return;}
>
$ret = array();
$cats = mysql_fetch_ass oc(mysql_query( "SELECT * FROM categories WHERE
cat_id='$cat_id '"));
$ret[$cats['cat_name']] = array();
>
$sub_cats = mysql_query("SE LECT * FROM categories WHERE
cat_parent='".$ cats['cat_id']."'");
>
$cur_level++;
while ($cats2 = mysql_fetch_ass oc($sub_cats)) {
$ret[$cats['cat_name']][] = load_tree($cats 2['cat_id'], $depth, $cur_level);
}
$cur_level--;
>
$items = mysql_query("SE LECT * FROM items WHERE item_cat='$cat_ id'");
while ($item = mysql_fetch_ass oc($items)) {
$ret[$cats['cat_name']][] = $item;
}
return $ret;
}
>
function print_tree($tre e, $indent = ' ') {
if (!is_array($tre e)) {return;}
if (isset($tree['item_name'])) {
echo $indent.$tree['item_name'].' '.$tree['item_descripti on'].'<br />';
} else {
foreach ($tree as $key =$val) {
echo $indent.$key.'< br />';
if (count($val) 0) {
foreach ($val as $val2) {
print_tree($val 2, $indent.$indent );
}
}
}
}
}
>
$tree = load_tree(1, 3);
>
//print_r($tree);
echo "\n\n";
print_tree($tre e);
?>
>
Output:
=============== =============== ==
>
books
fiction
classic
hamlet (shakespeare)
romeo & juliet (shakespeare)
sci-fi
episode 1 (star wars)
episode 2 (star wars)
non-fiction
=============== =============== ==
>
You could do the same thing in reverse, recursively querying for the
parent instead of the children, but you would only end up with a single
main category (categories other than 'books' would be ignored).
>
Hope this gives you another idea. I've used this method many times to
create download pages and other things, works quite well (even though
the '$tree' array is ugly).

Thanks onembk, I will give that a try.