perl - 将一组父子关系转化为层次结构

Question

我有一个 LDAP 目录，我正在使用 Net::LDAP 进行查询.这给了我一套父子关系。

这是一个人员目录 - 并包括一个“经理”DN(这是目录中的另一个字段)。

我在将这个经理 ->人员记录集转换为层次结构时遇到了真正的麻烦。

到目前为止，我得到的是:

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

这给了我一个经理和为他们工作的人的散列(使用 DN，这是独一无二的)。

来自 %people 的条目好像:

$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', 
                         ]
           };

但是我在将父子映射转换为层次结构时遇到了麻烦。

例如。:

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

我不知道如何做到这一点。鉴于每个人在组织结构中都是独一无二的，这似乎不应该太难做到。

注意 - 在上面，我有 cn=AnotherPerson NameHere,ou=OrgUnit谁有一个下属，我在做一个嵌套映射之后:

例如。:

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

Answer 1

您需要的是有向图，我建议使用 Graph::Directed 模块，其方法记录在 Graph

该程序将为您构建图表，但没有任何数据我无法测试它除了确保它编译

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;

结果 Graph::Directed对象具有字符串化重载，因此您可以通过简单地打印它来进行表面检查，但是当您想进一步询问结构时，您需要了解 graph theory 的一些术语.例如， $g->source_vertices将返回所有有后代但没有 parent 的节点的列表——在这种情况下，是高级管理人员的列表，或 $g->is_cyclic如果您的数据在任何地方有任何循环，将返回 true



这是一个程序示例，它使用您的简短示例数据来显示节点的层次结构树

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);
}

输出

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