# 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.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.

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¶

### 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

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

`pred`

result 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