Skip to content

A collection of graph search algorithms including Dijkstra's shortest path algorithm, Multi-Threaded Dijkstra's (MTD) for solving median problem, and a clustering heuristic for p-median problem in Python.

Notifications You must be signed in to change notification settings

saeedt/PythonGraphSearch

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

5 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Graph Search Algorithms

This repository includes several graph search algorithms based on Dijkstra's algorithm in Python. I implemented a searchable graph in JSON format which is stored in a pandas DataFrame to improve the performance. The graph files are stored in graph folder. Any data from OpenStreetMap can be used to build the graph.

Data Converter

dataConverter.py is a python script that reads a CSV file and converts it to JSON. You can download the data for your region of interest from OpenStreetMap project. I used osm2pgrouting to import it to a spatially enabled PostgreSQL database. Then, converted the 'ways_vertices_pgr' table where the edges are stored to CSV. source, target, x1, y1, x2, y2, dist are the required columns in the CSV file.

Dijkstra's shortest path algorithm

Dijkstra.py finds the shortest distance between two nodes in the graph identified by their node IDs.

Multi-Threaded Dijkstra's (MTD) algorithm

The median problem is a popular network location problem introduced by Hakimi (1964). MTD algorithm finds the median (i.e. node with the minimum total weighted distance to a set of demand points) of a weighted graph. MTD algorithm proposed by Ghanbartehrani and Porter (2019) in the paper titled An efficient algorithm for solving the median problem on real road networks is the most efficient optimal solution method for this NP-Hard problem. MTD is a scalable algorithm tested on real road networks with up to 28 million nodes. The 28-milion node experiment was performed using a solver implemented in Java and executed on server JRE, so do not expect such performance on the Python implementation provided here in MTDalgorithm.py. I am currently working on a high performance Julia implementation of the MTD algorithm based on a similar graph representation.

Clustering heuristics for solving the P-Median problem

pMedian.py is a clustering heuristic based on Klincewicz (1991) heuristic for p-hub median problem. The clustering algorithm is used in (Ghanbartehrani & Porter, 2018) to solve a p-median problem with over 3,000 demand points and 150 facilities, on a road network with over 28 million nodes.

The sample graph

TestData.csv and graph.json files in graph folder are the real road network for the city of Rockford, Illinois retrieved from OpenStreetMap project. The graph consists of 19,836 nodes and 27,970 edges.

Coming soon: visualization

I tried geoplot and geopandas to visualize the demand points and facility locations on map. I spent hours just to get everything installed (had to install anaconda, reset my environment, and used some advice from this thread to resolve conflicts) just to see how disappointing the plots look compared to what LeafLet generates with just a few lines of code and a 650 KB library. I will add an interactive data visualization module in JavaScript/LeafLet soon.

About

A collection of graph search algorithms including Dijkstra's shortest path algorithm, Multi-Threaded Dijkstra's (MTD) for solving median problem, and a clustering heuristic for p-median problem in Python.

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages