All simple paths of specified length in R

Question

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

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

But this is simply a huge computation. I don't think there is a shortcut here. What is the final goal of the operation - perhaps there is a different approach you can take? — Allan Cameron, Nov 10 '20 at 10:50
The final goal is find the all the nodes on all paths with length 2. Similarly, again find all the nodes on all paths with length 3. I just want to compute the similarity between two nodes by using all the nodes between them on specified path length. — abdul samad, Nov 11 '20 at 05:14

score 2 · Accepted Answer · answered Nov 14 '20 at 16:11

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)

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

A few test examples:

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.

All simple paths of specified length in R

1 Answers1

Linked