R中所有指定长度的简单路径 [英] All simple paths of specified length in R

问题描述

我有以下代码来查找图中两个节点(1和5)之间的所有路径.

I have the following code for finding all the paths between two nodes ( 1 and 5) in the graph.

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

它为我提供了节点之间的所有路径，但是从计算上讲太昂贵了.如果有一个包含数千个节点和边的大型图，则仅查找两个节点之间的路径将花费数小时甚至数小时以上的时间.我有成千上万的节点对，它们将找到指定长度(即长度2，长度3，长度4等)的所有简单路径.以下代码令我满足了所有指定长度的简单路径的要求，但这太昂贵了.任何人都可以帮助我.

It gives me all the paths between nodes, but it is computationally too expensive. If there is a large graph with thousands of nodes and edges, it will take hours or more than hours for just finding paths between two nodes. I have a thousands of pair of nodes for which I will find all simple paths of specified length (i.e., length 2, length 3, length 4 etc.). The following code satisfying me in finding all the simple path of specified length, but it is too expensive. Anyone help me.

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
   }
}

推荐答案

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

You can find simple paths of length n with a simple recursive function. You do not provide any test data so I start with a simple example.

## 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 仍需要花费很长时间.如果我们不需要 all 所有简单路径，而只需要一定长度的路径，则可以有效地获取它们(对于较小的长度).

Even though this graph is not large, running all_simple_paths on it takes a long time. If we don't need all simple paths, but only those of a certain length, we can get them efficiently (for smaller lengths).

## 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

这些实际上是瞬时运行的.

These run practically instantaneously.

这篇关于R中所有指定长度的简单路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！