pgr_primBFS

pgr_primBFS — Prim’s algorithm for Minimum Spanning Tree with Depth First Search ordering.

_images/boost-inside.jpeg

Boost Graph Inside

Availability

Support

Description

Visits and extracts the nodes information in Breath First Search ordering of the Minimum Spanning Tree created with Prims’s algorithm.

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 Breath First Search order
  • Breath First Search Running time: \(O(E + V)\)

Signatures

pgr_primBFS(Edges SQL, Root vid [, max_depth])
pgr_primBFS(Edges SQL, Root vids [, max_depth])

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

Single vertex

pgr_primBFS(Edges SQL, Root vid [, max_depth])

RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)
Example:The Minimum Spanning Tree having as root vertex \(2\)
SELECT * FROM pgr_primBFS(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
    2
);
 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 |     1 |         2 |    5 |    4 |    1 |        1
   5 |     2 |         2 |    4 |    3 |    1 |        2
   6 |     2 |         2 |    6 |    5 |    1 |        2
   7 |     2 |         2 |    8 |    7 |    1 |        2
   8 |     2 |         2 |   10 |   10 |    1 |        2
   9 |     3 |         2 |    9 |    9 |    1 |        3
  10 |     3 |         2 |   11 |   11 |    1 |        3
  11 |     3 |         2 |    7 |    6 |    1 |        3
  12 |     3 |         2 |   13 |   14 |    1 |        3
  13 |     4 |         2 |   12 |   13 |    1 |        4
(13 rows)

Multiple vertices

pgr_primBFS(Edges SQL, Root vids [, max_depth])

RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)
Example:The Minimum Spanning Tree starting on vertices \(\{13, 2\}\) with \(depth <= 3\)
SELECT * FROM pgr_primBFS(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
    ARRAY[13,2], max_depth := 3
);
 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 |     1 |         2 |    5 |    4 |    1 |        1
   5 |     2 |         2 |    4 |    3 |    1 |        2
   6 |     2 |         2 |    6 |    5 |    1 |        2
   7 |     2 |         2 |    8 |    7 |    1 |        2
   8 |     2 |         2 |   10 |   10 |    1 |        2
   9 |     3 |         2 |    9 |    9 |    1 |        3
  10 |     3 |         2 |   11 |   11 |    1 |        3
  11 |     3 |         2 |    7 |    6 |    1 |        3
  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 value is \(0\) then gets the spanning forest starting in aleatory nodes for each tree in the forest.
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.

Optional Parameters

Parameter Type Default Description
max_depth BIGINT \(9223372036854775807\)

Upper limit for depth of node in the tree

  • When value is Negative then throws error

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.