pgr_kruskalDFS

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

_images/boost-inside.jpeg

Boost Graph Inside

Availability

Support

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.

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

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.

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.