Re: [R-sig-Geo] Shortest-path (railway) distance calculation using R
Hi, You could use igraph package to do this See Barry Rowlingson's method : http://rpubs.com/geospacedman/routing Otherwrise, with OSM data, you can use osmar package. But I don't think you can coerce a SpatialLines object to an osmar one. Maybe if you convert your data into OSM XML data using GDAL first ? http://osmar.r-forge.r-project.org/ Hope this helps, Mathieu 2013/10/24 Daisuke Murakami murak...@sk.tsukuba.ac.jp Thank you very much! Daisuke Have you looked at http://cran.r-project.org/web/views/Spatial.html, specifically the `rgeos` package? Cheers, Roman On Wed, Oct 23, 2013 at 11:03 AM, Daisuke Murakami murak...@sk.tsukuba.ac.jp wrote: Hi everyone, I try to calculate railway distances from a railway station to the other stations on R. I have shp files of the stations and railway. Does anyone know useful R package/function for the distance calculation? Sincerely, Daisuke ___ R-sig-Geo mailing list R-sig-Geo@r-project.org https://stat.ethz.ch/mailman/listinfo/r-sig-geo -- In God we trust, all others bring data. ___ R-sig-Geo mailing list R-sig-Geo@r-project.org https://stat.ethz.ch/mailman/listinfo/r-sig-geo [[alternative HTML version deleted]] ___ R-sig-Geo mailing list R-sig-Geo@r-project.org https://stat.ethz.ch/mailman/listinfo/r-sig-geo
Re: [R-sig-Geo] Shortest-path (railway) distance calculation using R
Thank you for the interesting advice. I'll check it. Daisuke, Hi, You could use igraph package to do this See Barry Rowlingson's method : http://rpubs.com/geospacedman/routing Otherwrise, with OSM data, you can use osmar package. But I don't think you can coerce a SpatialLines object to an osmar one. Maybe if you convert your data into OSM XML data using GDAL first ? http://osmar.r-forge.r-project.org/ Hope this helps, Mathieu 2013/10/24 Daisuke Murakami murak...@sk.tsukuba.ac.jp Thank you very much! Daisuke Have you looked at http://cran.r-project.org/web/views/Spatial.html, specifically the `rgeos` package? Cheers, Roman On Wed, Oct 23, 2013 at 11:03 AM, Daisuke Murakami murak...@sk.tsukuba.ac.jp wrote: Hi everyone, I try to calculate railway distances from a railway station to the other stations on R. I have shp files of the stations and railway. Does anyone know useful R package/function for the distance calculation? Sincerely, Daisuke ___ R-sig-Geo mailing list R-sig-Geo@r-project.org https://stat.ethz.ch/mailman/listinfo/r-sig-geo -- In God we trust, all others bring data. ___ R-sig-Geo mailing list R-sig-Geo@r-project.org https://stat.ethz.ch/mailman/listinfo/r-sig-geo ___ R-sig-Geo mailing list R-sig-Geo@r-project.org https://stat.ethz.ch/mailman/listinfo/r-sig-geo
Re: [R-sig-Geo] Shortest-path (railway) distance calculation using R
Have you looked at http://cran.r-project.org/web/views/Spatial.html, specifically the `rgeos` package? Cheers, Roman On Wed, Oct 23, 2013 at 11:03 AM, Daisuke Murakami murak...@sk.tsukuba.ac.jp wrote: Hi everyone, I try to calculate railway distances from a railway station to the other stations on R. I have shp files of the stations and railway. Does anyone know useful R package/function for the distance calculation? Sincerely, Daisuke ___ R-sig-Geo mailing list R-sig-Geo@r-project.org https://stat.ethz.ch/mailman/listinfo/r-sig-geo -- In God we trust, all others bring data. [[alternative HTML version deleted]] ___ R-sig-Geo mailing list R-sig-Geo@r-project.org https://stat.ethz.ch/mailman/listinfo/r-sig-geo
Re: [R-sig-Geo] Shortest-path (railway) distance calculation using R
Thank you very much! Daisuke Have you looked at http://cran.r-project.org/web/views/Spatial.html, specifically the `rgeos` package? Cheers, Roman On Wed, Oct 23, 2013 at 11:03 AM, Daisuke Murakami murak...@sk.tsukuba.ac.jp wrote: Hi everyone, I try to calculate railway distances from a railway station to the other stations on R. I have shp files of the stations and railway. Does anyone know useful R package/function for the distance calculation? Sincerely, Daisuke ___ R-sig-Geo mailing list R-sig-Geo@r-project.org https://stat.ethz.ch/mailman/listinfo/r-sig-geo -- In God we trust, all others bring data. ___ R-sig-Geo mailing list R-sig-Geo@r-project.org https://stat.ethz.ch/mailman/listinfo/r-sig-geo
Re: [R-sig-Geo] shortest path
Edzer, I'm sorry. The only control I did was checking if the resulting network looked right. At a global extent, it was, but zooming in revealed some errors. The reason why I didn't compute the shortest path calculation on my script is that I didn't have the minimum knowledge in igraph to do it. That's why I said I didn't test the script completely. I should have mentionned I expected some feedback on the shortest path calculation. Your feedback and the code published by Barry helped me do some deeper inspection. The fact is that the lines that must go from one point to the nearest point on the lines network are well created but some connect to the network, some not. For those who don't, the distance between the end segment point and the line to which it is supposed is extremely small. My intent wasn't to pollute this thread, rather to contribute to it, not as an expert, which I am not, but as a beginner. I'll be more cautious in the future, with all the respect I owe to the R-sig-geo contributors who participate on the list. Mathieu 2012/9/11 Edzer Pebesma edzer.pebe...@uni-muenster.de On 09/10/2012 12:47 PM, Mathieu Rajerison wrote: Barry, I looked at your code and I wondered if it would not be more convenient to find the closest point on a an edge rather than the closest vertex? In this case, what technique would be the best? I thought of spatstat::project2Segment that I used in my script (but Edzer says it doesn't work - I have to check that) I only made a comment on sending untested scripts, I made no comment on whether project2Segment did what you want it to do. Mathieu 2012/9/10 Mathieu Rajerison mathieu.rajeri...@gmail.com It looks really nice. Thanks Barry! 2012/9/9 Barry Rowlingson b.rowling...@lancaster.ac.uk I've just pushed a cleanup and a bunch of examples to RPubs: http://rpubs.com/geospacedman/routing It uses the latest igraph! It's all there, building the network and routing and plotting. Barry ___ R-sig-Geo mailing list R-sig-Geo@r-project.org https://stat.ethz.ch/mailman/listinfo/r-sig-geo -- Edzer Pebesma Institute for Geoinformatics (ifgi), University of Münster Weseler Straße 253, 48151 Münster, Germany. Phone: +49 251 8333081, Fax: +49 251 8339763 http://ifgi.uni-muenster.de http://www.52north.org/geostatistics e.pebe...@wwu.de [[alternative HTML version deleted]] ___ R-sig-Geo mailing list R-sig-Geo@r-project.org https://stat.ethz.ch/mailman/listinfo/r-sig-geo
Re: [R-sig-Geo] shortest path
It looks really nice. Thanks Barry! 2012/9/9 Barry Rowlingson b.rowling...@lancaster.ac.uk I've just pushed a cleanup and a bunch of examples to RPubs: http://rpubs.com/geospacedman/routing It uses the latest igraph! It's all there, building the network and routing and plotting. Barry ___ R-sig-Geo mailing list R-sig-Geo@r-project.org https://stat.ethz.ch/mailman/listinfo/r-sig-geo [[alternative HTML version deleted]] ___ R-sig-Geo mailing list R-sig-Geo@r-project.org https://stat.ethz.ch/mailman/listinfo/r-sig-geo
Re: [R-sig-Geo] shortest path
Barry, I looked at your code and I wondered if it would not be more convenient to find the closest point on a an edge rather than the closest vertex? In this case, what technique would be the best? I thought of spatstat::project2Segment that I used in my script (but Edzer says it doesn't work - I have to check that) Mathieu 2012/9/10 Mathieu Rajerison mathieu.rajeri...@gmail.com It looks really nice. Thanks Barry! 2012/9/9 Barry Rowlingson b.rowling...@lancaster.ac.uk I've just pushed a cleanup and a bunch of examples to RPubs: http://rpubs.com/geospacedman/routing It uses the latest igraph! It's all there, building the network and routing and plotting. Barry ___ R-sig-Geo mailing list R-sig-Geo@r-project.org https://stat.ethz.ch/mailman/listinfo/r-sig-geo [[alternative HTML version deleted]] ___ R-sig-Geo mailing list R-sig-Geo@r-project.org https://stat.ethz.ch/mailman/listinfo/r-sig-geo
Re: [R-sig-Geo] shortest path
On Mon, Sep 10, 2012 at 11:47 AM, Mathieu Rajerison mathieu.rajeri...@gmail.com wrote: Barry, I looked at your code and I wondered if it would not be more convenient to find the closest point on a an edge rather than the closest vertex? In this case, what technique would be the best? I thought of spatstat::project2Segment that I used in my script (but Edzer says it doesn't work - I have to check that) I wasn't really concerned about that since it was extraneous to the core job of constructing an igraph from the lines, but should be trivial. There's also possible work on adding tolerances to the nodes and snapping line ends that don't quite make it to other lines, but that's all topological cleanup stuff that could expand into cleaning dangles and jumpbacks and other digitizing errors - I didn't want to get into all that at the moment! I have other fish to fry... Barry ___ R-sig-Geo mailing list R-sig-Geo@r-project.org https://stat.ethz.ch/mailman/listinfo/r-sig-geo
Re: [R-sig-Geo] shortest path
I've just pushed a cleanup and a bunch of examples to RPubs: http://rpubs.com/geospacedman/routing It uses the latest igraph! It's all there, building the network and routing and plotting. Barry ___ R-sig-Geo mailing list R-sig-Geo@r-project.org https://stat.ethz.ch/mailman/listinfo/r-sig-geo
Re: [R-sig-Geo] shortest path
Hi, My code isn't right as the Lines object has to be built from the beginning by including connecting lines. Then the graph can be constructed. I updated my initial thread on Lines network to graph with a new function that corrects that: http://r-sig-geo.2731867.n2.nabble.com/Lines-Network-to-Graph-td7580741.html I haven't tested my function and hope it works well. Some improvements can still be done in order to get an enriched function for the conversion of a Lines network to a graph, which should be very useful. Mathieu 2012/9/1 Mathieu Rajerison mathieu.rajeri...@gmail.com Hi, Following Barry's code and using spatstat::project2segment, I implemented the integration of extra nodes to the graph I tried to give different attributes to vertexes depending on whether they were on the lines or whether they're extra nodes, in order to facilitate queries but I don't find my code very clean. It's : E(graph)$weight=lengths nVtx - length(V(graph)) # TYPE ATTRIBUTE V(graph)$type - Line V(graph)[(nVtx-nrow(pts)+1):nVtx]$type - Point Would you see any improvement to my code? Here is the new function based on Barry's one buildTopo - function(lines, pts){ require(rgeos) require(igraph) require(spatstat) # (1) LINEAR NETWORK g = gIntersection(f,f) edges1 = do.call(rbind,lapply(g@lines [[1]]@Lines,function(ls){as.vector(t(ls@coords))})) # (2) POINT LOCATIONS froms2 - as(pts,ppp) tos2 - project2segment(froms2, as(g, psp))$Xproj edges2 - cbind(froms2$x, froms2$y, tos2$x, tos2$y) # MERGING BOTH ((1)+(2)) edges - rbind(edges1, edges2) # LENGTH CALCULATION lengths = sqrt((edges[,1]-edges[,3])^2+(edges[,2]-edges[,4])^2) # GRAPH froms = paste(edges[,1],edges[,2]) tos = paste(edges[,3],edges[,4]) graph = graph.edgelist(cbind(froms,tos),directed=FALSE) E(graph)$weight=lengths nVtx - length(V(graph)) # TYPE ATTRIBUTE V(graph)$type - Line V(graph)[(nVtx-nrow(pts)+1):nVtx]$type - Point return(graph) } m = readOGR(.,Line) pts - readOGR(., Point) gg = buildTopo(m, pts) E(gg)[get.shortest.paths(gg,V(gg)[1],V(gg)[14])[[1]]-1] I'm glad to have, now, a totally R topology function! Mathieu 2012/8/31 Mathieu Rajerison mathieu.rajeri...@gmail.com Wow, I'm really impressed by your geohacking skills. Thanks a lot. Yes, there is a GRASS::v.clean function that cuts lines. Also, GRASS already includes allocation algorithms. We could also imagine performing shortest path calculations for extra vertexes that aren't initally on the graph: shop locations, particular events, houses... For this, spatstat::project2segment might be the appropriate function. Based on your initial code, I think we could write a function that would combine a linear network with extra vertexes into a single graph. The vertex labels could discriminate the intersection nodes from the thematic ones. 2012/8/31 Barry Rowlingson b.rowling...@lancaster.ac.uk On Fri, Aug 31, 2012 at 11:58 AM, Rowlingson, Barry b.rowling...@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@lines [[1]]@Lines,function(ls){as.vector(t(ls@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 [[alternative HTML version deleted]] ___ R-sig-Geo mailing list R-sig-Geo@r-project.org https://stat.ethz.ch/mailman/listinfo/r-sig-geo
Re: [R-sig-Geo] shortest path
On 09/02/2012 03:51 PM, Mathieu Rajerison wrote: I haven't tested my function and hope it works well. I'd suggest not to send untested code to this list, but rather share your own attempts of testing it. I tried Barry's function, hacked it, tried to plot the line segments in black, and the shortest path in red, but it didn't plot a connected path, so I'd be happy to see such a proof of concept. Also, I strongly suggest in the following to use CRAN versions for packages, that is if we use the old igraph, do a require(igraph0) however if we say require(igraph) we'd understand this as the current version on CRAN. In this particular case, the packages are incompatible, and follow completely different assumptions. -- Edzer Pebesma Institute for Geoinformatics (ifgi), University of Münster Weseler Straße 253, 48151 Münster, Germany. Phone: +49 251 8333081, Fax: +49 251 8339763 http://ifgi.uni-muenster.de http://www.52north.org/geostatistics e.pebe...@wwu.de ___ R-sig-Geo mailing list R-sig-Geo@r-project.org https://stat.ethz.ch/mailman/listinfo/r-sig-geo
Re: [R-sig-Geo] shortest path
Hi, Following Barry's code and using spatstat::project2segment, I implemented the integration of extra nodes to the graph I tried to give different attributes to vertexes depending on whether they were on the lines or whether they're extra nodes, in order to facilitate queries but I don't find my code very clean. It's : E(graph)$weight=lengths nVtx - length(V(graph)) # TYPE ATTRIBUTE V(graph)$type - Line V(graph)[(nVtx-nrow(pts)+1):nVtx]$type - Point Would you see any improvement to my code? Here is the new function based on Barry's one buildTopo - function(lines, pts){ require(rgeos) require(igraph) require(spatstat) # (1) LINEAR NETWORK g = gIntersection(f,f) edges1 = do.call(rbind,lapply(g@lines [[1]]@Lines,function(ls){as.vector(t(ls@coords))})) # (2) POINT LOCATIONS froms2 - as(pts,ppp) tos2 - project2segment(froms2, as(g, psp))$Xproj edges2 - cbind(froms2$x, froms2$y, tos2$x, tos2$y) # MERGING BOTH ((1)+(2)) edges - rbind(edges1, edges2) # LENGTH CALCULATION lengths = sqrt((edges[,1]-edges[,3])^2+(edges[,2]-edges[,4])^2) # GRAPH froms = paste(edges[,1],edges[,2]) tos = paste(edges[,3],edges[,4]) graph = graph.edgelist(cbind(froms,tos),directed=FALSE) E(graph)$weight=lengths nVtx - length(V(graph)) # TYPE ATTRIBUTE V(graph)$type - Line V(graph)[(nVtx-nrow(pts)+1):nVtx]$type - Point return(graph) } m = readOGR(.,Line) pts - readOGR(., Point) gg = buildTopo(m, pts) E(gg)[get.shortest.paths(gg,V(gg)[1],V(gg)[14])[[1]]-1] I'm glad to have, now, a totally R topology function! Mathieu 2012/8/31 Mathieu Rajerison mathieu.rajeri...@gmail.com Wow, I'm really impressed by your geohacking skills. Thanks a lot. Yes, there is a GRASS::v.clean function that cuts lines. Also, GRASS already includes allocation algorithms. We could also imagine performing shortest path calculations for extra vertexes that aren't initally on the graph: shop locations, particular events, houses... For this, spatstat::project2segment might be the appropriate function. Based on your initial code, I think we could write a function that would combine a linear network with extra vertexes into a single graph. The vertex labels could discriminate the intersection nodes from the thematic ones. 2012/8/31 Barry Rowlingson b.rowling...@lancaster.ac.uk On Fri, Aug 31, 2012 at 11:58 AM, Rowlingson, Barry b.rowling...@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@lines [[1]]@Lines,function(ls){as.vector(t(ls@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 [[alternative HTML version deleted]] ___ R-sig-Geo mailing list R-sig-Geo@r-project.org https://stat.ethz.ch/mailman/listinfo/r-sig-geo
Re: [R-sig-Geo] shortest path
On Fri, Aug 31, 2012 at 9:39 AM, Mathieu Rajerison mathieu.rajeri...@gmail.com wrote: Hi, I've got a question which is graph-related. Let's suppose I have a linear network. I cut the lines at the intersections and get some vertexes and edges connecting them How can I turn this into a graph that I could treat in igraph? I've put a line sample as attached file if any geohacker is interested in facing the challenge ;) For complex geometry you'd probably want to feed this to one of the GRASS modules that builds topologies. I have a hacky method which I'll outline... * read lines using readOGR * use package rgeos to intersect the lines with themselves * that gives you a single object containing line segments that are only two points. * create a label for each point based on the x and y coordinate, suitably rounded * that gives you a node label for each point. hence the graph. I think this will work for data that is relatively clean. It won't fix certain data errors, for example if a point from one line is very close to the middle of another line, since no intersection will be found. Other topology build solutions might notice that point X is 1e-10 from the line from A to B and create an extra node there, thus 'snapping' X to that location and causing a new node in the graph... If I didn't have to be on a train in three hours I'd code this up... Barry ___ R-sig-Geo mailing list R-sig-Geo@r-project.org https://stat.ethz.ch/mailman/listinfo/r-sig-geo
Re: [R-sig-Geo] shortest path
Wow, I'm really impressed by your geohacking skills. Thanks a lot. Yes, there is a GRASS::v.clean function that cuts lines. Also, GRASS already includes allocation algorithms. We could also imagine performing shortest path calculations for extra vertexes that aren't initally on the graph: shop locations, particular events, houses... For this, spatstat::project2segment might be the appropriate function. Based on your initial code, I think we could write a function that would combine a linear network with extra vertexes into a single graph. The vertex labels could discriminate the intersection nodes from the thematic ones. 2012/8/31 Barry Rowlingson b.rowling...@lancaster.ac.uk On Fri, Aug 31, 2012 at 11:58 AM, Rowlingson, Barry b.rowling...@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@lines [[1]]@Lines,function(ls){as.vector(t(ls@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 [[alternative HTML version deleted]] ___ R-sig-Geo mailing list R-sig-Geo@r-project.org https://stat.ethz.ch/mailman/listinfo/r-sig-geo
Re: [R-sig-Geo] shortest path
On Fri, Aug 24, 2012 at 9:11 PM, Francis P. Boscoe fp...@health.state.ny.us wrote: Hi, I've been poking around igraph and spatgraphs but have not been able to find a sufficiently simple example to make sense of. Suppose I have three points A, B, and C. The path from A to B is 3 units, from B to C is 4 units, and from A to C is 8 units. Could someone provide a simple coding example showing that A-B-C represents the shortest path? using igraph, it couldn't be much simpler: #1 make a graph, giving a two-column matrix of FROM and TO node names: ABC = graph.edgelist(cbind(c(A,B,A),c(B,C,C))) #2 attach distances as weights: E(ABC)$weight = c(3,4,8) #3 see what we got: ABC Vertices: 3 Edges: 3 Directed: TRUE Edges: [0] 'A' - 'B' [1] 'B' - 'C' [2] 'A' - 'C' Note this is a Directed graph. There's no way back from B to A! #4 shortest path from A to C: get.shortest.paths(ABC,from=A,to=C) [[1]] [1] 0 1 2 And since there might be more than one shortest path, the return is a list. Here it has one element, and the numbers are the indices of the nodes. Starting from zero[1]. This is computer science, after all. To get the nodes, index the V (vertices) function: V(ABC)[get.shortest.paths(ABC,from=A,to=C)[[1]]] Vertex sequence: [1] A B C #5 just to check, lets set the distances to all 1 and see if the algorithm figures out the direct route is quicker: E(ABC)$weight = c(1,1,1) V(ABC)[get.shortest.paths(ABC,from=A,to=C)[[1]]] Vertex sequence: [1] A C Happy graphing! Barry [1] I think the zero indexing might be changing soon, or has changed... Recent igraphs might be different, but indexing the V function should still work. ___ R-sig-Geo mailing list R-sig-Geo@r-project.org https://stat.ethz.ch/mailman/listinfo/r-sig-geo