# Recording all vertices on shortest path with igraph?

I am working with a river network where vegetation surveys were conducted (black dots). I would like to:

• calculate the minimum distance between all points and the point highlighted by the red arrow

• for every shortest path between a point and "the red-arrow point" record all points located on that path. For example, the shortest path between the point highlighted by a circle goes through the points highlighted by rectangles. Therefore, I would to like to to record the unique ID of the "rectangle points". I have been trying to use shp2graph and igraph to find a solution but so far I was only able to calculate pairwise distances.

This is what I managed to do so far:

``````library(igraph)
library(shp2graph)
library(rgdal)
library(tidyverse)

#Import rivers and points into R

#Assign the points to the river network

ptsxy<-coordinates(points)[,1:2]
ptsxy<-cbind(ptsxy[, 1],ptsxy[, 2])
res.nv<-points2network(ntdata=rivers, pointsxy = ptsxy,Detailed=TRUE, ELComputed = TRUE,approach=2,ea.prop = rep(1, 2))

#Convert to igraph object

igr2 <-nel2igraph(res.nv[],res.nv[], weight = res.nv[])

#Calculate minimum distances between every pair of points

id_num <- as.numeric(res.nv[])
mat_dist<-distances(igr2,v=id_num,to=id_num)
``````

The result is a matrix of minimum distances between points.

Here's a link to the data I am currently using:

https://www.dropbox.com/s/zvjti3b7zp08ruy/sample_data.zip?dl=0

• You might do better on the R-sig-Geo mailing list – mdewey Dec 3 '18 at 17:04
• I'd like to help with this but the initial burden of setting up a sample river network shapefile to play with is a bit much. Any chance you can share yours or provide a link to a river network data file we can use? EG from OSM data: overpass-turbo.eu/s/Eg5 – Spacedman Dec 4 '18 at 8:34

I think this does it.

``````library(sp)
library(raster)
library(shp2graph)

rivers = shapefile("./sample_data/rivers.shp")
points = shapefile("./sample_data/points.shp")
``````

keep the largest connected component - not strictly necessary but helps

``````rivers = nt.connect(rivers)
``````

build the node-edge list with the points added in:

``````rivernel = points2network(ntdata=rivers,
pointsxy=coordinates(points),
ELComputed=TRUE,
approach=2, Detailed=TRUE, ea.prop=c(1,1))
``````

build the igraph object with distance weights

``````rivg = nel2igraph(rivernel[], rivernel[], weight=rivernel[])
``````

the added points are in this component:

``````ipoints = rivernel[]
``````

The target point arrowed is point 14 in `points` and so its the vertex number that is 14th in `ipoints`. Now we'll compute the paths from that point to all the vertexes of the points in `points`:

``````sps = get.shortest.paths(rivg, ipoints, ipoints)
``````

Now let's pick one, the 5th one. Lets get the vertexes from point 5 to point 14:

``````> v = sps\$vpath[]
> v
+ 75/1580 vertices, from 757c8ed:
 1580  317  319 1568  326  327  322  347  334  354  355  356  357  250  249
  248  260  267  276  278  287  289  295  202 1569  203  220  221  219  218
  300  299  282  274  271  270  269  254  253  324  348  349  353  342  314
  320  341  244  243  245  273  204  768  769  773  789  818  370  371  382
  455  468  470  442  441  443  502  475  494  509  507  508  489  471 1571
>
``````

We can plot that:

``````plot(rivers)
points(V(rivg)\$x[v], V(rivg)\$y[v], col="red")
``````

But which of those are in our points of interest? Select:

``````ipoints[ipoints %in% v]
 1568 1569 1571 1580
``````

Those are the vertexes of the added points that are on the route from point 5 to point 14. To get the corresponding row in `points` subtract this offset:

``````> (ipoints[ipoints %in% v]) - min(ipoints)+1
  2  3  5 14
``````

Which tells you the route from point 14 to point 5 also goes through point 2 and 3. Repeat for all the components of `sps\$vpath`.