This document shows how to go from a set of lines to an igraph network object, and then do shortest path routing on that network.
require(igraph)
require(RColorBrewer)
require(sp)
require(ANN)
require(rgeos)
First a function to generate some sample data. This code generates a number of random segments on the unit square, and converts them to a SpatialLines object. I think of this as like a nest of twigs.
makeNest <- function(n) {
### generate a bunch of SpatialLines on (0,1) square
xy = cbind(runif(n), runif(n), runif(n), runif(n))
lines = Lines(apply(xy, 1, function(z) {
Line(rbind(z[1:2], z[3:4]))
}), ID = 1)
SpatialLines(list(lines))
}
gg = makeNest(35)
plot(gg)
This function builds the igraph object. The fundamental trick is to intersect the lines with themselves. This creates vertices at all the end points and intersections. The graph is built with Euclidean distance as edge weight, and with the x and y coordinates attributed to the vertices. The plot method uses the x and y coordinates for the layout, but the large vertex symbols obscure things a bit.
buildTopo <- function(lines) {
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
xy = do.call(rbind, strsplit(V(graph)$name, " "))
V(graph)$x = as.numeric(xy[, 1])
V(graph)$y = as.numeric(xy[, 2])
return(graph)
}
graph = buildTopo(gg)
plot(graph)
This function maps two points (as one-row, two-column matrices) to the nearest node on the network then computes the vertices of the shortest path. We compute a route roughly across the diagonal of the unit square.
routePoints <- function(graph, from, to) {
require(FNN)
xyg = cbind(V(graph)$x, V(graph)$y)
ifrom = get.knnx(xyg, from, 1)$nn.index[1, 1]
ito = get.knnx(xyg, to, 1)$nn.index[1, 1]
p = get.shortest.paths(graph, ifrom, ito, output = "vpath")
p[[1]]
}
route1 = routePoints(graph, cbind(0.2, 0.2), cbind(0.8, 0.8))
## Loading required package: FNN
We can plot routes simply by getting the x and y coordinates of the vertices.
plotRoute <- function(graph, nodes, ...) {
lines(V(graph)[nodes]$x, V(graph)[nodes]$y, ...)
}
plot(gg)
plotRoute(graph, route1, lwd = 2, col = "red")
This code computes four more routes parallel to the sides of the unit square. We add the origin points to the plot and finally overplot the lines again to show that the paths really follow the network.
route2 = routePoints(graph, cbind(0.2, 0.2), cbind(0.2, 0.8))
route3 = routePoints(graph, cbind(0.2, 0.8), cbind(0.8, 0.8))
route4 = routePoints(graph, cbind(0.8, 0.8), cbind(0.8, 0.2))
route5 = routePoints(graph, cbind(0.8, 0.2), cbind(0.2, 0.2))
colours = brewer.pal(5, "Set1")
plot(gg)
points(rbind(c(0.2, 0.2), c(0.2, 0.8), c(0.8, 0.8), c(0.8, 0.2)),
pch = 19)
plotRoute(graph, route1, lwd = 10, col = colours[1])
plotRoute(graph, route2, lwd = 8, col = colours[2])
plotRoute(graph, route3, lwd = 6, col = colours[3])
plotRoute(graph, route4, lwd = 4, col = colours[4])
plotRoute(graph, route5, lwd = 2, col = colours[5])
plot(gg, add = TRUE, lty = 3)
Adding more points to the graph produces a more complex network and the routes more closely approximate the sides and diagonal of the square.
gg = makeNest(100)
graph = buildTopo(gg)
route1 = routePoints(graph, cbind(0.2, 0.2), cbind(0.8, 0.8))
route2 = routePoints(graph, cbind(0.2, 0.2), cbind(0.2, 0.8))
route3 = routePoints(graph, cbind(0.2, 0.8), cbind(0.8, 0.8))
route4 = routePoints(graph, cbind(0.8, 0.8), cbind(0.8, 0.2))
route5 = routePoints(graph, cbind(0.8, 0.2), cbind(0.2, 0.2))
colours = brewer.pal(5, "Set1")
plot(gg)
points(rbind(c(0.2, 0.2), c(0.2, 0.8), c(0.8, 0.8), c(0.8, 0.2)),
pch = 19)
plotRoute(graph, route1, lwd = 10, col = colours[1])
plotRoute(graph, route2, lwd = 8, col = colours[2])
plotRoute(graph, route3, lwd = 6, col = colours[3])
plotRoute(graph, route4, lwd = 4, col = colours[4])
plotRoute(graph, route5, lwd = 2, col = colours[5])
plot(gg, add = TRUE, lty = 3)
If the finish point can't be reached from the start point then plotRoute will stop with an error.
Only one shortest path is returned, even if there are multiple equally-short paths.
This document is released under a Creative Commons Attribution license, CC-BY. You may modify and redistribute it as long as you attribute the original author, Barry Rowlingson.