Perl two column flat file to a complex unordered l

Question

I have a data file for an organizational chart that has been pulled from our AD structure and looks like this, with the Manager being the first field, and the employee the second - in some situations a manager will look after a few staff:

__EXAMPLE__
user4   user8
user8   user9
    user1
user1   user2
user2   user3
user2   user5
user2   user4
user3   user5
user4   user6
user4   user7

This needs to be output in a HTML unordered list such as this:

# Intended output
#
# <ul>
#   <li>user1</li>
#   <ul>
#       <li>user2</li>
#       <ul>
#           <li>user3</li>
#           <ul>
#               <li>user5</li>
#           </ul>
#           <li>user4</li>
#           <ul>
#               <li>user6</li>
#               <li>user7</li>
#               <li>user8</li>
#             <ul>
#               <li>user9</li>
#             </ul>
#           </ul>
#       </ul>   
#   </ul>
# </ul>

I've figured I can probably use the example code at this location: Parse Text file and create complex tree structure in perl but I'm struggling to get the initial example into the required format.

I've got some code which sucks the whole datafile into an array, checks the Manager value is not null, then recursively tries to match the next manager up the tree (until it hits the null) which should give me the output like:

user1
user1 user2
user1 user2 user3
user1 user2 user3 user5
user1 user2 user4
user1 user2 user4 user6
user1 user2 user4 user7
user1 user2 user4 user8
user1 user2 user4 user8 user9

Unfortunately my Perl is very rusty and my code looks terrible; I'm not sure I'm approaching this the best way, so was hoping to get some words of wisdom from someone wiser than me.

Current example:

#!/usr/bin/perl
#
use strict;
use warnings;

my @Complete = <DATA>;

foreach my $line (@Complete) {
    chomp($line);
    my ($fl, $usr) = split(/\t/, $line); #Formal Leader && User
    foreach my $leader (@Complete) {
        chomp($leader);
        if ($leader =~ /$fl$/) {
            $line = $leader."\t".$usr;
            ($fl,$usr) = split(/\t/, $line, 2);
            $leader = '';
        }
        last if ($fl eq '');
    }
    print "'".$line."'\n";
}

__DATA__
user4   user8
user8   user9
    user1
user1   user2
user2   user3
user2   user5
user2   user4
user3   user5
user4   user6
user4   user7

Answer 1

The following program is close to what you want:

use strict;
use warnings;

use HTML::Entities;

sub render {
    my ($underlings_of, $level, $key) = @_;
    my $underlings = $underlings_of->{$key} or return;
    print "  " x $level, "<ul>\n";
    for my $underling (sort @$underlings) {
        print "  " x ($level + 1), "<li>", encode_entities($underling), "</li>\n";
        render($underlings_of, $level + 1, $underling);
    }
    print "  " x $level, "</ul>\n";
}

my %underlings_of;

while (my $line = readline DATA) {
    chomp $line;
    my ($mgr, $emp) = split /\t/, $line;
    push @{$underlings_of{$mgr}}, $emp;
}

render(\%underlings_of, 0, '');

__DATA__
user4   user8
user8   user9
    user1
user1   user2
user2   user3
user2   user5
user2   user4
user3   user5
user4   user6
user4   user7

It produces the following output:

<ul>
  <li>user1</li>
  <ul>
    <li>user2</li>
    <ul>
      <li>user3</li>
      <ul>
        <li>user5</li>
      </ul>
      <li>user4</li>
      <ul>
        <li>user6</li>
        <li>user7</li>
        <li>user8</li>
        <ul>
          <li>user9</li>
        </ul>
      </ul>
      <li>user5</li>
    </ul>
  </ul>
</ul>

User user5 is listed twice because they appear twice in the input hierarchy, under user2 and under user3. This means your structure isn't really a tree, it's a directed acyclic (hopefully) graph.

For other approaches, https://en.wikipedia.org/wiki/Topological_sorting may be helpful because I believe your problem is an instance of topological sorting.