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

Question

首先，我想澄清一下，我对图论和解析有向图的正确算法知之甚少，而且我在这里进行了搜索，但没有找到我想要的东西。希望你们能帮助我:)

我有一个大型有向图(大约 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模块分以下步骤:

1. 查找图中的所有源节点并将它们存储在数组中
2. 查找图中所有的sink节点并将它们存储在数组中
3. 使用 Floyd-Warshall 算法查找所有对的短路径
4. 搜索 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.:为了使程序运行得更快，我开始尝试将初始大图分解为其子图并运行原始脚本，但使用 Parallel::ForkManager fork 搜索源和接收器之间路径的主循环。 。你们觉得这种方法怎么样？

Answer 1

您对寻找最短路径不感兴趣，因此忘记所有这些最短路径算法。

您有兴趣查找所有路径。这称为树遍历，可以深度优先或广度优先执行。由于您要遍历整棵树，因此采用哪种方法并不重要。下面使用递归执行深度优先搜索:

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

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

我最关心的是内存。根据路径中分支的数量，您可能很容易就会耗尽内存。请注意，将路径存储为字符串(以逗号分隔的值)比将它们存储为数组占用的内存更少。