Perl 종속성 트리 솔버

Question

올바른 순서로 테스트의 회귀를 시작할 수 있도록 의존성을 결정하는 창의적인 방법을 찾으려고합니다. 예를 들어

:이 테스트 "a"는 등 테스트 "D, E 및 F"및 종료에 따라 의미

a: d, e, f 

b: c, d 

c: f 

d: e 

.

나는 "leaf"노드 "e"와 "f"를 인쇄 할 다음 코드를 가지고 있지만, 부모 노드를 가로 지르고 인쇄하는 방법을 고수 할 것입니다. 모든 팁은 크게 감사하겠습니다.

감사합니다.

my @input = ("a:d,e,f", "b:c,d", "c:f", "d:e"); 
my %Tests =(); 
my %Built =(); 

## Build Structure 
foreach my $elem (@input) { 
    my $depends = []; 
    my $target; 
    ($target,$depends) = parseData($elem); 
    $Tests{$target} = $depends; ## Setting array ref to hashkey $target  
} 


sub parseData { 
    my $data = shift; 
    my ($target, $deps) = split(/:/, $data); 
    my @deps; 
    @deps = split(/,/, $deps); 
    return ($target,\@deps); 
} 

foreach my $key (keys %Tests) { 
    doIT(\%Tests, \%Built, $key); 
} 

sub doIT { 
my ($testRef, $builtRef, $target) = @_; 
my $depends = $testRef->{$target}; 
if(exists $builtRef->{$target}) { 
    return; 
} 
if(!$depends) { 
    ## No dependency, build it 
    print "RunTest($target)\n"; 
    $builtRef->{$target}++; 
    return; 
} 

foreach my $dep (@$depends) { 
    doIT($testRef, $builtRef, $dep); 
} 
} 

Answer 1

항상 무력 방법있다 생산 : 예를 들어, 다음은 당신의 종속성을 충족시키는 순서를 제공합니다. 나는 다른 사람이 영리한 뭔가 올 드리겠습니다 :

use strict; 
use warnings; 

my @input = ("a:d,e,f", "b:c,d", "c:f", "d:e"); 

my %children; 
my %parents; 

for (@input) { 
    my ($parent, @kids) = split /[:,]/; 
    for (@kids) { 
     $children{$parent}{$_}++; 
     $children{$_} ||= {}; 
     push @{$parents{$_}}, $parent; 
    } 
} 

my @order; 
while (my $count = scalar keys %children) { 
    while (my ($p, $k) = each %children) { 
     if (! keys %$k) { 
      push @order, $p; 
      delete $children{$p}; 
      delete $children{$_}{$p} for @{$parents{$p}}; 
     } 
    } 

    die "circular dependency exists" if $count == scalar keys %children; 
} 

print "@order"; 

Answer 2

Graph :: Directed와 같은 그래프 모듈을 사용하는 것이 가장 좋습니다.

use Graph::Directed; 

my $graph = Graph::Directed->new(); 

my @edges = qw(d a e a f a c b d b f c e d); 
while (my ($from, $to) = splice @edges, 0, 2) { 
    $graph->add_edge($from, $to); 
} 
my @order = $graph->toposort(); 
print "@order\n"; 

그것은 출력

f e c d a b 

Answer 3

여기 MooX::Role::DependsOn를 사용하여 객체 지향 예입니다.

use feature 'say'; 

# Class (representing a 'job') that consumes MooX::Role::DependsOn: 
package Task; 
use Moo; 
with 'MooX::Role::DependsOn'; 

sub execute { 
    my ($self) = @_; 
    say "execute called for job ".$self->dependency_tag; 
} 

package main; 
# Create some objects that consume MooX::Role::DependsOn: 
my $job = {}; 
for my $jobname (qw/ A B C D E F /) { 
    $job->{$jobname} = Task->new(dependency_tag => $jobname) 
} 

# Add some dependencies: 
# A depends on D, E, F 
$job->{A}->depends_on($job->{D}, $job->{E}, $job->{F}); 
# B depends on C, D 
$job->{B}->depends_on($job->{C}, $job->{D}); 
# C depends on F 
$job->{C}->depends_on($job->{F}); 
# D depends on E 
$job->{D}->depends_on($job->{E}); 

# Resolve dependencies for an object: 
say "Object A:"; 
my @ordered = $job->{A}->dependency_schedule; 
for my $obj (@ordered) { 
    $obj->execute; 
}