# pgRouting Manual (3.6)

## pgr_withPointsCostMatrix - proposed

# `pgr_withPointsCostMatrix` - proposed

`pgr_withPointsCostMatrix` - Calculates a cost matrix using pgr_withPoints - Proposed.

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

- Version 2.2.0

  - New proposed function

## Description

Using Dijkstra algorithm, calculate and return a cost matrix.

Dijkstra’s algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956. It is a graph search algorithm that solves the shortest path problem for a graph with non-negative edge path costs, producing a shortest path from a starting vertex to an ending vertex. This implementation can be used with a directed graph and an undirected graph.

The main Characteristics are:

- Can be used as input to pgr_TSP.

  - Use directly when the resulting matrix is symmetric and there is no \(\infty\) value.

  - It will be the users responsibility to make the matrix symmetric.

    - By using geometric or harmonic average of the non symmetric values.

    - By using max or min the non symmetric values.

    - By setting the upper triangle to be the mirror image of the lower triangle.

    - By setting the lower triangle to be the mirror image of the upper triangle.

  - It is also the users responsibility to fix an \(\infty\) value.

- Each function works as part of the family it belongs to.

- It does not return a path.

- Returns the sum of the costs of the shortest path for pair combination of nodes in the graph.

- Process is done only on edges with positive costs.

- Values are returned when there is a path.

  - When the starting vertex and ending vertex are the same, there is no path.

    - The aggregate cost in the non included values (v, v) is 0.

  - When the starting vertex and ending vertex are the different and there is no path.

    - The aggregate cost in the non included values (u, v) is \(\infty\).

- Let be the case the values returned are stored in a table:

  - The unique index would be the pair: `(start_vid, end_vid)`.

- Depending on the function and its parameters, the results can be symmetric.

  - The aggregate cost of (u, v) is the same as for (v, u).

- Any duplicated value in the start vids are ignored.

- The returned values are ordered:

  - `start_vid` ascending

  - `end_vid` ascending

## Signatures

Summary

pgr_withPointsCostMatrix(Edges SQL, Points SQL, start vids, [options])
options: `[directed, driving_side]`
Returns set of `(start_vid, end_vid, agg_cost)`
OR EMPTY SET

Note

There is no details flag, unlike the other members of the withPoints family of functions.

Example:

  Cost matrix for points \(\{1, 6\}\) and vertices \(\{10, 11\}\) on an undirected graph

- Returning a symmetrical cost matrix

- Using the default `side` value on the points_sql query

- Using the default `driving_side` value

    SELECT * FROM pgr_withPointsCostMatrix(
      'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
      'SELECT pid, edge_id, fraction from pointsOfInterest',
      array[-1, 10, 11, -6], directed := false);
     start_vid | end_vid | agg_cost
    -----------+---------+----------
            -6 |      -1 |      1.3
            -6 |      10 |      1.7
            -6 |      11 |      1.3
            -1 |      -6 |      1.3
            -1 |      10 |      1.6
            -1 |      11 |      2.6
            10 |      -6 |      1.7
            10 |      -1 |      1.6
            10 |      11 |        1
            11 |      -6 |      1.3
            11 |      -1 |      2.6
            11 |      10 |        1
    (12 rows)

## Parameters

Column | Type | Description
--- | --- | ---
Edges SQL | `TEXT` | Edges SQL as described below
Points SQL | `TEXT` | Points SQL as described below
start vids | `ARRAY[BIGINT]` | Array of identifiers of starting vertices.

### Optional parameters

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

`directed`

`BOOLEAN`

`true`

- When `true` the graph is considered Directed

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

### With points optional parameters

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

`driving_side`

`CHAR`

`b`

Value in [`r`, `l`, `b`] indicating if the driving side is:

- `r` for right driving side.

- `l` for left driving side.

- `b` for both.

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

### Points SQL

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

`pid`

ANY-INTEGER

value

Identifier of the point.

- Use with positive value, as internally will be converted to negative value

- If column is present, it can not be NULL.

- If column is not present, a sequential negative value 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`

`b`

Value in [`b`, `r`, `l`, `NULL`] indicating if the point is:

- In the right `r`,

- In the left `l`,

- In both sides `b`, `NULL`

Where:

ANY-INTEGER:

  `SMALLINT`, `INTEGER`, `BIGINT`

ANY-NUMERICAL:

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

## Result columns

Set of `(start_vid, end_vid, agg_cost)`

Column | Type | Description
--- | --- | ---
`start_vid` | `BIGINT` | Identifier of the starting vertex.
`end_vid` | `BIGINT` | Identifier of the ending vertex.
`agg_cost` | `FLOAT` | Aggregate cost from `start_vid` to `end_vid`.

Note

When start_vid or end_vid columns have negative values, the identifier is for a Point.

## Additional Examples

### Use pgr_findCloseEdges in the Points SQL.

Find the matrix cost of the routes from vertex \(1\) and the two closest locations on the graph of point (2.9, 1.8).

    SELECT * FROM pgr_withPointsCostMatrix(
      $e$ SELECT * FROM edges $e$,
      $p$ SELECT edge_id, round(fraction::numeric, 2) AS fraction, side
          FROM pgr_findCloseEdges(
            $$SELECT id, geom FROM edges$$,
            (SELECT ST_POINT(2.9, 1.8)),
            0.5, cap => 2)
      $p$,
      ARRAY[5, 10, -1, -2]);
     start_vid | end_vid | agg_cost
    -----------+---------+----------
            -2 |      -1 |      3.9
            -2 |       5 |      2.9
            -2 |      10 |      3.1
            -1 |      -2 |      0.3
            -1 |       5 |      3.2
            -1 |      10 |      3.2
             5 |      -2 |      2.9
             5 |      -1 |      6.8
             5 |      10 |        6
            10 |      -2 |      1.1
            10 |      -1 |      0.8
            10 |       5 |        2
    (12 rows)

- Point \(-1\) corresponds to the closest edge from point (2.9, 1.8).

- Point \(-2\) corresponds to the next close edge from point (2.9, 1.8).

### Use with pgr_TSP.

    SELECT * FROM pgr_TSP(
      $$
      SELECT * FROM pgr_withPointsCostMatrix(
        'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
        'SELECT pid, edge_id, fraction from pointsOfInterest',
        array[-1, 10, 11, -6], directed := false);
      $$
    );
    NOTICE:  pgr_TSP no longer solving with simulated annaeling
    HINT:  Ignoring annaeling parameters
     seq | node | cost | agg_cost
    -----+------+------+----------
       1 |   -6 |    0 |        0
       2 |   -1 |  1.3 |      1.3
       3 |   10 |  1.6 |      2.9
       4 |   11 |    1 |      3.9
       5 |   -6 |  1.3 |      5.2
    (5 rows)

## See Also

- withPoints - Family of functions

- Cost Matrix - Category

- Traveling Sales Person - Family of functions

- Sample Data

Indices and tables

- Index

- Search Page