# pgRouting Manual (3.1)

## pgr_breadthFirstSearch - Experimental

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

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.

### 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

- The queries use the Sample Data network.

- Boost: Breadth First Search algorithm documentation

- Wikipedia: Breadth First Search algorithm

Indices and tables

- Index

- Search Page