Unsupported versions:2.6 2.5 2.4 2.3 2.2 2.1 2.0
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 v4.0.0-dev.
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.
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 - 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.
pgr_extractVertices - Extracts vertex information based on the edge table information.
Traveling Sales Person - Family of functions
pgr_TSP - When input is given as matrix cell information.
pgr_TSPeuclidean - When input are coordinates.
pgr_trsp - Turn Restriction Shortest Path (TRSP)
Utilities family
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 4.0.0 Release Notes¶
To see all issues & pull requests closed by this release see the Git closed milestone for 4.0.0
Functions promoted to official
pgr_trsp
pgr_trspVia
pgr_trspVia_withPoints
pgr_trsp_withPoints
pgr_withPoints
pgr_withPointsCost
pgr_withPointsCostMatrix
pgr_withPointsDD
pgr_withPointsKSP
pgr_withPointsVia
Signatures promoted to official
pgr_aStar(Combinations)
pgr_aStarCost(Combinations)
pgr_bdAstar(Combinations)
pgr_bdAstarCost(Combinations)
pgr_bdDijkstra(Combinations)
pgr_bdDijkstraCost(Combinations)
pgr_dijkstra(Combinations)
pgr_dijkstraCost(Combinations)
pgr_KSP(All signatures)
pgr_boykovKolmogorov(Combinations)
pgr_edmondsKarp(Combinations)
pgr_maxFlow(Combinations)
pgr_pushRelabel(Combinations)
code enhancements:
Removal of unused C/C++ code
Removal of SQL deprecated functions
pgr_trsp(text,integer,double precision,integer,double precision,boolean,boolean,text)
pgr_trsp(text,integer,integer,boolean,boolean,text)
pgr_trspviaedges(text,integer[],double precision[],boolean,boolean,text)
pgr_trspviavertices(text,anyarray,boolean,boolean,text)
Removal of SQL deprecated internal functions
_pgr_dijkstranear(text,anyarray,anyarray,bigint,boolean)
_pgr_dijkstranear(text,anyarray,bigint,bigint,boolean)
_pgr_dijkstranear(text,bigint,anyarray,bigint,boolean)
_pgr_dijkstra(text,anyarray,anyarray,boolean,boolean,boolean,bigint)
_pgr_dijkstra(text,text,boolean,boolean,boolean)
_pgr_drivingdistance(text,anyarray,double precision,boolean,boolean)
_pgr_kruskal(text,anyarray,text,bigint,double precision)
_pgr_prim(text,anyarray,text,bigint,double precision)
_pgr_trsp(text,integer,double precision,integer,double precision,boolean,boolean,text)
_pgr_trsp(text,text,anyarray,anyarray,boolean)
_pgr_trsp(text,text,anyarray,bigint,boolean)
_pgr_trsp(text,text,bigint,anyarray,boolean)
_pgr_trsp(text,text,bigint,bigint,boolean)
_pgr_trspviavertices(text,integer[],boolean,boolean,text)
_pgr_withpointsvia(text,bigint[],double precision[],boolean)
_trsp(text,text,anyarray,anyarray,boolean)
_v4trsp(text,text,anyarray,anyarray,boolean)
_v4trsp(text,text,text,boolean)
Deprecation of internal C/C++ functions
_pgr_drivingdistance(text,anyarray,double precision,boolean,boolean)
_pgr_kruskal(text,anyarray,text,bigint,double precision)
_pgr_prim(text,anyarray,text,bigint,double precision)
Internal C/C++ functions in legacy
_trsp(text,text,anyarray,anyarray,boolean)
_v4trsp(text,text,anyarray,anyarray,boolean)
_v4trsp(text,text,text,boolean)
All releases¶
Indices and tables