pgr_primDD - pgRouting Manual (3.0)

pgr_primDD

pgr_primDD - Catchament nodes using Prim’s algorithm.

images/boost-inside.jpeg — Boost Graph Inside

Availability

Version 3.0.0
- New Official function

Support

Supported versions: current( 3.0 )

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.