Message-ID: <4DDBB0CB.9050103@jrc.ec.europa.eu>
Date: 2011-05-24T13:21:15Z
From: Jon Olav Skoien
Subject: Find nearest downstream value of a river network
In-Reply-To: <BANLkTikvxOTJBExOGZudp35W+fm=t2OZeg@mail.gmail.com>
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