## pgr_bdAstarCost

 pgr_bdAstarCost  - Total cost of the shortest path(s) using the bidirectional A* algorithm.

Availability

• Version 3.2.0

• New proposed signature:

• Version 3.0.0

• Official function

• Version 2.4.0

• New proposed function

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

pgr_bdAstarCost( Edges SQL , start vid , end vid , [ options ])
pgr_bdAstarCost( Edges SQL , start vid , end vids , [ options ])
pgr_bdAstarCost( Edges SQL , start vids , end vid , [ options ])
pgr_bdAstarCost( Edges SQL , start vids , end vids , [ options ])
pgr_bdAstarCost( Edges SQL , Combinations SQL , [ options ])
options:  [directed, heuristic, factor, epsilon] 
RETURNS SET OF  (start_vid, end_vid, agg_cost) 
OR EMPTY SET

#### One to One

pgr_bdAstarCost( Edges SQL , start vid , end vid , [ options ])
options:  [directed, heuristic, factor, epsilon] 
RETURNS SET OF  (start_vid, end_vid, agg_cost) 
OR EMPTY SET
Example :

From vertex $$6$$ to vertex $$12$$ on a directed graph with heuristic $$2$$

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)



#### One to Many

pgr_bdAstarCost( Edges SQL , start vid , end vids , [ options ])
options:  [directed, heuristic, factor, epsilon] 
RETURNS SET OF  (start_vid, end_vid, agg_cost) 
OR EMPTY SET
Example :

From vertex $$6$$ to vertices $$\{10, 12\}$$ on a directed graph with heuristic $$3$$ and factor $$3.5$$

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)



#### Many to One

pgr_bdAstarCost( Edges SQL , start vids , end vid , [ options ])
options:  [directed, heuristic, factor, epsilon] 
RETURNS SET OF  (start_vid, end_vid, agg_cost) 
OR EMPTY SET
Example :

From vertices $$\{6, 8\}$$ to vertex $$10$$ on an undirected graph with heuristic $$4$$

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)



#### Many to Many

pgr_bdAstarCost( Edges SQL , start vids , end vids , [ options ])
options:  [directed, heuristic, factor, epsilon] 
RETURNS SET OF  (start_vid, end_vid, agg_cost) 
OR EMPTY SET
Example :

From vertices $$\{6, 8\}$$ to vertices $$\{10, 12\}$$ on a directed graph with factor $$0.5$$

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)



#### Combinations

pgr_bdAstarCost( Edges SQL , Combinations SQL , [ options ])
options:  [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 with factor $$0.5$$ .

The combinations table:

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



The query:

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

Column

Type

Description

 TEXT 

Edges SQL as described below

 TEXT 

Combinations SQL as described below

start vid

 BIGINT 

Identifier of the starting vertex of the path.

start vids

 ARRAY[BIGINT] 

Array of identifiers of starting vertices.

end vid

 BIGINT 

Identifier of the ending vertex of the path.

end vids

 ARRAY[BIGINT] 

Array of identifiers of ending 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(\Delta x, \Delta y))$$

• 2: $$h(v) = abs(min(\Delta x, \Delta y))$$

• 3: $$h(v) = \Delta x * \Delta x + \Delta y * \Delta y$$

• 4: $$h(v) = sqrt(\Delta x * \Delta x + \Delta y * \Delta y)$$

• 5: $$h(v) = abs(\Delta x) + abs(\Delta y)$$

 factor 

 FLOAT 

 1 

For units manipulation. $$factor > 0$$ .

 epsilon 

 FLOAT 

 1 

For less restricted results. $$epsilon >= 1$$ .

See heuristics available and factor handling.

### Inner Queries

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

#### Combinations SQL

Parameter

Type

Description

 source 

ANY-INTEGER

Identifier of the departure vertex.

 target 

ANY-INTEGER

Identifier of the arrival vertex.

Where:

ANY-INTEGER :

 SMALLINT  ,  INTEGER  ,  BIGINT 

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

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)