pgr_aStarCost

pgr_aStarCost - Total cost of the shortest path(s) using the A* algorithm.

_images/boost-inside.jpeg

Boost Graph Inside

Availability

Description

The pgr_aStarCost function sumarizes of the cost of the shortest path(s) using the A* algorithm.

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)\)
  • It does not return a path.
  • Returns the sum of the costs of the shortest path of each pair combination of nodes requested.
  • Let be the case the values returned are stored in a table, so the unique index would be the pair: (start_vid, end_vid)
  • For undirected graphs, the results are symmetric.
    • The agg_cost of (u, v) is the same as for (v, u).
  • The returned values are ordered in ascending order:
    • start_vid ascending
    • end_vid ascending

Signatures

Summary

pgr_aStarCost(Edges SQL, start vid, end vid
                 [, directed] [, heuristic] [, factor] [, epsilon])
pgr_aStarCost(Edges SQL, start vid, end vids
                 [, directed] [, heuristic] [, factor] [, epsilon])
pgr_aStarCost(Edges SQL, start vids, end vid
                 [, directed] [, heuristic] [, factor] [, epsilon])
pgr_aStarCost(Edges SQL, start vids, end vids
                 [, directed] [, heuristic] [, factor] [, epsilon])
pgr_aStarCost(Edges SQL, Combinations SQL
                 [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

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:From vertex \(6\) to vertex \(12\) on a directed graph with heuristic \(2\)
SELECT * FROM pgr_aStarCost(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  6, 12,
  directed => true, heuristic => 2);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         6 |      12 |        3
(1 row)

One to Many

pgr_aStarCost(Edges SQL, start vid, end vids
                 [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (start_vid, end_vid, 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_aStarCost(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  6, ARRAY[10, 12],
  heuristic => 3, factor => 3.5);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         6 |      10 |        5
         6 |      12 |        3
(2 rows)

Many to One

pgr_aStarCost(Edges SQL, start vids, end vid
                 [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET
Example:From vertices \(\{6, 8\}\) to vertex \(10\) on an undirected graph with heuristic \(4\)
SELECT * FROM pgr_aStarCost(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  ARRAY[6, 8], 10,
  false, heuristic => 4);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         6 |      10 |        1
         8 |      10 |        3
(2 rows)

Many to Many

pgr_aStarCost(Edges SQL, start vids, end vids
                 [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (start_vid, end_vid, 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_aStarCost(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  ARRAY[6, 8], ARRAY[10, 12],
  factor => 0.5);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         6 |      10 |        5
         6 |      12 |        3
         8 |      10 |        5
         8 |      12 |        1
(4 rows)

Combinations

pgr_aStarCost(Edges SQL, Combinations SQL
                 [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (start_vid, end_vid, 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_aStarCost(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  'SELECT * FROM combinations',
  factor => 0.5);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         5 |       6 |        1
         5 |      10 |        6
         6 |       5 |        1
         6 |      15 |        4
(4 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

Set of (start_vid, end_vid, agg_cost)

Column Type Description
start_vid BIGINT Identifier of the starting vertex.
end_vid BIGINT Identifier of the ending vertex.
agg_cost FLOAT Aggregate cost from start_vid to end_vid.

Additional Examples

Example 1:Demonstration of repeated values are ignored, and result is sorted.
 SELECT * FROM pgr_aStarCost(
  '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]);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         7 |      10 |        4
         7 |      15 |        3
        10 |       7 |        2
        10 |      15 |        3
        15 |       7 |        3
        15 |      10 |        1
(6 rows)

Example 2:Making start vids the same as end vids.
SELECT * FROM pgr_aStarCost(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  ARRAY[7, 10, 15], ARRAY[7, 10, 15]);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         7 |      10 |        4
         7 |      15 |        3
        10 |       7 |        2
        10 |      15 |        3
        15 |       7 |        3
        15 |      10 |        1
(6 rows)

Example 3:Manually assigned vertex combinations.
SELECT * FROM pgr_aStarCost(
  '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)');
 start_vid | end_vid | agg_cost
-----------+---------+----------
         6 |       7 |        1
         6 |      10 |        5
        12 |      10 |        4
(3 rows)