Maps are all well and good, but do you know what’s better. Graphs! I’m not talking about pie charts or even bar charts I mean the ones with edges and vertices (also known as networks). In this post, and this code, I’m going to convert a geodataframe of A-roads around St Pauls into a graph and then try to apply some algorithms to that graph. The key python package used in this post is NetworkX
While I might want to do something a bit different next, I want to start with something that already looks like a network. Roads.
This is a map of the A-roads around St-Pauls. While geographically accurate the geodataframe of these roads isn’t the best for doing network analysis, so the first thing to do is convert it to a network.
G = momepy.gdf_to_nx(remove_multipart(A_Road), approach="primal", length="Length")I can then plot this using matplotlib next to the original map.
That gives us the graph on the right-hand side. The A-road dataset was extracted from a dataframe of all UK roads so there are too many junctions. To do this I wrote some not very good code to find each node with dimension 2 and replace it and the two edges going into it with a single edge with the length of the new edge equal to the sum of the lengths of the two old edges.
The new graph is less geographically accurate for the roads (junctions are still accurate) but has been simplified to the point where each node is an A-Road junction.
This new graph can be plotted in different ways for different uses.
The first is just letting python plot the network without any link to geography, the second is with the junctions (nodes) in the correct place and the final circular plot lets us see which nodes are connected to which other nodes.
Now I want to find the shortest path between these two junctions on my graph marked with red diamonds
Networkx has a shortest path function which by default uses Dijkstra’s algorithm. I ran it using default settings and plotted my result.
Which looks a bit strange! By default, the function uses a weight of 1 for each edge rather than the length of the edge. Changing this gives a much more sensible outcome
Which is a much more sensible route by eye. I tried this on a few other routes and it seemed to make sense.
With the river drawn on
How does this compare to Google’s route?
Hmm, they suggest a quite different route. But I’m still happy with what I’ve said.
Network graphs open up lots of other options for analysis, but I don’t understand what a lot of them are and involve words I haven’t heard since university like eigenvector or Laplacian so I’ll leave them for another day.