# pgRouting Manual (3.6)

## pgr_turnRestrictedPath - Experimental

`pgr_turnRestrictedPath` Using Yen’s algorithm Vertex -Vertex routing with restrictions

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 function

## Description

Using Yen’s algorithm to obtain K shortest paths and analyze the paths to select the paths that do not use the restrictions

## Signatures

pgr_turnRestrictedPath(Edges SQL, Restrictions SQL, start vid, end vid, K, [options])
options: `[directed, heap_paths, stop_on_first, strict]`
Returns set of `(seq, path_id, path_seq, node, edge, cost, agg_cost)`
OR EMPTY SET

Example:

  From vertex \(3\) to vertex \(8\) on a directed graph

    SELECT * FROM pgr_turnRestrictedPath(
      $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
      $$SELECT path, cost FROM restrictions$$,
      3, 8, 3);
     seq | path_id | path_seq | node | edge | cost | agg_cost
    -----+---------+----------+------+------+------+----------
       1 |       1 |        1 |    3 |    7 |    1 | Infinity
       2 |       1 |        2 |    7 |   10 |    1 |        1
       3 |       1 |        3 |    8 |   -1 |    0 |        2
    (3 rows)

## Parameters

Column | Type | Description
--- | --- | ---
Edges SQL | `TEXT` | SQL query as described.
start vid | ANY-INTEGER | Identifier of the departure vertex.
end vid | ANY-INTEGER | Identifier of the destination vertex.
K | ANY-INTEGER | Number of required paths.

Where:

ANY-INTEGER:

  `SMALLINT`, `INTEGER`, `BIGINT`

### Optional parameters

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

`directed`

`BOOLEAN`

`true`

- When `true` the graph is considered Directed

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

## KSP Optional parameters

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

`heap_paths`

`BOOLEAN`

`false`

- When `false` Returns at most K paths.

- When `true` all the calculated paths while processing are returned.

- Roughly, when the shortest path has `N` edges, the heap will contain about than `N * K` paths for small value of `K` and `K > 5`.

## Special optional parameters

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

`stop_on_first`

`BOOLEAN`

`true`

- When `true` stops on first path found that dos not violate restrictions

- When `false` returns at most K paths

`strict`

`BOOLEAN`

`false`

- When `true` returns only paths that do not violate restrictions

- When `false` returns the paths found

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

### Restrictions SQL

Column | Type | Description
--- | --- | ---
`path` | `ARRAY` [ANY-INTEGER] | Sequence of edge identifiers that form a path that is not allowed to be taken. - Empty arrays or `NULL` arrays are ignored. - Arrays that have a `NULL` element will raise an exception.
`Cost` | ANY-NUMERICAL | Cost of taking the forbidden path.

Where:

ANY-INTEGER:

  `SMALLINT`, `INTEGER`, `BIGINT`

ANY-NUMERICAL:

  `SMALLINT`, `INTEGER`, `BIGINT`, `REAL`, `FLOAT`

## Result columns

Returns set of `(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)`

Column | Type | Description
--- | --- | ---
`seq` | `INTEGER` | Sequential value starting from 1.

`path_id`

`INTEGER`

Path identifier.

- Has value 1 for the first of a path from `start_vid` to `end_vid`.

`path_seq` | `INTEGER` | Relative position in the path. Has value 1 for the beginning of a path.
`start_vid` | `BIGINT` | Identifier of the starting vertex.
`end_vid` | `BIGINT` | Identifier of the ending vertex.
`node` | `BIGINT` | Identifier of the node in the path from `start_vid` to `end_vid`.
`edge` | `BIGINT` | Identifier of the edge used to go from `node` to the next node in the path sequence. -1 for the last node of the path.
`cost` | `FLOAT` | Cost to traverse from `node` using `edge` to the next node in the path sequence.
`agg_cost` | `FLOAT` | Aggregate cost from `start_vid` to `node`.

## Additional Examples

Example:

  From vertex \(3\) to \(8\) with `strict` flag on.

No results because the only path available follows a restriction.

    SELECT * FROM pgr_turnRestrictedPath(
      $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
      $$SELECT path, cost FROM restrictions$$,
      3, 8, 3,
      strict => true);
     seq | path_id | path_seq | node | edge | cost | agg_cost
    -----+---------+----------+------+------+------+----------
    (0 rows)

Example:

  From vertex \(3\) to vertex \(8\) on an undirected graph

    SELECT * FROM pgr_turnRestrictedPath(
      $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
      $$SELECT path, cost FROM restrictions$$,
      3, 8, 3,
      directed => false);
     seq | path_id | path_seq | node | edge | cost | agg_cost
    -----+---------+----------+------+------+------+----------
       1 |       1 |        1 |    3 |    7 |    1 |        0
       2 |       1 |        2 |    7 |    4 |    1 |        1
       3 |       1 |        3 |    6 |    2 |    1 |        2
       4 |       1 |        4 |   10 |    5 |    1 |        3
       5 |       1 |        5 |   11 |   11 |    1 |        4
       6 |       1 |        6 |   12 |   12 |    1 |        5
       7 |       1 |        7 |    8 |   -1 |    0 |        6
    (7 rows)

Example:

  From vertex \(3\) to vertex \(8\) with more alternatives

    SELECT * FROM pgr_turnRestrictedPath(
      $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
      $$SELECT path, cost FROM restrictions$$,
      3, 8, 3,
      directed => false,
      heap_paths => true,
      stop_on_first => false);
     seq | path_id | path_seq | node | edge | cost | agg_cost
    -----+---------+----------+------+------+------+----------
       1 |       1 |        1 |    3 |    7 |    1 |        0
       2 |       1 |        2 |    7 |    4 |    1 |        1
       3 |       1 |        3 |    6 |    2 |    1 |        2
       4 |       1 |        4 |   10 |    5 |    1 |        3
       5 |       1 |        5 |   11 |   11 |    1 |        4
       6 |       1 |        6 |   12 |   12 |    1 |        5
       7 |       1 |        7 |    8 |   -1 |    0 |        6
       8 |       2 |        1 |    3 |    7 |    1 |        0
       9 |       2 |        2 |    7 |    8 |    1 |        1
      10 |       2 |        3 |   11 |    9 |    1 |        2
      11 |       2 |        4 |   16 |   15 |    1 |        3
      12 |       2 |        5 |   17 |   13 |    1 |        4
      13 |       2 |        6 |   12 |   12 |    1 |        5
      14 |       2 |        7 |    8 |   -1 |    0 |        6
    (14 rows)

## See Also

- K shortest paths - Category

- Sample Data

Indices and tables

- Index

- Search Page