CODEWITHSUNDEEP
rshortest-path
seema aswani
seema aswani

Reputation: 177

Printing the intermediate vertex sequences in r

I am having a network in which i found the pairwise shortest paths between all the nodes. And i also found the intermediate shortest path sequences. These intermediate shortest path sequences are those sequences like for example the shortest path sequence from node B to node D is B C A D then the intermediate node sequence is C A. I am getting the intermediate shortest path sequence result not in form of ids but in numeric form. For getting vertex sequences i tried the following but in vertex sequences i am getting character(0) as output.My desired output is C A.

library(igraph)
g <- graph.ring(10)
V(g)$name <- LETTERS[1:10]
LETTERS[1:10]
tm <- get.all.shortest.paths(g,"B","D")
tm$res[[1]]
print(V(g)[tm$res[[1]]]) # printing the vertex sequences



for(i in 1:length(V(g))) {
for(k in 1:length(V(g)))
{   
temp <- get.all.shortest.paths(g,i,k) # finding the shortest paths between all nodes
print(temp$res[[1]]) #printing the result of shortest paths
for(j in 1:length(temp$res)) {
  d <- head(tail(temp$res[[j]], length(temp$res[[j]])-1),-1) # Show me only intermediate nodes
  print(d)
  e <- head(tail(V(g)[temp$res[[1]]], length(V(g)[temp$res[[1]]])-1),-1) # Show me only intermediate vertex sequences
  print(e)
}

}
}

In the result of variable e in my script I want to have an intermediate shortest paths vertex sequences. Like for shortest path from node A to C the shortest path sequence is A B D C then i want to have the intermediate nodes as my result except two nodes which are from and to in the shortest path function.

Upvotes: 0

Views: 262

Answers (1)

digEmAll
digEmAll

Reputation: 57210

I slightly modified your code (and reduced the input ring graph to 6 vertices):

library(igraph)
g <- graph.ring(6)
V(g)$name <- LETTERS[1:6]

intermediates <- list() # list to keep the result
for(i in 1:length(V(g))){
  from <- V(g)[i]
  temp <- get.all.shortest.paths(g,from=from,V(g))
  for(el in temp$res){
    to <- V(g)[el[length(el)]]

    # this "if" excludes paths from A to A, B to B etc...
    if(to != from){ 
      intermediate <- tail(head(el,-1),-1)

      # this "if" excludes shortest-paths without intermediate vertices e.g.
      # A -> B, B -> C etc...
      if(length(intermediate) > 0){ 
        intermediates[[length(intermediates)+1]] <- V(g)$name[intermediate] # append this intermediate vertices to list 
        cat('Intermediated vertices of shortest path from ',from$name,' to ',to$name,': ', paste(V(g)$name[intermediate],collapse=','), '\n', sep='')
      }

    }
  }
}

# find the most frequent (N.B. table() creates a table of occurrencies by element)
tbl <- table(unlist(intermediates))
most.freq <- names(tbl)[tbl == max(tbl)]
cat('Most frequent vertex (or vertices in case of ties): ', paste(most.freq,collapse=','),'\n')

Console output:

Intermediated vertices of shortest path from A to C: B
Intermediated vertices of shortest path from A to D: F,E
Intermediated vertices of shortest path from A to D: B,C
Intermediated vertices of shortest path from A to E: F
Intermediated vertices of shortest path from B to D: C
Intermediated vertices of shortest path from B to E: C,D
Intermediated vertices of shortest path from B to E: A,F
Intermediated vertices of shortest path from B to F: A
Intermediated vertices of shortest path from C to A: B
Intermediated vertices of shortest path from C to E: D
Intermediated vertices of shortest path from C to F: D,E
Intermediated vertices of shortest path from C to F: B,A
Intermediated vertices of shortest path from D to A: E,F
Intermediated vertices of shortest path from D to A: C,B
Intermediated vertices of shortest path from D to B: C
Intermediated vertices of shortest path from D to F: E
Intermediated vertices of shortest path from E to A: F
Intermediated vertices of shortest path from E to B: F,A
Intermediated vertices of shortest path from E to B: D,C
Intermediated vertices of shortest path from E to C: D
Intermediated vertices of shortest path from F to B: A
Intermediated vertices of shortest path from F to C: E,D
Intermediated vertices of shortest path from F to C: A,B
Intermediated vertices of shortest path from F to D: E

Most frequent vertex (or vertices in case of ties):  A,B,C,D,E,F

Some notes:

  • get.all.shortest.paths returns all shortest-paths between the vertex from to a list of vertices. So I got rid of your inner loop.
  • get.all.shortest.paths returns also the ties, i.e. if there are two or more equivalent shortest paths between two vertices they are returned (check for example A to D, B to E etc. in the example above).

EDIT :

Added storage of loop results into a list and final computation of the most frequent nodes.

Upvotes: 1

Related Questions