Re: Depth first search

Hello Phil,

Is it a learning exercise ? Oracle's 'conect by' construct already implements a DFS on trees. Why not just use it ? Whatever performance issues the 'connect by' might have, you won't beat it with a hand-coded cursor anyway ....

VC

"Phil Bewig" <pbewig_at_swbell.net> wrote in message news:455f7154.0402171210.388b47f2_at_posting.google.com...
> I know this sounds silly, but I'm having trouble coding depth-first
> search of a tree.
>
> My programming language is Oracle PL/SQL, and I'm reading a cursor, so
> I only have one record available at a time. The records are presented
> in pre-order, with the root first, then the root's leftmost child, then
> its children and so on recursively, the the root's second leftmost child,
> thens its children and so on recursively, etc. My task is to ensure
> that, at each level of the tree, an amount stored in each node of the
> tree is truly the sum of its children, or report an error if it is not.
> I also check the amount in the leaves of the tree against another table.
>
> Here is my pseudocode:
>
> DECLARE x GLOBAL;
>
> -- main processing code
> FETCH x_cursor INTO x;
> checktree(x.key,x.amt,x.depth);
> END;
>
> PROCEDURE checktree(key,amt,depth)
> sum := amt;
> LOOP FETCH x_cursor INTO x;
> EXIT WHEN endfile(x_cursor)
> OR x.depth <> depth;
> IF isleaf(x)
> THEN assert(x.amt=lookup(x.key),x.key || " fails lookup");
> ELSE checktree(x.key,x.amt,x.depth);
> sum := sum - x.amt;
> assert(sum=0,"summing error in " || key);
>
> Some sample data is shown below. The key field in x_cursor is
> indented to show the tree structure; normally, this indention is
> not present, and I rely on the depth field to follow the levels of
> the tree. Leaves have six-digit keys; nodes have five-digit keys.
> This data is correct, and my program should report no errors.
>
> x_cursor lookup
>
> key amount depth key amount
> 10000 2,660,835 0 100010 267,138
> 10001 355,957 1 100020 88,819
> 100010 267,138 2 100060 246,891
> 100020 88,819 2 100070 35,329
> 11000 374,457 1 111010 39,346
> 11006 246,891 2 112010 52,891
> 110060 246,891 3 130001 65,794
> 110070 35,329 2 130310 168,445
> 11100 39,346 2 130320 368,276
> 111010 39,346 3 130331 154,758
> 11200 52,891 2 130340 178,380
> 112010 52,891 3 130350 92,575
> 13000 1,930,421 1 130501 4,000
> 130001 65,794 2 130511 209,034
> 13030 962,434 2 130520 108,263
> 130310 168,445 3 130531 50,470
> 130320 368,276 3 130550 184,158
> 13033 154,758 3 130560 124,522
> 130331 154,758 4 130571 103,589
> 130340 178,380 3 130900 118,157
> 130350 92,575 3
> 13050 784,036 2
> 130501 4,000 3
> 13051 209,034 3
> 130511 209,034 4
> 130520 108,263 3
> 13053 50,470 3
> 130531 50,470 4
> 130550 184,158 3
> 130560 124,522 3
> 13057 103,589 3
> 130571 103,589 4
> 130900 118,157 2
>
> Tracing with print statements shows that my code fetches too frequently,
> getting out of sync with the running totals. There also seem to be
> problems where the depth decreases by two or more levels. I see what is
> going wrong, I think, but I don't see how to fix it.
>
> I've been chasing this problem for two days, feeling dumber and dumber
> by the minute. Please help!
>
> Phil
Received on Tue Feb 17 2004 - 18:02:03 CST