algorithm help

Hey everyone,

I'm having a little trouble writing an algorithm to create a
hierarchal structure from a database which looks like this:

Code:

parent_id | child_id |
----------------+-------------+
1 | 2 |
2 | 3 |
3 | 4 |
3 | 5 |
5 | 6 |
5 | 7 |


So coming out of the database, I get an array which looks like this:

Code:

Array
(
[0] => Array
(
[parent_id] => 1
[child_id] => 2
)

[1] => Array
(
[parent_id] => 2
[child_id] => 3
)

[2] => Array
(
[parent_id] => 3
[child_id] => 4
)
....


I would like to put this into an array which represents the following
structure:

Code:

1
\
2
\
3
/ \
4 5
/ \
6 7


Can anyone point me in the right direction? Let me know if this isn't
clear - I can try to elaborate.

Thanks!

Ben

Re: algorithm help

How to get that into an array depends on your situation.

If you don't already have a lot of data in the database, working with
XML files is a much easier way to deal with hierarchies unless of
course there are other needs for a database or individual node access.

If you don't already have a lot of data in the database and will be
putting data in with another algorithm, I would suggest creating
another field in which you can save a string which represents the
node's location in the hierarchy (such as "1|2|3|5|7" for the bottom
right node in your tree example). Then you can explode()/split() the
string to more quickly get it into the appropriate location in the
array. Hopefully the data in the database will be returned in an order
that nodes come after their parent nodes and the root node is first
(hint - sort with your query), and you can iterate through the nodes
in the location string to get to where in your tree array the data
should go. If the database result is not ordered this way, you can
still create upper level nodes from the location string because the
location string says the IDs of the upper level nodes.

If you keep your database table the way you described it, you have to
iterate through every node of the tree array to find the parent node
specified for each row returned from the database. If the database
result is not ordered as described above, you will not be able to
determine the root-relative location in the hierarchy of the current
row if its parents are not all entered already so you will need to
create a "payload" of orphan branches, and constantly see if the
branches can be matched up to any of the newly added nodes or if new
nodes can be added to one of those branches in the payload.

If the last method causes too much trouble and you'd like to switch to
XML files or the first mentioned database table layout, you can create
the latter algorithm to make an array and then write it back to a
database or file with yet another algorithm.

What works for you will also depend on how large the hierarchy is and
how much data is in it.

-Michael Placentra II


On Oct 19, 3:06 pm, uidzer0 wrote:
> Hey everyone,
>
> I'm having a little trouble writing an algorithm to create a
> hierarchal structure from a database
>
> I would like to put this into an array
>
> Can anyone point me in the right direction? Let me know if this isn't
> clear - I can try to elaborate.
>
> Thanks!
> Ben

Re: algorithm help

On 19 Oct, 20:06, uidzer0 wrote:
> Hey everyone,
>
> I'm having a little trouble writing an algorithm to create a
> hierarchal structure from a database which looks like this:
>
> Code:
>
> parent_id | child_id |
> ----------------+-------------+
> 1 | 2 |
> 2 | 3 |
> 3 | 4 |
> 3 | 5 |
> 5 | 6 |
> 5 | 7 |
>

>
> 1
> \
> 2
> \
> 3
> / \
> 4 5
> / \
> 6 7
>

Some relational DBMS provide tree walking SQL extensions (like
Oracle's 'connect by') but they're not portable, and you don't say
what DBMS you use.

You're data already *represents* that structure - just perhaps not in
a very useful way.

Its probably a lot simpler if you do it in PHP code. There are any
number of ways to solve this, but its worth observing that you're code
is probably an over-simplification of the data structure. e.g. you
might go with a right threaded binary tree:

// this is a template of the node structure
$node=array( $current=-1, $next=-1, $first_child=-1,
$payload=array() );
// e.g. 5,4,7, blah
// 7,6,-1,foo
// 6,5,-1,bar
// 4,3,-1,tog
// 3,2,5, zip
// 2,1,3
Which work very nicely when you want to dynamically tinker with the
structure and perform lots of tree walks (hint: use recursive
functions). And they scale really nicely.

Or simply use nested arrays. Do you really need someone to explain how
to code this? Admittedly a single pass algorithm is a little tricky,
but if you can't get your head around a multipass solution, you're
going to be back here a lot asking for help.

C.

Re: algorithm help

uidzer0 wrote:
> I'm having a little trouble writing an algorithm to create a
> hierarchal structure from a database which looks like this:
> parent_id | child_id |
> ----------------+-------------+
> 1 | 2 |
> 2 | 3 |
> 3 | 4 |
> 3 | 5 |
> 5 | 6 |
> 5 | 7 |
> I would like to put this into an array which represents the following
> structure:
> 1
> \
> 2
> \
> 3
> / \
> 4 5
> / \
> 6 7

if you understand french language :



--
@@@@@
E -00 comme on est very beaux dis !
' `) /
|\_ =="

Re: algorithm help

uidzer0 wrote:
> Hey everyone,
>
> I'm having a little trouble writing an algorithm to create a
> hierarchal structure from a database which looks like this:
>
> Code:
>
> parent_id | child_id |
> ----------------+-------------+
> 1 | 2 |
> 2 | 3 |
> 3 | 4 |
> 3 | 5 |
> 5 | 6 |
> 5 | 7 |
>
>
> So coming out of the database, I get an array which looks like this:
>
> Code:
>
> Array
> (
> [0] => Array
> (
> [parent_id] => 1
> [child_id] => 2
> )
>
> [1] => Array
> (
> [parent_id] => 2
> [child_id] => 3
> )
>
> [2] => Array
> (
> [parent_id] => 3
> [child_id] => 4
> )
> ...
>
>
> I would like to put this into an array which represents the following
> structure:
>
> Code:
>
> 1
> \
> 2
> \
> 3
> / \
> 4 5
> / \
> 6 7
>
>
> Can anyone point me in the right direction? Let me know if this isn't
> clear - I can try to elaborate.
>
> Thanks!
>
> Ben
>


Try a recursive call to the database..

Thats how I at least got a picture of such a tree structure for my
application. I didn't load it into an array at all.

basically there is a subroutine that takes the parent ID as parameter,
and finds all its children.

For each child, it calls itself with the child as the new parent.

This essentially walks down each branch to a end node and then tries the
next branch.

I love recursion. It makes a fine way to solve a maze.

If you had the data into an array, you wouldn't need a SQL call per
node: In practice it wasn't actually a huge overhead for me.


thats how to walk the tree. To represent it? well I didn't need it
represented in a memory structure, - my tree is like a list of headings
and subheadings, and all I wanted was a table of contents printed out.
Wasn't that hard to do.

I'd say that making a memory structure analogous to the database
structure is the only way to get a one-to-many node going.

Which begs the question of why duplicate that in memory, when its in the
database already, and likely as not cached in memory!

In other words, you have the correct representation already What you may
be lacking is a smart way to walk that tree.

In pseudo code mine goes like this

function walk tree(parent)
FOR I=0 , I less than SIZEOF (total array), I++
DO
if array[i].parent eq parent
THEN walk tree (array[i].child);
DONE
ENDFUNCTION

Or in Mysql type speak
WALK TREE: Parent_id
SELECT * from TREE where PARENT=parent_id ORDER by (whatever);
FOR EACH ROW
WALK TREE(CHILD);
END
END (WALK TREE)

Re: algorithm help

"The Natural Philosopher" wrote in message
news:1192832545.26334.0@proxy02.news.clara.net...
> uidzer0 wrote:
>> Hey everyone,
>>
>> I'm having a little trouble writing an algorithm to create a
>> hierarchal structure from a database which looks like this:
>>
>> Code:
>>
>> parent_id | child_id |
>> ----------------+-------------+
>> 1 | 2 |
>> 2 | 3 |
>> 3 | 4 |
>> 3 | 5 |
>> 5 | 6 |
>> 5 | 7 |
>>
>>
>> So coming out of the database, I get an array which looks like this:
>>
>> Code:
>>
>> Array
>> (
>> [0] => Array
>> (
>> [parent_id] => 1
>> [child_id] => 2
>> )
>>
>> [1] => Array
>> (
>> [parent_id] => 2
>> [child_id] => 3
>> )
>>
>> [2] => Array
>> (
>> [parent_id] => 3
>> [child_id] => 4
>> )
>> ...
>>
>>
>> I would like to put this into an array which represents the following
>> structure:
>>
>> Code:
>>
>> 1
>> \
>> 2
>> \
>> 3
>> / \
>> 4 5
>> / \
>> 6 7
>>
>>
>> Can anyone point me in the right direction? Let me know if this isn't
>> clear - I can try to elaborate.
>>
>> Thanks!
>>
>> Ben
>>
>
>
> Try a recursive call to the database..

that's wretched! your db is needlessly put through the ringer!

if you're going to have the db do it, then put the recursion in a udf in the
db. that way there's only one call to the db and one result set returned.
plenty of examples of this on the net for any db you want to use.

Re: algorithm help

On 19 Oct, 20:06, uidzer0 wrote:
> Hey everyone,
>
> I'm having a little trouble writing an algorithm to create a
> hierarchal structure from a database which looks like this:
>
> Code:
>
> parent_id | child_id |
> ----------------+-------------+
> 1 | 2 |
> 2 | 3 |
> 3 | 4 |
> 3 | 5 |
> 5 | 6 |
> 5 | 7 |
>
> So coming out of the database, I get an array which looks like this:
>
> Code:
>
> Array
> (
> [0] => Array
> (
> [parent_id] => 1
> [child_id] => 2
> )
>
> [1] => Array
> (
> [parent_id] => 2
> [child_id] => 3
> )
>
> [2] => Array
> (
> [parent_id] => 3
> [child_id] => 4
> )
> ...
>
> I would like to put this into an array which represents the following
> structure:
>
> Code:
>
> 1
> \
> 2
> \
> 3
> / \
> 4 5
> / \
> 6 7
>
> Can anyone point me in the right direction? Let me know if this isn't
> clear - I can try to elaborate.
>
> Thanks!
>
> Ben

http://del.icio.us/Captain_Paralytic/hierarchical