pgr_primDD¶
pgr_primDD
— Catchament nodes using Prim’s algorithm.
Availability
- Version 3.0.0
- New Official function
Description¶
Using Prim algorithm, extracts the nodes that have aggregate costs less than
or equal to the value Distance
within the calculated minimum spanning tree.
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¶
Summary
pgr_prim(Edges SQL, root vid, distance)
pgr_prim(Edges SQL, root vids, distance)
RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)
Single vertex¶
pgr_primDD(Edges SQL, root vid, distance)
RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)
Example: | The Minimum Spanning Tree starting on vertex \(2\) with \(agg\_cost <= 3.5\) |
---|
SELECT * FROM pgr_primDD(
'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
2, 3.5
);
seq | depth | start_vid | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+----------
1 | 0 | 2 | 2 | -1 | 0 | 0
2 | 1 | 2 | 1 | 1 | 1 | 1
3 | 1 | 2 | 3 | 2 | 1 | 1
4 | 2 | 2 | 4 | 3 | 1 | 2
5 | 2 | 2 | 6 | 5 | 1 | 2
6 | 3 | 2 | 9 | 9 | 1 | 3
7 | 3 | 2 | 11 | 11 | 1 | 3
8 | 1 | 2 | 5 | 4 | 1 | 1
9 | 2 | 2 | 8 | 7 | 1 | 2
10 | 3 | 2 | 7 | 6 | 1 | 3
11 | 2 | 2 | 10 | 10 | 1 | 2
12 | 3 | 2 | 13 | 14 | 1 | 3
(12 rows)
Multiple vertices¶
pgr_primDD(Edges SQL, root vids, distance)
RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)
Example: | The Minimum Spanning Tree starting on vertices \(\{13, 2\}\) with \(agg\_cost <= 3.5\); |
---|
SELECT * FROM pgr_primDD(
'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
ARRAY[13,2], 3.5
);
seq | depth | start_vid | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+----------
1 | 0 | 2 | 2 | -1 | 0 | 0
2 | 1 | 2 | 1 | 1 | 1 | 1
3 | 1 | 2 | 3 | 2 | 1 | 1
4 | 2 | 2 | 4 | 3 | 1 | 2
5 | 2 | 2 | 6 | 5 | 1 | 2
6 | 3 | 2 | 9 | 9 | 1 | 3
7 | 3 | 2 | 11 | 11 | 1 | 3
8 | 1 | 2 | 5 | 4 | 1 | 1
9 | 2 | 2 | 8 | 7 | 1 | 2
10 | 3 | 2 | 7 | 6 | 1 | 3
11 | 2 | 2 | 10 | 10 | 1 | 2
12 | 3 | 2 | 13 | 14 | 1 | 3
13 | 0 | 13 | 13 | -1 | 0 | 0
14 | 1 | 13 | 10 | 14 | 1 | 1
15 | 2 | 13 | 5 | 10 | 1 | 2
16 | 3 | 13 | 2 | 4 | 1 | 3
17 | 3 | 13 | 8 | 7 | 1 | 3
(17 rows)
Parameters¶
Parameter | Type | Description |
---|---|---|
Edges SQL | TEXT |
SQL query described in Inner query. |
Root vid | BIGINT |
Identifier of the root vertex of the tree.
|
Root vids | ARRAY[ANY-INTEGER] |
Array of identifiers of the root vertices.
|
Distance | ANY-NUMERIC |
Upper limit for the inclusion of the node in the result.
|
Where:
ANY-INTEGER: | SMALLINT, INTEGER, BIGINT |
---|---|
ANY-NUMERIC: | SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC |
Inner query¶
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 (target, source),
|
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)
Column | Type | Description |
---|---|---|
seq | BIGINT |
Sequential value starting from \(1\). |
depth | BIGINT |
Depth of the
|
start_vid | BIGINT |
Identifier of the root vertex.
|
node | BIGINT |
Identifier of node reached using edge . |
edge | BIGINT |
Identifier of the
|
cost | FLOAT |
Cost to traverse edge . |
agg_cost | FLOAT |
Aggregate cost from start_vid to node . |
See Also¶
- Spanning Tree - Category
- Prim - Family of functions
- The queries use the Sample Data network.
- Boost: Prim’s algorithm documentation
- Wikipedia: Prim’s algorithm
Indices and tables