R中指定长度的所有简单路径

Question

我有以下代码用于查找图中两个节点（1 和 5）之间的所有路径。

pxy= all_simple_paths(graph,1,5)  #get all paths between node 1 and 5

它为我提供了节点之间的所有路径，但计算成本太高。如果有一个包含数千个节点和边的大图，光是找到两个节点之间的路径就需要数小时或数小时以上。我有几千对节点，我会为它们找到指定长度的所有简单路径（即长度 2、长度 3、长度 4 等 ）。下面的代码满足了我找到 指定长度 的所有简单路径的要求，但它太昂贵了。谁帮帮我。

L=2                             #set length 
for (i in 1:length(pxy)){
   plist = as.vector(pxy[[i]])  #check every path one by one
   if(length(plist)==L){        #find path of specified length
      print(plist)              #display path
   }
}

Answer 1

您可以使用简单的递归函数找到长度为 n 的简单路径。你没有提供任何测试数据，所以我从一个简单的例子开始。

## test data
set.seed(1234)
g2 = erdos.renyi.game(20, 0.2)
plot(g2, layout=layout_with_graphopt)

## Commented out because this will run a LONG time
## all_simple_paths(g2,3,9)

虽然这张图不大，但是运行宁all_simple_paths要花很长时间。如果我们不需要所有个简单路径，而只需要特定长度的路径，我们可以高效地获取它们（对于更小的长度）。

## Recursively find simple paths of length n
SimplePathsLengthN = function(graph, node1, node2, pathlength=2) {
    SP = list()
    if(pathlength == 1) {
        if(node2 %in% neighbors(graph, node1)) {
            SP[[1]] = c(node1, node2) }
        return(SP) }
    Nbrs2 = neighbors(graph, node2)
    for(nbr2 in Nbrs2) {
        ASPn2 = SimplePathsLengthN(graph, node1, nbr2, pathlength-1)
        for(i in seq_along(ASPn2)) {
            if(!(node2 %in% ASPn2[[i]])) {
                SP = append(SP, list(c(ASPn2[[i]], node2))) }
        }
    }
    return(SP)
}

几个测试例子：

SimplePathsLengthN(g2, 4, 17, 3)
[[1]]
[1]  4 13  1 17
[[2]]
[1]  4 19  2 17

SimplePathsLengthN(g2, 4, 1, 4)
[[1]]
[1]  4 19  2  8  1
[[2]]
[1]  4 19 11 13  1
[[3]]
[1]  4 19  2 17  1

这些运行几乎是瞬时的。

R中指定长度的所有简单路径

All simple paths of specified length in R

r

path

dijkstra

shortest-path

igraph