## pgr_kruskalDD

``` pgr_kruskalDD ``` - Catchament nodes using Kruskal’s algorithm.

Availability

• Version 3.0.0

• New Official function

### Description

Using Kruskal’s algorithm, extracts the nodes that have aggregate costs less than or equal to the value ``` Distance ``` from a root vertex (or vertices) within the calculated minimum spanning tree.

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_kruskalDD(edges_sql, root_vid, distance)
pgr_kruskalDD(edges_sql, root_vids, distance)

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

#### Single vertex

```pgr_kruskalDD(edges_sql, root_vid, distance)

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

The Minimum Spanning Tree starting on vertex \(2\) with \(agg\_cost <= 3.5\)

```SELECT * FROM pgr_kruskalDD(
'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
2, 3.5
);
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
(5 rows)

```

#### Multiple vertices

```pgr_kruskalDD(edges_sql, root_vids, distance)

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

The Minimum Spanning Tree starting on vertices \(\{13, 2\}\) with \(agg\_cost <= 3.5\) ;

```SELECT * FROM pgr_kruskalDD(
'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
ARRAY[13,2],
3.5
);
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 \(0\) gets the spanning forest starting in aleatory nodes for each tree.

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.

Distance

``` ANY-NUMERIC ```

Upper limit for the inclusion of the node in the result.

• When the value is Negative throws error

Where:

ANY-INTEGER :

SMALLINT, INTEGER, BIGINT

ANY-NUMERIC :

SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC

### 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 ``` .