# pgRouting Manual (3.6)

## pgr_trspVia - Proposed

# `pgr_trspVia` - Proposed

`pgr_trspVia` Route that goes through a list of vertices with restrictions.

Boost Graph Inside

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.

Availability

- Version 3.4.0

  - New proposed function:

    - `pgr_trspVia` (One Via)

## Description

Given a list of vertices and a graph, this function is equivalent to finding the shortest path between \(vertex_i\) and \(vertex_{i+1}\) for all \(i < size\_of(via\;vertices)\) trying not to use restricted paths.

The paths represents the sections of the route.

The general algorithm is as follows:

- Execute a pgr_dijkstraVia - Proposed.

- For the set of sub paths of the solution that pass through a restriction then

  - Execute the TRSP algorithm with restrictions for the paths.

  - NOTE when this is done, `U_turn_on_edge` flag is ignored.

## Signatures

### One Via

pgr_trspVia(Edges SQL, Restrictions SQL, via vertices, [options])
options: `[directed, strict, U_turn_on_edge]`
Returns set of `(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost, route_agg_cost)`
OR EMPTY SET

Example:

  Find the route that visits the vertices \(\{ 5, 1, 8\}\) in that order on an directed graph.

    SELECT * FROM pgr_trspVia(
      $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
      $$SELECT path, cost FROM restrictions$$,
      ARRAY[5, 1, 8]);
     seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
    -----+---------+----------+-----------+---------+------+------+------+----------+----------------
       1 |       1 |        1 |         5 |       1 |    5 |    1 |    1 |        0 |              0
       2 |       1 |        2 |         5 |       1 |    6 |    4 |    1 |        1 |              1
       3 |       1 |        3 |         5 |       1 |    7 |   10 |    1 |        2 |              2
       4 |       1 |        4 |         5 |       1 |    8 |   12 |    1 |        3 |              3
       5 |       1 |        5 |         5 |       1 |   12 |   13 |    1 |        4 |              4
       6 |       1 |        6 |         5 |       1 |   17 |   15 |    1 |        5 |              5
       7 |       1 |        7 |         5 |       1 |   16 |    9 |    1 |        6 |              6
       8 |       1 |        8 |         5 |       1 |   11 |    8 |    1 |        7 |              7
       9 |       1 |        9 |         5 |       1 |    7 |    7 |    1 |        8 |              8
      10 |       1 |       10 |         5 |       1 |    3 |    6 |    1 |        9 |              9
      11 |       1 |       11 |         5 |       1 |    1 |   -1 |    0 |       10 |             10
      12 |       2 |        1 |         1 |       8 |    1 |    6 |    1 |        0 |             10
      13 |       2 |        2 |         1 |       8 |    3 |    7 |    1 |        1 |             11
      14 |       2 |        3 |         1 |       8 |    7 |   10 |  101 |        2 |             12
      15 |       2 |        4 |         1 |       8 |    8 |   -2 |    0 |      103 |            113
    (15 rows)

## Parameters

Parameter | Type | Description
--- | --- | ---
Edges SQL | `TEXT` | Edges SQL query as described.
Restrictions SQL | `TEXT` | Restrictions SQL query as described.
via vertices | `ARRAY[` ANY-INTEGER `]` | Array of ordered vertices identifiers that are going to be visited.

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.

### Via optional parameters

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

`strict`

`BOOLEAN`

`false`

- When `true` if a path is missing stops and returns EMPTY SET

- When `false` ignores missing paths returning all paths found

`U_turn_on_edge`

`BOOLEAN`

`true`

- When `true` departing from a visited vertex will not try to avoid

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

Column | Type | Description
--- | --- | ---
`seq` | `INTEGER` | Sequential value starting from 1.
`path_id` | `INTEGER` | Identifier of a path. Has value 1 for the first path.
`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 of the path.
`end_vid` | `BIGINT` | Identifier of the ending vertex of the path.
`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.

- -2 for the last node of the route.

`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`.
`route_agg_cost` | `FLOAT` | Total cost from `start_vid` of `seq = 1` to `end_vid` of the current `seq`.

## Additional Examples

All this examples are about the route that visits the vertices \(\{5, 7, 1, 8, 15\}\) in that order on a directed graph.

### The main query

    SELECT * FROM pgr_trspVia(
      $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
      $$SELECT path, cost FROM restrictions$$,
      ARRAY[5, 7, 1, 8, 15]);
     seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
    -----+---------+----------+-----------+---------+------+------+------+----------+----------------
       1 |       1 |        1 |         5 |       7 |    5 |    1 |    1 |        0 |              0
       2 |       1 |        2 |         5 |       7 |    6 |    4 |    1 |        1 |              1
       3 |       1 |        3 |         5 |       7 |    7 |   -1 |    0 |        2 |              2
       4 |       2 |        1 |         7 |       1 |    7 |    7 |    1 |        0 |              2
       5 |       2 |        2 |         7 |       1 |    3 |    6 |    1 |        1 |              3
       6 |       2 |        3 |         7 |       1 |    1 |   -1 |    0 |        2 |              4
       7 |       3 |        1 |         1 |       8 |    1 |    6 |    1 |        0 |              4
       8 |       3 |        2 |         1 |       8 |    3 |    7 |    1 |        1 |              5
       9 |       3 |        3 |         1 |       8 |    7 |   10 |  101 |        2 |              6
      10 |       3 |        4 |         1 |       8 |    8 |   -1 |    0 |      103 |            107
      11 |       4 |        1 |         8 |      15 |    8 |   12 |    1 |        0 |            107
      12 |       4 |        2 |         8 |      15 |   12 |   13 |    1 |        1 |            108
      13 |       4 |        3 |         8 |      15 |   17 |   15 |    1 |        2 |            109
      14 |       4 |        4 |         8 |      15 |   16 |   16 |    1 |        3 |            110
      15 |       4 |        5 |         8 |      15 |   15 |   -2 |    0 |        4 |            111
    (15 rows)

#### Aggregate cost of the third path.

    SELECT agg_cost FROM pgr_trspVia(
      $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
      $$SELECT path, cost FROM restrictions$$,
      ARRAY[5, 7, 1, 8, 15])
    WHERE path_id = 3 AND edge < 0;
     agg_cost
    ----------
          103
    (1 row)

#### Route’s aggregate cost of the route at the end of the third path.

    SELECT route_agg_cost FROM pgr_trspVia(
      $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
      $$SELECT path, cost FROM restrictions$$,
      ARRAY[5, 7, 1, 8, 15])
    WHERE path_id = 3 AND edge < 0;
     route_agg_cost
    ----------------
                107
    (1 row)

#### Nodes visited in the route.

    SELECT row_number() over () as node_seq, node
    FROM pgr_trspVia(
      $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
      $$SELECT path, cost FROM restrictions$$,
      ARRAY[5, 7, 1, 8, 15])
    WHERE edge <> -1 ORDER BY seq;
     node_seq | node
    ----------+------
            1 |    5
            2 |    6
            3 |    7
            4 |    3
            5 |    1
            6 |    3
            7 |    7
            8 |    8
            9 |   12
           10 |   17
           11 |   16
           12 |   15
    (12 rows)

#### The aggregate costs of the route when the visited vertices are reached.

    SELECT path_id, route_agg_cost FROM pgr_trspVia(
      $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
      $$SELECT path, cost FROM restrictions$$,
      ARRAY[5, 7, 1, 8, 15])
    WHERE edge < 0;
     path_id | route_agg_cost
    ---------+----------------
           1 |              2
           2 |              4
           3 |            107
           4 |            111
    (4 rows)

#### Status of “passes in front” or “visits” of the nodes.

    SELECT seq, route_agg_cost, node, agg_cost ,
    CASE WHEN edge = -1 THEN $$visits$$
    ELSE $$passes in front$$
    END as status
    FROM pgr_trspVia(
      $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
      $$SELECT path, cost FROM restrictions$$,
      ARRAY[5, 7, 1, 8, 15])
    WHERE agg_cost <> 0 or seq = 1;
     seq | route_agg_cost | node | agg_cost |     status
    -----+----------------+------+----------+-----------------
       1 |              0 |    5 |        0 | passes in front
       2 |              1 |    6 |        1 | passes in front
       3 |              2 |    7 |        2 | visits
       5 |              3 |    3 |        1 | passes in front
       6 |              4 |    1 |        2 | visits
       8 |              5 |    3 |        1 | passes in front
       9 |              6 |    7 |        2 | passes in front
      10 |            107 |    8 |      103 | visits
      12 |            108 |   12 |        1 | passes in front
      13 |            109 |   17 |        2 | passes in front
      14 |            110 |   16 |        3 | passes in front
      15 |            111 |   15 |        4 | passes in front
    (12 rows)

### Simulation of how algorithm works.

The algorithm performs a pgr_dijkstraVia - Proposed

    SELECT * FROM pgr_dijkstraVia(
      $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
      ARRAY[6, 3, 6]);
     seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
    -----+---------+----------+-----------+---------+------+------+------+----------+----------------
       1 |       1 |        1 |         6 |       3 |    6 |    4 |    1 |        0 |              0
       2 |       1 |        2 |         6 |       3 |    7 |    7 |    1 |        1 |              1
       3 |       1 |        3 |         6 |       3 |    3 |   -1 |    0 |        2 |              2
       4 |       2 |        1 |         3 |       6 |    3 |    7 |    1 |        0 |              2
       5 |       2 |        2 |         3 |       6 |    7 |    4 |    1 |        1 |              3
       6 |       2 |        3 |         3 |       6 |    6 |   -2 |    0 |        2 |              4
    (6 rows)

Detects which of the sub paths pass through a restriction in this case is for the `path_id = 5` from `6` to `3` because the path \(15 \rightarrow 1\) is restricted.

Executes the pgr_trsp - Proposed algorithm for the conflicting paths.

    SELECT 1 AS path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost FROM pgr_trsp(
      $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
      $$SELECT path, cost FROM restrictions$$,
      6, 3);
     path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
    ---------+----------+-----------+---------+------+------+------+----------
           1 |        1 |         6 |       3 |    6 |    4 |    1 |        0
           1 |        2 |         6 |       3 |    7 |   10 |    1 |        1
           1 |        3 |         6 |       3 |    8 |   12 |    1 |        2
           1 |        4 |         6 |       3 |   12 |   13 |    1 |        3
           1 |        5 |         6 |       3 |   17 |   15 |    1 |        4
           1 |        6 |         6 |       3 |   16 |    9 |    1 |        5
           1 |        7 |         6 |       3 |   11 |    8 |    1 |        6
           1 |        8 |         6 |       3 |    7 |    7 |    1 |        7
           1 |        9 |         6 |       3 |    3 |   -1 |    0 |        8
    (9 rows)

From the pgr_dijkstraVia - Proposed result it removes the conflicting paths and builds the solution with the results of the pgr_trsp - Proposed algorithm:

    WITH
    solutions AS (
      SELECT path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost FROM pgr_dijkstraVia(
        $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
        ARRAY[6, 3, 6]) WHERE path_id != 1
      UNION
      SELECT 1 AS path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost FROM pgr_trsp(
        $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
        $$SELECT path, cost FROM restrictions$$,
        6, 3)),
    with_seq AS (
      SELECT row_number() over(ORDER BY path_id, path_seq) AS seq, *
      FROM solutions),
    aggregation AS (SELECT seq, SUM(cost) OVER(ORDER BY seq) AS route_agg_cost FROM with_seq)
    SELECT with_seq.*, COALESCE(route_agg_cost, 0) AS route_agg_cost
    FROM with_seq LEFT JOIN aggregation ON (with_seq.seq = aggregation.seq + 1);
     seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
    -----+---------+----------+-----------+---------+------+------+------+----------+----------------
       1 |       1 |        1 |         6 |       3 |    6 |    4 |    1 |        0 |              0
       2 |       1 |        2 |         6 |       3 |    7 |   10 |    1 |        1 |              1
       3 |       1 |        3 |         6 |       3 |    8 |   12 |    1 |        2 |              2
       4 |       1 |        4 |         6 |       3 |   12 |   13 |    1 |        3 |              3
       5 |       1 |        5 |         6 |       3 |   17 |   15 |    1 |        4 |              4
       6 |       1 |        6 |         6 |       3 |   16 |    9 |    1 |        5 |              5
       7 |       1 |        7 |         6 |       3 |   11 |    8 |    1 |        6 |              6
       8 |       1 |        8 |         6 |       3 |    7 |    7 |    1 |        7 |              7
       9 |       1 |        9 |         6 |       3 |    3 |   -1 |    0 |        8 |              8
      10 |       2 |        1 |         3 |       6 |    3 |    7 |    1 |        0 |              8
      11 |       2 |        2 |         3 |       6 |    7 |    4 |    1 |        1 |              9
      12 |       2 |        3 |         3 |       6 |    6 |   -2 |    0 |        2 |             10
    (12 rows)

Getting the same result as `pgr_trspVia`:

    SELECT * FROM pgr_trspVia(
      $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
      $$SELECT path, cost FROM restrictions$$,
      ARRAY[6, 3, 6]);
     seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
    -----+---------+----------+-----------+---------+------+------+------+----------+----------------
       1 |       1 |        1 |         6 |       3 |    6 |    4 |    1 |        0 |              0
       2 |       1 |        2 |         6 |       3 |    7 |   10 |    1 |        1 |              1
       3 |       1 |        3 |         6 |       3 |    8 |   12 |    1 |        2 |              2
       4 |       1 |        4 |         6 |       3 |   12 |   13 |    1 |        3 |              3
       5 |       1 |        5 |         6 |       3 |   17 |   15 |    1 |        4 |              4
       6 |       1 |        6 |         6 |       3 |   16 |    9 |    1 |        5 |              5
       7 |       1 |        7 |         6 |       3 |   11 |    8 |    1 |        6 |              6
       8 |       1 |        8 |         6 |       3 |    7 |    7 |    1 |        7 |              7
       9 |       1 |        9 |         6 |       3 |    3 |   -1 |    0 |        8 |              8
      10 |       2 |        1 |         3 |       6 |    3 |    7 |    1 |        0 |              8
      11 |       2 |        2 |         3 |       6 |    7 |    4 |    1 |        1 |              9
      12 |       2 |        3 |         3 |       6 |    6 |   -2 |    0 |        2 |             10
    (12 rows)

Example 8:

  Sometimes `U_turn_on_edge` flag is ignored when is set to `false`.

The first step, doing a pgr_dijkstraVia - Proposed does consider not making a U turn on the same edge. But the path \(16 \rightarrow 13\) (Rows 4 and 5) is restricted and the result is using it.

    SELECT * FROM pgr_dijkstraVia(
        $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
        ARRAY[6, 7, 6], U_turn_on_edge => false);
     seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
    -----+---------+----------+-----------+---------+------+------+------+----------+----------------
       1 |       1 |        1 |         6 |       7 |    6 |    4 |    1 |        0 |              0
       2 |       1 |        2 |         6 |       7 |    7 |   -1 |    0 |        1 |              1
       3 |       2 |        1 |         7 |       6 |    7 |    8 |    1 |        0 |              1
       4 |       2 |        2 |         7 |       6 |   11 |    9 |    1 |        1 |              2
       5 |       2 |        3 |         7 |       6 |   16 |   16 |    1 |        2 |              3
       6 |       2 |        4 |         7 |       6 |   15 |    3 |    1 |        3 |              4
       7 |       2 |        5 |         7 |       6 |   10 |    2 |    1 |        4 |              5
       8 |       2 |        6 |         7 |       6 |    6 |   -2 |    0 |        5 |              6
    (8 rows)

When executing the pgr_trsp - Proposed algorithm for the conflicting path, there is no `U_turn_on_edge` flag.

    SELECT 1 AS path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost FROM pgr_trsp(
      $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
      $$SELECT path, cost FROM restrictions$$,
      7, 6);
     path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
    ---------+----------+-----------+---------+------+------+------+----------
           1 |        1 |         7 |       6 |    7 |    4 |    1 |        0
           1 |        2 |         7 |       6 |    6 |   -1 |    0 |        1
    (2 rows)

Therefore the result ignores the `U_turn_on_edge` flag when set to `false`.

    SELECT * FROM pgr_trspVia(
      $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
      $$SELECT path, cost FROM restrictions$$,
      ARRAY[6, 7, 6], U_turn_on_edge => false);
     seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
    -----+---------+----------+-----------+---------+------+------+------+----------+----------------
       1 |       1 |        1 |         6 |       7 |    6 |    4 |    1 |        0 |              0
       2 |       1 |        2 |         6 |       7 |    7 |   -1 |    0 |        1 |              1
       3 |       2 |        1 |         7 |       6 |    7 |    4 |    1 |        0 |              1
       4 |       2 |        2 |         7 |       6 |    6 |   -2 |    0 |        1 |              2
    (4 rows)

## See Also

- Via - Category

- Sample Data network.

Indices and tables

- Index

- Search Page