使用Perl查找有向图中的所有循环依赖
Finding the all cyclic dependencies in directed graph using Perl
我正在寻找 Perl 脚本可以检测有向图中所有循环节点的问题的解决方案?
例如,我有下图:
A<-N<-G<-L<- A<-B<-C<-D<-E<-F<-A Be a Graph with cyclic edges.
use strict;
use warnings;
my @graphNodes=(A,N,G,L, A,B,C,D,E,F,A );
my depEdges= dependBy(); #Let dependBy be hypothetical function that return immediate dependents.
在其余代码中,我需要逻辑帮助来收集循环依赖中涉及的所有节点。例如,在我的例子中,在节点 'A' 上存在循环依赖。如何递归实现 dependBy 函数来查找循环边或依赖项?
虽然这不是概念上的帮助,但它是最快的解决方案:检查是否有人已经找到了解决方案。在这种情况下,您可以使用 CPAN 中的 Graph 模块来执行此操作。
use strict;
use warnings;
use feature 'say';
use Graph;
my $g = Graph->new;
my @edges = qw(A B C D E F A);
for (my $i =0; $i < $#edges; $i++) {
$g->add_edge($edges[$i], $edges[$i+1]);
}
say $g;
say "is cyclic" if $g->is_cyclic;
say $g->find_a_cycle;
这将输出:
A-B,B-C,C-D,D-E,E-F,F-A
is cyclic
FABCDE
我正在寻找 Perl 脚本可以检测有向图中所有循环节点的问题的解决方案? 例如,我有下图:
A<-N<-G<-L<- A<-B<-C<-D<-E<-F<-A Be a Graph with cyclic edges.
use strict;
use warnings;
my @graphNodes=(A,N,G,L, A,B,C,D,E,F,A );
my depEdges= dependBy(); #Let dependBy be hypothetical function that return immediate dependents.
在其余代码中,我需要逻辑帮助来收集循环依赖中涉及的所有节点。例如,在我的例子中,在节点 'A' 上存在循环依赖。如何递归实现 dependBy 函数来查找循环边或依赖项?
虽然这不是概念上的帮助,但它是最快的解决方案:检查是否有人已经找到了解决方案。在这种情况下,您可以使用 CPAN 中的 Graph 模块来执行此操作。
use strict;
use warnings;
use feature 'say';
use Graph;
my $g = Graph->new;
my @edges = qw(A B C D E F A);
for (my $i =0; $i < $#edges; $i++) {
$g->add_edge($edges[$i], $edges[$i+1]);
}
say $g;
say "is cyclic" if $g->is_cyclic;
say $g->find_a_cycle;
这将输出:
A-B,B-C,C-D,D-E,E-F,F-A
is cyclic
FABCDE