[pgrouting-dev] Framework which supports addition of contraction techniques for pgRouting - Final Report

Hi all,

I am working on the implementation of a framework which supports addition of contraction techniques for pgRouting for the GsoC 2016. This is my final report. I would like to thank my mentors, Vicky Vergara and Daniel Kastl for their constant support and guidance.

Brief Description

In big graphs, like the road graphs, or electric networks, graph contraction can be used to speed up some graph algorithms. Contraction reduces the size of the graph by removing some of the vertices and edges and, for example, might add edges that represent a sequence of original edges decreasing the total time and space used in graph algorithms.

This implementation gives a flexible framework for adding contraction algorithms in the future, currently, it supports two algorithms:

  • Dead end contraction

  • Linear contraction

Allowing the user to:

  • Forbid contraction on a set of nodes.
  • Decide the order of the contraction algorithms and set the maximum number of times they are to be executed.

State of the project before GSoC

Previously there is no contraction functionality in the library.

Addition that my project brought to the software

I implemented the following during the GSoC program


I learned a lot from my mentors and it has been a very good learning experience. I hope this project keeps growing and would like to continue my contribution.

Rohith Reddy
Lab for Spatial Informatics
International Institute of Information Technology
Hyderabad, India.