# pgRouting Manual (3.6)

## pgr_breadthFirstSearch - Experimental

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

- Version 3.0.0

  - New experimental signature:

    - `pgr_breadthFirstSearch` (Single Vertex)

    - `pgr_breadthFirstSearch` (Multiple Vertices)

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

- Running time: \(O(E + V)\)

## Signatures

Summary

pgr_breadthFirstSearch(Edges SQL, root vid, [options])
pgr_breadthFirstSearch(Edges SQL, root vids, [options])
options: `[max_depth, directed]`
Returns set of `(seq, depth, start_vid, node, edge, cost, agg_cost)`

### Single vertex

pgr_breadthFirstSearch(Edges SQL, root vid, [options])
options: `[max_depth, directed]`
Returns set of `(seq, depth, start_vid, node, edge, cost, agg_cost)`

Example:

  From root vertex \(6\) on a directed graph with edges in ascending order of `id`

    SELECT * FROM pgr_breadthFirstSearch(
      'SELECT id, source, target, cost, reverse_cost
      FROM edges ORDER BY id',
      6);
     seq | depth | start_vid | node | edge | cost | agg_cost
    -----+-------+-----------+------+------+------+----------
       1 |     0 |         6 |    6 |   -1 |    0 |        0
       2 |     1 |         6 |    5 |    1 |    1 |        1
       3 |     1 |         6 |    7 |    4 |    1 |        1
       4 |     2 |         6 |    3 |    7 |    1 |        2
       5 |     2 |         6 |   11 |    8 |    1 |        2
       6 |     2 |         6 |    8 |   10 |    1 |        2
       7 |     3 |         6 |    1 |    6 |    1 |        3
       8 |     3 |         6 |   16 |    9 |    1 |        3
       9 |     3 |         6 |   12 |   11 |    1 |        3
      10 |     3 |         6 |    9 |   14 |    1 |        3
      11 |     4 |         6 |   17 |   15 |    1 |        4
      12 |     4 |         6 |   15 |   16 |    1 |        4
      13 |     5 |         6 |   10 |    3 |    1 |        5
    (13 rows)

### Multiple vertices

pgr_breadthFirstSearch(Edges SQL, root vids, [options])
options: `[max_depth, directed]`
Returns set of `(seq, depth, start_vid, node, edge, cost, agg_cost)`

Example:

  From root vertices \(\{12, 6\}\) on an undirected graph with depth \(<= 2\) and edges in ascending order of `id`

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

## Parameters

Parameter | Type | Description
--- | --- | ---
Edges SQL | `TEXT` | Edges SQL as described below.

root vid

`BIGINT`

Identifier of the root vertex of the tree.

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

> - \(0\) values are ignored

> - For optimization purposes, any duplicated value is ignored.

Where:

ANY-INTEGER:

  SMALLINT, INTEGER, BIGINT

ANY-NUMERIC:

  SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC

### Optional parameters

Column | Type | Default | Description
--- | --- | --- | ---

`directed`

`BOOLEAN`

`true`

- When `true` the graph is considered Directed

- When `false` the graph is considered as Undirected.

### DFS optional parameters

Parameter | Type | Default | Description
--- | --- | --- | ---

`max_depth`

`BIGINT`

\(9223372036854775807\)

Upper limit of the depth of the tree.

- When negative throws an error.

## Inner Queries

### Edges SQL

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`)

`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)`

Parameter | 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`.

Where:

ANY-INTEGER:

  SMALLINT, INTEGER, BIGINT

ANY-NUMERIC:

  SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC

## Additional Examples

Example:

  Same as Single vertex with edges in ascending order of `id`.

    SELECT * FROM pgr_breadthFirstSearch(
      'SELECT id, source, target, cost, reverse_cost
      FROM edges ORDER BY id',
      6);
     seq | depth | start_vid | node | edge | cost | agg_cost
    -----+-------+-----------+------+------+------+----------
       1 |     0 |         6 |    6 |   -1 |    0 |        0
       2 |     1 |         6 |    5 |    1 |    1 |        1
       3 |     1 |         6 |    7 |    4 |    1 |        1
       4 |     2 |         6 |    3 |    7 |    1 |        2
       5 |     2 |         6 |   11 |    8 |    1 |        2
       6 |     2 |         6 |    8 |   10 |    1 |        2
       7 |     3 |         6 |    1 |    6 |    1 |        3
       8 |     3 |         6 |   16 |    9 |    1 |        3
       9 |     3 |         6 |   12 |   11 |    1 |        3
      10 |     3 |         6 |    9 |   14 |    1 |        3
      11 |     4 |         6 |   17 |   15 |    1 |        4
      12 |     4 |         6 |   15 |   16 |    1 |        4
      13 |     5 |         6 |   10 |    3 |    1 |        5
    (13 rows)

Example:

  Same as Single vertex with edges in descending order of `id`.

    SELECT * FROM pgr_breadthFirstSearch(
      'SELECT id, source, target, cost, reverse_cost
      FROM edges ORDER BY id DESC',
      6);
     seq | depth | start_vid | node | edge | cost | agg_cost
    -----+-------+-----------+------+------+------+----------
       1 |     0 |         6 |    6 |   -1 |    0 |        0
       2 |     1 |         6 |    7 |    4 |    1 |        1
       3 |     1 |         6 |    5 |    1 |    1 |        1
       4 |     2 |         6 |    8 |   10 |    1 |        2
       5 |     2 |         6 |   11 |    8 |    1 |        2
       6 |     2 |         6 |    3 |    7 |    1 |        2
       7 |     3 |         6 |    9 |   14 |    1 |        3
       8 |     3 |         6 |   12 |   12 |    1 |        3
       9 |     3 |         6 |   16 |    9 |    1 |        3
      10 |     3 |         6 |    1 |    6 |    1 |        3
      11 |     4 |         6 |   17 |   13 |    1 |        4
      12 |     4 |         6 |   15 |   16 |    1 |        4
      13 |     5 |         6 |   10 |    3 |    1 |        5
    (13 rows)

The resulting traversal is different.

The left image shows the result with ascending order of ids and the right image shows with descending order of the edge identifiers.

## See Also

- BFS - Category

- Sample Data

- Boost: Breadth First Search algorithm documentation

- Wikipedia: Breadth First Search algorithm

Indices and tables

- Index

- Search Page