-
Notifications
You must be signed in to change notification settings - Fork 4
Graph analysis on a transportation network
Underneath the hood, ST_GraphAnalysis uses a modified version of Dijkstra's algorithm (for weighted graphs) or Breadth First Search (BFS) (for unweighted graphs--generally much faster!) to calculate, for a given node, this shortest distance to every other node, as well as the number of shortest paths to every other node. Betweenness (and closeness) centrality indices are calculated using Brande's algorithm (A faster algorithm for betweenness centrality, 2001). This algorithm evaluates in O( nm ) time for unweighted graphs and O( nm+n^2 log n ) time for weighted graphs, where n is the number of nodes and m is the number of edges.
The user may consider the graph to be unweighted (equivalently, all edge weights are equal to 1) or weighted. If the graph is weighted, the user must specify the weights (e.g., distance, cost, etc.).
The user is asked to specify the orientation of the graph by a given integer:
-
1Directed -
2Reversed (directed with all edge orientations reversed) -
3Bidirectional (equivalently: undirected)
The following are estimated computation times on the road networks of the given geographical regions computed on a 64-bit Dell Latitude E6500 running Arch Linux.
First letter:
- W = Weighted
- U = Unweighted
Second letter:
- D = Directed
- U = Undirected
| Graph | Nodes | Edges | UU | WU | UD | WD |
|---|---|---|---|---|---|---|
| Nantes | 17 611 | 23 482 | 20m | 20m | 19m30s | 19m30s |
We will do graph analysis on an input table named routes. The input table must contain a column the_geom of one-dimensional geometries (such as MULTILINESTRINGs). For illustration purposes, in this guide we will consider the graph to be bidirectional.