pgr_prim¶

pgr_prim — Minimum spanning forest of graph using Prim algorithm.

_images/boost-inside.jpeg — Boost Graph Inside¶

Availability

Version 3.0.0
- New Official function

Support

Description¶

This algorithm finds the minimum spanning forest in a possibly disconnected graph using Prim’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)\)

EMPTY SET is returned when there are no edges in the graph.

Signatures¶

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)

Parameters¶

Parameter	Type	Description
Edges SQL	`TEXT`	SQL query described in Inner query.

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) When negative: edge (source, target) does not exist, therefore it’s not part of the graph.
reverse_cost	`ANY-NUMERICAL`	-1	Weight of the edge (target, source), When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

Where:

ANY-INTEGER: SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL: SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Result Columns¶

Returns SET OF (edge, cost)

Column	Type	Description
edge	`BIGINT`	Identifier of the edge.
cost	`FLOAT`	Cost to traverse the edge.