Turning a set of parent-child relationships into a hierarchical structure

Question

I have an LDAP directory that I'm querying using Net::LDAP. This gives me a set of parent-child relationships.

It's a directory of people - and includes a 'manager' DN (which is another field within the directory).

I'm having real trouble turning this manager->person set of records into a hierarchical structure.

What I've got so far is:

#!/usr/bin/env perl
use strict;
use warnings;
use Net::LDAP;
use Data::Dumper;

my %people;

my $ldap   = Net::LDAP->new('my_ldap_server');
my $result = $ldap->bind('bind_dn');
die if $result->code;

my $search = $ldap->search(
    base   => 'ou=yaddayadda',
    scope  => 'subtree',
    filter => 'objectClass=person',
    attrs  => ['manager'],
);
foreach my $found ( $search->entries ) {
    my $mgr = $found->get_value('manager');
    my $dn  = $result->dn;
    push( @{ $people{$mgr} }, $dn );
}

What this gives me is a hash of managers and the people who work for them (using DN, which is unique).

An entry from %people looks like:

$VAR1 = { 
            'cn=Firstname Lastname,ou=OrgUnit' => [
                          'cn=Personame Lastname,ou=OrgUnit',
                          'cn=AnotherPerson NameHere,ou=OrgUnit', 
                         ],
            'cn=AnotherPerson NameHere,ou=OrgUnit' => [
                         'cn=Someone Else,ou=OrgUnit', 
                         ]
           };

But I'm having trouble with turning that parent-child mapping into a hierarchical structure.

e.g.:

'ceo' => [
             'pa' => [],
             'head_of_dept' => [ 
                       'person' => [],
                       'person_with_staff' => [ 'person3', 'person4' ]
                    ]
          ]

I'm at something of a loss for how to accomplish this. It seems it shouldn't be too hard to do, given that each person is unique within the organisation structure.

NB - in the above, I've got cn=AnotherPerson NameHere,ou=OrgUnit who has a subordinate, and I'm after making a nested mapping out of this:

e.g.:

$VAR1 = {
          'cn=Firstname Lastname,ou=OrgUnit' => [
                                                  'cn=Personame Lastname,ou=OrgUnit',
                                                  'cn=AnotherPerson NameHere,ou=OrgUnit',
                                                  [
                                                    'cn=Someone Else,ou=OrgUnit'
                                                  ]
                                                ]
        };

Answer 1

What you need is a directed graph, and I suggest using the Graph::Directed module, whose methods are documented in Graph

This program will build the graph for you, but without any data I couldn't test it beyond making sure it compiles

use strict;
use warnings 'all';
use feature 'say';

use Net::LDAP;
use Graph::Directed;
use Data::Dumper;

my $ldap   = Net::LDAP->new('my_ldap_server');
my $result = $ldap->bind('bind_dn');
die if $result->code;

my $search = $ldap->search(
    base   => 'ou=yaddayadda',
    scope  => 'subtree',
    filter => 'objectClass=person',
    attrs  => ['manager'],
);

my $g = Graph::Directed->new;

for my $found ( $search->entries ) {
    my $mgr = $found->get_value('manager');
    my $dn  = $result->dn;
    $g->add_edge($mgr, $dn);
}

say $g;

The resulting Graph::Directed object has a stringification overload so you can examine it superficially by simply printing it, but when you want to interrogate the structure further you will need to know some of the terms of graph theory. For instance, $g->source_vertices will return a list of all nodes that have descendants but no parents—in this case, a list of senior management, or $g->is_cyclic will return true if your data has any loops anywhere

---

Here's an example of a program that uses your brief sample data to display a hierarchical tree of nodes

use strict;
use warnings 'all';
use Graph::Directed;

my $data = {
    'cn=Firstname Lastname,ou=OrgUnit' => [
        'cn=Personame Lastname,ou=OrgUnit',
        'cn=AnotherPerson NameHere,ou=OrgUnit',
    ],
    'cn=AnotherPerson NameHere,ou=OrgUnit' =>
        [ 'cn=Someone Else,ou=OrgUnit', ]
};

my $g = Graph::Directed->new;

for my $mgr ( keys %$data ) {
    $g->add_edge($mgr, $_) for @{ $data->{$mgr} };
}

dump_tree($_) for $g->source_vertices;


sub dump_tree {
    my ($node, $level) = ( @_, 0);
    print '   ' x $level, $node, "\n";
    dump_tree($_, $level+1) for $g->successors($node);
}

output

cn=Firstname Lastname,ou=OrgUnit
   cn=AnotherPerson NameHere,ou=OrgUnit
      cn=Someone Else,ou=OrgUnit
   cn=Personame Lastname,ou=OrgUnit

Answer 2

@Hunter McMillen unfortunately deleted his very good but slightly off answer. Here is my attempt to augment his code by turning the relationship from underling -> boss towards boss -> underlings.

To simulate the LDAP responses, I created a simple Moose class.

package Person;
use Moose;

has name => ( is => 'ro' );
has boss => ( is => 'ro', predicate => 'has_boss' );

package main;
use strict;
use warnings;
use Data::Printer;

# make a randomized list of people
my %people = map { $_->name => $_ }
    map { 
      Person->new( 
        name => $_->[0], ( $_->[1] ? ( boss => $_->[1] ) : () ) 
      ) 
    } (
      [qw( ceo )],                       [qw( head_of_dept ceo)],
      [qw( person head_of_dept)],        [qw( person_with_staff head_of_dept )],
      [qw( person3 person_with_staff )], [qw( person4 person_with_staff )],
    );

my %manages;
foreach my $p (values %people) {
    push @{ $manages{ $p->boss } }, $p->name if $p->has_boss;
}

# this part shamelessly stolen from @HunterMcMillen's deleted answer
sub build_tree {
    my ($person) = @_;

    my @subtrees;
    foreach my $managee ( @{ $manages{$person} } ) {
        push @subtrees, build_tree($managee);
    }

    return { $person => \@subtrees };
}

p build_tree 'ceo';

Here's the output.

\ {
    ceo   [
        [0] {
            head_of_dept   [
                [0] {
                    person   []
                },
                [1] {
                    person_with_staff   [
                        [0] {
                            person4   []
                        },
                        [1] {
                            person3   []
                        }
                    ]
                }
            ]
        }
    ]
}

This should be more or less what you want.