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

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 .

See Also

Indices and tables