Search code examples
rigraphshortest-pathminimum-spanning-tree

Maximum edge weight in R (igraph)

I have found a minimum spanning tree (MST) of a graph using igraph (minimum.spanning.tree). From this MST I extracted an adjacency matrix with weights. Now I want to get a matrix of the shortest paths in this MST. This is quite easily done using shortest.paths. But I need the matrix A, where the element A(i,j) is the weight of the edge with maximum weight in the shortest path from vertex i to j. I simply do not need the total length of the shortest path in the matrix but only the maximum edge weight. Thanks in advance for any advice. For example

A = matrix(c(0, 0.25, 0, 0, 0.25, 0, 0.5, 0, 0, 0.5, 0, 0.75, 0,0,0.75, 0),nrow=4,ncol=4,   byrow = TRUE)
mst<-graph.adjacency(A, mode=c("undirected"), weighted=TRUE)
shortest.paths(mst)

I do not need shortest.paths(mst) but only weight of the maximum edge in the corresponding shortest path.

Solution

  • For nodes i, j, the max weight in the shortest path is, I think, given by:

    max(E(g,path=get.shortest.paths(g,i,j)$vpath[[1]])$weight)

    (basically get the shortest path, get the edges as a path, find the max weight.

    To magically loop over and make a matrix...

    bigweight = function(g){Vectorize(function(i,j){ifelse(i==j,0,max(E(g,path=get.shortest.paths(g,i,j)$vpath[[1]])$weight))})}

    Then bigweight is a function-generating function.... So you can then do:

    > outer(1:4,1:4,bigweight(mst))
     [,1] [,2] [,3] [,4]
[1,] 0.00 0.25 0.50 0.75
[2,] 0.25 0.00 0.50 0.75
[3,] 0.50 0.50 0.00 0.75
[4,] 0.75 0.75 0.75 0.00

    which should be the matrix of largest weights over edges of shortest paths between i,j.

    Note inefficiency due to symmetry and you can probably speed it up by calling get.shortest.paths with more than one destination node, but I think this works and is a benchmark for testing. Do test it.

    My testing is as far as:

    > E(mst)[[1]]$weight=99
> outer(1:4,1:4,bigweight(mst))
     [,1]  [,2]  [,3]  [,4]
[1,]    0 99.00 99.00 99.00
[2,]   99  0.00  0.50  0.75
[3,]   99  0.50  0.00  0.75
[4,]   99  0.75  0.75  0.00

    which shows if I up the weight from 2 to 1 then it only affects the paths going through 2 to 1 (your sample graph is 1--2--3--4).