pgr_drivingDistance

pgr_drivingDistance - Returns the driving distance from a start node.

_images/boost-inside.jpeg

Boost Graph Inside

Availability

Description

Using the Dijkstra algorithm, extracts all the nodes that have costs less than or equal to the value distance. The edges extracted will conform to the corresponding spanning tree.

Signatures

pgr_drivingDistance(Edges SQL, Root vid,  distance
           [, directed])
pgr_drivingDistance(Edges SQL, Root vids, distance
           [, directed] [, equicost])
RETURNS SET OF (seq, [from_v,] node, edge, cost, agg_cost)

Single Vertex

pgr_drivingDistance(Edges SQL, Root vid,  distance
           [, directed])
RETURNS SET OF (seq, node, edge, cost, agg_cost)
Example:From vertex \(11\) for a distance of \(3.0\) 
SELECT * FROM pgr_drivingDistance(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  11, 3.0);
 seq | node | edge | cost | agg_cost
-----+------+------+------+----------
   1 |   11 |   -1 |    0 |        0
   2 |    7 |    8 |    1 |        1
   3 |   12 |   11 |    1 |        1
   4 |   16 |    9 |    1 |        1
   5 |    3 |    7 |    1 |        2
   6 |    6 |    4 |    1 |        2
   7 |    8 |   10 |    1 |        2
   8 |   15 |   16 |    1 |        2
   9 |   17 |   15 |    1 |        2
  10 |    1 |    6 |    1 |        3
  11 |    5 |    1 |    1 |        3
  12 |    9 |   14 |    1 |        3
  13 |   10 |    3 |    1 |        3
(13 rows)

Multiple Vertices

pgr_drivingDistance(Edges SQL, Root vids, distance
           [, directed] [, equicost])
RETURNS SET OF (seq, from_v, node, edge, cost, agg_cost)
Example:From vertices \(\{11, 16\}\) for a distance of \(3.0\) with equi-cost on a directed graph 
SELECT * FROM pgr_drivingDistance(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  array[11, 16], 3.0, equicost => true);
 seq | from_v | node | edge | cost | agg_cost
-----+--------+------+------+------+----------
   1 |     11 |   11 |   -1 |    0 |        0
   2 |     11 |    7 |    8 |    1 |        1
   3 |     11 |   12 |   11 |    1 |        1
   4 |     11 |    3 |    7 |    1 |        2
   5 |     11 |    6 |    4 |    1 |        2
   6 |     11 |    8 |   10 |    1 |        2
   7 |     11 |    1 |    6 |    1 |        3
   8 |     11 |    5 |    1 |    1 |        3
   9 |     11 |    9 |   14 |    1 |        3
  10 |     16 |   16 |   -1 |    0 |        0
  11 |     16 |   15 |   16 |    1 |        1
  12 |     16 |   17 |   15 |    1 |        1
  13 |     16 |   10 |    3 |    1 |        2
(13 rows)

Parameters

Parameter Type Description
Edges SQL TEXT Edges SQL as described below.
Root vid BIGINT Identifier of the root vertex of the tree.
Root vids ARRAY[ANY-INTEGER]

Array of identifiers of the root vertices.

  • \(0\) values are ignored
  • For optimization purposes, any duplicated value is ignored.
distance FLOAT Upper limit for the inclusion of a node in the result.

Where:

ANY-INTEGER:SMALLINT, INTEGER, BIGINT
ANY-NUMERIC:SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Optional parameters

Column Type Default Description
directed BOOLEAN true
  • When true the graph is considered Directed
  • When false the graph is considered as Undirected.

Driving distance optional parameters

Column Type Default Description
equicost BOOLEAN true
  • When true the node will only appear in the closest from_v list.
  • When false which resembles several calls using the single starting point signatures. Tie brakes are arbitrary.

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

Result Columns

Returns SET OF (seq, from_v, node, edge, cost, agg_cost)

Parameter Type Description
seq BIGINT Sequential value starting from \(1\).
[from_v] BIGINT Identifier of the root vertex.
node BIGINT Identifier of node within the limits from from_v.
edge BIGINT

Identifier of the edge used to arrive to node.

  • \(0\) when node = from_v.
cost FLOAT Cost to traverse edge.
agg_cost FLOAT Aggregate cost from from_v to node.

Where:

ANY-INTEGER:SMALLINT, INTEGER, BIGINT
ANY-NUMERIC:SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC

Additional Examples

Example:From vertices \(\{11, 16\}\) for a distance of \(3.0\) on an undirected graph 
SELECT * FROM pgr_drivingDistance(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  array[11, 16], 3.0, directed => false);
 seq | from_v | node | edge | cost | agg_cost
-----+--------+------+------+------+----------
   1 |     11 |   11 |   -1 |    0 |        0
   2 |     11 |    7 |    8 |    1 |        1
   3 |     11 |   10 |    5 |    1 |        1
   4 |     11 |   12 |   11 |    1 |        1
   5 |     11 |   16 |    9 |    1 |        1
   6 |     11 |    3 |    7 |    1 |        2
   7 |     11 |    6 |    2 |    1 |        2
   8 |     11 |    8 |   10 |    1 |        2
   9 |     11 |   15 |    3 |    1 |        2
  10 |     11 |   17 |   15 |    1 |        2
  11 |     11 |    1 |    6 |    1 |        3
  12 |     11 |    5 |    1 |    1 |        3
  13 |     11 |    9 |   14 |    1 |        3
  14 |     16 |   16 |   -1 |    0 |        0
  15 |     16 |   11 |    9 |    1 |        1
  16 |     16 |   15 |   16 |    1 |        1
  17 |     16 |   17 |   15 |    1 |        1
  18 |     16 |    7 |    8 |    1 |        2
  19 |     16 |   10 |    5 |    1 |        2
  20 |     16 |   12 |   13 |    1 |        2
  21 |     16 |    3 |    7 |    1 |        3
  22 |     16 |    6 |    4 |    1 |        3
  23 |     16 |    8 |   10 |    1 |        3
(23 rows)

See Also

Indices and tables