A list of parents and children. How to make a tree?

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

I am not a novice programmer, but this has been the most difficult programming task I've ever had to accomplish.

There is a big room full of about 150 people. I have a list of the names of all of the people, and their parents. Some of the people there are older, and have no living or present parents, and thus no parents on the list. The goal is to create a javascript menu of parents, and their children, until finally, the youngest have no children.

I have a list of people, and for each person, a list of their parents (if the parents are present). If the parents are not present at the gathering, they are not listed.

I've managed to get the data in a sort of hash of hash of list format like this:


$VAR1 = {
          'Sally Smith' => {
                            'parents' => [
                                           'Bob Smith', 'Rhonda Smith'
                                         ]
                          },
          'Betty Freeman' => {
                            'parents' => [
                                           'Earl Freeman', 'Harmony El
+lis'
                                         ]
                          },
          'Betty Boop' => {
                            'parents' => [
                                           'Rhonda Smith', 'Louis McFe
+rn'
                                         ]
                          },
};
[download]

How can I put this in some format (perl data structure) that I can easily turn into a menu list.

I was thinking that I would start by making a list of all of the individuals that do not have any parents. This would give me a root menu, no problem there.

Now, for each of those parents, in the root menu, I have a function called get_immediate_children($person,\%hash) which returns a reference to an array/list of children.

Man this is getting complicated fast. Is there a really easy way to do this? There must be!

What is the best format to use? I was think about something like:

$menu[$level] = 0; #<- contains several hashes of individuals and thei
+r children as lists
$menu[$level] = 1; #<- for each of those children, a new hash with the
+ir children as lists
$menu[$level] = 2; #<- for each of those children, a new hash with the
+ir children as lists
...
...
[download]

, and so on, until every individual has been accounted for

Please, is there a monk available to shed some light on the problem?

Comment on A list of parents and children. How to make a tree? Select or Download Code

Replies are listed 'Best First'.
Re: A list of parents and children. How to make a tree? by bobr (Monk) on Jan 01, 2010 at 21:45 UTC
Hello, I played a bit with your input. Maybe it would be of help. First I added one person (Jim Morris) to have three levels in your data: `my $input = { 'Sally Smith' => { parents => ['Bob Smith', 'Rhonda Smith']}, 'Betty Freeman' => { parents => ['Earl Freeman', 'Harmony Ellis']} +, 'Betty Boop' => { parents => ['Rhonda Smith', 'Louis McFern']}, 'Jim Morris' => { parents => ['Betty Boop', 'John Wayne']}, };` [download] You wrote that you want to descent from top, so I made new structure with children relationships and listing all people: `my $people = {}; for my $m (keys %$input) { add_person($people,$m, parents => $input->{$m}{parents}); for my $p (@{ $input->{$m}{parents} }) { add_person($people,$p,children => $m); } } sub add_person { my ($people,$name,%params) = @_; if(! defined $people->{$name}) { $people->{$name} = { children => [], parents => [] }; } for my $par (keys %params) { push @{ $people->{$name}{$par} }, ref($params{$par}) eq "ARRAY" ? @{$params{$par}} : $params +{$par}; } }` [download] The `$people` structure dumped: { "Betty Boop" => { children => ["Jim Morris"], parents => ["Rhond +a Smith", "Louis McFern"], }, "Betty Freeman" => { children => [], parents => ["Earl Freeman", "Ha +rmony Ellis"] }, "Bob Smith" => { children => ["Sally Smith"], parents => [] }, "Earl Freeman" => { children => ["Betty Freeman"], parents => [] }, "Harmony Ellis" => { children => ["Betty Freeman"], parents => [] }, "Jim Morris" => { children => [], parents => ["Betty Boop", "John + Wayne"] }, "John Wayne" => { children => ["Jim Morris"], parents => [] }, "Louis McFern" => { children => ["Betty Boop"], parents => [] }, "Rhonda Smith" => { children => ["Sally Smith", "Betty Boop"], pare +nts => [] }, "Sally Smith" => { children => [], parents => ["Bob Smith", "Rhond +a Smith"] }, } [download] Now you can start with people not having any parents and recurse over children. `for my $top_level (sort keys %$people) { next if @{ $people->{$top_level}{parents} }; print_level($people,$top_level,0); } sub print_level { my ($people,$name,$level) = @_; print " "x$level,$name,"\n"; for my $child (@{ $people->{$name}{children} }) { print_level($people,$child,$level+1); } }` [download] It produces this tree using indentation: `Bob Smith Sally Smith Earl Freeman Betty Freeman Harmony Ellis Betty Freeman John Wayne Jim Morris Louis McFern Betty Boop Jim Morris Rhonda Smith Sally Smith Betty Boop Jim Morris` [download] Is this what you expected to see? If yes, producing some kind of javascript tree should be quite easy. -- Roman	[reply] [d/l] [select]
Re^2: A list of parents and children. How to make a tree? by tejinashi (Initiate) on Jan 03, 2010 at 10:44 UTC
I really like this solution whereas it does not require any external perl modules. The recursive function was the key to this problem, and your solution was simple and elegant. Thank you!	[reply]
Re: A list of parents and children. How to make a tree? by Anonymous Monk on Jan 01, 2010 at 21:21 UTC
What is a menu list? :) Its easier to wrap your head around this problem when you don't have to worry about the details of data structures, so I would use Gedcom or Tree::Simple to map relationships, and maybe Tree::Simple::View::DHTML for display. Example Read more... (2 kB) Bob Smith Sally Smith Louis McFern Betty Boop Harmony Ellis Betty Freeman Earl Freeman Betty Freeman Rhonda Smith Sally Smith Betty Boop	[reply] [d/l]