[R-sig-Geo] Find nearest downstream value of a river network

[Jon Olav Skoien]

On 19-May-11 18:06, Barry Rowlingson wrote:
>
>   If the FROMJCT and TOJCT numbers define nodes of a graph, and the
> presence of a row with FROMJCT=a and TOJCT=b defines an edge from a to
> b of the graph, then you could use something like R's igraph package
> to build a graph object. Once you've done that it should be easy to
> use the graph algorithms in that package to wander down the river
> system at your leisure...
It was my first look at the igraph package, and I dont think I found the 
optimal set of functions. So far I ended up with the following, although 
I am sure there are better solutions:

rndf = data.frame(FROMJCT = nres$FROMJCT, TOJCT = nres$TOJCT,
                OBJECTIT = nres$OBJECTID, pred = nres$pred)
igr = graph.data.frame(rndf)
igrs = topological.sort(igr, mode = "out")
rndf$to = match(as.character(rndf$TOJCT), V(igr)$name[igrs+1])

while (TRUE) {
   lcon = which(rndf$to == min(rndf$to[is.na(rndf$pred)]))
   if (length(lcon)==0) break()
   while(is.na(rndf$pred[lcon[1]])) lcon = c(neighbors(igr,lcon[1]-1)+1, 
lcon)
   rndf$pred[lcon] = rndf$pred[lcon[1]]
}

The best with this solution is that it is extremely fast compared to my 
first suggestion, about 20-30 times faster for 1200 segments. And it 
also seems to scale better with larger data sets. So I think I will 
either try to simplify this further, or just make a function of the 
lines above.

>   It might get complicated if you are modelling on the Orinoco where it
> bifurcates, or a river delta :)

Complicated or more interesting, depending on how you see it and how 
much time you have ;-)
For the second reason I am happy that the river system I am interested 
in behaves rather "normal"...

Thanks!
Jon