pgr_bdAstar

pgr_bdAstar — Shortest path using the bidirectional A* algorithm.

Boost Graph Inside

Availability

• Version 3.2.0

  • New proposed signature:

    • pgr_bdAstar (Combinations)

• Version 3.0.0

  • Official function

• Version 2.5.0

  • New Proposed signatures:

    • pgr_bdAstar (One to Many)

    • pgr_bdAstar (Many to One)

    • pgr_bdAstar (Many to Many)

  • Signature change on pgr_bdAstar (One to One)

    • Old signature no longer supported

• Version 2.0.0

  • Official pgr_bdAstar (One to One)

Description

The main characteristics are:

• Process works for directed and undirected graphs.

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

• 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_bdAStar( One to One ) on the:

  • pgr_bdAstar( One to Many )

  • pgr_bdAstar( Many to One )

  • pgr_bdAstar( Many to Many )

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

Signatures

Summary

pgr_bdAstar(Edges SQL, start vid, end vid, [options])

pgr_bdAstar(Edges SQL, start vid, end vids, [options])

pgr_bdAstar(Edges SQL, start vids, end vid, [options])

pgr_bdAstar(Edges SQL, start vids, end vids, [options])

pgr_bdAstar(Edges SQL, Combinations SQL, [options])

options: [directed, heuristic, factor, epsilon]

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.

One to One

pgr_bdAstar(Edges SQL, start vid, end vid, [options])

options: [directed, heuristic, factor, epsilon]

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

OR EMPTY SET

Example:

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

SELECT * FROM pgr_bdAstar(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  6, 12,
  directed => true, heuristic => 2
);
 seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
   1 |        1 |    6 |    4 |    1 |        0
   2 |        2 |    7 |   10 |    1 |        1
   3 |        3 |    8 |   12 |    1 |        2
   4 |        4 |   12 |   -1 |    0 |        3
(4 rows)

One to Many

pgr_bdAstar(Edges SQL, start vid, end vids, [options])

options: [directed, heuristic, factor, epsilon]

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

OR EMPTY SET

Example:

From vertex \(6\) to vertices \(\{10, 12\}\) on a directed graph with heuristic \(3\) and factor \(3.5\)

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

Many to One

pgr_bdAstar(Edges SQL, start vids, end vid, [options])

options: [directed, heuristic, factor, epsilon]

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

OR EMPTY SET

Example:

From vertices \(\{6, 8\}\) to vertex \(10\) on an undirected graph with heuristic \(4\)

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

Many to Many

pgr_bdAstar(Edges SQL, start vids, end vids, [options])

options: [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 \(\{6, 8\}\) to vertices \(\{10, 12\}\) on a directed graph with factor \(0.5\)

SELECT * FROM pgr_bdAstar(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  ARRAY[6, 8], ARRAY[10, 12],
  factor => 0.5
);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         6 |      10 |    6 |    4 |    1 |        0
   2 |        2 |         6 |      10 |    7 |    8 |    1 |        1
   3 |        3 |         6 |      10 |   11 |    9 |    1 |        2
   4 |        4 |         6 |      10 |   16 |   16 |    1 |        3
   5 |        5 |         6 |      10 |   15 |    3 |    1 |        4
   6 |        6 |         6 |      10 |   10 |   -1 |    0 |        5
   7 |        1 |         6 |      12 |    6 |    4 |    1 |        0
   8 |        2 |         6 |      12 |    7 |   10 |    1 |        1
   9 |        3 |         6 |      12 |    8 |   12 |    1 |        2
  10 |        4 |         6 |      12 |   12 |   -1 |    0 |        3
  11 |        1 |         8 |      10 |    8 |   10 |    1 |        0
  12 |        2 |         8 |      10 |    7 |    8 |    1 |        1
  13 |        3 |         8 |      10 |   11 |    9 |    1 |        2
  14 |        4 |         8 |      10 |   16 |   16 |    1 |        3
  15 |        5 |         8 |      10 |   15 |    3 |    1 |        4
  16 |        6 |         8 |      10 |   10 |   -1 |    0 |        5
  17 |        1 |         8 |      12 |    8 |   12 |    1 |        0
  18 |        2 |         8 |      12 |   12 |   -1 |    0 |        1
(18 rows)

Combinations

pgr_bdAstar(Edges SQL, Combinations SQL, [options])

options: [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 with factor \(0.5\).

The combinations table:

SELECT * FROM combinations;
 source | target
--------+--------
      5 |      6
      5 |     10
      6 |      5
      6 |     15
      6 |     14
(5 rows)

The query:

SELECT * FROM pgr_bdAstar(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  'SELECT * FROM combinations',
  factor => 0.5
);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         5 |       6 |    5 |    1 |    1 |        0
   2 |        2 |         5 |       6 |    6 |   -1 |    0 |        1
   3 |        1 |         5 |      10 |    5 |    1 |    1 |        0
   4 |        2 |         5 |      10 |    6 |    4 |    1 |        1
   5 |        3 |         5 |      10 |    7 |    8 |    1 |        2
   6 |        4 |         5 |      10 |   11 |    9 |    1 |        3
   7 |        5 |         5 |      10 |   16 |   16 |    1 |        4
   8 |        6 |         5 |      10 |   15 |    3 |    1 |        5
   9 |        7 |         5 |      10 |   10 |   -1 |    0 |        6
  10 |        1 |         6 |       5 |    6 |    1 |    1 |        0
  11 |        2 |         6 |       5 |    5 |   -1 |    0 |        1
  12 |        1 |         6 |      15 |    6 |    4 |    1 |        0
  13 |        2 |         6 |      15 |    7 |    8 |    1 |        1
  14 |        3 |         6 |      15 |   11 |    9 |    1 |        2
  15 |        4 |         6 |      15 |   16 |   16 |    1 |        3
  16 |        5 |         6 |      15 |   15 |   -1 |    0 |        4
(16 rows)

Parameters

Column	Type	Description
Edges SQL	TEXT	Edges SQL as described below
Combinations SQL	TEXT	Combinations SQL as described below
start vid	BIGINT	Identifier of the starting vertex of the path.
start vids	ARRAY[BIGINT]	Array of identifiers of starting vertices.
end vid	BIGINT	Identifier of the ending vertex of the path.
end vids	ARRAY[BIGINT]	Array of identifiers of ending vertices.

Optional parameters

Column	Type	Default	Description
directed	BOOLEAN	true	When true the graph is considered Directed When false the graph is considered as Undirected.

aStar optional Parameters

Parameter	Type	Default	Description
heuristic	INTEGER	5	Heuristic number. Current valid values 0~5. 0: \(h(v) = 0\) (Use this value to compare with pgr_dijkstra) 1: \(h(v) = abs(max(\Delta x, \Delta y))\) 2: \(h(v) = abs(min(\Delta x, \Delta y))\) 3: \(h(v) = \Delta x * \Delta x + \Delta y * \Delta y\) 4: \(h(v) = sqrt(\Delta x * \Delta x + \Delta y * \Delta y)\) 5: \(h(v) = abs(\Delta x) + abs(\Delta y)\)
factor	FLOAT	1	For units manipulation. \(factor > 0\).
epsilon	FLOAT	1	For less restricted results. \(epsilon >= 1\).

See heuristics available and factor handling.

Inner Queries

Edges SQL

Parameter	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 SQL

Parameter	Type	Description
source	ANY-INTEGER	Identifier of the departure vertex.
target	ANY-INTEGER	Identifier of the arrival vertex.

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	INTEGER	Sequential value starting from 1.
path_seq	INTEGER	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_vid to node.

Additional Examples

Example 1:

Demonstration of repeated values are ignored, and result is sorted.

 SELECT * FROM pgr_bdAstar(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  ARRAY[7, 10, 15, 10, 10, 15], ARRAY[10, 7, 10, 15]);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         7 |      10 |    7 |    8 |    1 |        0
   2 |        2 |         7 |      10 |   11 |    9 |    1 |        1
   3 |        3 |         7 |      10 |   16 |   16 |    1 |        2
   4 |        4 |         7 |      10 |   15 |    3 |    1 |        3
   5 |        5 |         7 |      10 |   10 |   -1 |    0 |        4
   6 |        1 |         7 |      15 |    7 |    8 |    1 |        0
   7 |        2 |         7 |      15 |   11 |    9 |    1 |        1
   8 |        3 |         7 |      15 |   16 |   16 |    1 |        2
   9 |        4 |         7 |      15 |   15 |   -1 |    0 |        3
  10 |        1 |        10 |       7 |   10 |    5 |    1 |        0
  11 |        2 |        10 |       7 |   11 |    8 |    1 |        1
  12 |        3 |        10 |       7 |    7 |   -1 |    0 |        2
  13 |        1 |        10 |      15 |   10 |    5 |    1 |        0
  14 |        2 |        10 |      15 |   11 |    9 |    1 |        1
  15 |        3 |        10 |      15 |   16 |   16 |    1 |        2
  16 |        4 |        10 |      15 |   15 |   -1 |    0 |        3
  17 |        1 |        15 |       7 |   15 |   16 |    1 |        0
  18 |        2 |        15 |       7 |   16 |    9 |    1 |        1
  19 |        3 |        15 |       7 |   11 |    8 |    1 |        2
  20 |        4 |        15 |       7 |    7 |   -1 |    0 |        3
  21 |        1 |        15 |      10 |   15 |    3 |    1 |        0
  22 |        2 |        15 |      10 |   10 |   -1 |    0 |        1
(22 rows)

Example 2:

Making start vids the same as end vids.

SELECT * FROM pgr_bdAstar(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  ARRAY[7, 10, 15], ARRAY[7, 10, 15]);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         7 |      10 |    7 |    8 |    1 |        0
   2 |        2 |         7 |      10 |   11 |    9 |    1 |        1
   3 |        3 |         7 |      10 |   16 |   16 |    1 |        2
   4 |        4 |         7 |      10 |   15 |    3 |    1 |        3
   5 |        5 |         7 |      10 |   10 |   -1 |    0 |        4
   6 |        1 |         7 |      15 |    7 |    8 |    1 |        0
   7 |        2 |         7 |      15 |   11 |    9 |    1 |        1
   8 |        3 |         7 |      15 |   16 |   16 |    1 |        2
   9 |        4 |         7 |      15 |   15 |   -1 |    0 |        3
  10 |        1 |        10 |       7 |   10 |    5 |    1 |        0
  11 |        2 |        10 |       7 |   11 |    8 |    1 |        1
  12 |        3 |        10 |       7 |    7 |   -1 |    0 |        2
  13 |        1 |        10 |      15 |   10 |    5 |    1 |        0
  14 |        2 |        10 |      15 |   11 |    9 |    1 |        1
  15 |        3 |        10 |      15 |   16 |   16 |    1 |        2
  16 |        4 |        10 |      15 |   15 |   -1 |    0 |        3
  17 |        1 |        15 |       7 |   15 |   16 |    1 |        0
  18 |        2 |        15 |       7 |   16 |    9 |    1 |        1
  19 |        3 |        15 |       7 |   11 |    8 |    1 |        2
  20 |        4 |        15 |       7 |    7 |   -1 |    0 |        3
  21 |        1 |        15 |      10 |   15 |    3 |    1 |        0
  22 |        2 |        15 |      10 |   10 |   -1 |    0 |        1
(22 rows)

Example 3:

Manually assigned vertex combinations.

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

See Also

• A* - Family of functions

• Bidirectional A* - 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