### representing a tree graphically...

by cLive ;-) (Prior)
 on Jan 09, 2002 at 02:01 UTC Need Help??

cLive ;-) has asked for the wisdom of the Perl Monks concerning the following question:

OK, so someone asked what context my ugly reference question was in yesterday, and since what I'm doing might be useful for someone else, I thought I'd post the problem and my solution to see if (a) someone else could use it or (b) I'm reinventing the wheel and there's a better way commonly known.

```1
|_2
|  \_5
|_3
\_4
```
is stored as 'treepaths', like this:
```1 => 001:000:000
2 => 001:002:000
3 => 001:003:000
4 => 001:003:004
5 => 001:002:005
```
that way, sorting them on these values brings them out in the desired display order.

Now, I want to display a lovely graphical tree depicting this, so I have 5 graphics and assign them values:

```    - a blank square (0)
|#| - a page icon (1)
|_ - an 'L' shape icon (2)
|  - a vertical pipe icon (4)
|- - a "t' shape icon (6)
```
So to create the correct matrix, I take the following rules:
1. create an initial matrix by sorting the treepaths and then splitting them on ':' and converting to a number
```1 0 0
1 2 0
1 2 5
1 3 0
1 3 4
```
2. Then, parsing from right to left,
• change 1st non-zero element to '1'
• change next to '2'
• change remaining to '0'
ie
```1 0 0
2 1 0
0 2 1
2 1 0
0 2 1
```
3. Finally, parse each element, going from bottom right to top left with the rule "For this element, if this element !=1 and the one below it is >=2, add 4. ie
```1 0 0
6 1 0
4 2 1
2 1 0
0 2 1
```
Then just convert each number to the relevant icon and you have a pretty tree structure.

Or am I making a mountain out of a molehill?

cLive ;-)

Replies are listed 'Best First'.
Re: representing a tree graphically...
by merlyn (Sage) on Jan 09, 2002 at 06:30 UTC
I've done some code that does exactly that for a client. The same client that I wrote my most recent Linux Mag column article about, although the part that I wrote up in that past article wasn't the HTML part. But, there's a good chance that I'll write it up for this month, so if you can wait a few days, I'll give you some great code that does that (and even deals with what you would have as "symlinks").
Re: representing a tree graphically...
by hossman (Prior) on Jan 09, 2002 at 03:47 UTC
While you solved your problem, and it (apparently) works -- assuming that someone will some day have to maintain/modify this, it will be a nightmare.

I would suggest that you parse 'treepaths' into a true tree datastructure of some kind (either nested Objects, or a simple hash of hashes). Once you have that, rendering tree's in the way you describe becomes extremely trivial using a recursive method which takes a "node" and a "indenting" depth as input.

They already are in a HoH structure
```\$page->[\$id]->{'parent'} = whatever..
The 'treepath' element is just there to make sorting them a lot easier.

Since it's 'trivial' to render, perhaps you could provide an example? That would really help! Oh, and although I didn't specifiy, the graphical representation is for a web page.

thanks

cLive ;-)

Okay, a couple of things...

1. I don't really understand your example of "\$page->[\$id]->{'parent'}". I don't see how that's a hash of hashes.

2. I underestimated the problem, because of the "|" issue. When I've seen this problem before, the only important issues were:
1. Nest/tab the children properly
2. Do something special for hte first/last child
An example of "pipeless" output is in the method "render_node_nopipe" below

3. Even with the pipes, I still think it's cleaner to use a recursive method -- BUT, instead of passing an "indent" depth, you pass an acctuall padding string, that contains the pipes. The only real new complexity is that when dealing with each node, it's not enough to know if that node is the last of it's siblings, you also have to know if it's parent was the last of it's siblings (in order to build up the padding string properly).
An example of the recursive solution is the method "render_node" below.

4. It should be clear how to make this generate the appropriate HTML (<img src..>) output by modifing the single letter vars.

```#!/usr/local/bin/perl -w
use strict;

my \$d = " #";
my \$t = " +";
my \$l = " \\";
my \$p = " |";
my \$s = "  ";

my \$tree = {
'one' => {
'two' => {
'five' => {
'boo' => {
'baz' => { },
},
},
},
'three' => {
'four' => { },
'yak' => { },
'six' => {
'foo' => {
'yuk' => { },
},
'ggg' => { },
},
},
},
};

print "with pipes...\n" . &render_node(\$tree->{'one'}, 'one');
print "no pipes...\n" . &render_node_tab(\$tree->{'one'}, 'one');

sub render_node {
my (\$tree, \$node, \$tok, \$pad, \$last) = @_;
\$tok  = \$s unless defined \$tok;
\$last = 1  unless defined \$last;

my \$out = \$pad . \$tok . \$d . \$node . "\n";

my @kids = sort keys %{\$tree};
for (my \$i = 0; \$i < scalar @kids; \$i++) {
my \$knode = \$kids[\$i];
my \$ktree = \$tree->{\$knode};
my \$klast = (\$i+1 == scalar @kids);
my \$ktok  = (\$klast ? \$l : \$t);

\$out .= &render_node(\$ktree, \$knode, \$ktok, \$kpad, \$klast);
}
return \$out;
}

sub render_node_tab {
my (\$tree, \$node, \$tok, \$indent) = @_;
\$tok    = \$s unless defined \$tok;
\$indent = 0  unless defined \$indent;

my \$out = (\$s x \$indent) . \$tok . \$d . \$node . "\n";

my @kids = sort keys %{\$tree};

for (my \$i = 0; \$i < scalar @kids; \$i++) {
my \$knode   = \$kids[\$i];
my \$ktree   = \$tree->{\$knode};
my \$ktok    = (\$i+1 == scalar @kids) ? \$l : \$t;
my \$kindent = \$indent+1;

\$out .= &render_node_tab(\$ktree, \$knode, \$ktok, \$kindent);
}

return \$out;
}
__END__
with pipes...
#one
+ #three
| + #four
| + #six
| | + #foo
| | | \ #yuk
| | \ #ggg
| \ #yak
\ #two
\ #five
\ #boo
\ #baz
no pipes...
#one
+ #three
+ #four
+ #six
+ #foo
\ #yuk
\ #ggg
\ #yak
\ #two
\ #five
\ #boo
\ #baz
Re: representing a tree graphically...
by jreades (Friar) on Jan 09, 2002 at 03:53 UTC

Well, it depends. :^)

If this is an HTML-related question, then I've always preferred to use a LoL along the following lines:

• my @submenu = ('div', 'img', 'alt');
• );

This does away with the sorting issue and gives you a fairly obvious way to change parameters in a menu so that if you need a special icon or want to manipulate the menu while writing an HTML file, you can.

Of course, this doesn't have any obvious mechanism for drawing your nodes correctly (this straight scenario works best for DHTML menus where elements aren't supposed to cause a reflow.

For displaying a tree more properly I've found JavaScript objects to be pretty handy (unless you want to write for NN3 or IE3 and early IE4) -- you create a Tree object and Node object and then assign your nodes to the tree in any order using some kind of simple path system. Each node 'knows' how deep it is in the tree (since it can query its parent node) and can draw itself appropriately (again, by querying its parents as necessary).

I don't know if this exactly answers your question since it's unclear (to me at least) what your output format is, and I do like some aspects of your system a lot (the matrix transformations seem quite quick and simple), while having doubts about others (the numbering scheme is unduly difficult for a human to read).

HTH

Re: representing a tree graphically...
by clemburg (Curate) on Jan 09, 2002 at 21:13 UTC

OK, after looking at your sample output I realize this is not what you need ... but anyway, for those that have a similar need (visualizing tree structures) let me point out GraphViz, the Perl interface to the GraphViz tool.

With GraphViz installed, making a little nice postscript (could be PNG, too, or whatever you can postscript convert too) image of your treepath input from above (assumed to be in file try.txt below) becomes as easy as this little shell script:

```echo 'digraph G { concentrate = true; ' > try.dot
cat try.txt | perl -lane '\$F[2] =~ s/:000//g; \$F[2] =~ s/:/ -> /g; \$F[
+2] .= ";"; print \$F[2] if \$F[2] =~ /->/' >> try.dot
echo '}' >> try.dot
dot -Tps -o try.ps try.dot

Where file try.txt is:

```1 => 001:000:000
2 => 001:002:000
3 => 001:003:000
4 => 001:003:004
5 => 001:002:005

Christian Lemburg
Brainbench MVP for Perl
http://www.brainbench.com

```cat try.txt | perl -lane '\$F[2] =~ s/:000//g; \$F[2] =~ s/:/ -> /g; \$F[
+2] .= ";"; print \$F[2] if \$F[2] =~ /->/' >> try.dot
If that had been posted to comp.unix.questions, I'd have given it a Useless Use of Cat Award.

I stand corrected.

Christian Lemburg
Brainbench MVP for Perl
http://www.brainbench.com

(cLive ;-) Re: representing a tree graphically...
by cLive ;-) (Prior) on Jan 09, 2002 at 04:24 UTC

For the curious:

Here's a capture of some sample output (with text added to each row) - each image is 16x16

In answer to another comment - yes, it's easy to work out the 'treepath' by parent lookup, but that doesn't tell you whether to use an 'L' or a '|-', or a '|' or a '|-' for parts of the tree, so I fail to see how you can 'trivially' build the graphic ;-)

cLive ;-)

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://137273]
Approved by root
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (4)
As of 2021-11-28 23:12 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?