pgr_primDFS
¶
pgr_primDFS
— Prim 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 Depth First Search ordering of the Minimum Spanning Tree created using 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 Depth First Search order
Depth 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_primDFS(
'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 | 2 | 6 | 15 | 3 | 1 | 2
5 | 2 | 6 | 11 | 5 | 1 | 2
6 | 3 | 6 | 16 | 9 | 1 | 3
7 | 3 | 6 | 12 | 11 | 1 | 3
8 | 4 | 6 | 17 | 13 | 1 | 4
9 | 1 | 6 | 7 | 4 | 1 | 1
10 | 2 | 6 | 3 | 7 | 1 | 2
11 | 3 | 6 | 1 | 6 | 1 | 3
12 | 2 | 6 | 8 | 10 | 1 | 2
13 | 3 | 6 | 9 | 14 | 1 | 3
(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_primDFS(
'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 | 2 | 6 | 15 | 3 | 1 | 2
5 | 2 | 6 | 11 | 5 | 1 | 2
6 | 3 | 6 | 16 | 9 | 1 | 3
7 | 3 | 6 | 12 | 11 | 1 | 3
8 | 1 | 6 | 7 | 4 | 1 | 1
9 | 2 | 6 | 3 | 7 | 1 | 2
10 | 3 | 6 | 1 | 6 | 1 | 3
11 | 2 | 6 | 8 | 10 | 1 | 2
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
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
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¶
Indices and tables