Construct a network from shapefile and do analytics such as finding number of shortest paths from origin to destination, calculating centrality, degree of the nodes in network.

This python module allow you to get number of alpha times shortest paths from origin to destination where alpha is some constant specified by the user. You can also do some analysis over the network like finding degree, centrality of the nodes in graph.

• Install python >= 2.7

  • Ubuntu

    $ sudo apt-get install python-2.7
    

  • Mac

    $ brew install python
    

• Run setup.py for installing required packages

  $ python2.7 setup.py install
  

• GraphConvertor.py - This module will take the input line shapefile and the path of output directory
• ShortestPath.py - This module will calculate the number of alpha times shortest path from origin to destination in the graph

• BufferedGraph.py - This module create the square (buffer) of given size around the point geometry
• GraphSimplify.py - This module will clean and remove all the redundant edges and extra/ uninformative nodes from the graph
• MultiDiGraphConvertor.py - This module will convert the MultiDiGraph to SimpleGraph

• Create the line shapefile of the road network (if not available)

  • Using QGIS

    • Open the shapefile in QGIS which need to be converted to line shapefile
    • Go to Vector -> Geometry Tools and select Polygons to lines to convert shapefile into line shapefile

  • Using python

    • Need to be implemented

• Convert the created line shapefile into network using GraphConvertor.py

  • Create GraphConvertor object by passing the path of input shapefile and the output directory

    input_file  =  'path of the line shapefile'
    output_dir  =  'path of directory to save new shapefiles'
    
    graph_convertor_obj = GraphConvertor(input_file, output_dir)

  • Call graph_convertor function to convert the input shapefile into road network and save the newly created shapefile into specifed output_dir along with list of nodes and edges in .csv files

    network = graph_convertor_obj.graph_convertor()

• Find number of shortest paths from origin to destination in new simplified network

  • Create ShortestPath object by passing all required parameters listed below

    g            =  network
    alpha        =  0.1
    graph_buffer =  100
    point_buffer =  50
    break_point  =  200         # Upper limit to save computation time
    
    shortest_path_obj   =  ShortestPath(g, alpha, graph_buffer, point_buffer, break_point)

  • Run alpha_times_shortestpath function to calculate number of paths which are alpha times the shortest path

    start_tuple  =  (lat,lon)
    end_tuple    =  (lat,lon)
    
    total_path   =  shortest_path_obj.alpha_time_shortestpath(start_tuple, end_tuple)

• Find metrics like degree centrality, closeness centrality, communicability and load centrality for doing analysis over created network.

  • Create Centrality object by passing the network and the weight attribute of the network

    centrality = Centrality(g, weight='distance')

  • Get all the metrics of the network by calling metrics function of centrality class

    degree_centrality, closeness_centrality, communicability, load_centrality = centrality.metrics()

For reference/citing: Journal Paper.