Graph contraction framework for pgRouting

Worked on this project as a student developer for the Google Summer of Code 2016.


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.


GSoC Proposal