pgr_drivingDistance

pgr_drivingDistance - Returns the driving distance from a start node.

_images/boost-inside.jpeg

Boost Graph Inside

Availability

  • Version 2.1.0:

    • Signature change pgr_drivingDistance(single vertex)

    • New Official pgr_drivingDistance(multiple vertices)

  • Version 2.0.0:

    • Official pgr_drivingDistance(single vertex)

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, [options])
options: [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, path_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, [options])
options: [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