pgr_depthFirstSearch - Proposed - pgRouting Manual (3.4)

Description

Depth First Search algorithm is a traversal algorithm which starts from a root vertex, goes as deep as possible, and backtracks once a vertex is reached with no adjacent vertices or with all visited adjacent vertices. The traversal continues until all the vertices reachable from the root vertex are visited.

The main Characteristics are:

• The implementation works for both directed and undirected graphs.

• Provides the Depth First Search traversal order from a root vertex or from a set of root vertices.

• An optional non-negative maximum depth parameter to limit the results up to a particular depth.

• For optimization purposes, any duplicated values in the Root vids are ignored.

• It does not produce the shortest path from a root vertex to a target vertex.

• The aggregate cost of traversal is not guaranteed to be minimal.

• The returned values are ordered in ascending order of start_vid .

• Depth First Search Running time: \(O(E + V)\)

Signatures

Summary

SELECT * FROM pgr_depthFirstSearch(
  'SELECT id, source, target, cost, reverse_cost FROM edges
  ORDER BY id',
  6);
 seq  depth  start_vid  node  edge  cost  agg_cost
-----+-------+-----------+------+------+------+----------
   1      0          6     6    -1     0         0
   2      1          6     5     1     1         1
   3      1          6     7     4     1         1
   4      2          6     3     7     1         2
   5      3          6     1     6     1         3
   6      2          6    11     8     1         2
   7      3          6    16     9     1         3
   8      4          6    17    15     1         4
   9      4          6    15    16     1         4
  10      5          6    10     3     1         5
  11      3          6    12    11     1         3
  12      2          6     8    10     1         2
  13      3          6     9    14     1         3
(13 rows)

SELECT * FROM pgr_depthFirstSearch(
  'SELECT id, source, target, cost, reverse_cost FROM edges
  ORDER BY id',
  ARRAY[12, 6], directed => false, max_depth => 2);
 seq  depth  start_vid  node  edge  cost  agg_cost
-----+-------+-----------+------+------+------+----------
   1      0          6     6    -1     0         0
   2      1          6     5     1     1         1
   3      1          6    10     2     1         1
   4      2          6    15     3     1         2
   5      2          6    11     5     1         2
   6      1          6     7     4     1         1
   7      2          6     3     7     1         2
   8      2          6     8    10     1         2
   9      0         12    12    -1     0         0
  10      1         12    11    11     1         1
  11      2         12    10     5     1         2
  12      2         12     7     8     1         2
  13      2         12    16     9     1         2
  14      1         12     8    12     1         1
  15      2         12     9    14     1         2
  16      1         12    17    13     1         1
(16 rows)

Parameters

Where:

ANY-INTEGER :

SMALLINT, INTEGER, BIGINT

ANY-NUMERIC :

SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC

Inner Queries

Return columns

Returns SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)

Where:

ANY-INTEGER :

SMALLINT, INTEGER, BIGINT

ANY-NUMERIC :

SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC

Additional Examples

Example :

Same as Single vertex but with edges in descending order of id .

SELECT * FROM pgr_depthFirstSearch(
  'SELECT id, source, target, cost, reverse_cost FROM edges
  ORDER BY id DESC',
  6);
 seq  depth  start_vid  node  edge  cost  agg_cost
-----+-------+-----------+------+------+------+----------
   1      0          6     6    -1     0         0
   2      1          6     7     4     1         1
   3      2          6     8    10     1         2
   4      3          6     9    14     1         3
   5      3          6    12    12     1         3
   6      4          6    17    13     1         4
   7      5          6    16    15     1         5
   8      6          6    15    16     1         6
   9      7          6    10     3     1         7
  10      8          6    11     5     1         8
  11      2          6     3     7     1         2
  12      3          6     1     6     1         3
  13      1          6     5     1     1         1
(13 rows)

The resulting traversal is different.

The left image shows the result with ascending order of ids and the right image shows with descending order of the edge identifiers.

See Also

• DFS - Category

• Sample Data

• Boost: Depth First Search algorithm documentation

• Boost: Undirected DFS algorithm documentation

• Wikipedia: Depth First Search algorithm

Indices and tables

• Index

• Search Page