pgr_bdAstarCost

pgr_bdAstarCost — Returns the aggregate cost shortest path using pgr_aStar algorithm.

Boost Graph Inside

Availability

• Version 3.2.0

  • New proposed function:

    • pgr_bdAstarCost(Combinations)

• Version 3.0.0

  • Official function

• Version 2.5.0

  • New Proposed function

Description

• Default kind of graph is directed when

  • directed flag is missing.

  • directed flag is set to true

• Unless specified otherwise, 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\)

• Edges with negative costs are not included in the graph.

• 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)\)

• The results are equivalent to the union of the results of the pgr_bdAstarCost( One to One ) on the:

  • pgr_bdAstarCost( One to Many )

  • pgr_bdAstarCost( Many to One )

  • pgr_bdAstarCost( Many to Many )

Signatures

Summary

pgr_bdAstarCost(Edges SQL, from_vid,  to_vid  [, directed] [, heuristic] [, factor] [, epsilon])
pgr_bdAstarCost(Edges SQL, from_vid,  to_vids [, directed] [, heuristic] [, factor] [, epsilon])
pgr_bdAstarCost(Edges SQL, from_vids, to_vid  [, directed] [, heuristic] [, factor] [, epsilon])
pgr_bdAstarCost(Edges SQL, from_vids, to_vids [, directed] [, heuristic] [, factor] [, epsilon])
pgr_bdAstarCost(Edges SQL, Combinations SQL [, directed] [, heuristic] [, factor] [, epsilon]) -- Proposed on v3.2

RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

Optional parameters are named parameters and have a default value.

Using defaults

pgr_bdAstarCost(Edges SQL, from_vid,  to_vid)
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

Example

From vertex \(2\) to vertex \(3\) on a directed graph

SELECT * FROM pgr_bdAstarCost(
    'SELECT id, source, target, cost, reverse_cost, x1,y1,x2,y2
    FROM edge_table',
    2, 3
);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         2 |       3 |        5
(1 row)

One to One

pgr_bdAstarCost(Edges SQL, from_vid,  to_vid  [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

Example

From vertex \(2\) to vertex \(3\) on an directed graph using heuristic \(2\)

SELECT * FROM pgr_bdAstarCost(
    'SELECT id, source, target, cost, reverse_cost, x1,y1,x2,y2
    FROM edge_table',
    2, 3,
    true, heuristic := 2
);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         2 |       3 |        5
(1 row)

One to many

pgr_bdAstarCost(Edges SQL, from_vid,  to_vids [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

Example

From vertex 2 to vertices \(\{3, 11\}\) on a directed graph using heuristic 3 and factor \(3.5\)

SELECT * FROM pgr_bdAstarCost(
    'SELECT id, source, target, cost, reverse_cost, x1,y1,x2,y2
    FROM edge_table',
    2, ARRAY[3, 11],
    heuristic := 3, factor := 3.5
);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         2 |       3 |        5
         2 |      11 |        3
(2 rows)

Many to One

pgr_bdAstarCost(Edges SQL, from_vids, to_vid  [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

Example

From vertices \(\{7, 2\}\) to vertex \(3\) on a undirected graph using heuristic \(4\)

SELECT * FROM pgr_bdAstarCost(
    'SELECT id, source, target, cost, reverse_cost, x1,y1,x2,y2
    FROM edge_table',
    ARRAY[2, 7], 3,
    false, heuristic := 4
);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         2 |       3 |        1
         7 |       3 |        4
(2 rows)

Many to Many

pgr_bdAstarCost(Edges SQL, from_vids, to_vids [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

Example

From vertices \(\{7, 2\}\) to vertices \(\{3, 11\}\) on a directed using heuristic \(5\) and factor \(0.5\)

SELECT * FROM pgr_bdAstarCost(
    'SELECT id, source, target, cost, reverse_cost, x1,y1,x2,y2
    FROM edge_table',
    ARRAY[2, 7], ARRAY[3, 11],
    factor := 0.5
);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         2 |       3 |        5
         2 |      11 |        3
         7 |       3 |        6
         7 |      11 |        4
(4 rows)

Combinations

pgr_bdAstarCost(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 using factor \(0.5\).

SELECT * FROM pgr_bdAstarCost(
    'SELECT id, source, target, cost, reverse_cost, x1,y1,x2,y2
    FROM edge_table',
    'SELECT * FROM ( VALUES (2, 3), (7, 11) ) AS t(source, target)',
    factor := 0.5
);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         2 |       3 |        5
         7 |      11 |        4
(2 rows)

Parameters

Parameter	Type	Description
Edges SQL	TEXT	Edges query as described below.
Combinations SQL	TEXT	Combinations query as described below.
from_vid	ANY-INTEGER	Starting vertex identifier. Parameter in: One to One One to Many
from_vids	ARRAY[ANY-INTEGER]	Array of starting vertices identifiers. Parameter in: Many to One Many to Many
to_vid	ANY-INTEGER	Ending vertex identifier. Parameter in: One to One Many to One
to_vids	ARRAY[ANY-INTEGER]	Array of ending vertices identifiers. Parameter in: One to Many Many to Many

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 queries

Edges query

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

Combinations query

Column	Type	Default	Description
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.

Where:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

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.

See Also

• Bidirectional A* - Family of functions

• Cost - Category

• Cost Matrix - Category

• Examples use Sample Data network.

Indices and tables

• Index

• Search Page