使用 Perl 查找从源节点开始的所有路径

Question

首先，我想澄清一下，我对图论和解析有向图的正确算法的经验很少，而且我已经在 SO 上进行了搜索，但没有完全找到我要找的东西.希望你们能帮助我:)

我有一个大型有向图（大约 3000 个节点），它有几个由连接节点组成的子图，并且子图彼此不连接。这是我这里的数据的一个小代表图：

我正在编写一个 Perl 脚本来查找从每个源节点到汇节点的所有可能路径，并将它们存储在一个数组数组中。因此，对于此图，可能的路径为：

1,2,3,4,5,6
1,2,3,4,5,7
1,8,9,10
11,12,13
11,14
15,16,17

我在脚本中完成此搜索的方法是在以下步骤中使用 Graph 模块：

找到图中的所有源节点并将它们存储在一个数组中
找出图中所有的sink节点，存入数组
使用 Floyd-Warshall 算法查找所有成对的短路径
搜索 APSP Floyd-Warshall 图对象是否存在源节点和汇节点之间的路径。如果有路径，则将其存储在数组的数组中。如果没有路径，什么也不做。

这是我执行此操作的脚本部分：

#Getting all source nodes in the graph:
my @source_nodes = $dot_graph->source_vertices();
my @sink_nodes = $dot_graph->sink_vertices();

# Getting all possible paths between from source to sink nodes in the graph:
print "Calculating all possible overlaps in graph\n";
my $all_possible_paths = $dot_graph->APSP_Floyd_Warshall();
print "Done\n"; 

# print "Extending overlapping contigs\n"; 
my @all_paths;
foreach my $source (@source_nodes) {
    foreach my $sink (@sink_nodes) {
        my @path_vertices = $all_possible_paths->path_vertices($source, $sink);
        my $path_length = $all_possible_paths->path_length($source,$sink);

        #Saving only the paths that actually exist:
        push (@all_paths, \@path_vertices) unless (!@path_vertices);
    }
}

问题在于它适用于小图，但现在我有 3000 个节点，完成它需要非常非常长的时间（假设找到每条路径需要 1 毫秒，它会需要 312.5 天来完成所有这些）。我知道使用 Floyd-Warshall 算法来查找图中所有可能的路径以仅查找源和汇之间的路径效率不高，但是当我编写脚本时我需要尽快得到结果并且我的图小了很多.

我的问题是 如何在不首先找到所有可能路径的情况下找到从图中每个源开始并以汇节点结束的所有路径？是什么称为广度优先或深度优先搜索？如何用 Perl 实现它（如果可能的话，用 Graph 模块）？任何帮助都会很棒！

P.S.: 为了使程序运行更快，我开始尝试将初始大图分解为其子图并运行ning 原始脚本，但是分叉使用 Parallel::ForkManager 搜索源和汇之间路径的主循环。你们觉得这种方法怎么样？

Answer 1

您对寻找最短路径不感兴趣，所以忘掉所有那些最短路径算法吧。

您有兴趣查找所有路径。这称为树遍历，可以执行 depth-first 或 breadth-first。由于您正在遍历整棵树，因此采用哪种方法并不重要。以下使用递归执行 depth-first 搜索：

sub build_paths {
   my ($graph) = @_;

   my @paths;

   local *_helper = sub {
      my $v = $_[-1];
      my @successors = $graph->successors($v);
      if (@successors) {
         _helper(@_, $_)
            for @successors;
      } else {
         push @paths, [ @_ ];
      }
   };

   _helper($_)
      for $graph->source_vertices();

   return \@paths;
}

die if $graph->has_a_cycle;

my $paths = build_paths($graph);

是的，可以并行化工作，但我不是为你写的。

我最关心的是内存。根据路径中分支的数量，您很容易以运行内存不足而告终。请注意，将路径存储为字符串（comma-separated 值）比将它们存储为数组占用的内存更少。

使用 Perl 查找从源节点开始的所有路径

Find all paths starting from source node with Perl

perl

graph-theory

graph

directed-graph