pgr_primBFS
¶
pgr_primBFS
— Prim’s algorithm for Minimum Spanning Tree with Depth First
Search ordering.
Availability
Version 3.0.0
New Official function
Description¶
Visits and extracts the nodes information in Breath First Search ordering of the Minimum Spanning Tree created with Prims’s algorithm.
The main Characteristics are:
It’s implementation is only on undirected graph.
Process is done only on edges with positive costs.
When the graph is connected
The resulting edges make up a tree
When the graph is not connected,
Finds a minimum spanning tree for each connected component.
The resulting edges make up a forest.
Prim’s running time: \(O(E * log V)\)
Returned tree nodes from a root vertex are on Breath First Search order
Breath First Search Running time: \(O(E + V)\)
Signatures¶
(seq, depth, start_vid, node, edge, cost, agg_cost)
Single vertex¶
max_depth
])(seq, depth, start_vid, node, edge, cost, agg_cost)
- Example:
The Minimum Spanning Tree having as root vertex \(6\)
SELECT * FROM pgr_primBFS(
'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 | 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 | 3 | 6 | 16 | 9 | 1 | 3
10 | 3 | 6 | 12 | 11 | 1 | 3
11 | 3 | 6 | 1 | 6 | 1 | 3
12 | 3 | 6 | 9 | 14 | 1 | 3
13 | 4 | 6 | 17 | 13 | 1 | 4
(13 rows)
Multiple vertices¶
max_depth
])(seq, depth, start_vid, node, edge, cost, agg_cost)
- Example:
The Minimum Spanning Tree starting on vertices \(\{9, 6\}\) with \(depth \leq 3\)
SELECT * FROM pgr_primBFS(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
ARRAY[9, 6], max_depth => 3);
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 | 3 | 6 | 16 | 9 | 1 | 3
10 | 3 | 6 | 12 | 11 | 1 | 3
11 | 3 | 6 | 1 | 6 | 1 | 3
12 | 3 | 6 | 9 | 14 | 1 | 3
13 | 0 | 9 | 9 | -1 | 0 | 0
14 | 1 | 9 | 8 | 14 | 1 | 1
15 | 2 | 9 | 7 | 10 | 1 | 2
16 | 3 | 9 | 6 | 4 | 1 | 3
17 | 3 | 9 | 3 | 7 | 1 | 3
(17 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
BFS 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
Result 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
See Also¶
The queries use the Sample Data network.
Indices and tables