in reply to Adjacency Tree Confusion

Try something like the following. It should run in linear time, and reasonably efficiently. You will of course want to edit it so it's reading in data from your mySQL table (required fields id and parent), but that should be relatively easy. If you're constructing one specific thread from a mySQL query, you'll also need to store the root id with each post record, so you can select the thread you want without having to map all the post dependencies. 
use strict;
use warnings;
use Data::Dumper;

my (%posts, @threads, $id, $parent, $title);

while (<DATA>) {
    chomp; ### It's easy to add more fields here if you want:
    ($id, $parent, $title) = split / /, $_, 3;
    my %post = ('id' => $id, 'title' => $title);
    $posts{$id} = \%post;
    if ($id == $parent) {
        push @threads, \%post;
    }
    else {
        push @{$posts{$parent}{'children'}}, \%post;
    }
}

construct($_) for @threads;

sub construct {
    my $p = $_[0];
    print "$p->{'id'} $p->{'title'}\n";
    construct($_) for @{$p->{'children'}};
}

__DATA__
1 1 Title
2 1 Re: Title
3 1 Re: Title
4 2 Re: Re: Title
5 5 Title 2
6 5 Re: Title 2
7 4 Re: Re: Re: Title

[download]
EDIT: If you want to generate a subtree of a thread, a lineage field isn't necessary, or even that efficient if you have a large number of threads. Just select all posts with a root equal to the root of the subtree, then map those post dependencies (there probably won't be more than a few dozen posts total) and display just the ones dependant on the subtree ID. This saves you the trouble of storing all ancestor IDs for all posts and having to search through them, which can be quite wasteful in terms of disk space and/or processing time.

Replies are listed 'Best First'.
Re^2: Adjancey Tree Confusion
by ChrisR (Hermit) on Apr 08, 2006 at 00:36 UTC
    Thanks for the example. I really appreciate it. I couldn't get it to work with my own data until I realized that you had the parent of the first row equal to the id of that row. In my data, I had the parent of the first row equal to zero. Just a logic fault on my part.

    I added a pre-sort at the beginning so that the time stamp of the node would be taken into account for nodes with the same parent, though I'm sure there is a better way to do it. 

    use strict;
use warnings;

my (%posts, @threads, $id, $root, $board, $parent, $stamp, $title);

my @array;
while (<DATA>)
{
    chomp($_);
    my @subarray = split(/,/,$_);
    push @array, [@subarray];
}
my @sortedarray = sort { $a->[4] cmp $b->[4] } @array;

for my $x (0..$#sortedarray) {    
    ($id, $root, $board, $parent, $stamp, $title) = @{$sortedarray[$x]
+};
    my %post = ('id' => $id, 'root' => $root, 'parent' => $parent, 'st
+amp' => $stamp, 'title' => $title);
    $posts{$id} = \%post;
    if ($id == $parent) {
        push @threads, \%post;
    }
    else {
        push @{$posts{$parent}{'children'}}, \%post;
    }
}

construct($_) for @threads;
    
sub construct {
    my $p = $_[0];
    print  "$p->{'id'} $p->{'title'}\n";
    construct($_) for @{$p->{'children'}};
}

#id,board,root,parent,stamp,text
__DATA__
1,2,0,1,2006-01-02 08:15:00,test line 1 (first)
2,2,1,1,2006-01-02 08:16:00,test line 2 (second)
3,2,1,2,2006-01-02 08:21:00,test line 3 (third)
6,2,1,1,2006-01-02 08:23:00,test line 6 (seventh)
4,2,1,1,2006-01-02 08:22:00,test line 4 (sixth)
7,2,1,6,2006-01-02 08:25:00,test line 7 (eighth)
5,2,1,3,2006-01-02 08:23:00,test line 5 (fourth)
8,2,1,1,2006-01-02 08:17:00,test line 8 (fifth)

    [download]
    Is it possible to have the all data produced by construct assigned/returned to a single array of hashes without the array having to be scoped globally? This is the main reason that I didn't want to use a recursive routine.
[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom