pgr_primDD¶

pgr_primDD — Catchament nodes using Prim’s algorithm.

Boost Graph Inside

Availability

Version 3.0.0
- New Official function

Support

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
-----+-------+-----------+------+------+------+----------
|     0 |         2 |    2 |   -1 |    0 |        0
|     1 |         2 |    1 |    1 |    1 |        1
|     1 |         2 |    3 |    2 |    1 |        1
|     2 |         2 |    4 |    3 |    1 |        2
|     2 |         2 |    6 |    5 |    1 |        2
|     3 |         2 |    9 |    9 |    1 |        3
|     3 |         2 |   11 |   11 |    1 |        3
|     1 |         2 |    5 |    4 |    1 |        1
|     2 |         2 |    8 |    7 |    1 |        2
|     3 |         2 |    7 |    6 |    1 |        3
|     2 |         2 |   10 |   10 |    1 |        2
|     3 |         2 |   13 |   14 |    1 |        3
|     0 |        13 |   13 |   -1 |    0 |        0
|     1 |        13 |   10 |   14 |    1 |        1
|     2 |        13 |    5 |   10 |    1 |        2
|     3 |        13 |    2 |    4 |    1 |        3
|     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.