pgr_vidsToDMatrix¶

Name¶

pgr_vidsToDMatrix - Creates a distances matrix from an array of vertex_id.

Warning

This is a proposed function

Is not officially in the release.
Name could change.
Signature could change.
Needs testing.
Functionality could change.

Synopsis¶

This function takes an array of vertex_id, the original array of points used to generate the array of vertex_id, an edge table name and a tol. It then computes kdijkstra() distances for each vertex to all the other vertices and creates a symmetric distance matrix suitable for TSP. The pnt array and the tol are used to establish a BBOX for limiting selection of edges. The extents of the points is expanded by tol.

The function returns:

record - with two fields as describe here

dmatrix: float8[] - the distance matrix suitable to pass to pgrTSP() function.

ids: integer[] - an array of ids for the distance matrix.

dmatrix:	`float8[]` - the distance matrix suitable to pass to pgrTSP() function.

ids:	`integer[]` - an array of ids for the distance matrix.

record pgr_vidsToDMatrix(IN vids integer[], IN pnts geometry[], IN edges text, tol float8 DEFAULT(0.1), OUT dmatrix double precision[], OUT ids integer[])

Description¶

Paramters

vids:	`integer[]` - An array of `vertex_id`.
pnts:	`geometry[]` - An array of point geometries that approximates the extents of the `vertex_id`.
edges:	`text` - The edge table to be used for the conversion.
tol:	`float8` - The amount to expand the BBOX extents of `pnts` when building the graph.

Warning

we compute a symmetric matrix because TSP requires that so the distances are better the Euclidean but but are not perfect
kdijkstra() can fail to find a path between some of the vertex ids. We to not detect this other than the cost might get set to -1.0, so the dmatrix shoule be checked for this as it makes it invalid for TSP

History

Proposed in version 2.1.0

Examples¶

This example uses existing data of points.

SELECT * FROM pgr_vidstodmatrix(
    ARRAY[1,2,3,5],
    ARRAY(select the_geom FROM edge_table_vertices_pgr WHERE id in (1,2,3,5)),
    'edge_table'
);
                  dmatrix                  |    ids    
-------------------------------------------+-----------
 {{0,1,4,2},{1,0,3,1},{4,3,0,2},{2,1,2,0}} | {1,2,3,5}
(1 row)

This example uses points that are not part of the graph.

pgr_textToPoints - is used to convert the locations into point geometries.
pgr_pointsToVids - to convert the array of point geometries into vertex ids.

SELECT * FROM pgr_vidstodmatrix(
    pgr_pointstovids(pgr_texttopoints('2,0;2,1;3,1;2,2', 0), 'edge_table'),
    pgr_texttopoints('2,0;2,1;3,1;2,2', 0),
    'edge_table');
                  dmatrix                  |    ids    
-------------------------------------------+-----------
 {{0,1,4,2},{1,0,3,1},{4,3,0,2},{2,1,2,0}} | {1,2,3,5}
(1 row)

This example shows how this can be used in the context of feeding the results into pgr_tsp() function.

SELECT * FROM pgr_tsp(
    (SELECT dMatrix FROM pgr_vidstodmatrix(
        pgr_pointstovids(pgr_texttopoints('2,0;2,1;3,1;2,2', 0), 'edge_table'),
        pgr_texttopoints('2,0;2,1;3,1;2,2', 0),
        'edge_table')
    ),
    1
);
 seq | id 
-----+----
   0 |  1
   1 |  2
   2 |  3
   3 |  0
(4 rows)

This example uses the Sample Data network.

pgRouting Manual (2.2)