Table of Contents - pgRouting Manual (3.7)
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.7.1.
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.7.1 Release Notes
To see all issues & pull requests closed by this release see the Git closed milestone for 3.7.1
Bug fixes
-
#2680 fails to compile under mingw64 gcc 13.2
-
#2689 When point is a vertex, the withPoints family do not return results.
C/C++ code enhancemet
-
TRSP family
pgRouting 3.7.0 Release Notes
To see all issues & pull requests closed by this release see the Git closed milestone for 3.7.0
Support
-
#2656 Stop support of PostgreSQL12 on pgrouting v3.7
-
Stopping support of PostgreSQL 12
-
CI does not test for PostgreSQL 12
-
New experimental functions
-
Metrics
-
pgr_betweennessCentrality
-
Official functions changes
-
#2605 Standarize spanning tree functions output
-
Functions:
-
pgr_kruskalDD -
pgr_kruskalDFS -
pgr_kruskalBFS -
pgr_primDD -
pgr_primDFS -
pgr_primBFS
-
-
Standarizing output columns to
(seq, depth, start_vid, pred, node, edge, cost, agg_cost)-
Added
predresult columns.
-
-
Experimental promoted to proposed.
-
#2635 pgr_LineGraph ignores directed flag and use negative values for identifiers.
-
pgr_lineGraph
-
Promoted to proposed signature.
-
Works for directed and undirected graphs.
-
Code enhancement
All releases
Indices and tables