pgr_aStar

pgr_aStar — Shortest path using A* algorithm.

Boost Graph Inside

Availability

• Version 3.2.0

  • New proposed function:

    • pgr_aStar(Combinations)

• Version 3.0.0

  • Official function

• Version 2.4.0

  • New Proposed functions:

    • pgr_aStar(One to Many)

    • pgr_aStar(Many to One)

    • pgr_aStar(Many to Many)

• Version 2.3.0

  • Signature change on pgr_astar(One to One)

    • Old signature no longer supported

• Version 2.0.0

  • Official pgr_aStar(One to One)

Description

The main characteristics are:

• Default kind of graph is directed when

  • directed flag is missing.

  • directed flag is set to true

• Unless specified otherwise, ordering is:

  • first by start_vid (if exists)

  • then by end_vid

• Values are returned when there is a path

• Let \(v\) and \(u\) be nodes on the graph:

  • If there is no path from \(v\) to \(u\):

    • no corresponding row is returned

    • agg_cost from \(v\) to \(u\) is \(\infty\)

  • There is no path when \(v = u\) therefore

    • no corresponding row is returned

    • agg_cost from v to u is \(0\)

• Edges with negative costs are not included in the graph.

• 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)\)

• The results are equivalent to the union of the results of the pgr_aStar( One to One ) on the:

  • pgr_aStar( One to Many )

  • pgr_aStar( Many to One )

  • pgr_aStar( Many to Many )

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

Signatures

Summary

pgr_aStar(Edges SQL, from_vid,  to_vid  [, directed] [, heuristic] [, factor] [, epsilon])
pgr_aStar(Edges SQL, from_vid,  to_vids [, directed] [, heuristic] [, factor] [, epsilon])
pgr_aStar(Edges SQL, from_vids, to_vid  [, directed] [, heuristic] [, factor] [, epsilon])
pgr_aStar(Edges SQL, from_vids, to_vids [, directed] [, heuristic] [, factor] [, epsilon])
pgr_aStar(Edges SQL, Combinations SQL  [, directed] [, heuristic] [, factor] [, epsilon]) -- Proposed on v3.2

RETURNS SET OF (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)
OR EMPTY SET

Optional parameters are named parameters and have a default value.

Using defaults

pgr_aStar(Edges SQL, from_vid, to_vid)
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET

Example

From vertex \(2\) to vertex \(12\) on a directed graph

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 |   11 |    1 |        2
   4 |        4 |   11 |   13 |    1 |        3
   5 |        5 |   12 |   -1 |    0 |        4
(5 rows)

One to One

pgr_aStar(Edges SQL, from_vid,  to_vid  [, directed] [, heuristic] [, factor] [, epsilon])

RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET

Example

From vertex \(2\) to vertex \(12\) on an undirected graph 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 |    2 |    1 |        0
   2 |        2 |    3 |    3 |    1 |        1
   3 |        3 |    4 |   16 |    1 |        2
   4 |        4 |    9 |   15 |    1 |        3
   5 |        5 |   12 |   -1 |    0 |        4
(5 rows)

One to many

pgr_aStar(Edges SQL, from_vid,  to_vids [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (seq, path_seq, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET

Example

From vertex \(2\) to vertices \(\{3, 12\}\) on a directed graph using heuristic \(2\)

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 |   10 |    1 |        1
   9 |        3 |      12 |   10 |   12 |    1 |        2
  10 |        4 |      12 |   11 |   13 |    1 |        3
  11 |        5 |      12 |   12 |   -1 |    0 |        4
(11 rows)

Many to One

pgr_aStar(Edges SQL, from_vids, to_vid  [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (seq, path_seq, start_vid, node, edge, cost, agg_cost)
OR EMPTY SET

Example

From vertices \(\{7, 2\}\) to vertex \(12\) on a directed graph using heuristic \(0\)

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, from_vids, to_vids [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET

Example

From vertices \(\{7, 2\}\) to vertices \(\{3, 12\}\) on a directed graph using heuristic \(2\)

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 |        1 |         2 |       3 |    2 |    4 |    1 |        0
   2 |        2 |         2 |       3 |    5 |    8 |    1 |        1
   3 |        3 |         2 |       3 |    6 |    9 |    1 |        2
   4 |        4 |         2 |       3 |    9 |   16 |    1 |        3
   5 |        5 |         2 |       3 |    4 |    3 |    1 |        4
   6 |        6 |         2 |       3 |    3 |   -1 |    0 |        5
   7 |        1 |         2 |      12 |    2 |    4 |    1 |        0
   8 |        2 |         2 |      12 |    5 |   10 |    1 |        1
   9 |        3 |         2 |      12 |   10 |   12 |    1 |        2
  10 |        4 |         2 |      12 |   11 |   13 |    1 |        3
  11 |        5 |         2 |      12 |   12 |   -1 |    0 |        4
  12 |        1 |         7 |       3 |    7 |    6 |    1 |        0
  13 |        2 |         7 |       3 |    8 |    7 |    1 |        1
  14 |        3 |         7 |       3 |    5 |    8 |    1 |        2
  15 |        4 |         7 |       3 |    6 |    9 |    1 |        3
  16 |        5 |         7 |       3 |    9 |   16 |    1 |        4
  17 |        6 |         7 |       3 |    4 |    3 |    1 |        5
  18 |        7 |         7 |       3 |    3 |   -1 |    0 |        6
  19 |        1 |         7 |      12 |    7 |    6 |    1 |        0
  20 |        2 |         7 |      12 |    8 |    7 |    1 |        1
  21 |        3 |         7 |      12 |    5 |   10 |    1 |        2
  22 |        4 |         7 |      12 |   10 |   12 |    1 |        3
  23 |        5 |         7 |      12 |   11 |   13 |    1 |        4
  24 |        6 |         7 |      12 |   12 |   -1 |    0 |        5
(24 rows)

Combinations

pgr_aStar(Edges SQL, Combinations SQL  [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET

Example

Using a combinations table on a directed graph using heuristic \(2\).

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

Parameters

Parameter	Type	Description
Edges SQL	TEXT	Edges query as described below.
Combinations SQL	TEXT	Combinations query as described below.
from_vid	ANY-INTEGER	Starting vertex identifier. Parameter in: One to One One to Many
from_vids	ARRAY[ANY-INTEGER]	Array of starting vertices identifiers. Parameter in: Many to One Many to Many
to_vid	ANY-INTEGER	Ending vertex identifier. Parameter in: One to One Many to One
to_vids	ARRAY[ANY-INTEGER]	Array of ending vertices identifiers. Parameter in: One to Many Many to Many

Optional Parameters

Parameter	Type	Default	Description
directed	BOOLEAN	true	When true the graph is considered as Directed. When false the graph is considered as Undirected.
heuristic	INTEGER	5	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	1	For units manipulation. \(factor > 0\). See Factor
epsilon	FLOAT	1	For less restricted results. \(epsilon >= 1\).

Inner queries

Edges query

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

Combinations query

Column	Type	Default	Description
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.

Where:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

Result Columns

Returns set of (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)

Column	Type	Description
seq	INT	Sequential value starting from 1.
path_seq	INT	Relative position in the path. Has value 1 for the beginning of a path.
start_vid	BIGINT	Identifier of the starting vertex. Returned when multiple starting vetrices are in the query. Many to One Many to Many
end_vid	BIGINT	Identifier of the ending vertex. Returned when multiple ending vertices are in the query. One to Many Many to Many
node	BIGINT	Identifier of the node in the path from start_vid to end_vid.
edge	BIGINT	Identifier of the edge used to go from node to the next node in the path sequence. -1 for the last node of the path.
cost	FLOAT	Cost to traverse from node using edge to the next node in the path sequence.
agg_cost	FLOAT	Aggregate cost from start_v to node.

See Also

• aStar - Family of functions

• Sample Data

• https://www.boost.org/libs/graph/doc/astar_search.html

• https://en.wikipedia.org/wiki/A*_search_algorithm

Indices and tables

• Index

• Search Page