CODEWITHSUNDEEP
rpathigraphshortest-pathdijkstra
abdul samad
abdul samad

Reputation: 61

All simple paths of specified length in R

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

Upvotes: 2

Views: 777

Answers (1)

G5W
G5W

Reputation: 37641

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)

small test graph

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.

Upvotes: 3

Related Questions