pgr_prim
— Minimum spanning forest of graph using Prim algorithm.
Availability
Support
This algorithm finds the minimum spanning forest in a possibly disconnected graph using Prim’s algorithm.
The main characteristics are:
Summary
pgr_prim(edges_sql)
RETURNS SET OF (edge, cost)
OR EMPTY SET
Example: | Minimum Spanning Forest of a subgraph |
---|
SELECT edge, cost FROM pgr_prim(
'SELECT id, source, target, cost, reverse_cost FROM edge_table WHERE id < 14'
) ORDER BY edge;
edge | cost
------+------
1 | 1
2 | 1
3 | 1
4 | 1
5 | 1
6 | 1
7 | 1
9 | 1
10 | 1
11 | 1
13 | 1
(11 rows)
Parameter | Type | Description |
---|---|---|
Edges SQL | TEXT |
SQL query described in 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 |
Returns SET OF (edge, cost)
Column | Type | Description |
---|---|---|
edge | BIGINT |
Identifier of the edge. |
cost | FLOAT |
Cost to traverse the edge. |
Indices and tables