Supported versions: Latest (3.3) 3.2 3.1 3.0

`pgr_prim`¶

pgr_prim — Minimum spanning forest of a graph using Prim’s algorithm.

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

Availability

Version 3.0.0
- New Official function

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`	Edges SQL as described below.

Inner query¶

Edges SQL¶

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`) 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¶

include:: pgRouting-concepts.rst

start-after: r-edge-cost-start
end-before: r-edge-cost-end

pgr_prim¶