Supported versions: Latest (3.3) 3.2 3.1 3.0
Unsupported versions: 2.6 2.5

`pgr_bdAstarCostMatrix`¶

pgr_bdAstarCostMatrix - Calculates the a cost matrix using pgr_aStar.

_images/boost-inside.jpeg — Boost Graph Inside¶

Availability

Version 3.0.0
- Official function
Version 2.5.0
- New proposed function

Description¶

The main characteristics are:

Using internaly the pgr_bdAstar algorithm
Returns a cost matrix.
No ordering is performed
let v and u are nodes on the graph:
- when there is no path from v to u:
  - no corresponding row is returned
  - cost from v to u is \(\inf\)
- when \(v = u\) then
  - no corresponding row is returned
  - cost from v to u is \(0\)
When the graph is undirected the cost matrix is symmetric

Signatures¶

Summary

pgr_bdAstarCostMatrix(Edges SQL, vids [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (start_vid, end_vid, agg_cost)

Example: Symmetric cost matrix for vertices \(\{1, 2, 3, 4\}\) on an undirected graph using heuristic \(2\)

SELECT * FROM pgr_bdAstarCostMatrix(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
  (SELECT array_agg(id) FROM edge_table_vertices_pgr WHERE id < 5),
  directed => false, heuristic => 2
);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         1 |       2 |        1
         1 |       3 |        2
         1 |       4 |        3
         2 |       1 |        1
         2 |       3 |        1
         2 |       4 |        2
         3 |       1 |        2
         3 |       2 |        1
         3 |       4 |        1
         4 |       1 |        3
         4 |       2 |        2
         4 |       3 |        1
(12 rows)

Parameters¶

Column	Type	Description
Edges SQL	`TEXT`	Edges SQL as described below
start vids	`ARRAY[BIGINT]`	Array of identifiers of starting 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(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\).

Parameter

Type

Default

Description

heuristic

INTEGER

Heuristic number. Current valid values 0~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 query¶

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

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: Use with pgr_TSP

SELECT * FROM pgr_TSP(
  $$
  SELECT * FROM pgr_bdAstarCostMatrix(
    'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
    (SELECT array_agg(id) FROM edge_table_vertices_pgr WHERE id < 5),
    directed=> false, heuristic => 2
  )
  $$,
  randomize => false
);
NOTICE:  pgr_TSP no longer solving with simulated annaeling
HINT:  Ignoring annaeling parameters
 seq | node | cost | agg_cost
-----+------+------+----------
   1 |    1 |    0 |        0
   2 |    2 |    1 |        1
   3 |    3 |    1 |        2
   4 |    4 |    1 |        3
   5 |    1 |    3 |        6
(5 rows)

pgr_bdAstarCostMatrix¶