## pgr_primDD

``` pgr_primDD ``` - Catchament nodes using Prim’s algorithm.

Availability

• Version 3.0.0

• New Official function

### Description

Using Prim algorithm, extracts the nodes that have aggregate costs less than or equal to the value ``` Distance ``` 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.

• Prim’s running time: \(O(E*log V)\)

• Returned tree nodes from a root vertex are on Depth First Search order.

• Depth First Search running time: \(O(E + V)\)

### Signatures

Summary

```pgr_prim(Edges SQL, root vid, distance)
pgr_prim(Edges SQL, root vids, distance)

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

#### Single vertex

```pgr_primDD(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_primDD(
'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      2          2     6     5     1         2
6      3          2     9     9     1         3
7      3          2    11    11     1         3
8      1          2     5     4     1         1
9      2          2     8     7     1         2
10      3          2     7     6     1         3
11      2          2    10    10     1         2
12      3          2    13    14     1         3
(12 rows)

```

#### Multiple vertices

```pgr_primDD(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_primDD(
'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      2          2     6     5     1         2
6      3          2     9     9     1         3
7      3          2    11    11     1         3
8      1          2     5     4     1         1
9      2          2     8     7     1         2
10      3          2     7     6     1         3
11      2          2    10    10     1         2
12      3          2    13    14     1         3
13      0         13    13    -1     0         0
14      1         13    10    14     1         1
15      2         13     5    10     1         2
16      3         13     2     4     1         3
17      3         13     8     7     1         3
(17 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 ``` .