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. Used on Single Vertex.
Root vids	`ARRAY[ANY-INTEGER]`	Array of identifiers of the root vertices. Used on Multiple Vertices. For optimization purposes, any duplicated value is ignored.

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.

Root vids

ARRAY[ANY-INTEGER]

Array of identifiers of the root vertices.

Used on Multiple Vertices.
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
directed	`BOOLEAN`	`true`	When `true` Graph is considered Directed When `false` the graph is considered as Undirected.

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)

pgr_breadthFirstSearch - Experimental¶

Description¶

Signatures¶

Single Vertex¶

Multiple Vertices¶

Parameters¶

Optional Parameters¶

Inner query¶

Result Columns¶

Additional Examples¶

See Also¶