pgr_bdDijkstraCostMatrix

pgr_bdDijkstraCostMatrix - Calculates a cost matrix using pgr_bdDijkstra.

Boost Graph Inside

Availability

• Version 3.0.0

  • Official function

• Version 2.5.0

  • New proposed function

Description

Using bidirectional Dijkstra algorithm, calculate and return a cost matrix.

• Process is done only on edges with positive costs.

  • A negative value on a cost column is interpreted as the edge does not exist.

• Values are returned when there is a path.

• When there is no path:

  • When the starting vertex and ending vertex are the same.

    • The aggregate cost of the non included values \((v, v)\) is \(0\)

  • When the starting vertex and ending vertex are the different and there is no path:

    • The aggregate cost the non included values \((u, v)\) is \(\infty\)

• For optimization purposes, any duplicated value in the starting vertices or on the ending vertices are ignored.

• Running time (worse case scenario): \(O((V \log V + E))\)

• For large graphs where there is a path bewtween the starting vertex and ending vertex:

  • It is expected to terminate faster than pgr_dijkstra

The main Characteristics are:

• Can be used as input to pgr_TSP.

  • Use directly when the resulting matrix is symmetric and there is no \(\infty\) value.

  • It will be the users responsibility to make the matrix symmetric.

    • By using geometric or harmonic average of the non symmetric values.

    • By using max or min the non symmetric values.

    • By setting the upper triangle to be the mirror image of the lower triangle.

    • By setting the lower triangle to be the mirror image of the upper triangle.

  • It is also the users responsibility to fix an \(\infty\) value.

• Each function works as part of the family it belongs to.

• It does not return a path.

• Returns the sum of the costs of the shortest path for pair combination of nodes in the graph.

• Process is done only on edges with positive costs.

• Values are returned when there is a path.

  • When the starting vertex and ending vertex are the same, there is no path.

    • The aggregate cost in the non included values (v, v) is 0.

  • When the starting vertex and ending vertex are the different and there is no path.

    • The aggregate cost in the non included values (u, v) is \(\infty\).

• Let be the case the values returned are stored in a table:

  • The unique index would be the pair: (start_vid, end_vid).

• Depending on the function and its parameters, the results can be symmetric.

  • The aggregate cost of (u, v) is the same as for (v, u).

• Any duplicated value in the start vids are ignored.

• The returned values are ordered:

  • start_vid ascending

  • end_vid ascending

Signatures

Summary

pgr_bdDijkstraCostMatrix(Edges SQL, start vids, [directed])

RETURNS SET OF (start_vid, end_vid, agg_cost)

OR EMPTY SET

Example:

Symmetric cost matrix for vertices \(\{5, 6, 10, 15\}\) on an undirected graph

SELECT * FROM pgr_bdDijkstraCostMatrix(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  (SELECT array_agg(id)
    FROM vertices
    WHERE id IN (5, 6, 10, 15)),
  false);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         5 |       6 |        1
         5 |      10 |        2
         5 |      15 |        3
         6 |       5 |        1
         6 |      10 |        1
         6 |      15 |        2
        10 |       5 |        2
        10 |       6 |        1
        10 |      15 |        1
        15 |       5 |        3
        15 |       6 |        2
        15 |      10 |        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.

Inner Queries

Edges SQL

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

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_bdDijkstraCostMatrix(
    'SELECT id, source, target, cost, reverse_cost FROM edges',
    (SELECT array_agg(id)
      FROM vertices
      WHERE id IN (5, 6, 10, 15)),
    false)
  $$);
NOTICE:  pgr_TSP no longer solving with simulated annaeling
HINT:  Ignoring annaeling parameters
 seq | node | cost | agg_cost
-----+------+------+----------
   1 |    5 |    0 |        0
   2 |    6 |    1 |        1
   3 |   10 |    1 |        2
   4 |   15 |    1 |        3
   5 |    5 |    3 |        6
(5 rows)

See Also

• Bidirectional Dijkstra - Family of functions

• Cost Matrix - Category

• Traveling Sales Person - Family of functions

• Sample Data

Indices and tables

• Index

• Search Page