Table of Contents — pgRouting Manual (3.8) (original) (raw)
pgRouting extends the PostGIS/PostgreSQL geospatial database to provide geospatial routing and other network analysis functionality.
This is the manual for pgRouting v3.8.0.
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 tohttps://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.
- pgr_degree - Returns a set of vertices and corresponding count of incident edges to the vertex.
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 - Deprecated since v3.8.0 - create a topology based on the geometry.
- pgr_createVerticesTable - Deprecated since 3.8.0 - reconstruct the vertices table based on the source and target information.
- pgr_analyzeGraph – Deprecated since 3.8.0 - to analyze the edges and vertices of the edge table.
- pgr_analyzeOneWay - Deprecated since 3.8.0 - to analyze directionality of the edges.
- pgr_nodeNetwork - Deprecated since 3.8.0 - 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)
Utilities
- pgr_extractVertices - Extracts vertex information based on the edge table information.
- pgr_findCloseEdges - Finds close edges of points on the fly
- pgr_separateCrossing - Breaks geometries that cross each other.
- pgr_separateTouching - Breaks geometries that (almost) touch each other.
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 processing
- pgr_alphaShape - Alpha shape computation
- pgr_KSP - Yen’s algorithm based on pgr_dijkstra
Available Functions but not official pgRouting functions¶
Release Notes¶
pgRouting 3.8.0 Release Notes¶
To see all issues & pull requests closed by this release see the Git closed milestone for 3.8.0
Promotion to official function of pgRouting.
Metric
- #2760: Promoted to official pgr_degree in version 3.8
- Error messages adjustment.
- New signature with only Edges SQL.
- Function promoted to official.
Utilities
- #2772: Promoted to official pgr_extractVertices in version 3.8
- Error messages adjustment.
- Function promoted to official.
- #2774: Promoted to official pgr_findCloseEdges in version 3.8
- Error messages adjustment.
partialoption is removed.- Function promoted to official.
- #2873: Promoted to official pgr_separateCrossing in version 3.8
- Function promoted to official.
- Proposed function.
- #2874: Promoted to official pgr_separateTouching in version 3.8
- Function promoted to official.
- Proposed function.
Proposed functions
Contraction
- #2790: pgr_contractionDeadEnd new contraction function
- #2791: pgr_contractionLinear new contraction function
- #2536: Support for contraction hierarchies (pgr_contractionHierarchies)
Utilities
- #2848: Create pgr_separateCrossing new utility function
- #2849: Create of pgr_separateTouching new utility function
Official functions changes
- #2786: pgr_contraction(edges) new signature
- New signature:
* Previously compulsory parameter Contraction order is now optional with namemethods.
* New name and order of optional parameters. - Deprecated signature pgr_contraction(text,bigint[],integer,bigint[],boolean)
- New signature:
C/C++ code enhancements
SQL code enhancements
- #2850: Rewrite pgr_nodeNetwork
Deprecation of SQL functions
- #2749: Deprecate pgr_AlphaShape in 3.8
- #2750: Deprecate pgr_CreateTopology in 3.8
- #2753: Deprecate pgr_analyzeGraph in 3.8
- #2754: Deprecate pgr_analyzeOneWay in 3.8
- #2826: Deprecate pgr_createVerticesTable in 3.8
- #2847: Deprecate pgr_nodeNetwork in 3.8
In the deprecated functions:
- Migration section is created.
- The use of the functions is removed in the documentation.
All releases¶
Indices and tables