pgr_binaryBreadthFirstSearch
- Experimental¶
pgr_binaryBreadthFirstSearch
— Returns the shortest path(s) in a binary
graph.
Any graph whose edge-weights belongs to the set {0,X}, where ‘X’ is any non-negative integer, is termed as a ‘binary graph’.
Warning
Possible server crash
- These functions might create a server crash
Warning
Experimental functions
- They are not officially of the current release.
- They likely will not be officially be part of the next release:
- The functions might not make use of ANY-INTEGER and ANY-NUMERICAL
- Name might change.
- Signature might change.
- Functionality might change.
- pgTap tests might be missing.
- Might need c/c++ coding.
- May lack documentation.
- Documentation if any might need to be rewritten.
- Documentation examples might need to be automatically generated.
- Might need a lot of feedback from the comunity.
- Might depend on a proposed function of pgRouting
- Might depend on a deprecated function of pgRouting
Availability
- Version 3.2.0
- New experimental signature:
- pgr_binaryBreadthFirstSearch(Combinations)
- New experimental signature:
- Version 3.0.0
- New experimental signatures:
- pgr_binaryBreadthFirstSearch(One to One)
- pgr_binaryBreadthFirstSearch(One to Many)
- pgr_binaryBreadthFirstSearch(Many to One)
- pgr_binaryBreadthFirstSearch(Many to Many)
- New experimental signatures:
Description¶
It is well-known that the shortest paths between a single source and all other vertices can be found using Breadth First Search in \(O(|E|)\) in an unweighted graph, i.e. the distance is the minimal number of edges that you need to traverse from the source to another vertex. We can interpret such a graph also as a weighted graph, where every edge has the weight \(1\). If not alledges in graph have the same weight, that we need a more general algorithm, like Dijkstra’s Algorithm which runs in \(O(|E|log|V|)\) time.
However if the weights are more constrained, we can use a faster algorithm. This algorithm, termed as ‘Binary Breadth First Search’ as well as ‘0-1 BFS’, is a variation of the standard Breadth First Search problem to solve the SSSP (single-source shortest path) problem in \(O(|E|)\), if the weights of each edge belongs to the set {0,X}, where ‘X’ is any non-negative real integer.
The main Characteristics are:
- Process is done only on ‘binary graphs’. (‘Binary Graph’: Any graph whose edge-weights belongs to the set {0,X}, where ‘X’ is any non-negative real integer.)
- For optimization purposes, any duplicated value in the start_vids or end_vids are ignored.
- The returned values are ordered:
- start_vid ascending
- end_vid ascending
- Running time: \(O(| start\_vids | * |E|)\)
Signatures¶
Summary
pgr_binaryBreadthFirstSearch(Edges SQL, start vid, end vid [, directed]) pgr_binaryBreadthFirstSearch(Edges SQL, start vid, end vids [, directed]) pgr_binaryBreadthFirstSearch(Edges SQL, start vids, end vid [, directed]) pgr_binaryBreadthFirstSearch(Edges SQL, start vids, end vids [, directed]) pgr_binaryBreadthFirstSearch(Edges SQL, Combinations SQL [, directed]) RETURNS (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost) OR EMPTY SET
Note: Using the Sample Data Network as all weights are same (i.e \(1\))
One to One¶
pgr_binaryBreadthFirstSearch(Edges SQL, start vid, end vid [, directed]); RETURNS (seq, path_seq, node, edge, cost, agg_cost) OR EMPTY SET
Example: | From vertex \(6\) to vertex \(10\) on a directed graph |
---|
SELECT * FROM pgr_binaryBreadthFirstSearch(
'SELECT id, source, target, cost, reverse_cost from edges',
6, 10, true);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 6 | 4 | 1 | 0
2 | 2 | 7 | 8 | 1 | 1
3 | 3 | 11 | 9 | 1 | 2
4 | 4 | 16 | 16 | 1 | 3
5 | 5 | 15 | 3 | 1 | 4
6 | 6 | 10 | -1 | 0 | 5
(6 rows)
One to Many¶
pgr_binaryBreadthFirstSearch(Edges SQL, start vid, end vids [, directed]); RETURNS (seq, path_seq, end_vid, node, edge, cost, agg_cost) OR EMPTY SET
Example: | From vertex \(6\) to vertices \(\{10, 17\}\) on a directed graph |
---|
SELECT * FROM pgr_binaryBreadthFirstSearch(
'SELECT id, source, target, cost, reverse_cost from edges',
6, ARRAY[10, 17]);
seq | path_seq | end_vid | node | edge | cost | agg_cost
-----+----------+---------+------+------+------+----------
1 | 1 | 10 | 6 | 4 | 1 | 0
2 | 2 | 10 | 7 | 8 | 1 | 1
3 | 3 | 10 | 11 | 9 | 1 | 2
4 | 4 | 10 | 16 | 16 | 1 | 3
5 | 5 | 10 | 15 | 3 | 1 | 4
6 | 6 | 10 | 10 | -1 | 0 | 5
7 | 1 | 17 | 6 | 4 | 1 | 0
8 | 2 | 17 | 7 | 8 | 1 | 1
9 | 3 | 17 | 11 | 11 | 1 | 2
10 | 4 | 17 | 12 | 13 | 1 | 3
11 | 5 | 17 | 17 | -1 | 0 | 4
(11 rows)
Many to One¶
pgr_binaryBreadthFirstSearch(Edges SQL, start vids, end vid [, directed]); RETURNS (seq, path_seq, start_vid, node, edge, cost, agg_cost) OR EMPTY SET
Example: | From vertices \(\{6, 1\}\) to vertex \(17\) on a directed graph |
---|
SELECT * FROM pgr_binaryBreadthFirstSearch(
'SELECT id, source, target, cost, reverse_cost from edges',
ARRAY[6, 1], 17);
seq | path_seq | start_vid | node | edge | cost | agg_cost
-----+----------+-----------+------+------+------+----------
1 | 1 | 1 | 1 | 6 | 1 | 0
2 | 2 | 1 | 3 | 7 | 1 | 1
3 | 3 | 1 | 7 | 8 | 1 | 2
4 | 4 | 1 | 11 | 11 | 1 | 3
5 | 5 | 1 | 12 | 13 | 1 | 4
6 | 6 | 1 | 17 | -1 | 0 | 5
7 | 1 | 6 | 6 | 4 | 1 | 0
8 | 2 | 6 | 7 | 8 | 1 | 1
9 | 3 | 6 | 11 | 11 | 1 | 2
10 | 4 | 6 | 12 | 13 | 1 | 3
11 | 5 | 6 | 17 | -1 | 0 | 4
(11 rows)
Many to Many¶
pgr_binaryBreadthFirstSearch(Edges SQL, start vids, end vids [, directed]); RETURNS (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost) OR EMPTY SET
Example: | From vertices \(\{6, 1\}\) to vertices \(\{10, 17\}\) on an undirected graph |
---|
SELECT * FROM pgr_binaryBreadthFirstSearch(
'SELECT id, source, target, cost, reverse_cost from edges',
ARRAY[6, 1], ARRAY[10, 17],
directed => false);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 10 | 1 | 6 | 1 | 0
2 | 2 | 1 | 10 | 3 | 7 | 1 | 1
3 | 3 | 1 | 10 | 7 | 4 | 1 | 2
4 | 4 | 1 | 10 | 6 | 2 | 1 | 3
5 | 5 | 1 | 10 | 10 | -1 | 0 | 4
6 | 1 | 1 | 17 | 1 | 6 | 1 | 0
7 | 2 | 1 | 17 | 3 | 7 | 1 | 1
8 | 3 | 1 | 17 | 7 | 8 | 1 | 2
9 | 4 | 1 | 17 | 11 | 11 | 1 | 3
10 | 5 | 1 | 17 | 12 | 13 | 1 | 4
11 | 6 | 1 | 17 | 17 | -1 | 0 | 5
12 | 1 | 6 | 10 | 6 | 2 | 1 | 0
13 | 2 | 6 | 10 | 10 | -1 | 0 | 1
14 | 1 | 6 | 17 | 6 | 4 | 1 | 0
15 | 2 | 6 | 17 | 7 | 8 | 1 | 1
16 | 3 | 6 | 17 | 11 | 11 | 1 | 2
17 | 4 | 6 | 17 | 12 | 13 | 1 | 3
18 | 5 | 6 | 17 | 17 | -1 | 0 | 4
(18 rows)
Combinations¶
pgr_binaryBreadthFirstSearch(Edges SQL, Combinations SQL [, directed]); RETURNS (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost) OR EMPTY SET
Example: | Using a combinations table on an undirected graph |
---|
The combinations table:
SELECT source, target FROM combinations;
source | target
--------+--------
5 | 6
5 | 10
6 | 5
6 | 15
6 | 14
(5 rows)
The query:
SELECT * FROM pgr_binaryBreadthFirstSearch(
'SELECT id, source, target, cost, reverse_cost FROM edges',
'SELECT source, target FROM combinations',
false);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 5 | 6 | 5 | 1 | 1 | 0
2 | 2 | 5 | 6 | 6 | -1 | 0 | 1
3 | 1 | 5 | 10 | 5 | 1 | 1 | 0
4 | 2 | 5 | 10 | 6 | 2 | 1 | 1
5 | 3 | 5 | 10 | 10 | -1 | 0 | 2
6 | 1 | 6 | 5 | 6 | 1 | 1 | 0
7 | 2 | 6 | 5 | 5 | -1 | 0 | 1
8 | 1 | 6 | 15 | 6 | 2 | 1 | 0
9 | 2 | 6 | 15 | 10 | 3 | 1 | 1
10 | 3 | 6 | 15 | 15 | -1 | 0 | 2
(10 rows)
Parameters¶
Column | Type | Description |
---|---|---|
Edges SQL | TEXT |
Edges SQL as described below |
Combinations SQL | 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 |
|
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 (
|
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 (seq, path_id, path_seq [, start_vid] [, end_vid], node, edge, cost,
agg_cost)
Column | Type | Description |
---|---|---|
seq |
INTEGER |
Sequential value starting from 1. |
path_id |
INTEGER |
Path identifier.
|
path_seq |
INTEGER |
Relative position in the path. Has value 1 for the beginning of a path. |
start_vid |
BIGINT |
Identifier of the starting vertex. Returned when multiple starting vetrices are in the query. |
end_vid |
BIGINT |
Identifier of the ending vertex. Returned when multiple ending vertices are in the query. |
node |
BIGINT |
Identifier of the node in the path from start_vid to end_vid . |
edge |
BIGINT |
Identifier of the edge used to go from node to the next node in the
path sequence. -1 for the last node of the path. |
cost |
FLOAT |
Cost to traverse from node using edge to the next node in the
path sequence. |
agg_cost |
FLOAT |
Aggregate cost from start_vid to node . |
Additional Examples¶
Example: | Manually assigned vertex combinations. |
---|
SELECT * FROM pgr_binaryBreadthFirstSearch(
'SELECT id, source, target, cost, reverse_cost FROM edges',
'SELECT * FROM (VALUES (6, 10), (6, 7), (12, 10)) AS combinations (source, target)');
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 7 | 6 | 4 | 1 | 0
2 | 2 | 6 | 7 | 7 | -1 | 0 | 1
3 | 1 | 6 | 10 | 6 | 4 | 1 | 0
4 | 2 | 6 | 10 | 7 | 8 | 1 | 1
5 | 3 | 6 | 10 | 11 | 9 | 1 | 2
6 | 4 | 6 | 10 | 16 | 16 | 1 | 3
7 | 5 | 6 | 10 | 15 | 3 | 1 | 4
8 | 6 | 6 | 10 | 10 | -1 | 0 | 5
9 | 1 | 12 | 10 | 12 | 13 | 1 | 0
10 | 2 | 12 | 10 | 17 | 15 | 1 | 1
11 | 3 | 12 | 10 | 16 | 16 | 1 | 2
12 | 4 | 12 | 10 | 15 | 3 | 1 | 3
13 | 5 | 12 | 10 | 10 | -1 | 0 | 4
(13 rows)