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