Include a set of parent-child relationships in a hierarchical structure

Question

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

This is a directory of people - and includes a "manager" DN (this is another field in the directory).

I am having problems turning this manager → set of people records into a hierarchical structure.

What I have so far:

 #!/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 ); } 

This gives me a hash of managers and the people who work for them (using a unique unique DN).

The entry from %people looks like this:

 $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 am having trouble converting this parent-child mapping to a hierarchical structure.

eg:.

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

I am at a loss how to do this. It does not seem to be too difficult to do, given that each person is unique in the structure of the organization.

NB - in the above example, I have cn=AnotherPerson NameHere,ou=OrgUnit , who has a subordinate, and I will make a nested mapping from this:

eg:.

 $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 a graph for you, but without any data, I could not check it, except that 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 string overloading, so you can test it superficially by simply printing it, but when you want to interrogate the structure further, you need to know some terms of graph theory . For example, $g->source_vertices will return a list of all nodes that have children but no parents. In this case, the senior management list or $g->is_cyclic will return true if your data has any loops anywhere

---

Here is an example program that uses your brief data examples 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 responsive . Here is my attempt to increase his code by turning the relationship from chin → boss to boss → subordinates.

To simulate 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 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 is the conclusion.

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

It should be more or less what you want.