Is it possible to route shapefiles using python and without ArcGIS, QGIS, or Pgrouting?

Question

The question is pretty much in the title.

Is there a way to route through a road line shapefile using python and some library without having to resort to converting the data into PostGIS/pgrouting or going through desktop software API such as ArcGIS and QGIS?

Answer 1

The link given by MappaGnosis is the first attempt to implement Graph theory algorithms in Python (by Guido van Rossum, the creator of Python).

Since, many modules were developed:

• Graph theory
• network
• routing network

One of the most comprehensive is NetworkX, mentioned before in GS

• it can read or write shapefiles natively (thanks to bwreilly in nx_spatial)
• all the graph algorithms are implemented (Graph traversal, Shortests Paths with the A* algorithm and many more)

import networkx  as nx  
graph = nx.read_shp('lines.shp')  
print graph.nodes()  
[(1.0, 2.0), (3.0, 2.0),...]  
print graph.edges()
[((1.0, 2.0), (1.0, 1.0)),...]

Result with matplotlib

Result with graphviz:

A* Algorithm

def dist(a, b):
   (x1, y1) = a
   (x2, y2) = b
    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5

print(nx.astar_path(graph,(3.0,2.0),(1.0, 1.0),dist))
[(3.0, 2.0), (2.0, 1.0), (1.0, 1.0)]

and you can export the results:

to shapefiles:

nx.write_shp(graph, ‘/shapefiles’)

to ogr geometries:

from osgeo import ogr
line = osgeo.ogr.Geometry(ogr.wkbLineString)
from points in (nx.astar_path(graph,(3.0,2.0),(1.0, 1.0),dist)):
    line.AddPoint(points[0],points[1])

print line.ExportToWkt()
LINESTRING (3 2 0,2 1 0,1 1 0)

or to shapely geometries:

from shapely.geometry import LineString
line = LineString(nx.astar_path(graph,(3.0,2.0),(1.0, 1.0),dist))
print line.wkt
LINESTRING (3.00 2.00, 2.00 1.00, 1.00 1.00)

Answer 2

'Yes' is the short answer. However, you will need to implement the A* algorithm. This link may be helpful for your implementation. To read the shapefile you will probably want to use the GDAL/OGR python libraries (and if you are on Windows I strongly recommend the 'gisinternals' link).

Answer 3

Yes! A short answer, but I implement this little functionality in python-s2g (https://github.com/caesar0301/python-s2g).

import s2g
import networkx as nx

sg = s2g.ShapeGraph(shapefile='path/to/roads.shp', resolution=1.0)

assert isinstance(sg.graph, nx.Graph)

Use resolution parameter to adjust the spatial sampling, default 1 km in great circle distance.