pg.ddx.io pgsql-sql@postgresql.org mailing list archive
help / color / mirror / Atom feedhow to use recursion to find end nodes of a tree
4+ messages / 3 participants
[nested] [flat]
* how to use recursion to find end nodes of a tree
@ 2006-04-10 15:09 mike@mikeandems.com
0 siblings, 2 replies; 4+ messages in thread
From: mike@mikeandems.com @ 2006-04-10 15:09 UTC (permalink / raw)
To: pgsql-sql
Hello All,
I have been having a really hard time trying to come up with a pl/pgsql
recursive function to returns the end nodes of a tree.
Here is an example table definition:
CREATE TABLE parent_child (
parent_id integer NOT NULL,
child_id integer NOT NULL
);
INSERT INTO parent_child (parent_id, child_id) VALUES (1, 2);
INSERT INTO parent_child (parent_id, child_id) VALUES (1, 3);
INSERT INTO parent_child (parent_id, child_id) VALUES (1, 4);
INSERT INTO parent_child (parent_id, child_id) VALUES (2, 5);
INSERT INTO parent_child (parent_id, child_id) VALUES (2, 6);
INSERT INTO parent_child (parent_id, child_id) VALUES (4, 7);
INSERT INTO parent_child (parent_id, child_id) VALUES (4, 8);
INSERT INTO parent_child (parent_id, child_id) VALUES (4, 9);
INSERT INTO parent_child (parent_id, child_id) VALUES (9, 10);
This produces the following tree of data:
1
___|___
| | |
2 3 4
_|_ _|_
| | | | |
5 6 7 8 9
|
10
I want to create a function that returns the terminating nodes of
of this tree below a certain level i.e. if I input 1 to the function
I need it to return 5,6,3,7,8,10. If I input 4 to the function I would
get 7,8,10. I have written recursive functions which return all nodes
on a branch of a tree but I can't think of a way to return the end nodes
does anyone know of a solution?
Many thanks,
Mike
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: how to use recursion to find end nodes of a tree
@ 2006-04-10 16:12 Yasir Malik <ymalik@cs.stevens.edu>
parent: mike@mikeandems.com
1 sibling, 1 reply; 4+ messages in thread
From: Yasir Malik @ 2006-04-10 16:12 UTC (permalink / raw)
To: mike@mikeandems.com; +Cc: pgsql-sql
> Hello All,
>
> I have been having a really hard time trying to come up with a pl/pgsql
> recursive function to returns the end nodes of a tree.
> Here is an example table definition:
>
> CREATE TABLE parent_child (
> parent_id integer NOT NULL,
> child_id integer NOT NULL
> );
>
> INSERT INTO parent_child (parent_id, child_id) VALUES (1, 2);
> INSERT INTO parent_child (parent_id, child_id) VALUES (1, 3);
> INSERT INTO parent_child (parent_id, child_id) VALUES (1, 4);
> INSERT INTO parent_child (parent_id, child_id) VALUES (2, 5);
> INSERT INTO parent_child (parent_id, child_id) VALUES (2, 6);
> INSERT INTO parent_child (parent_id, child_id) VALUES (4, 7);
> INSERT INTO parent_child (parent_id, child_id) VALUES (4, 8);
> INSERT INTO parent_child (parent_id, child_id) VALUES (4, 9);
> INSERT INTO parent_child (parent_id, child_id) VALUES (9, 10);
>
> This produces the following tree of data:
>
> 1
> ___|___
> | | |
> 2 3 4
> _|_ _|_
> | | | | |
> 5 6 7 8 9
> |
> 10
>
> I want to create a function that returns the terminating nodes of
> of this tree below a certain level i.e. if I input 1 to the function
> I need it to return 5,6,3,7,8,10. If I input 4 to the function I would
> get 7,8,10. I have written recursive functions which return all nodes
> on a branch of a tree but I can't think of a way to return the end nodes
> does anyone know of a solution?
>
I haven't programmed in PL/pgSQL in a while, but I'll write some pseudo
code. I think the code should be similar:
func(int node)
{
dynamic_array s;
dynamic_array leaves;
int top, count, leaf_id, popped, child;
leaf_id = top = 0;
s[top] = node;
count = 1;
// to a depth first search
while(count != 0)
{
popped = s[top];
top--;
count--;
foreach(select pc.child_id into child from parent_child pc where
pc.parent_id = popped)
{
select * from parect_child pc where parent_id = child;
// a count of zero indicates that child node has no children
if(count_of_above_query = 0)
{
leaves[leaf_id] = child;
leaf_id++;
}
else
{
// not a leaf, so add it to the stack for the next time through
// the loop
top++;
s[top] = child;
count++;
}
}
}
return leaves;
}
Regards,
Yasir
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: how to use recursion to find end nodes of a tree
@ 2006-04-10 23:57 Ross Johnson <ross.johnson@homemail.com.au>
parent: mike@mikeandems.com
1 sibling, 0 replies; 4+ messages in thread
From: Ross Johnson @ 2006-04-10 23:57 UTC (permalink / raw)
To: mike@mikeandems.com; +Cc: pgsql-sql
On Mon, 2006-04-10 at 16:09 +0100, mike@mikeandems.com wrote:
> Hello All,
>
> I have been having a really hard time trying to come up with a pl/pgsql
> recursive function to returns the end nodes of a tree.
> Here is an example table definition:
>
> CREATE TABLE parent_child (
> parent_id integer NOT NULL,
> child_id integer NOT NULL
> );
>
> INSERT INTO parent_child (parent_id, child_id) VALUES (1, 2);
> INSERT INTO parent_child (parent_id, child_id) VALUES (1, 3);
> INSERT INTO parent_child (parent_id, child_id) VALUES (1, 4);
> INSERT INTO parent_child (parent_id, child_id) VALUES (2, 5);
> INSERT INTO parent_child (parent_id, child_id) VALUES (2, 6);
> INSERT INTO parent_child (parent_id, child_id) VALUES (4, 7);
> INSERT INTO parent_child (parent_id, child_id) VALUES (4, 8);
> INSERT INTO parent_child (parent_id, child_id) VALUES (4, 9);
> INSERT INTO parent_child (parent_id, child_id) VALUES (9, 10);
>
What you appear to have is really this, with a missing first node:
CREATE TABLE parent_child (
parent_id integer NOT NULL,
this_node_id integer NULL,
);
INSERT INTO parent_child (parent_id, this_node_id) VALUES (0, 1);
INSERT INTO parent_child (parent_id, this_node_id) VALUES (1, 2);
INSERT INTO parent_child (parent_id, this_node_id) VALUES (1, 3);
INSERT INTO parent_child (parent_id, this_node_id) VALUES (1, 4);
INSERT INTO parent_child (parent_id, this_node_id) VALUES (2, 5);
INSERT INTO parent_child (parent_id, this_node_id) VALUES (2, 6);
INSERT INTO parent_child (parent_id, this_node_id) VALUES (4, 7);
INSERT INTO parent_child (parent_id, this_node_id) VALUES (4, 8);
INSERT INTO parent_child (parent_id, this_node_id) VALUES (4, 9);
INSERT INTO parent_child (parent_id, this_node_id) VALUES (9, 10);
This makes it easy to search from leaf to root, but not from root to
leaf. Without a list of child_ids in each node you must search the whole
table for nodes that have the current node id as their parent_id in
order to determine if a node is a leaf node or not. Perhaps you can
include a child_id[] in each node, or a has_children boolean flag that
you set and unset when inserting or deleting rows.
But perhaps you can get PostgreSQL to do it for you by setting
this_node_id as primary key and parent_id as foreign key referencing
this same table. You could then test if it's a leaf node by attempting
to change the node's this_node_id to some out-of-range value and see if
it produces as error. If no error then it's a leaf node, (then you must
restore this_node_id - I would try just negating it for the test, so I
don't have to actually store the original value somewhere).
> This produces the following tree of data:
>
> 1
> ___|___
> | | |
> 2 3 4
> _|_ _|_
> | | | | |
> 5 6 7 8 9
> |
> 10
>
> I want to create a function that returns the terminating nodes of
> of this tree below a certain level i.e. if I input 1 to the function
> I need it to return 5,6,3,7,8,10. If I input 4 to the function I would
> get 7,8,10. I have written recursive functions which return all nodes
> on a branch of a tree but I can't think of a way to return the end nodes
> does anyone know of a solution?
>
> Many thanks,
>
> Mike
>
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 4: Have you searched our list archives?
>
> http://archives.postgresql.org
>
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: how to use recursion to find end nodes of a tree
@ 2006-04-11 18:00 mike@mikeandems.com
parent: Yasir Malik <ymalik@cs.stevens.edu>
0 siblings, 0 replies; 4+ messages in thread
From: mike@mikeandems.com @ 2006-04-11 18:00 UTC (permalink / raw)
To: 'Yasir Malik' <ymalik@cs.stevens.edu>; ross.johnson@homemail.com.au; +Cc: pgsql-sql
Thankyou very much Yasir and Ross for your help and advice.
I have created a pl/pgsql version of Yasirs algorithm which
works perfectly, I am also looking into improving efficiency
by flaging leaf records. Here is my pl/pgsql solution in case
it helps anyone out:
CREATE OR REPLACE FUNCTION parentchildtest(int4)
RETURNS _int4 AS
'DECLARE
node ALIAS FOR $1;
s INTEGER[];
leaves INTEGER[];
top INTEGER;
counter INTEGER;
leaf_id INTEGER;
popped INTEGER;
child RECORD;
childCount RECORD;
BEGIN
leaf_id := 0;
top := 0;
s := ''{}'';
leaves := ''{}'';
s[top] := node;
counter := 1;
-- t a depth first search
WHILE (counter <> 0) LOOP
popped := s[top];
top := top - 1;
counter := counter - 1;
FOR child IN SELECT pc.child_id FROM parent_child AS pc
WHERE pc.parent_id = popped
LOOP
SELECT INTO childCount COUNT(*) AS count FROM parent_child AS pc
WHERE pc.parent_id = child.child_id;
--a count of zero indicates that child node has no children
IF (childCount.count = 0) THEN
leaves[leaf_id] = child.child_id;
leaf_id := leaf_id + 1;
ELSE
-- not a leaf, so add it to the stack for the next time
through
-- the loop
top := top + 1;
s[top] = child.child_id;
counter := counter + 1;
END IF;
END LOOP;
END LOOP;
RETURN leaves;
END;'
LANGUAGE 'plpgsql' VOLATILE;
-----Original Message-----
From: Yasir Malik [mailto:ymalik@cs.stevens.edu]
Sent: 10 April 2006 17:13
To: mike@mikeandems.com
Cc: pgsql-sql@postgresql.org
Subject: Re: [SQL] how to use recursion to find end nodes of a tree
> Hello All,
>
> I have been having a really hard time trying to come up with a
> pl/pgsql recursive function to returns the end nodes of a tree. Here
> is an example table definition:
>
> CREATE TABLE parent_child (
> parent_id integer NOT NULL,
> child_id integer NOT NULL
> );
>
> INSERT INTO parent_child (parent_id, child_id) VALUES (1, 2); INSERT
> INTO parent_child (parent_id, child_id) VALUES (1, 3); INSERT INTO
> parent_child (parent_id, child_id) VALUES (1, 4); INSERT INTO
> parent_child (parent_id, child_id) VALUES (2, 5); INSERT INTO
> parent_child (parent_id, child_id) VALUES (2, 6); INSERT INTO
> parent_child (parent_id, child_id) VALUES (4, 7); INSERT INTO
> parent_child (parent_id, child_id) VALUES (4, 8); INSERT INTO
> parent_child (parent_id, child_id) VALUES (4, 9); INSERT INTO
> parent_child (parent_id, child_id) VALUES (9, 10);
>
> This produces the following tree of data:
>
> 1
> ___|___
> | | |
> 2 3 4
> _|_ _|_
> | | | | |
> 5 6 7 8 9
> |
> 10
>
> I want to create a function that returns the terminating nodes of of
> this tree below a certain level i.e. if I input 1 to the function I
> need it to return 5,6,3,7,8,10. If I input 4 to the function I would
> get 7,8,10. I have written recursive functions which return all nodes
> on a branch of a tree but I can't think of a way to return the end
> nodes does anyone know of a solution?
>
I haven't programmed in PL/pgSQL in a while, but I'll write some pseudo
code. I think the code should be similar:
func(int node)
{
dynamic_array s;
dynamic_array leaves;
int top, count, leaf_id, popped, child;
leaf_id = top = 0;
s[top] = node;
count = 1;
// to a depth first search
while(count != 0)
{
popped = s[top];
top--;
count--;
foreach(select pc.child_id into child from parent_child pc where
pc.parent_id = popped)
{
select * from parect_child pc where parent_id = child;
// a count of zero indicates that child node has no children
if(count_of_above_query = 0)
{
leaves[leaf_id] = child;
leaf_id++;
}
else
{
// not a leaf, so add it to the stack for the next time through
// the loop
top++;
s[top] = child;
count++;
}
}
}
return leaves;
}
Regards,
Yasir
^ permalink raw reply [nested|flat] 4+ messages in thread
end of thread, other threads:[~2006-04-11 18:00 UTC | newest]
Thread overview: 4+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2006-04-10 15:09 how to use recursion to find end nodes of a tree mike@mikeandems.com
2006-04-10 16:12 ` Yasir Malik <ymalik@cs.stevens.edu>
2006-04-11 18:00 ` mike@mikeandems.com
2006-04-10 23:57 ` Ross Johnson <ross.johnson@homemail.com.au>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox