Supported versions: latest (3.8) 3.7 3.6 3.5 3.4 3.3 3.2 3.1 3.0 main dev
Unsupported versions:2.6 2.5 2.4 2.3 2.2

Contraction - Family of functions

Warning

Proposed functions for next mayor release.

  • They are not officially in the current release.

  • They will likely officially be part of the next mayor release:

    • The functions make use of ANY-INTEGER and ANY-NUMERICAL

    • Name might not change. (But still can)

    • Signature might not change. (But still can)

    • Functionality might not change. (But still can)

    • pgTap tests have being done. But might need more.

    • Documentation might need refinement.

Warning

Possible server crash

  • These functions might create a server crash

Warning

Experimental functions

  • They are not officially of the current release.

  • They likely will not be officially be part of the next release:

    • The functions might not make use of ANY-INTEGER and ANY-NUMERICAL

    • Name might change.

    • Signature might change.

    • Functionality might change.

    • pgTap tests might be missing.

    • Might need c/c++ coding.

    • May lack documentation.

    • Documentation if any might need to be rewritten.

    • Documentation examples might need to be automatically generated.

    • Might need a lot of feedback from the community.

    • Might depend on a proposed function of pgRouting

    • Might depend on a deprecated function of pgRouting

Introduction

In large graphs, like road graphs or electric networks, graph contraction can be used to speed up some graph algorithms. Contraction can reduce the size of the graph by removing some of the vertices and edges and adding edges that represent a sequence of original edges (the original ones can be kept in some methods). In this way, it decreases the total time and space used by graph algorithms, particularly those searching for an optimal path.

This implementation gives a flexible framework for adding contraction algorithms in the future. Currently, it supports three algorithms.

  1. Dead end contraction

  2. Linear contraction

  3. Contraction hierarchies

The two first ones can be combined through a iterative procedure, via the pgr_contraction method. The third one is implemented on its own.

All functions allow the user to forbid contraction on a set of nodes.

See Also

Indices and tables