Function Families - pgRouting Manual (3.2)

Function Families

All Pairs - Family of Functions

• pgr_floydWarshall - Floyd-Warshall’s algorithm.

• pgr_johnson - Johnson’s algorithm

aStar - Family of functions

• 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

• pgr_contraction

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.

Flow - Family of functions

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

Kruskal - Family of functions

• pgr_kruskal

• pgr_kruskalBFS

• pgr_kruskalDD

• pgr_kruskalDFS

Prim - Family of functions

• pgr_prim

• pgr_primBFS

• pgr_primDD

• pgr_primDFS

Topology - Family of Functions

• pgr_createTopology - to create a topology based on the geometry.

• pgr_createVerticesTable - to 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 - Turn Restriction Shortest Path (TRSP) - Turn Restriction Shortest Path (TRSP)