NetworkX - How to create MultiDiGraph from Shapefile?

Question

I'm just picking up NetworkX and trying to learn how to use it with Shapefiles.

Right now I have a .shp with a road network that I want to represent in a Graph with NetworkX, so that I can find the shortest path between 2 GPS points. I tried using this, but the problem is that when I run the write_shp() function I lose edges because DiGraph does not allow more than one edge between the same two nodes. The arrow in the figure below shows an example of an edge I lose by using a DiGraph.

So I was wondering if there's any way to create a MultiDiGraph so I don't lose any edges, or if there's any way around it that I could use. I was thinking maybe I could write some code to extract the attributes from the Shapefile and create the MultiDiGraph without using NetworkX's read_shp(), but I don't have any experience at all working with graphs, so I'm not exactly sure if it'd be possible.

I'd really appreciate any help or guidance you could give me, or if I've missed any documentation please let me know. Thanks in advance.

Answer 1

As best I can follow from your question, the following will do it, basically copied from the original read_shp command.

def read_multi_shp(path):
    """
    copied from read_shp, but allowing MultiDiGraph instead.
    """
    try:
        from osgeo import ogr
    except ImportError:
        raise ImportError("read_shp requires OGR: http://www.gdal.org/")

    net = nx.MultiDiGraph() # <--- here is the main change I made

    def getfieldinfo(lyr, feature, flds):
            f = feature
            return [f.GetField(f.GetFieldIndex(x)) for x in flds]

    def addlyr(lyr, fields):
        for findex in xrange(lyr.GetFeatureCount()):
            f = lyr.GetFeature(findex)
            flddata = getfieldinfo(lyr, f, fields)
            g = f.geometry()
            attributes = dict(zip(fields, flddata))
            attributes["ShpName"] = lyr.GetName()
            if g.GetGeometryType() == 1:  # point
                net.add_node((g.GetPoint_2D(0)), attributes)
            if g.GetGeometryType() == 2:  # linestring
                attributes["Wkb"] = g.ExportToWkb()
                attributes["Wkt"] = g.ExportToWkt()
                attributes["Json"] = g.ExportToJson()
                last = g.GetPointCount() - 1
                net.add_edge(g.GetPoint_2D(0), g.GetPoint_2D(last), attr_dict=attributes) #<--- also changed this line

    if isinstance(path, str):
        shp = ogr.Open(path)
        lyrcount = shp.GetLayerCount()  # multiple layers indicate a directory
        for lyrindex in xrange(lyrcount):
            lyr = shp.GetLayerByIndex(lyrindex)
            flds = [x.GetName() for x in lyr.schema]
            addlyr(lyr, flds)
    return net

I changed the returned graph from a DiGraph to a MultiDigraph and I had to change the add_edge command since the MultiDiGraph version has different syntax from DiGraph

Answer 2

If the multi-lines are disconnected at the joint, I think this library python-s2g(https://github.com/caesar0301/python-s2g) could help you. Even networkx's Graph object is used under the hood, those multi-paths are actually recorded by the graph data.

Answer 3

I have implemented a solution here: https://gitlab.com/njacadieux/upstream_downstream_shortests_path_dijkstra

I read the shapefile using GeoPandas and not the networkx.readwrite.nx_shp.read_shp. When I build the graph, I check for parallel edges. If found, rather than skipping them, as does the networkx.readwrite.nx_shp.read_shp function, I split the parallel edges in two edges of equal length and then divide the user length by 2. The user length variable field name must be given.