Graph contraction framework for pgRouting
Worked on this project as a student developer for the Google Summer of Code 2016.
Overview
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.