[R-sig-Geo] Building a graph/network matrix

[jeremy.raw at dot.gov]

See details below ====

-----Original Message-----
From: r-sig-geo-bounces at r-project.org
[mailto:r-sig-geo-bounces at r-project.org] On Behalf Of Sadz A
Sent: Friday, December 03, 2010 3:52 PM
To: r-sig-geo at r-project.org
Subject: [R-sig-Geo] Building a graph/network matrix

I have some networks in GIS shape file (vector) format, the data I have
are road 
maps that I digitised from satellite images in ArcGIS. (I can change
them to 
raster or Ascii), is there a way to convert them into matrix that can be
loaded 
and analysed with igraph in R?

==== Details Follow

I think the only difficult part in your project will be identifying the
appropriate points in your input files -- my experience with digitized
maps is that line segments don't always end at logical places,
particularly when you're interested in right angle turns on a single
otherwise continuous segment.  It would probably make sense to spend
some time simplifying the network before launching into igraph-type
analysis.

It's also desirable to have "single part" features (so you don't have
one feature with spatially disjoint parts); that's not often an issue
with digitized maps, however. Assuming you can break up the features at
the necessary places (so all the points you are interested in occur at
the "ends" of features), you can easily create a list of edges which can
then be loaded into igraph.

Here are some hints about steps you can take in that direction:

The goal for getting this into igraph is to make an edgelist (which is,
not coincidentally, equally suitable for building a sparse matrix
showing which nodes are connected).

Read the shapefile into R using rgdal or maptools.  That will give you a
spatial object (specifically a SpatialLinesDataFrame) with a list of
features from which you can extract coordinates.  I'll call that
"my.network" in the code fragment below.

Here are a few lines of code that illustrate the rest of the procedure
(note that this presumes you have simple features, with a single
connected set of vertices for each feature as noted above):

# First build a data.frame of network segment end point coordinates
# That first line is the hardest part, and there may be a much easier
way to do it (e.g. in ArcGIS if you have
# access to that; but it's nice to have a 'pure R' solution...)

c<-t(sapply(unlist(coordinates(my.network),recursive=FALSE),FUN=function
(x) cbind(x[1,],x[nrow(x),])))
c<-as.data.frame(c)
names(c)<-c("From.x","From.y","To.x","To.y")

# Then complete the vertex table

n2 <- cbind(my.network,c)
v<-unique(rbind(
data.frame(X=n2$From.x,Y=n2$From.y),data.frame(X=n2$To.x,Y=n2$To.y)))
v$ID <- 1:nrow(v)

# Then match back to the original network coordinates to assign vertex
IDs to each feature end point

n3<-merge(n2,data.frame(From=v$ID,From.x=v$X,From.y=v$Y),by=c("From.x","
From.y"))
n4<-merge(n3,data.frame(To=v$ID,To.x=v$X,To.y=v$Y),by=c("To.x","To.y"))

# Then make an igraph
# remember igraph indices are 0-based (although if you don't, you'll
just end up with one unconnected vertex labeled 0)

library(igraph)
edge.list <-
cbind(n4[,c("From","To")],n4[,grep("^(From|To)$",names(n4),invert=TRUE)]
)
edge.list$From <- edgelist$From-1    # 0-based conversion
edge.list$To <- edgelist$To-1
g <- graph.data.frame(edge.list,directed=FALSE) # All the shapefile
attributes are now edge attributes

# At this point, you can take your questions back to the igraph list :-)

# Alternatively, make a sparse matrix showing which vertices are
directly connected
# Warning: N^2 matrix where N is the number of vertices in the network,
so sparseMatrix is your friend
# Also, this code assumes FID != 0 for any feature

library(Matrix)
m <- sparseMatrix( i=n4$From, j=n4$To, x=n4$FID )

I hope that helps!

Jeremy Raw, P.E., AICP
FHWA Office of Planning
jeremy.raw at dot.gov
(202) 366-0986