Hi Monks, I've been struggling with this problem for over a week now and I am about to admit failure at getting a working algorithm! I have a thesaurus of terms consisting of hierarchical tree structures which we use to index our library collection. My objective is to create a database like SQLite to store all existing entries (over 3,000). The thesaurus consists of a subject term and a unique identifier, a description and some other information. Example:

ID 211
TERM BODY REGIONS
TREE A01
DESCRIPTION Anatomical areas of the body.

ID 2
TERM ABDOMEN
TREE A01.047
DESCRIPTION Portion of the body that lies between the
thorax and the pelvis.
Since I experienced some problems creating foreign keys in SQLite, I decided to store my data in a Hash of Array like:
%HoA =(
##id =>["term","parent_id","left_id", "right_id"]
1 => ["Body Regions","","",""],
2 => ["Extremities","1","",""],
3 => ["Arm","2","",""],
4 => ["Elbow","2","",""],
5 => ["Hand","2","",""],
6 => ["Fingers","5","",""],
7 => ["Thumbs","6","",""]
);

[download]
The algorith for nested sets calls for a recursive technique to populate children nodes.
use strict;
my %HoA;
my $k;
my $root = 1;
my $ctr =1;

for $k (sort keys %HoA){
walktree($root) unless $k eq"";

}

sub walktree{
my $id = shift;
$HoA{$k}[2]=$ctr++ if $id = $k;

##The walktree recursive sub below enters an eternal loop 
##and doesn't execute properly.  When I tried to push the 
##children elements to a temporary array, it worked just 
##fine.  Would it be the $id???
walktree($id) if $id =$HoA{$k}[1] ;

$HoA{$k}[3]=$ctr++;
local $" = "|";
print "$k = @{$HoA{$k}}\n";
}

[download]

Could anybody direct me in the right direction? Or could you recommend an alternative algorithm using regex for instance? Any help would be appreciated.
I've looked at the ISO Thesaurus modules on CPAN but our data does not conform to this standard. I've also looked at some XML approaches but it was mind boggling, to say the least.
Thanks everybody...

Raad

Edited by Chady -- removed <br> tags from code.

In reply to Tree Traversal Script/Nested Sets by Raad

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.