首页 文章

使用Perl在有向图中查找所有循环依赖项

提问于
浏览 次
1

I am looking for the solution to a problem where Perl script could detect all the cyclic nodes in a directed graph? 例如，我有以下图表：

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函数来查找循环边或依赖项？

perl loops graph while-loop cyclic

1 回答

  • 1

    虽然这不是概念上的帮助，但它是最快的解决方案：检查是否有人已找到解决方案 . 在这种情况下，您可以使用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
    回复于

相关问题