# pgRouting Manual (3.1)

## pgr_bdAstarCostMatrix

`pgr_bdAstarCostMatrix` - Calculates the a cost matrix using pgr_aStar.

Boost Graph Inside

Availability

- Version 3.0.0

  - Official function

- Version 2.5.0

  - New Proposed function

Support

- Supported versions: current(3.1) 3.0 2.6

- Unsupported versions: 2.5

## 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)

Using defaults

    pgr_bdAstarCostMatrix(edges_sql, vids)
    RETURNS SET OF (start_vid, end_vid, agg_cost)

Example

  Cost matrix for vertices \(\{1, 2, 3, 4\}\) on a directed graph

    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)
    );
     start_vid | end_vid | agg_cost
    -----------+---------+----------
             1 |       2 |        1
             1 |       3 |        6
             1 |       4 |        5
             2 |       1 |        1
             2 |       3 |        5
             2 |       4 |        4
             3 |       1 |        2
             3 |       2 |        1
             3 |       4 |        3
             4 |       1 |        3
             4 |       2 |        2
             4 |       3 |        1
    (12 rows)

### Complete Signature

    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),
        false
    );
     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

Parameter | Type | Description
--- | --- | ---
edges_sql | `TEXT` | edges_sql inner query.
vids | `ARRAY[ANY-INTEGER]` | Array of vertices identifiers.

### 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 query

### edges_sql

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

## Result Columns

Returns 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),
            false
        )
        $$,
        randomize := false
    );
     seq | node | cost | agg_cost
    -----+------+------+----------
       1 |    1 |    1 |        0
       2 |    2 |    1 |        1
       3 |    3 |    1 |        2
       4 |    4 |    3 |        3
       5 |    1 |    0 |        6
    (5 rows)

## See Also

- aStar - Family of functions

- Bidirectional A* - Family of functions

- Cost - Category

- Cost Matrix - Category

- Traveling Sales Person - Family of functions

- The queries use the Sample Data network.

Indices and tables

- Index

- Search Page