pgr_drivingDistance

pgr_drivingDistance - Returns the driving distance from a start node.

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

• pgr_alphaShape - Alpha shape computation

• Sample Data network.

Indices and tables

• Index

• Search Page