my $cats_sth = $dbh->prepare(<<"EndOfSQL");
  SELECT category_id, name, parent
  FROM   $sql{categories}
  ORDER BY category_id ASC
  -- assumes parent id is always less than child id
EndOfSQL

my @cats;

# build the data structure
while (my($cat_id, $name, $parent_id) = $cats_sth->fetchrow_array()) {
    $cats[$cat_id] = [$name, $parent_id, []];
    if ($cats[$parent_id]) {
        push @{$cats[$parent_id][2]}, $cat_id;
    } elsif ($parent_id) {
        warn "Parent $parent_id not found for category $cat_id '$name'
+\n";
    }
}

# print the categories
foreach my $cat (@cats) {
    next unless $cat and !$cat->[1];
    print_category($cat, \@cats, '');
}

# recursively print a category and its children
sub print_category {
    my($cat, $cats, $indent) = @_;
    
    print $indent, $cat->[0], "\n";
    foreach my $child_id (@{$cat->[2]}) {
        print_category($cats->[$child_id], $cats, "$indent  ");
    }
}
[download]

[
   [ name, parent id, [ child ids ] ],
   [ name, parent id, [ child ids ] ],
   ...
]
[download]

This probably is not the best data structure for your task, although it does get the job done. It should give you some ideas about solving the problem.

I had a similar database construct that I built a tree structure around. I won't attempt to write your code, but I'll explain what I did and maybe it will help.

Each level of the tree was an array reference. The array members were hash references representing the individual nodes. Those nodes had optional references to other array references (children nodes), etc ...

To implement this you have two functions: One to create the tree, and one to traverse it. The creation function algorithm is:

• Accept one optional argument: A parent node (hash reference)
• Get nodes for the parent (or root nodes if no parent given) from the database
• If the DB hands back any nodes ...
• Create an array reference
• For each DB node returned ...
• Create a hash reference representing the node. Keys are name, ID, etc.
• Push the created hash (node) reference onto the array created above
• Call yourself recursively with the node reference as an argument
• If a parent was given set a "children" key in it to the created array reference
• Return the created array reference (or undef if no nodes)

• Accept three arguments: An array reference of nodes, a depth, and a CODE reference to a function to call per node
• For each node in the given array reference ...
• Call the node processing function with the node and the given depth
• If the node has a "children" array reference ...
• Call yourself recursively with the "children" array reference, depth+1, and the node processing CODE reference

Once I got this far I optimized by loading all nodes with one DB call and building the tree as a secondary step. But I was able to do that by virtue of having another set of data that defined the relationships (the node "links"). So your mileage may vary there.

$all_cats = $dbh->selectall_arrayref("SELECT category_id,name FROM $sq
+l{catego
  +ries} WHERE parent=$parent_cat_id ORDER BY category_id");
[download]

@categories = (
               {
                 id   => <i>insert category_id value here</i>,
                 name => <i>insert name value here</i>
                 level => <i>level (inside a category etc.) </i>
               },
               {
                 ...
               },
               ...
               );
[download]

$indent .= "  ...";
[download]

$level++;
[download]

        foreach my $current_cat (sort { $a->[1] cmp $b->[1] } @{$all_c
+ats}) {
              ($cat{id}, $cat{name}) = @$current_cat;
              push @main::categories {level=>$level,name=>$cat{name},i
+d=>$cat{id}};
              &ListCategories($indent, $cat{id}, 'y');
          }
[download]

If it works I will be happy, because I've been away from Perl for a long time, and I'm trying to shake off some rust. Even if it doesn't work, it's got to be close. Anyway:

$tree = GetCategories($node)

  # # # # # #  
#'  .     .  `#
#      i      #     making an ass out of u and me since 1975
# assumptions #
#+_.       ._+#


my %sql;    # is filled w/ names of tables that hold category data
my $dbh;    # database handle


=head2 The Structure of a Node

    {
      id       => $number,
      name     => $string,
      children => $array_ref_of_more_nodes,
    }

=head2 Usage

To get the whole tree:

    my $tree = GetCategories(); 

To get a partial tree, pass in a hashref that
has an C<id> key representing the parent C<category_id>
to start with:

    my $subtree = GetCategories($starting_node);
   
=cut


sub GetCategories {
    my $node            = shift || undef;
    my $select_children =
        "SELECT category_id,name FROM $sql{categories} ";

    # Create the root node only on the 1st time through,
    # and complete the SQL statement for 
    # selecting all the nodes children.
    if (not defined $node) {
        $node = {
            id       =>   0,
            name     => '/',
            children => [ ],
        };
        $select_children .= "WHERE parent IS NULL";
    } else {
        $select_children .= "WHERE parent=$node->{id}";
    }

    # Find all the children of the current node.
    my $all_cats = $dbh->selectall_arrayref($select_children);
    my $c;

    # Add each child to $node->{children}, and
    # then recursively add get each child's children
    foreach $c (sort { $a->[1] cmp $b->[1] } @{$all_cats}) {
        my $child_node = {
            id       => $c->[0],
            name     => $c->[1],
            children => [ ],
        };

        # ............. depth-first style .....

        push @{$node->{children}}, $child_node;
        GetCategories($child_node);
    }
        
    return $node;
}
[download]

Or is your graph guaranteed to be a tree with no cycles?

Matt

1. replacing the print with $output_string .=
2. changing the function to this

   {
      my $output_string;
      sub DoListCategories {
        $output_string = "";
        ListCategories(@_);
      }
      sub ListCategories {
        #Just as you had it with the change in 1 above
      }
   }
   [download]

   Note the outer braces so $output_string is "private" to these two functions.
3. Changing the calls in the main program from ListCategories to DoListCategories

HTH, --traveler

I used your solution first because it seemed the most straight forward and required the least amount of change to my existing code.

It worked perfectly and accomplished exactly what I wanted. The problem I had been running into was, indeed, that I was trying to be too "smart". From the moment I sat down to write the routine, I did it with the mindset that I'd accomplish everything in one sub which obviously was rediculous (now I see the error of my ways).

I had suspected that doing what you suggested would work and may be the necessary way, but I also thought that there must be a standard solution to doing it all in one simple routine and that I was just too inexperienced to see it. Forest for the trees.

Now that I at least have it working, I intend to go back and try implementing some of the changes the other posters above suggested for more efficiency, readability and flexibility.

Thanks for the help!