Re: [igraph] shortest path between all nodes on a weighted network

[Gabor Csardi]

Colin,

igraph is claimed to be good in rapid prototyping, well it isn't that good,
it took me some time to implement for the weighted shortest path
problem, especially the line with 'lapply' is nasty. So it was a good
experiment.

wsp <- function(g, from=V(g), weights=E(g)$weight) {
  if (!is.igraph(g)) {
    stop("Not a graph object!")
  }
  if (is.null(weights)) {
    stop("Weights missing")
  }
  if (!is.connected(g)) {
    stop("Unconnected graph")
  }
  
  vc <- vcount(g)
  from <- as.numeric(from)
  res <- matrix(0, nr=length(from), nc=vc)
  for (i in seq(along=from)) {
    visited <- logical(vc)
    visited[from[i]+1] <- TRUE
    while (any(!visited)) {
      edges <-  E(g) [ V(g)[visited] %--% V(g)[!visited] ]
      ft <- matrix(unlist(lapply(edges, function(x) get.edge(g, x))), nr=2)
      weig <- weights[ edges+1 ] + res[i, ft[1,]+1] + res[i, ft[2,]+1]
      minw <- which.min(weig)
      ft <- ft[,minw]
      if (visited[ft[2]+1]) ft <- rev(ft)
      res[i, ft[2]+1] <- weig[minw]
      visited[ ft+1 ] <- TRUE
    }
  }
  res
}

I haven't tested it too much though. It cannot handle negative
weights. Probably a Bellman-Ford algorithm would have been better.


Best,
Gabor

On Wed, Apr 11, 2007 at 04:25:44PM -0400, Colin Garroway wrote:
>    Gabor,
> 
>    Thanks for the quick response.  I'll keep working at it.
> 
>    Again I'm new to networks but Holme et al. 2007 Physica A 373 (2007),
>    821-830 ([1]http://arxiv.org/abs/cond-mat/0411634 ) seem to have come up
>    with a clustering coefficient for weighted networks that has all the
>    typical desired porperties.
> 
>    Colin
> 
>    On 11/04/07, Gabor Csardi <address@hidden> wrote:
> 
>      Colin,
> 
>      the short answer is no, this is not possible.
>      Some igraph functions can handle weighted edges,
>      but the shortest path and the transitivity functions can't. (Btw. how
>      to define the weighted transitivity of a network?)
> 
>      Check the sna and the RBGL packages, these might help. Unfortunately
>      igraph is quite bad on weighted networks.
> 
>      Best,
>      Gabor
> 
>      On Wed, Apr 11, 2007 at 03:55:20PM -0400, Colin Garroway wrote:
>      >    Hello All,
>      >
>      >    I have a small undirected weighted network.  34 nodes and 93
>      edges.  Edges
>      >    are weighted as the dissimilarity between between nodes.  I want to
>      >    determine the shortest path length between all nodes.  Is this
>      possible in
>      >    igraph or an existing R package?  Also does transitivity
>      calculation
>      >    incorporate edge weight some how?
>      >
>      >    I am new to igraph and relatively new to R and am quite stuck on
>      the
>      >    shortest path question.  Any suggestions would be greatly
>      appreciated.
>      >
>      >    Thank you
>      >    Colin
> 
>      > _______________________________________________
>      > igraph-help mailing list
>      > address@hidden
>      > [4]http://lists.nongnu.org/mailman/listinfo/igraph-help
> 
>      --
>      Csardi Gabor <address@hidden>    MTA RMKI, ELTE TTK
> 
>      _______________________________________________
>      igraph-help mailing list
>      address@hidden
>      [7]http://lists.nongnu.org/mailman/listinfo/igraph-help
> 
>    --
>    Colin Garroway (PhD candidate)
>    Wildlife Research and Development Section
>    Ontario Ministry of Natural Resources
>    c/o Trent University
>    DNA Building
>    2140 East Bank Drive
>    Peterborough, ON, K9J 7B9
>    Canada
>    Phone: 705-755-1535
> 
> References
> 
>    Visible links
>    1. http://arxiv.org/abs/cond-mat/0411634
>    2. mailto:address@hidden
>    3. mailto:address@hidden
>    4. http://lists.nongnu.org/mailman/listinfo/igraph-help
>    5. mailto:address@hidden
>    6. mailto:address@hidden
>    7. http://lists.nongnu.org/mailman/listinfo/igraph-help

> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help


-- 
Csardi Gabor <address@hidden>    MTA RMKI, ELTE TTK