Skip to content

Convert Shapefile to the Network and find number of shortest paths

License

Notifications You must be signed in to change notification settings

Garvit244/Shapefile_to_Network

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

29 Commits
 
 
 
 
 
 
 
 

Repository files navigation

Shapefile To Network

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.

Overview

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.

Original Network


New Simplified Network


Installation

  • 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
    

Documentation

Core Scripts

  • 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

Other Scripts

  • 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

How to use

  • 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()

More Info

For reference/citing: Journal Paper.