pgr_bdAstarCost - pgRouting Manual (3.3)

Description

The pgr_bdAstarCost function sumarizes of the cost of the shortest path(s) using the bidirectional 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

SELECT * FROM pgr_bdAstarCost(
  '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)

SELECT * FROM pgr_bdAstarCost(
  '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)

SELECT * FROM pgr_bdAstarCost(
  '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)

SELECT * FROM pgr_bdAstarCost(
  '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)

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

SELECT * FROM pgr_bdAstarCost(
  '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

Inner Queries

Result Columns

Set of (start_vid, end_vid, agg_cost)

Additional Examples

Example 1 :

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

 SELECT * FROM pgr_bdAstarCost(
  '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_bdAstarCost(
  '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_bdAstarCost(
  '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)

See Also

• Bidirectional A* - Family of functions

• Cost - Category

• Sample Data

Indices and tables

• Index

• Search Page