Table of Contents¶
pgRouting extends the PostGIS/PostgreSQL geospatial database to provide geospatial routing and other network analysis functionality.
This is the manual for pgRouting v3.6.3.
The pgRouting Manual is licensed under a Creative Commons Attribution-Share Alike 3.0 License. Feel free to use this material any way you like, but we ask that you attribute credit to the pgRouting Project and wherever possible, a link back to https://pgrouting.org. For other licenses used in pgRouting see the Licensing page.
General¶
Sample Data that is used in the examples of this manual.
Pgrouting Concepts¶
Function Families¶
All Pairs - Family of Functions
pgr_floydWarshall - Floyd-Warshall’s algorithm.
pgr_johnson - Johnson’s algorithm
pgr_aStar - A* algorithm for the shortest path.
pgr_aStarCost - Get the aggregate cost of the shortest paths.
pgr_aStarCostMatrix - Get the cost matrix of the shortest paths.
Bidirectional A* - Family of functions
pgr_bdAstar - Bidirectional A* algorithm for obtaining paths.
pgr_bdAstarCost - Bidirectional A* algorithm to calculate the cost of the paths.
pgr_bdAstarCostMatrix - Bidirectional A* algorithm to calculate a cost matrix of paths.
Bidirectional Dijkstra - Family of functions
pgr_bdDijkstra - Bidirectional Dijkstra algorithm for the shortest paths.
pgr_bdDijkstraCost - Bidirectional Dijkstra to calculate the cost of the shortest paths
pgr_bdDijkstraCostMatrix - Bidirectional Dijkstra algorithm to create a matrix of costs of the shortest paths.
Components - Family of functions
pgr_connectedComponents - Connected components of an undirected graph.
pgr_strongComponents - Strongly connected components of a directed graph.
pgr_biconnectedComponents - Biconnected components of an undirected graph.
pgr_articulationPoints - Articulation points of an undirected graph.
pgr_bridges - Bridges of an undirected graph.
Contraction - Family of functions
Dijkstra - Family of functions
pgr_dijkstra - Dijkstra’s algorithm for the shortest paths.
pgr_dijkstraCost - Get the aggregate cost of the shortest paths.
pgr_dijkstraCostMatrix - Use pgr_dijkstra to create a costs matrix.
pgr_drivingDistance - Use pgr_dijkstra to calculate catchament information.
pgr_KSP - Use Yen algorithm with pgr_dijkstra to get the K shortest paths.
pgr_maxFlow - Only the Max flow calculation using Push and Relabel algorithm.
pgr_boykovKolmogorov - Boykov and Kolmogorov with details of flow on edges.
pgr_edmondsKarp - Edmonds and Karp algorithm with details of flow on edges.
pgr_pushRelabel - Push and relabel algorithm with details of flow on edges.
Applications
pgr_edgeDisjointPaths - Calculates edge disjoint paths between two groups of vertices.
pgr_maxCardinalityMatch - Calculates a maximum cardinality matching in a graph.
Topology - Family of Functions
The following functions modify the database directly therefore the user must have special permissions given by the administrators to use them.
pgr_createTopology - create a topology based on the geometry.
pgr_createVerticesTable - reconstruct the vertices table based on the source and target information.
pgr_analyzeGraph - to analyze the edges and vertices of the edge table.
pgr_analyzeOneWay - to analyze directionality of the edges.
pgr_nodeNetwork - to create nodes to a not noded edge table.
Traveling Sales Person - Family of functions
pgr_TSP - When input is given as matrix cell information.
pgr_TSPeuclidean - When input are coordinates.
pgr_trsp - Proposed - Turn Restriction Shortest Path (TRSP)
Functions by categories¶
pgr_drivingDistance - Driving Distance based on Dijkstra’s algorithm
pgr_primDD - Driving Distance based on Prim’s algorithm
pgr_kruskalDD - Driving Distance based on Kruskal’s algorithm
Post pocessing
pgr_alphaShape - Alpha shape computation
pgr_KSP - Yen’s algorithm based on pgr_dijkstra
Available Functions but not official pgRouting functions¶
Release Notes¶
Current release¶
pgRouting 3.6.3 Release Notes¶
To see all issues & pull requests closed by this release see the Git closed milestone for 3.6.3
Build
Explicit minimum requirements:
postgres 11.0.0
postgis 3.0.0
Code fixes
Fix warnings from cpplint.
Fix warnings from clang 18.
CI tests
Add a clang tidy test on changed files.
Update test not done on versions: 3.0.1, 3.0.2, 3.0.3, 3.0.4, 3.1.0, 3.1.1, 3.1.2
Documentation
Results of documentation queries adujsted to boost 1.83.0 version:
pgr_edgeDisjointPaths
pgr_stoerWagner
pgtap tests
bug fixes
pgRouting 3.6.2 Release Notes¶
To see all issues & pull requests closed by this release see the Git closed milestone for 3.6.2
Upgrade fix
The upgrade was failing for same minor
Code fixes
Fix warnings from cpplint
Others
Adjust NEWS generator
Name change to NEWS.md for better visualization on GitHub
All releases¶
Indices and tables