pgr_depthFirstSearch - Experimental - pgRouting Manual (3.2)

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

pgr_depthFirstSearch(Edges SQL, Root vid [, directed] [, max_depth]) -- Experimental on v3.2
pgr_depthFirstSearch(Edges SQL, Root vids [, directed] [, max_depth]) -- Experimental on v3.2

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

Using defaults

Example :

From root vertex \(2\) on a directed graph

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

pgr_depthFirstSearch(Edges SQL, Root vid [, directed] [, max_depth])

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

SELECT * FROM pgr_depthFirstSearch(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table
    ORDER BY id',
    2, directed => false, max_depth => 2
);
 seq  depth  start_vid  node  edge  cost  agg_cost
-----+-------+-----------+------+------+------+----------
   1      0          2     2    -1     0         0
   2      1          2     1     1     1         1
   3      1          2     3     2     1         1
   4      2          2     4     3     1         2
   5      2          2     6     5     1         2
   6      1          2     5     4     1         1
   7      2          2     8     7     1         2
   8      2          2    10    10     1         2
(8 rows)

pgr_depthFirstSearch(Edges SQL, Root vids [, directed] [, max_depth])

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

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

Parameters

Inner query

Edges SQL

Where:

ANY-INTEGER :

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL :

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Result Columns

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

Additional Examples

The examples of this section are based on the Sample Data network.

Example: No internal ordering on traversal

In the following query, the inner query of the example: "Using defaults" is modified so that the data is entered into the algorithm is given in the reverse ordering of the id.

SELECT * FROM pgr_depthFirstSearch(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table
    ORDER BY id DESC',
    2
);
 seq  depth  start_vid  node  edge  cost  agg_cost
-----+-------+-----------+------+------+------+----------
   1      0          2     2    -1     0         0
   2      1          2     5     4     1         1
   3      2          2    10    10     1         2
   4      3          2    13    14     1         3
   5      3          2    11    12     1         3
   6      4          2    12    13     1         4
   7      5          2     9    15     1         5
   8      6          2     4    16     1         6
   9      7          2     3     3     1         7
  10      8          2     6     5     1         8
  11      2          2     8     7     1         2
  12      3          2     7     6     1         3
  13      1          2     1     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 ids:

See Also

• The queries use the Sample Data network.

• Boost: Depth First Search algorithm documentation

• Boost: Undirected DFS algorithm documentation

• Wikipedia: Depth First Search algorithm

Indices and tables

• Index

• Search Page