Murcia has asked for the wisdom of the Perl Monks concerning the following question:

Hi confreres,

I want to make a hash of a tree.

The tree consists of ontologies. any number of children is possible. e.g. Building House Window Glas Silicium Door Roof Wood Hut Pizza Garage Door
the result should be $hash = { label =>'Building', children=>[ {label=>'House', children=>[ {label=>'Window', children=>[ .... ], { ... }, ] };

I tried with a recursive call, but I did not manage it to get all nodes.

Any hints

Murcia

Replies are listed 'Best First'.
Re: tree in hash
by davorg (Chancellor) on Jul 22, 2004 at 08:28 UTC

    Looks like this gives the data structure you wanted.

    #!/usr/bin/perl use strict; use warnings; use Data::Dumper; $Data::Dumper::Indent = 1; my $tree; my @refs; while (<DATA>) { chomp; my ($prefix) = /^(\s+)/; s/^$prefix// if $prefix; my $lvl = $prefix ? (length $prefix) / 2 : 0; my $rec = { label => $_, children => [] }; $refs[$lvl] = $rec; $#refs = $lvl; if ($tree) { push @{$refs[$lvl - 1]->{children}}, $rec; } else { $tree = $rec; } } print Dumper $tree; __DATA__ Building House Window Glas Silicium Door Roof Wood Hut Pizza Garage Door
    --
    <http://www.dave.org.uk>

    "The first rule of Perl club is you do not talk about Perl club."
    -- Chip Salzenberg

Re: tree in hash
by Enlil (Parson) on Jul 22, 2004 at 08:40 UTC
    I believe this returns the structure you requested:
    #!/usr/bin/perl use strict; use warnings; use Data::Dumper; my $tree ; my %tree_levels; while ( <DATA> ) { chomp; m/^(\s+)?/; my $length; if ( defined $1 ) {$length = length($1);} else { $length = 0 } my $hr = { label => $_, children => [] }; $tree_levels{$length} = $hr; unless ( defined $tree ) { $tree = $hr; } else { push @{$tree_levels{$length - 2}->{children}}, $hr; } } print Dumper $tree; __DATA__ Building House Window Glas Silicium Door Roof Wood Hut Pizza Garage Door

    -enlil

Re: tree in hash
by relax99 (Monk) on Jul 22, 2004 at 13:23 UTC

    And there's another favorite:

    #!/usr/local/bin/perl use strict; use warnings; use Data::Dumper; my $hash = {}; while( my $line = <DATA> ) { chomp($line); $line =~ m/(\s*)(.*)/; my $level = int(length($1) / 2); my $caption = $2; my $node = { label => $caption, children => [] }; if( $level == 0 ) { $hash = $node; } else { my $hash_item = $hash; for (1 .. ($level - 1)) { $hash_item = @{$hash_item->{children}}[scalar(@{$hash_item +->{children}}) - 1]; } push(@{$hash_item->{children}}, $node); } } print Dumper ($hash); __DATA__ Building House Window Glas Silicium Door Roof Wood Hut Pizza Garage Door
Re: tree in hash
by PodMaster (Abbot) on Jul 22, 2004 at 08:20 UTC

    update3: seeing how i got ++ed besides this code being broken, here it is, fixed up (i also added readmore tags, made clear which update was which):

    use Tree::DAG_Node; use Data::Dumper; local $Data::Dumper::Indent=1; use strict; use warnings; my $t = tits( \*DATA ); #print Dumper( $t ),$/; print Dumper( $t->tree_to_lol ), $/; print map { "$_\n" } @{$t->draw_ascii_tree}; sub tits { my( $fh, $d ) = @_; $d ||= 2; my @t = Tree::DAG_Node->new(); my $depth = 0; my $pdepth = 0; while(defined( $_ = readline $fh )){ chomp; if(/\A((?:\s{$d})+)(.*)\z/){ $depth = length($1)/$d; if( $depth > $pdepth ){ push @t, $t[-1]->new_daughter({ name => $2 }); } elsif( $depth == $pdepth ){ $t[-1] = $t[-1]->mother->new_daughter({ name => $2 }); } else { pop @t until @t == $depth; push @t, $t[-1]->new_daughter({ name => $2 }); } } else { # should only happen at root (depth/pdepth both 0) $t[0]->name($_); } $pdepth = $depth; } return $t[0]; } __DATA__ Building House Window Glas Silicium Door Roof Wood Hut Pizza Garage Door
    $VAR1 = [
      [
        [
          [
            [
              'Silicium'
            ],
            'Glas'
          ],
          'Window'
        ],
        [
          'Door'
        ],
        [
          [
            'Wood'
          ],
          'Roof'
        ],
        'House'
      ],
      [
        [
          'Pizza'
        ],
        'Hut'
      ],
      [
        [
          'Door'
        ],
        'Garage'
      ],
      'Building'
    ];
    
                        |                    
                   <Building>                
               /----------------+-------\    
               |                |       |    
            <House>           <Hut>  <Garage>
        /--------+------\       |       |    
        |        |      |    <Pizza>  <Door> 
     <Window>  <Door> <Roof>                 
        |               |                    
      <Glas>          <Wood>                 
        |                                    
    <Silicium>                               
    
    

    MJD says "you can't just make shit up and expect the computer to know what you mean, retardo!"
    I run a Win32 PPM repository for perl 5.6.x and 5.8.x -- I take requests (README).
    ** The third rule of perl club is a statement of fact: pod is sexy.

Re: tree in hash
by stvn (Monsignor) on Jul 22, 2004 at 16:37 UTC

    If you don't strictly need a nested-hash structure, and are willing to go more OO. You could use a module I created called Tree::Parser.

    It parses many types of structured text into Tree::Simple object hierarchies. After that you can use Tree::Simple::VisitorFactory which supplies a number of Visitor object such as Breadth-first traversal, post-order traversal, gathering descendents, finding the path back to the root, etc. You can also use Tree::Simple::View to easily display your Tree::Simple object hierarchies in HTML and DHTML.

    The Tree::Parser code to do this would look like:

    use Tree::Parser; my $tp = Tree::Parser->new($input); $tp->useSpaceIndentedFilters(2); my $tree = $tp->parse();
    The $input can be any number of things, including a single string (with embedded newlines), an array reference of lines from a file, etc (see the docs for more info). If your file uses tabs (\t) instead of spaces, then you can use the useTabIndentedFilters method instead, or even write your own custom filter, again, see the docs for more info.

    The $tree variable will be a Tree::Simple object hierachy. You can print it out easily with this:

    $tree->traverse(sub { my ($t) = @_; print(("\t" x $t->getDepth()) . $t->getNodeValue() . "\n"); });
    You could also use Tree::Parser's deparse feature as well, which will write it back into the format it was parse from:
    my $deparsed_tree = $tp->deparse(); print $deparsed_tree; # or in array context you get an array of lines my @lines = $tp->deparse(); print join "\n" => @lines;
    If you wanted to traverse your tree breadth-first, it is pretty simple to do with the BreadthFirstTraversal Visitor in Tree::Simple::VisitorFactory.
    use Tree::Simple::VisitorFactory; my $visitor = Tree::Simple::VisitorFactory->get("BreadthFirstTraversal +"); $tree->accept($visitor); print join ", " => $visitor->getResults(); # this prints : Building, House, Hut, Garage, Window, Door, Roof, Pizz +a, Door, Glas, Wood, Silicium
    And if you needed to display your tree's in HTML or DHTML, you can use Tree::Simple::View to do that. This page contains a number of examples of the DHTML output, as well as the code used to create that output. We have tested the DHTML to work on most modern browsers (5.0+), and if you require support on earlier browsers, you can use the HTML output.

    And of course, if you have any questions on these modules, you can either contact me here at PM, or you can email me.

    -stvn