pgr_breadthFirstSearch - Experimental

pgr_breadthFirstSearch - Returns the traversal order(s) using Breadth First Search algorithm.

images/boost-inside.jpeg

Boost Graph Inside

Warning

Possible server crash

  • These functions might create a server crash

Warning

Experimental functions

  • They are not officially of the current release.

  • They likely will not be officially be part of the next release:

    • The functions might not make use of ANY-INTEGER and ANY-NUMERICAL

    • Name might change.

    • Signature might change.

    • Functionality might change.

    • pgTap tests might be missing.

    • Might need c/c++ coding.

    • May lack documentation.

    • Documentation if any might need to be rewritten.

    • Documentation examples might need to be automatically generated.

    • Might need a lot of feedback from the comunity.

    • Might depend on a proposed function of pgRouting

    • Might depend on a deprecated function of pgRouting

Availability

Description

Provides the Breadth First Search traversal order from a root vertex to a particular depth.

The main Characteristics are:

  • The implementation will work on any type of graph.

  • Provides the Breadth First Search traversal order from a source node to a target depth level

  • Breath First Search Running time: \(O(E + V)\)

Signatures 

pgr_breadthFirstSearch(Edges SQL, Root vid [, max_depth] [, directed])
pgr_breadthFirstSearch(Edges SQL, Root vids [, max_depth] [, directed])

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

Single Vertex 

pgr_breadthFirstSearch(Edges SQL, Root vid [, max_depth] [, directed])

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

The Breadth First Search traversal with root vertex \(2\) 

SELECT * FROM pgr_breadthFirstSearch(
    '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     5     4     1         1
   4      2          2     8     7     1         2
   5      2          2     6     8     1         2
   6      2          2    10    10     1         2
   7      3          2     7     6     1         3
   8      3          2     9     9     1         3
   9      3          2    11    11     1         3
  10      3          2    13    14     1         3
  11      4          2    12    15     1         4
  12      4          2     4    16     1         4
  13      5          2     3     3     1         5
(13 rows)

Multiple Vertices 

pgr_breadthFirstSearch(Edges SQL, Root vids [, max_depth] [, directed])

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

The Breadth First Search traverls starting on vertices \(\{11, 12\}\) with \(depth <= 2\) 

SELECT * FROM pgr_breadthFirstSearch(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
    ARRAY[11,12], max_depth := 2
);
 seq  depth  start_vid  node  edge  cost  agg_cost
-----+-------+-----------+------+------+------+----------
   1      0         11    11    -1     0         0
   2      1         11    12    13     1         1
   3      2         11     9    15     1         2
   4      0         12    12    -1     0         0
   5      1         12     9    15     1         1
   6      2         12     6     9     1         2
   7      2         12     4    16     1         2
(7 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.

Root vids

ARRAY[ANY-INTEGER]

Array of identifiers of the root vertices.

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

directed

BOOLEAN

true

  • When true Graph is considered Directed

  • When false the graph is considered as Undirected .

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.

  • In Multiple Vertices results are in ascending order.

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 .

Additional Examples

Undirected Graph

Example :

The Breadth First Search traverls starting on vertices \(\{11, 12\}\) with \(depth <= 2\) as well as considering the graph to be undirected. 

SELECT * FROM pgr_breadthFirstSearch(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
    ARRAY[11,12], max_depth := 2, directed := false
);
 seq  depth  start_vid  node  edge  cost  agg_cost
-----+-------+-----------+------+------+------+----------
   1      0         11    11    -1     0         0
   2      1         11     6    11     1         1
   3      1         11    10    12     1         1
   4      1         11    12    13     1         1
   5      2         11     3     5     1         2
   6      2         11     5     8     1         2
   7      2         11     9     9     1         2
   8      2         11    13    14     1         2
   9      0         12    12    -1     0         0
  10      1         12    11    13     1         1
  11      1         12     9    15     1         1
  12      2         12     6    11     1         2
  13      2         12    10    12     1         2
  14      2         12     4    16     1         2
(14 rows)

Vertex Out Of Graph

Example :

The output of the function when a vertex not present in the graph is passed as a parameter. 

SELECT * FROM pgr_breadthFirstSearch(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
    -10
);
 seq  depth  start_vid  node  edge  cost  agg_cost
-----+-------+-----------+------+------+------+----------
(0 rows)

See Also

Indices and tables