pgr_aStarCost – proposed¶

Name¶

pgr_aStarCost — Returns the aggregate cost shortest path using aStar - Family of functions algorithm.

Boost Graph Inside

Availability: 2.4.0

Signature Summary¶

Warning

Proposed functions for next mayor release.

They are not officially in the current release.
They will likely officially be part of the next mayor release:
- The functions make use of ANY-INTEGER and ANY-NUMERICAL
- Name might not change. (But still can)
- Signature might not change. (But still can)
- Functionality might not change. (But still can)
- pgTap tests have being done. But might need more.
- Documentation might need refinement.

pgr_aStarCost(edges_sql, start_vid, end_vid) -- Proposed
pgr_aStarCost(edges_sql, start_vid, end_vid, directed, heuristic, factor, epsilon) -- Proposed
pgr_aStarCost(edges_sql, start_vid, end_vids, directed, heuristic, factor, epsilon) -- Proposed
pgr_aStarCost(edges_sql, starts_vid, end_vid, directed, heuristic, factor, epsilon) -- Proposed
pgr_aStarCost(edges_sql, starts_vid, end_vids, directed, heuristic, factor, epsilon) -- Proposed

RETURNS SET OF (start_vid, end_vid, agg_cost) OR EMPTY SET

Signatures¶

Minimal Signature¶

pgr_aStarCost(edges_sql, start_vid, end_vid)
RETURNS SET OF (start_vid, end_vid, agg_cost) OR EMPTY SET

Example:	Using the defaults

SELECT * FROM pgr_aStarCost(
    'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
    2, 12);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         2 |      12 |        4
(1 row)

One to One¶

pgr_aStarCost(edges_sql, start_vid, end_vid, directed, heuristic, factor, epsilon)
RETURNS SET OF (start_vid, end_vid, agg_cost) OR EMPTY SET

Example:	Setting a Heuristic

SELECT * FROM pgr_aStarCost(
    'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
    2, 12,
    directed := false, heuristic := 2);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         2 |      12 |        4
(1 row)

One to many¶

pgr_aStarCost(edges_sql, start_vid, end_vids, directed, heuristic, factor, epsilon) -- Proposed
RETURNS SET OF (start_vid, end_vid, agg_cost) OR EMPTY SET

This signature finds a path from one start_vid to each end_vid in end_vids:

on a directed graph when directed flag is missing or is set to true.
on an undirected graph when directed flag is set to false.

Using this signature, will load once the graph and perform a one to one pgr_astar where the starting vertex is fixed, and stop when all end_vids are reached.

The result is equivalent to the union of the results of the one to one pgr_astar.
The extra end_vid column in the result is used to distinguish to which path it belongs.

Example:

SELECT * FROM pgr_aStarCost(
    'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
    2, ARRAY[3, 12], heuristic := 2);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         2 |       3 |        5
         2 |      12 |        4
(2 rows)

Many to One¶

pgr_aStarCost(edges_sql, starts_vid, end_vid, directed, heuristic, factor, epsilon) -- Proposed
RETURNS SET OF (start_vid, end_vid, agg_cost) OR EMPTY SET

This signature finds the shortest path from each start_vid in start_vids to one end_vid:

on a directed graph when directed flag is missing or is set to true.
on an undirected graph when directed flag is set to false.

Using this signature, will load once the graph and perform several one to one pgr_aStar where the ending vertex is fixed.

The result is the union of the results of the one to one pgr_aStar.
The extra start_vid column in the result is used to distinguish to which path it belongs.

Example:

SELECT * FROM pgr_aStarCost(
    'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
    ARRAY[7, 2], 12, heuristic := 0);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         2 |      12 |        4
         7 |      12 |        5
(2 rows)

Many to Many¶

pgr_aStarCost(edges_sql, starts_vid, end_vids, directed, heuristic, factor, epsilon) -- Proposed
RETURNS SET OF (start_vid, end_vid, agg_cost) OR EMPTY SET

This signature finds the shortest path from each start_vid in start_vids to each end_vid in end_vids:

on a directed graph when directed flag is missing or is set to true.
on an undirected graph when directed flag is set to false.

Using this signature, will load once the graph and perform several one to Many pgr_dijkstra for all start_vids.

The result is the union of the results of the one to one pgr_dijkstra.
The extra start_vid in the result is used to distinguish to which path it belongs.

The extra start_vid and end_vid in the result is used to distinguish to which path it belongs.

Example:

SELECT * FROM pgr_aStarCost(
    'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
    ARRAY[7, 2], ARRAY[3, 12], heuristic := 2);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         2 |       3 |        5
         2 |      12 |        4
         7 |       3 |        6
         7 |      12 |        5
(4 rows)

Description of the Signatures¶

Description of the edges_sql query for astar like functions¶

edges_sql:	an SQL query, which should return a set of rows with the following columns:

Column	Type	Default	Description
id	`ANY-INTEGER`		Identifier of the edge.
source	`ANY-INTEGER`		Identifier of the first end point vertex of the edge.
target	`ANY-INTEGER`		Identifier of the second end point vertex of the edge.
cost	`ANY-NUMERICAL`		Weight of the edge (source, target) When negative: edge (source, target) does not exist, therefore it’s not part of the graph.
reverse_cost	`ANY-NUMERICAL`	-1	Weight of the edge (target, source), When negative: edge (target, source) does not exist, therefore it’s not part of the graph.
x1	`ANY-NUMERICAL`		X coordinate of source vertex.
y1	`ANY-NUMERICAL`		Y coordinate of source vertex.
x2	`ANY-NUMERICAL`		X coordinate of target vertex.
y2	`ANY-NUMERICAL`		Y coordinate of target vertex.

Where:

ANY-INTEGER:	SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL:	SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Description of the parameters of the signatures¶

Parameter	Type	Description
edges_sql	`TEXT`	Edges SQL query as described above.
start_vid	`ANY-INTEGER`	Starting vertex identifier.
end_vid	`ANY-INTEGER`	Ending vertex identifier.
directed	`BOOLEAN`	Optional. When `false` the graph is considered as Undirected. Default is `true` which considers the graph as Directed.
heuristic	`INTEGER`	(optional). Heuristic number. Current valid values 0~5. Default `5` 0: h(v) = 0 (Use this value to compare with pgr_dijkstra) 1: h(v) abs(max(dx, dy)) 2: h(v) abs(min(dx, dy)) 3: h(v) = dx * dx + dy * dy 4: h(v) = sqrt(dx * dx + dy * dy) 5: h(v) = abs(dx) + abs(dy)
factor	`FLOAT`	(optional). For units manipulation. \(factor > 0\). Default `1`. See Factor
epsilon	`FLOAT`	(optional). For less restricted results. \(epsilon >= 1\). Default `1`.

Description of the return values for a Cost function¶

Returns set of (start_vid, end_vid, agg_cost)

Column	Type	Description
start_vid	`BIGINT`	Identifier of the starting vertex. Used when multiple starting vetrices are in the query.
end_vid	`BIGINT`	Identifier of the ending vertex. Used when multiple ending vertices are in the query.
agg_cost	`FLOAT`	Aggregate cost from `start_vid` to `end_vid`.

pgRouting Manual (2.6)