小编ped*_*000的帖子

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

我有一个大型有向图（大约 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 …