pgr_breadthFirstSearch - Experimental - pgRouting Manual (3.4)
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