pgr_aStarCostMatrix

pgr_aStarCostMatrix - Calculates the a cost matrix using pgr_aStar.

Boost Graph Inside

Availability

• Version 3.0.0

  • Official function

• Version 2.4.0

  • New proposed function

Description

The main characteristics are:

• Using internaly the pgr_aStar 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_aStarCostMatrix(edges_sql, vids [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (start_vid, end_vid, agg_cost)

Using defaults

pgr_aStarCostMatrix(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_aStarCostMatrix(
    '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_aStarCostMatrix(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_aStarCostMatrix(
    '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

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_aStarCostMatrix(
        '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
);
 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

• Cost - Category

• Cost Matrix - Category

• Traveling Sales Person - Family of functions

• The queries use the Sample Data network.

Indices and tables

• Index

• Search Page