pgr_withPointsCostMatrix - proposed - pgRouting Manual (3.4)

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

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

Inner Queries

Result Columns

Set of (start_vid, end_vid, agg_cost)

Additional Examples

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)

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