pgr_dijkstraCost¶

pgr_dijkstraCost

Using Dijkstra algorithm implemented by Boost.Graph, and extract only the aggregate cost of the shortest path(s) found, for the combination of vertices given.

_images/boost-inside.jpeg — Boost Graph Inside¶

Availability

Version 3.1.0
- New Proposed functions:
  - pgr_dijkstraCost(combinations)
Version 2.2.0
- New Official function

Description¶

The pgr_dijkstraCost algorithm, is a good choice to calculate the sum of the costs of the shortest path for a subset of pairs of nodes of the graph. We make use of the Boost’s implementation of dijkstra which runs in \(O(V \log V + E)\) time.

The main characteristics are:

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.
- The returned values are in the form of a set of (start_vid, end_vid, agg_cost).
- When the starting vertex and ending vertex are the same, there is no path.
  - The agg_cost int the non included values (v, v) is 0
- When the starting vertex and ending vertex are the different and there is no path.
  - The agg_cost in the non included values (u, v) is \(\infty\)
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).
Any duplicated value in the start_vids or end_vids is ignored.
The returned values are ordered:
- start_vid ascending
- end_vid ascending
Running time: \(O(| start\_vids | * (V \log V + E))\)

Signatures¶

Summary

pgr_dijkstraCost(edges_sql, from_vid,  to_vid  [, directed])
pgr_dijkstraCost(edges_sql, from_vid,  to_vids [, directed])
pgr_dijkstraCost(edges_sql, from_vids, to_vid  [, directed])
pgr_dijkstraCost(edges_sql, from_vids, to_vids [, directed])
pgr_dijkstraCost(edges_sql, combinations_sql   [, directed]) -- Proposed on v3.1
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

Using defaults

pgr_dijkstraCost(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_dijkstraCost(
    'select id, source, target, cost, reverse_cost from edge_table',
    2, 3);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         2 |       3 |        5
(1 row)

One to One¶

pgr_dijkstraCost(edges_sql, from_vid,  to_vid  [, directed])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

Example: From vertex \(2\) to vertex \(3\) on an undirected graph

SELECT * FROM pgr_dijkstraCost(
    'select id, source, target, cost, reverse_cost from edge_table',
    2, 3, false);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         2 |       3 |        1
(1 row)

One to Many¶

pgr_dijkstraCost(edges_sql, from_vid,  to_vids [, directed])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

Example: From vertex \(2\) to vertices \(\{3, 11\}\) on a directed graph

SELECT * FROM pgr_dijkstraCost(
    'select id, source, target, cost, reverse_cost from edge_table',
    2, ARRAY[3, 11]);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         2 |       3 |        5
         2 |      11 |        3
(2 rows)

Many to One¶

pgr_dijkstraCost(edges_sql, from_vids, to_vid  [, directed])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

Example: From vertices \(\{2, 7\}\) to vertex \(3\) on a directed graph

SELECT * FROM pgr_dijkstraCost(
    'select id, source, target, cost, reverse_cost from edge_table',
    ARRAY[2, 7], 3);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         2 |       3 |        5
         7 |       3 |        6
(2 rows)

Many to Many¶

pgr_dijkstraCost(edges_sql, from_vids, to_vids [, directed])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

Example: From vertices \(\{2, 7\}\) to vertices \(\{3, 11\}\) on a directed graph

SELECT * FROM pgr_dijkstraCost(
    'select id, source, target, cost, reverse_cost from edge_table',
    ARRAY[2, 7], ARRAY[3, 11]);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         2 |       3 |        5
         2 |      11 |        3
         7 |       3 |        6
         7 |      11 |        4
(4 rows)

Combinations¶

pgr_dijkstraCost(TEXT edges_sql, TEXT combination_sql, BOOLEAN directed:=true);
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET

Example: Using a combinations table on an undirected graph

SELECT * FROM pgr_dijkstraCost(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
    'SELECT source, target FROM combinations_table',
    FALSE
);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         1 |       2 |        1
         1 |       4 |        3
         2 |       1 |        1
         2 |       4 |        2
(4 rows)

Parameters¶

Parameter	Type	Default	Description
Edges SQL	`TEXT`		Edges query as described below
Combinations SQL	`TEXT`		Combinations query 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.
directed	`BOOLEAN`	`true`	When `true` Graph is considered Directed When `false` the graph is considered as Undirected.

Inner query¶

Edges query¶

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.

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.