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

• 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.

• The total weight of all the edges in the tree or forest is minimized.

• Kruskal’s running time: $$O(E * log E)$$

• Extracts all the nodes that have costs less than or equal to the value distance.

• The edges extracted will conform to the corresponding spanning tree.

• Edge $$(u, v)$$ will not be included when:

• The distance from the root to $$u$$ > limit distance.

• The distance from the root to $$v$$ > limit distance.

• No new nodes are created on the graph, so when is within the limit and is not within the limit, the edge is not included.

• 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 $$6$$ with $$distance \leq 3.5$$

SELECT * FROM pgr_kruskalDD(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
6, 3.5);
seq  depth  start_vid  node  edge  cost  agg_cost
-----+-------+-----------+------+------+------+----------
1      0          6     6    -1     0         0
2      1          6     5     1     1         1
3      1          6    10     2     1         1
4      2          6    15     3     1         2
5      3          6    16    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 $$\{9, 6\}$$ with $$distance \leq 3.5$$

SELECT * FROM pgr_kruskalDD(
'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
ARRAY[9, 6], 3.5);
seq  depth  start_vid  node  edge  cost  agg_cost
-----+-------+-----------+------+------+------+----------
1      0          6     6    -1     0         0
2      1          6     5     1     1         1
3      1          6    10     2     1         1
4      2          6    15     3     1         2
5      3          6    16    16     1         3
6      0          9     9    -1     0         0
7      1          9     8    14     1         1
8      2          9     7    10     1         2
9      3          9     3     7     1         3
10      2          9    12    12     1         2
11      3          9    11    11     1         3
12      3          9    17    13     1         3
(12 rows)



### Parameters

Parameter

Type

Description

 TEXT 

Edges SQL as described below.

Root vid

 BIGINT 

Identifier of the root vertex of the tree.

Root vids

 ARRAY[ANY-INTEGER] 

Array of identifiers of the root vertices.

• $$0$$ values are ignored

• For optimization purposes, any duplicated value is ignored.

distance

 FLOAT 

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

Where:

ANY-INTEGER :

 SMALLINT  ,  INTEGER  ,  BIGINT 

ANY-NUMERIC :

 SMALLINT  ,  INTEGER  ,  BIGINT  ,  REAL  ,  FLOAT 

### Inner Queries

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

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

Parameter

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  .

Where:

ANY-INTEGER :

SMALLINT, INTEGER, BIGINT

ANY-NUMERIC :

SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC