pgr_kruskalDD¶

pgr_kruskalDD — Catchament nodes using Kruskal’s algorithm.

_images/boost-inside.jpeg — Boost Graph Inside¶

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 the value 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.
The total weight of all the edges in the tree or forest is minimized.
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.
Kruskal’s running time: \(O(E * log E)\)

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 \(2\) with \(agg\_cost <= 3.5\)

SELECT * FROM pgr_kruskalDD(
    '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 |     3 |         2 |    9 |   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 \(\{13, 2\}\) with \(agg\_cost <= 3.5\);

SELECT * FROM pgr_kruskalDD(
    '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 |     3 |         2 |    9 |   16 |    1 |        3
   6 |     0 |        13 |   13 |   -1 |    0 |        0
   7 |     1 |        13 |   10 |   14 |    1 |        1
   8 |     2 |        13 |    5 |   10 |    1 |        2
   9 |     3 |        13 |    8 |    7 |    1 |        3
  10 |     2 |        13 |   11 |   12 |    1 |        2
  11 |     3 |        13 |    6 |   11 |    1 |        3
  12 |     3 |        13 |   12 |   13 |    1 |        3
(12 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.