[R-sig-Geo] shortest path

[Barry Rowlingson]

On Fri, Aug 31, 2012 at 11:58 AM, Rowlingson, Barry
<b.rowlingson at lancaster.ac.uk> wrote:

>  If I didn't have to be on a train in three hours I'd code this up...

 Oh who am I kidding:

buildTopo <- function(lines){
  require(rgeos)
  require(igraph)

  g = gIntersection(lines,lines)
  edges = do.call(rbind,lapply(g at lines[[1]]@Lines,function(ls){as.vector(t(ls at coords))}))
  lengths = sqrt((edges[,1]-edges[,3])^2+(edges[,2]-edges[,4])^2)

  froms = paste(edges[,1],edges[,2])
  tos = paste(edges[,3],edges[,4])

  graph = graph.edgelist(cbind(froms,tos),directed=FALSE)
  E(graph)$weight=lengths
  return(graph)

}

 > m = readOGR(".","Line")
 > gg = buildTopo(m)

compute shortest distance between two vertices (note the -1 is because
I'm still on old igraph with 0-indexing):

 > E(gg)[get.shortest.paths(gg,V(gg)[1],V(gg)[14])[[1]]-1]

Edge sequence:

[0]  0.81711193 47.57711634 -- -0.28546154 48.4287593
[1]  2.2151139 46.49728033  -- 0.81711193 47.57711634
[9]  1.57160852 45.36348513 -- 2.2151139 46.49728033
[10] 1.39973834 45.06066625 -- 1.57160852 45.36348513
[11] 1.29755246 44.88062446 -- 1.39973834 45.06066625
[12] 0.91544563 43.67971729 -- 1.29755246 44.88062446
[13] 0.88815229 43.43407719 -- 0.91544563 43.67971729

I think this could be improved by adding the coordinates to the nodes.
But anyway, 90% done.

Barry