pgr_breadthFirstSearch
- Experimental¶
pgr_breadthFirstSearch
— Returns the traversal order(s) using Breadth First
Search algorithm.
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.0.0
New experimental signature:
pgr_breadthFirstSearch
(Single Vertex)pgr_breadthFirstSearch
(Multiple Vertices)
Description¶
Provides the Breadth First Search traversal order from a root vertex to a particular depth.
The main Characteristics are:
The implementation will work on any type of graph.
Provides the Breadth First Search traversal order from a source node to a target depth level.
Running time: \(O(E + V)\)
Signatures¶
Summary
[max_depth, directed]
(seq, depth, start_vid, node, edge, cost, agg_cost)
Single vertex¶
[max_depth, directed]
(seq, depth, start_vid, node, edge, cost, agg_cost)
- Example:
From root vertex \(6\) on a directed graph with edges in ascending order of
id
SELECT * FROM pgr_breadthFirstSearch(
'SELECT id, source, target, cost, reverse_cost
FROM edges ORDER BY id',
6);
seq | depth | start_vid | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+----------
1 | 0 | 6 | 6 | -1 | 0 | 0
2 | 1 | 6 | 5 | 1 | 1 | 1
3 | 1 | 6 | 7 | 4 | 1 | 1
4 | 2 | 6 | 3 | 7 | 1 | 2
5 | 2 | 6 | 11 | 8 | 1 | 2
6 | 2 | 6 | 8 | 10 | 1 | 2
7 | 3 | 6 | 1 | 6 | 1 | 3
8 | 3 | 6 | 16 | 9 | 1 | 3
9 | 3 | 6 | 12 | 11 | 1 | 3
10 | 3 | 6 | 9 | 14 | 1 | 3
11 | 4 | 6 | 17 | 15 | 1 | 4
12 | 4 | 6 | 15 | 16 | 1 | 4
13 | 5 | 6 | 10 | 3 | 1 | 5
(13 rows)
Multiple vertices¶
[max_depth, directed]
(seq, depth, start_vid, node, edge, cost, agg_cost)
- Example:
From root vertices \(\{12, 6\}\) on an undirected graph with depth \(<= 2\) and edges in ascending order of
id
SELECT * FROM pgr_breadthFirstSearch(
'SELECT id, source, target, cost, reverse_cost
FROM edges ORDER BY id',
ARRAY[12, 6], directed => false, max_depth => 2);
seq | depth | start_vid | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+----------
1 | 0 | 6 | 6 | -1 | 0 | 0
2 | 1 | 6 | 5 | 1 | 1 | 1
3 | 1 | 6 | 10 | 2 | 1 | 1
4 | 1 | 6 | 7 | 4 | 1 | 1
5 | 2 | 6 | 15 | 3 | 1 | 2
6 | 2 | 6 | 11 | 5 | 1 | 2
7 | 2 | 6 | 3 | 7 | 1 | 2
8 | 2 | 6 | 8 | 10 | 1 | 2
9 | 0 | 12 | 12 | -1 | 0 | 0
10 | 1 | 12 | 11 | 11 | 1 | 1
11 | 1 | 12 | 8 | 12 | 1 | 1
12 | 1 | 12 | 17 | 13 | 1 | 1
13 | 2 | 12 | 10 | 5 | 1 | 2
14 | 2 | 12 | 7 | 8 | 1 | 2
15 | 2 | 12 | 16 | 9 | 1 | 2
16 | 2 | 12 | 9 | 14 | 1 | 2
(16 rows)
Parameters¶
Parameter |
Type |
Description |
---|---|---|
|
Edges SQL as described below. |
|
root vid |
|
Identifier of the root vertex of the tree.
|
root vids |
|
Array of identifiers of the root vertices.
|
Where:
- ANY-INTEGER:
SMALLINT, INTEGER, BIGINT
- ANY-NUMERIC:
SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC
Optional parameters¶
Column |
Type |
Default |
Description |
---|---|---|---|
|
|
|
|
DFS optional parameters¶
Parameter |
Type |
Default |
Description |
---|---|---|---|
|
|
\(9223372036854775807\) |
Upper limit of the depth of the tree.
|
Inner Queries¶
Edges SQL¶
Column |
Type |
Default |
Description |
---|---|---|---|
|
ANY-INTEGER |
Identifier of the edge. |
|
|
ANY-INTEGER |
Identifier of the first end point vertex of the edge. |
|
|
ANY-INTEGER |
Identifier of the second end point vertex of the edge. |
|
|
ANY-NUMERICAL |
Weight of the edge ( |
|
|
ANY-NUMERICAL |
-1 |
Weight of the edge (
|
Where:
- ANY-INTEGER:
SMALLINT
,INTEGER
,BIGINT
- ANY-NUMERICAL:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Return columns¶
Returns SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)
Parameter |
Type |
Description |
---|---|---|
|
|
Sequential value starting from \(1\). |
|
|
Depth of the
|
|
|
Identifier of the root vertex. |
|
|
Identifier of |
|
|
Identifier of the
|
|
|
Cost to traverse |
|
|
Aggregate cost from |
Where:
- ANY-INTEGER:
SMALLINT, INTEGER, BIGINT
- ANY-NUMERIC:
SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC
Additional Examples¶
- Example:
Same as Single vertex with edges in ascending order of
id
.
SELECT * FROM pgr_breadthFirstSearch(
'SELECT id, source, target, cost, reverse_cost
FROM edges ORDER BY id',
6);
seq | depth | start_vid | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+----------
1 | 0 | 6 | 6 | -1 | 0 | 0
2 | 1 | 6 | 5 | 1 | 1 | 1
3 | 1 | 6 | 7 | 4 | 1 | 1
4 | 2 | 6 | 3 | 7 | 1 | 2
5 | 2 | 6 | 11 | 8 | 1 | 2
6 | 2 | 6 | 8 | 10 | 1 | 2
7 | 3 | 6 | 1 | 6 | 1 | 3
8 | 3 | 6 | 16 | 9 | 1 | 3
9 | 3 | 6 | 12 | 11 | 1 | 3
10 | 3 | 6 | 9 | 14 | 1 | 3
11 | 4 | 6 | 17 | 15 | 1 | 4
12 | 4 | 6 | 15 | 16 | 1 | 4
13 | 5 | 6 | 10 | 3 | 1 | 5
(13 rows)
- Example:
Same as Single vertex with edges in descending order of
id
.
SELECT * FROM pgr_breadthFirstSearch(
'SELECT id, source, target, cost, reverse_cost
FROM edges ORDER BY id DESC',
6);
seq | depth | start_vid | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+----------
1 | 0 | 6 | 6 | -1 | 0 | 0
2 | 1 | 6 | 7 | 4 | 1 | 1
3 | 1 | 6 | 5 | 1 | 1 | 1
4 | 2 | 6 | 8 | 10 | 1 | 2
5 | 2 | 6 | 11 | 8 | 1 | 2
6 | 2 | 6 | 3 | 7 | 1 | 2
7 | 3 | 6 | 9 | 14 | 1 | 3
8 | 3 | 6 | 12 | 12 | 1 | 3
9 | 3 | 6 | 16 | 9 | 1 | 3
10 | 3 | 6 | 1 | 6 | 1 | 3
11 | 4 | 6 | 17 | 13 | 1 | 4
12 | 4 | 6 | 15 | 16 | 1 | 4
13 | 5 | 6 | 10 | 3 | 1 | 5
(13 rows)
The resulting traversal is different.
The left image shows the result with ascending order of ids and the right image shows with descending order of the edge identifiers.
See Also¶
Indices and tables