pgr_kruskal¶

pgr_kruskal — Returns the minimum spanning tree of graph using Kruskal 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 Kruskal’s algorithm.

The main Characteristics are:

It’s implementation is only on undirected graph.
Process is done only on edges with positive costs.
The total weight of all the edges in the tree or forest is minimized.
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.
Kruskal’s running time: \(O(E * log E)\)

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

Signatures¶

Summary

pgr_kruskal(edges_sql)

RETURNS SET OF (seq, edge, cost)
OR EMPTY SET

Example: Minimum Spanning Forest

SELECT * FROM pgr_kruskal(
    'SELECT id, source, target, cost, reverse_cost
        FROM edge_table ORDER BY id'
) ORDER BY edge;
 edge | cost
------+------
    1 |    1
    2 |    1
    3 |    1
    6 |    1
    7 |    1
   10 |    1
   11 |    1
   12 |    1
   13 |    1
   14 |    1
   15 |    1
   16 |    1
   17 |    1
   18 |    1
(14 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.