pgr_drivingDistance

pgr_drivingDistance - Returns the driving distance from a start node.

_images/boost-inside.jpeg

Boost Graph Inside

Availability

Version 3.6.0

  • Standarizing output columns to (seq, depth, start_vid, pred, node, edge, cost, agg_cost)

    • pgr_drivingdistance (Single vertex)

      • Added depth and start_vid result columns.

    • pgr_drivingdistance (Multiple vertices)

      • Result column name change: from_v to start_vid.

      • Added depth and pred result columns.

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 spaning 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, depth, start_vid, pred, node, edge, cost, agg_cost)

Single Vertex

pgr_drivingDistance(Edges SQL, Root vid, distance, [directed])
Returns set of (seq, depth, start_vid, pred, 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 | depth | start_vid | pred | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+------+----------
   1 |     0 |        11 |   11 |   11 |   -1 |    0 |        0
   2 |     1 |        11 |   11 |    7 |    8 |    1 |        1
   3 |     1 |        11 |   11 |   12 |   11 |    1 |        1
   4 |     1 |        11 |   11 |   16 |    9 |    1 |        1
   5 |     2 |        11 |    7 |    3 |    7 |    1 |        2
   6 |     2 |        11 |    7 |    6 |    4 |    1 |        2
   7 |     2 |        11 |    7 |    8 |   10 |    1 |        2
   8 |     2 |        11 |   16 |   15 |   16 |    1 |        2
   9 |     2 |        11 |   16 |   17 |   15 |    1 |        2
  10 |     3 |        11 |    3 |    1 |    6 |    1 |        3
  11 |     3 |        11 |    6 |    5 |    1 |    1 |        3
  12 |     3 |        11 |    8 |    9 |   14 |    1 |        3
  13 |     3 |        11 |   15 |   10 |    3 |    1 |        3
(13 rows)

Multiple Vertices

pgr_drivingDistance(Edges SQL, Root vids, distance, [options])
options: [directed, equicost]
Returns set of (seq, depth, start_vid, pred, 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 | depth | start_vid | pred | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+------+----------
   1 |     0 |        11 |   11 |   11 |   -1 |    0 |        0
   2 |     1 |        11 |   11 |    7 |    8 |    1 |        1
   3 |     1 |        11 |   11 |   12 |   11 |    1 |        1
   4 |     2 |        11 |    7 |    3 |    7 |    1 |        2
   5 |     2 |        11 |    7 |    6 |    4 |    1 |        2
   6 |     2 |        11 |    7 |    8 |   10 |    1 |        2
   7 |     3 |        11 |    3 |    1 |    6 |    1 |        3
   8 |     3 |        11 |    6 |    5 |    1 |    1 |        3
   9 |     3 |        11 |    8 |    9 |   14 |    1 |        3
  10 |     0 |        16 |   16 |   16 |   -1 |    0 |        0
  11 |     1 |        16 |   16 |   15 |   16 |    1 |        1
  12 |     1 |        16 |   16 |   17 |   15 |    1 |        1
  13 |     2 |        16 |   15 |   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-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 start_vid list. Tie brakes are arbitrary.

  • When false which resembles several calls using the single vertex signature.

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, depth, start_vid, pred, node, edge, cost, agg_cost)

Parameter

Type

Description

seq

BIGINT

Sequential value starting from \(1\).

depth

BIGINT

Depth of the node.

  • \(0\) when node = start_vid.

  • \(depth-1\) is the depth of pred

start_vid

BIGINT

Identifier of the root vertex.

pred

BIGINT

Predecessor of node.

  • When node = start_vid then has the value node.

node

BIGINT

Identifier of node reached using edge.

edge

BIGINT

Identifier of the edge used to arrive from pred to node.

  • \(-1\) when node = start_vid.

cost

FLOAT

Cost to traverse edge.

agg_cost

FLOAT

Aggregate cost from start_vid to node.

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 | depth | start_vid | pred | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+------+----------
   1 |     0 |        11 |   11 |   11 |   -1 |    0 |        0
   2 |     1 |        11 |   11 |    7 |    8 |    1 |        1
   3 |     1 |        11 |   11 |   10 |    5 |    1 |        1
   4 |     1 |        11 |   11 |   12 |   11 |    1 |        1
   5 |     1 |        11 |   11 |   16 |    9 |    1 |        1
   6 |     2 |        11 |    7 |    3 |    7 |    1 |        2
   7 |     2 |        11 |   10 |    6 |    2 |    1 |        2
   8 |     2 |        11 |    7 |    8 |   10 |    1 |        2
   9 |     2 |        11 |   10 |   15 |    3 |    1 |        2
  10 |     2 |        11 |   16 |   17 |   15 |    1 |        2
  11 |     3 |        11 |    3 |    1 |    6 |    1 |        3
  12 |     3 |        11 |    6 |    5 |    1 |    1 |        3
  13 |     3 |        11 |    8 |    9 |   14 |    1 |        3
  14 |     0 |        16 |   16 |   16 |   -1 |    0 |        0
  15 |     1 |        16 |   16 |   11 |    9 |    1 |        1
  16 |     1 |        16 |   16 |   15 |   16 |    1 |        1
  17 |     1 |        16 |   16 |   17 |   15 |    1 |        1
  18 |     2 |        16 |   11 |    7 |    8 |    1 |        2
  19 |     2 |        16 |   11 |   10 |    5 |    1 |        2
  20 |     2 |        16 |   17 |   12 |   13 |    1 |        2
  21 |     3 |        16 |    7 |    3 |    7 |    1 |        3
  22 |     3 |        16 |    7 |    6 |    4 |    1 |        3
  23 |     3 |        16 |    7 |    8 |   10 |    1 |        3
(23 rows)

See Also

Indices and tables