pgr_aStar¶

Name¶

pgr_aStar — Returns the shortest path using A* algorithm.

Boost Graph Inside

Availability:

pgr_astar(one to one) 2.0.0, Signature changed 2.3.0
pgr_astar(other signatures) 2.4.0

Characteristics¶

The main Characteristics are:

Process is done only on edges with positive costs.

Vertices of the graph are:

positive when it belongs to the edges_sql

Values are returned when there is a path.

When the starting vertex and ending vertex are the same, there is no path.

The agg_cost the non included values (v, v) is 0

When the starting vertex and ending vertex are the different and there is no path:

The agg_cost the non included values (u, v) is ∞

When (x,y) coordinates for the same vertex identifier differ:

A random selection of the vertex’s (x,y) coordinates is used.

Running time: \(O((E + V) * \log V)\)

Signature Summary¶

pgr_aStar(edges_sql, start_vid, end_vid)
pgr_aStar(edges_sql, start_vid, end_vid, directed, heuristic, factor, epsilon)

Warning

These are 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_aStar(edges_sql, start_vid, end_vids, directed, heuristic, factor, epsilon) -- proposed
pgr_aStar(edges_sql, starts_vid, end_vid, directed, heuristic, factor, epsilon) -- proposed
pgr_aStar(edges_sql, starts_vid, end_vids, directed, heuristic, factor, epsilon) -- proposed
RETURNS SET OF (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)
  OR EMPTY SET

Signatures¶

Minimal Signature¶

pgr_aStar(edges_sql, start_vid, end_vid)
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)

Example:	Using the defaults

SELECT * FROM pgr_astar(
    'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
    2, 12);
 seq | path_seq | node | edge | cost | agg_cost 
-----+----------+------+------+------+----------
   1 |        1 |    2 |    4 |    1 |        0
   2 |        2 |    5 |    8 |    1 |        1
   3 |        3 |    6 |    9 |    1 |        2
   4 |        4 |    9 |   15 |    1 |        3
   5 |        5 |   12 |   -1 |    0 |        4
(5 rows)

One to One¶

pgr_aStar(edges_sql, start_vid, end_vid, directed, heuristic, factor, epsilon)
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)

Example:	Undirected using Heuristic 2

SELECT * FROM pgr_astar(
    'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
    2, 12,
    directed := false, heuristic := 2);
 seq | path_seq | node | edge | cost | agg_cost 
-----+----------+------+------+------+----------
   1 |        1 |    2 |    4 |    1 |        0
   2 |        2 |    5 |   10 |    1 |        1
   3 |        3 |   10 |   12 |    1 |        2
   4 |        4 |   11 |   13 |    1 |        3
   5 |        5 |   12 |   -1 |    0 |        4
(5 rows)

One to many¶

pgr_aStar(edges_sql, start_vid, end_vids, directed, heuristic, factor, epsilon) -- Proposed
RETURNS SET OF (seq, path_seq, end_vid, node, edge, cost, agg_cost) or EMPTY SET

This signature finds the shortest 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 in the result is used to distinguish to which path it belongs.

Example:

SELECT * FROM pgr_astar(
    'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
    2, ARRAY[3, 12], heuristic := 2);
 seq | path_seq | end_vid | node | edge | cost | agg_cost 
-----+----------+---------+------+------+------+----------
   1 |        1 |       3 |    2 |    4 |    1 |        0
   2 |        2 |       3 |    5 |    8 |    1 |        1
   3 |        3 |       3 |    6 |    9 |    1 |        2
   4 |        4 |       3 |    9 |   16 |    1 |        3
   5 |        5 |       3 |    4 |    3 |    1 |        4
   6 |        6 |       3 |    3 |   -1 |    0 |        5
   7 |        1 |      12 |    2 |    4 |    1 |        0
   8 |        2 |      12 |    5 |    8 |    1 |        1
   9 |        3 |      12 |    6 |    9 |    1 |        2
  10 |        4 |      12 |    9 |   15 |    1 |        3
  11 |        5 |      12 |   12 |   -1 |    0 |        4
(11 rows)

Many to One¶

pgr_aStar(edges_sql, starts_vid, end_vid, directed, heuristic, factor, epsilon) -- Proposed
RETURNS SET OF (seq, path_seq, start_vid, node, edge, cost, 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 in the result is used to distinguish to which path it belongs.

Example:

SELECT * FROM pgr_astar(
    'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
    ARRAY[7, 2], 12, heuristic := 0);
 seq | path_seq | start_vid | node | edge | cost | agg_cost 
-----+----------+-----------+------+------+------+----------
   1 |        1 |         2 |    2 |    4 |    1 |        0
   2 |        2 |         2 |    5 |   10 |    1 |        1
   3 |        3 |         2 |   10 |   12 |    1 |        2
   4 |        4 |         2 |   11 |   13 |    1 |        3
   5 |        5 |         2 |   12 |   -1 |    0 |        4
   6 |        1 |         7 |    7 |    6 |    1 |        0
   7 |        2 |         7 |    8 |    7 |    1 |        1
   8 |        3 |         7 |    5 |   10 |    1 |        2
   9 |        4 |         7 |   10 |   12 |    1 |        3
  10 |        5 |         7 |   11 |   13 |    1 |        4
  11 |        6 |         7 |   12 |   -1 |    0 |        5
(11 rows)

Many to Many¶

pgr_aStar(edges_sql, starts_vid, end_vids, directed, heuristic, factor, epsilon) -- Proposed
RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, 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_astar(
    'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
    ARRAY[7, 2], ARRAY[3, 12], heuristic := 2);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost 
-----+----------+-----------+---------+------+------+------+----------
|        1 |         2 |       3 |    2 |    4 |    1 |        0
|        2 |         2 |       3 |    5 |    8 |    1 |        1
|        3 |         2 |       3 |    6 |    9 |    1 |        2
|        4 |         2 |       3 |    9 |   16 |    1 |        3
|        5 |         2 |       3 |    4 |    3 |    1 |        4
|        6 |         2 |       3 |    3 |   -1 |    0 |        5
|        1 |         2 |      12 |    2 |    4 |    1 |        0
|        2 |         2 |      12 |    5 |    8 |    1 |        1
|        3 |         2 |      12 |    6 |    9 |    1 |        2
|        4 |         2 |      12 |    9 |   15 |    1 |        3
|        5 |         2 |      12 |   12 |   -1 |    0 |        4
|        1 |         7 |       3 |    7 |    6 |    1 |        0
|        2 |         7 |       3 |    8 |    7 |    1 |        1
|        3 |         7 |       3 |    5 |    8 |    1 |        2
|        4 |         7 |       3 |    6 |    9 |    1 |        3
|        5 |         7 |       3 |    9 |   16 |    1 |        4
|        6 |         7 |       3 |    4 |    3 |    1 |        5
|        7 |         7 |       3 |    3 |   -1 |    0 |        6
|        1 |         7 |      12 |    7 |    6 |    1 |        0
|        2 |         7 |      12 |    8 |    7 |    1 |        1
|        3 |         7 |      12 |    5 |    8 |    1 |        2
|        4 |         7 |      12 |    6 |    9 |    1 |        3
|        5 |         7 |      12 |    9 |   15 |    1 |        4
|        6 |         7 |      12 |   12 |   -1 |    0 |        5
(24 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¶

Returns set of (seq, path_seq, node, edge, cost, agg_cost)

Column	Type	Description
seq	`INTEGER`	Row sequence.
path_seq	`INTEGER`	Path sequence that indicates the relative position on the path.
node	`BIGINT`	Identifier of the node: A positive value indicates the node is a vertex of edges_sql. A negative value indicates the node is a point of points_sql.
edge	`BIGINT`	Identifier of the edge used to go from `node` to the next node in the path sequence. `-1` for the last row in the path sequence.
cost	`FLOAT`	Cost to traverse from `node` using `edge` to the next `node` in the path sequence. `0` for the last row in the path sequence.
agg_cost	`FLOAT`	Aggregate cost from `start_vid` to `node`. `0` for the first row in the path sequence.