algorithm help

[uidzer0]

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

[C. (http://symcbean.blogspot.com/)]

On 19 Oct, 20:06, uidzer0 <[e-mail]:

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 |

<snip>

>
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.

[denisb]

uidzer0 <be************@gmail.comwrote:

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 :

<http://sql.developpez.com/arborescence/>

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

[Steve]

"The Natural Philosopher" <[e-mail] in message
news:11****************@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.

[Captain Paralytic]

On 19 Oct, 20:06, uidzer0 <[e-mail]:

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