# pgRouting Manual (2.5)

## pgr_withPointsKSP - Proposed

## Name

`pgr_withPointsKSP` - Find the K shortest paths using Yen’s algorithm.

Warning

Proposed functions for next mayor release.

- They are not officially in the current release.
- They will likely officially be part of the next mayor release:
  - The functions make use of ANY-INTEGER and ANY-NUMERICAL
  - Name might not change. (But still can)
  - Signature might not change. (But still can)
  - Functionality might not change. (But still can)
  - pgTap tests have being done. But might need more.
  - Documentation might need refinement.

Boost Graph Inside

Availability: 2.2.0

## Synopsis

Modifies the graph to include the points defined in the `points_sql` and using Yen algorithm, finds the K shortest paths.

## Signature Summary

    pgr_withPointsKSP(edges_sql, points_sql, start_pid, end_pid, K)
    pgr_withPointsKSP(edges_sql, points_sql, start_pid, end_pid, K, directed, heap_paths, driving_side, details)
    RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost)

## Signatures

### Minimal Usage

The minimal usage:
  - Is for a directed graph.
  - The driving side is set as b both. So arriving/departing to/from the point(s) can be in any direction.
  - No details are given about distance of other points of the query.
  - No heap paths are returned.

    pgr_withPointsKSP(edges_sql, points_sql, start_pid, end_pid, K)
    RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost)

Example: |

    SELECT * FROM pgr_withPointsKSP(
        'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
        'SELECT pid, edge_id, fraction, side from pointsOfInterest',
        -1, -2, 2);
     seq | path_id | path_seq | node | edge | cost | agg_cost
    -----+---------+----------+------+------+------+----------
       1 |       1 |        1 |   -1 |    1 |  0.6 |        0
       2 |       1 |        2 |    2 |    4 |    1 |      0.6
       3 |       1 |        3 |    5 |    8 |    1 |      1.6
       4 |       1 |        4 |    6 |    9 |    1 |      2.6
       5 |       1 |        5 |    9 |   15 |  0.4 |      3.6
       6 |       1 |        6 |   -2 |   -1 |    0 |        4
       7 |       2 |        1 |   -1 |    1 |  0.6 |        0
       8 |       2 |        2 |    2 |    4 |    1 |      0.6
       9 |       2 |        3 |    5 |    8 |    1 |      1.6
      10 |       2 |        4 |    6 |   11 |    1 |      2.6
      11 |       2 |        5 |   11 |   13 |    1 |      3.6
      12 |       2 |        6 |   12 |   15 |  0.6 |      4.6
      13 |       2 |        7 |   -2 |   -1 |    0 |      5.2
    (13 rows)

### Complete Signature

Finds the K shortest paths depending on the optional parameters setup.

    pgr_withPointsKSP(edges_sql, points_sql, start_pid, end_pid, K,
        directed:=true, heap_paths:=false, driving_side:='b', details:=false)
    RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost)

Example: | With details.

    SELECT * FROM pgr_withPointsKSP(
        'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
        'SELECT pid, edge_id, fraction, side from pointsOfInterest',
        -1, 6, 2, details := true);
     seq | path_id | path_seq | node | edge | cost | agg_cost
    -----+---------+----------+------+------+------+----------
       1 |       1 |        1 |   -1 |    1 |  0.6 |        0
       2 |       1 |        2 |    2 |    4 |  0.7 |      0.6
       3 |       1 |        3 |   -6 |    4 |  0.3 |      1.3
       4 |       1 |        4 |    5 |    8 |    1 |      1.6
       5 |       1 |        5 |    6 |   -1 |    0 |      2.6
       6 |       2 |        1 |   -1 |    1 |  0.6 |        0
       7 |       2 |        2 |    2 |    4 |  0.7 |      0.6
       8 |       2 |        3 |   -6 |    4 |  0.3 |      1.3
       9 |       2 |        4 |    5 |   10 |    1 |      1.6
      10 |       2 |        5 |   10 |   12 |  0.6 |      2.6
      11 |       2 |        6 |   -3 |   12 |  0.4 |      3.2
      12 |       2 |        7 |   11 |   13 |    1 |      3.6
      13 |       2 |        8 |   12 |   15 |  0.6 |      4.6
      14 |       2 |        9 |   -2 |   15 |  0.4 |      5.2
      15 |       2 |       10 |    9 |    9 |    1 |      5.6
      16 |       2 |       11 |    6 |   -1 |    0 |      6.6
    (16 rows)

## Description of the Signatures

### Description of the edges_sql query for dijkstra like functions

edges_sql: | an SQL query, which should return a set of rows with the following columns:

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

### Description of the Points SQL query

points_sql: | an SQL query, which should return a set of rows with the following columns:

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

pid

`ANY-INTEGER`

(optional) Identifier of the point.

- If column present, it can not be NULL.
- If column not present, a sequential identifier will be given automatically.

edge_id | `ANY-INTEGER` | Identifier of the “closest” edge to the point.
fraction | `ANY-NUMERICAL` | Value in <0,1> that indicates the relative postition from the first end point of the edge.

side

`CHAR`

(optional) Value in [‘b’, ‘r’, ‘l’, NULL] indicating if the point is:

- In the right, left of the edge or
- If it doesn’t matter with ‘b’ or NULL.
- If column not present ‘b’ is considered.

Where:

ANY-INTEGER: | smallint, int, bigint
ANY-NUMERICAL: | smallint, int, bigint, real, float

### Description of the parameters of the signatures

Parameter | Type | Description
--- | --- | ---
edges_sql | `TEXT` | Edges SQL query as described above.
points_sql | `TEXT` | Points SQL query as described above.
start_pid | `ANY-INTEGER` | Starting point id.
end_pid | `ANY-INTEGER` | Ending point id.
K | `INTEGER` | Number of shortest paths.
directed | `BOOLEAN` | (optional). When `false` the graph is considered as Undirected. Default is `true` which considers the graph as Directed.
heap_paths | `BOOLEAN` | (optional). When `true` the paths calculated to get the shortests paths will be returned also. Default is `false` only the K shortest paths are returned.

driving_side

`CHAR`

(optional) Value in [‘b’, ‘r’, ‘l’, NULL] indicating if the driving side is:
  - In the right or left or
  - If it doesn’t matter with ‘b’ or NULL.
  - If column not present ‘b’ is considered.

details | `BOOLEAN` | (optional). When `true` the results will include the driving distance to the points with in the `distance`. Default is `false` which ignores other points of the points_sql.

### Description of the return values

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

Column | Type | Description
--- | --- | ---
seq | `INTEGER` | Row sequence.
path_seq | `INTEGER` | Relative position in the path of node and edge. Has value 1 for the beginning of a path.
path_id | `INTEGER` | Path identifier. The ordering of the paths: For two paths i, j if i < j then agg_cost(i) <= agg_cost(j).
node | `BIGINT` | Identifier of the node in the path. Negative values are the identifiers of a point.

edge

`BIGINT`

Identifier of the edge used to go from `node` to the next node in the path sequence.
  - `-1` for the last row in the path sequence.

cost

`FLOAT`

Cost to traverse from `node` using `edge` to the next `node` in the path sequence.
  - `0` for the last row in the path sequence.

agg_cost

`FLOAT`

Aggregate cost from `start_pid` to `node`.
  - `0` for the first row in the path sequence.

## Examples

Example: | Left side driving topology with details.

    SELECT * FROM pgr_withPointsKSP(
        'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
        'SELECT pid, edge_id, fraction, side from pointsOfInterest',
        -1, -2, 2,
        driving_side := 'l', details := true);
     seq | path_id | path_seq | node | edge | cost | agg_cost
    -----+---------+----------+------+------+------+----------
       1 |       1 |        1 |   -1 |    1 |  0.6 |        0
       2 |       1 |        2 |    2 |    4 |  0.7 |      0.6
       3 |       1 |        3 |   -6 |    4 |  0.3 |      1.3
       4 |       1 |        4 |    5 |    8 |    1 |      1.6
       5 |       1 |        5 |    6 |    9 |    1 |      2.6
       6 |       1 |        6 |    9 |   15 |    1 |      3.6
       7 |       1 |        7 |   12 |   15 |  0.6 |      4.6
       8 |       1 |        8 |   -2 |   -1 |    0 |      5.2
       9 |       2 |        1 |   -1 |    1 |  0.6 |        0
      10 |       2 |        2 |    2 |    4 |  0.7 |      0.6
      11 |       2 |        3 |   -6 |    4 |  0.3 |      1.3
      12 |       2 |        4 |    5 |    8 |    1 |      1.6
      13 |       2 |        5 |    6 |   11 |    1 |      2.6
      14 |       2 |        6 |   11 |   13 |    1 |      3.6
      15 |       2 |        7 |   12 |   15 |  0.6 |      4.6
      16 |       2 |        8 |   -2 |   -1 |    0 |      5.2
    (16 rows)

Example: | Right side driving topology with heap paths and details.

    SELECT * FROM pgr_withPointsKSP(
        'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
        'SELECT pid, edge_id, fraction, side from pointsOfInterest',
        -1, -2, 2,
        heap_paths := true, driving_side := 'r', details := true);
     seq | path_id | path_seq | node | edge | cost | agg_cost
    -----+---------+----------+------+------+------+----------
       1 |       1 |        1 |   -1 |    1 |  0.4 |        0
       2 |       1 |        2 |    1 |    1 |    1 |      0.4
       3 |       1 |        3 |    2 |    4 |  0.7 |      1.4
       4 |       1 |        4 |   -6 |    4 |  0.3 |      2.1
       5 |       1 |        5 |    5 |    8 |    1 |      2.4
       6 |       1 |        6 |    6 |    9 |    1 |      3.4
       7 |       1 |        7 |    9 |   15 |  0.4 |      4.4
       8 |       1 |        8 |   -2 |   -1 |    0 |      4.8
       9 |       2 |        1 |   -1 |    1 |  0.4 |        0
      10 |       2 |        2 |    1 |    1 |    1 |      0.4
      11 |       2 |        3 |    2 |    4 |  0.7 |      1.4
      12 |       2 |        4 |   -6 |    4 |  0.3 |      2.1
      13 |       2 |        5 |    5 |    8 |    1 |      2.4
      14 |       2 |        6 |    6 |   11 |    1 |      3.4
      15 |       2 |        7 |   11 |   13 |    1 |      4.4
      16 |       2 |        8 |   12 |   15 |    1 |      5.4
      17 |       2 |        9 |    9 |   15 |  0.4 |      6.4
      18 |       2 |       10 |   -2 |   -1 |    0 |      6.8
      19 |       3 |        1 |   -1 |    1 |  0.4 |        0
      20 |       3 |        2 |    1 |    1 |    1 |      0.4
      21 |       3 |        3 |    2 |    4 |  0.7 |      1.4
      22 |       3 |        4 |   -6 |    4 |  0.3 |      2.1
      23 |       3 |        5 |    5 |   10 |    1 |      2.4
      24 |       3 |        6 |   10 |   12 |  0.6 |      3.4
      25 |       3 |        7 |   -3 |   12 |  0.4 |        4
      26 |       3 |        8 |   11 |   13 |    1 |      4.4
      27 |       3 |        9 |   12 |   15 |    1 |      5.4
      28 |       3 |       10 |    9 |   15 |  0.4 |      6.4
      29 |       3 |       11 |   -2 |   -1 |    0 |      6.8
    (29 rows)

The queries use the Sample Data network.

History

- Proposed in version 2.2

## See Also

- withPoints - Family of functions

Indices and tables

- Index
- Search Page