Line to Graph to Route

Barry Rowlingson

Introduction

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.

Requirements

require(igraph)
require(RColorBrewer)
require(sp)
require(ANN)
require(rgeos)

Make Some Data

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)

plot of chunk nest

Build Topology

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)

plot of chunk buildTopo

Shortest Path Routing

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

Plotting Routes

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")

plot of chunk plottingroutes

Further Examples

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)

plot of chunk furtherexample

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)

plot of chunk bigexample

Notes

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.

License

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.