pgr_kruskalDFS¶

pgr_kruskalDFS — Kruskal algorithm for Minimum Spanning Tree with Depth First Search ordering.

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

Availability

Version 3.0.0
- New Official function

Description¶

Visits and extracts the nodes information in Depth First Search ordering of the Minimum Spanning Tree created 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)\)

Returned tree nodes from a root vertex are on Depth First Search order
Depth First Search Running time: \(O(E + V)\)

Signatures¶

pgr_kruskalDFS(Edges SQL, Root vid [, max_depth])
pgr_kruskalDFS(Edges SQL, Root vids [, max_depth])

RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)

Single vertex¶

pgr_kruskalDFS(Edges SQL, Root vid [, max_depth])

RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)

Example: The Minimum Spanning Tree starting on vertex \(2\)

SELECT * FROM pgr_kruskalDFS(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
    2
);
 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 |     3 |         2 |    9 |   16 |    1 |        3
   6 |     4 |         2 |   12 |   15 |    1 |        4
   7 |     5 |         2 |   11 |   13 |    1 |        5
   8 |     6 |         2 |    6 |   11 |    1 |        6
   9 |     6 |         2 |   10 |   12 |    1 |        6
  10 |     7 |         2 |    5 |   10 |    1 |        7
  11 |     8 |         2 |    8 |    7 |    1 |        8
  12 |     9 |         2 |    7 |    6 |    1 |        9
  13 |     7 |         2 |   13 |   14 |    1 |        7
(13 rows)

Multiple vertices¶

pgr_kruskalDFS(Edges SQL, Root vids [, max_depth])

RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)

Example: The Minimum Spanning Tree starting on vertices \(\{13, 2\}\) with \(depth <= 3\)

SELECT * FROM pgr_kruskalDFS(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
    ARRAY[13,2], max_depth := 3
);
 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 |     3 |         2 |    9 |   16 |    1 |        3
   6 |     0 |        13 |   13 |   -1 |    0 |        0
   7 |     1 |        13 |   10 |   14 |    1 |        1
   8 |     2 |        13 |    5 |   10 |    1 |        2
   9 |     3 |        13 |    8 |    7 |    1 |        3
  10 |     2 |        13 |   11 |   12 |    1 |        2
  11 |     3 |        13 |    6 |   11 |    1 |        3
  12 |     3 |        13 |   12 |   13 |    1 |        3
(12 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. Used on Single vertex When value is \(0\) then gets the spanning forest starting in aleatory nodes for each tree in the forest.
Root vids	`ARRAY[ANY-INTEGER]`	Array of identifiers of the root vertices. Used on Multiple vertices \(0\) values are ignored For optimization purposes, any duplicated value is ignored.

Parameter

Type

Description

Edges SQL

TEXT

SQL query described in Inner query.

Root vid

BIGINT

Identifier of the root vertex of the tree.

Used on Single vertex
When value is \(0\) then gets the spanning forest starting in aleatory nodes for each tree in the forest.

Root vids

ARRAY[ANY-INTEGER]

Array of identifiers of the root vertices.

Used on Multiple vertices
\(0\) values are ignored
For optimization purposes, any duplicated value is ignored.

Optional Parameters¶

Parameter	Type	Default	Description
max_depth	`BIGINT`	\(9223372036854775807\)	Upper limit for depth of node in the tree When value is `Negative` then throws error

Parameter

Type

Default

Description

max_depth

BIGINT

\(9223372036854775807\)

Upper limit for depth of node in the tree

When value is Negative then throws error

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 (seq, depth, start_vid, node, edge, cost, agg_cost)

Column	Type	Description
seq	`BIGINT`	Sequential value starting from \(1\).
depth	`BIGINT`	Depth of the `node`. \(0\) when `node` = `start_vid`.
start_vid	`BIGINT`	Identifier of the root vertex. In Multiple Vertices results are in ascending order.
node	`BIGINT`	Identifier of `node` reached using `edge`.
edge	`BIGINT`	Identifier of the `edge` used to arrive to `node`. \(-1\) when `node` = `start_vid`.
cost	`FLOAT`	Cost to traverse `edge`.
agg_cost	`FLOAT`	Aggregate cost from `start_vid` to `node`.