GSoC '20: Detailed signature and usage of the new function pgr_depthFirstSearch() to be added in pgRouting

[krashish8]

The function pgr_depthFirstSearch is required in pgRouting. Here are the function's signature and usage:

Name of the function:

pgr_depthFirstSearch(): Provides the Depth First Search traversal order from a root vertex to a particular max depth.

All the pgRouting functions have a similar name pgr_camelCase, e.g. pgr_breadthFirstSearch. And therefore, I have chosen this name.

Main Characteristics of the function:

• Implementation works for both directed graphs (boost::depth_first_search) and undirected graphs (boost::undirected_dfs).
• The graph can be either weighted or unweighted.
• Depth First Search Running Time: O (E + V)

Variants:

• pgr_depthFirstSearch() Single Vertex - ONE to DEPTH

pgr_depthFirstSearch(edges_sql, root_vid [, max_depth] [, directed])
RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)
OR EMPTY SET

• pgr_depthFirstSearch() Multiple Vertices - MANY to DEPTH

pgr_depthFirstSearch(edges_sql, root_vids [, max_depth] [, directed])
RETURNS SET OF​ (seq, depth, start_vid, node, edge, cost, agg_cost)
OR EMPTY SET

Parameters:

Parameter	Type	Description
edges_sql	TEXT	Inner SQL query, as described below.
root_vid	BIGINT	Identifier of the root vertex of the tree (Used on Single vertex).
root_vids	ARRAY[ANY-INTEGER]	Array of identifiers of the root vertices (Used on Mutiple vertices, duplicate values are removed)

Optional Parameters:

Parameter	Type	Default	Description
max_depth	BIGINT	9223372036854775807	Upper limit for depth of node in the tree (When negative, throws error)
directed	BOOLEAN	true	true: Directed Graph, false: Undirected Graph

Inner Query

edges_sql: ​ It should be an SQL query which should return a set of rows with the following columns:

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). When negative: edge (source, target) does not exist, therefore it’s not part of the graph.
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.

Here,
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)

Column	Type	Description
seq	BIGINT	Sequential value starting from ​1
depth	BIGINT	Depth of the ​ node​ (0 when node = start_vid)
start_vid	BIGINT	Identifier of the root vertex (In Multiple vertices, results are in ascending order)
node	BIGINT	Identifier of ​ node​ reached using ​ edge​
edge	BIGINT	Identifier of the edge used t​o arrive at the node​ (-1 when ​ node​ = ​ start_vid​)
cost	FLOAT	Cost to traverse the edge
agg_cost	FLOAT	Aggregate cost from ​ start_vid​ to ​ node

Usage

Sample Graph:

SELECT * FROM sample_table ORDER BY id;
 id | source | target | cost | reverse_cost 
----+--------+--------+------+--------------
  1 |      3 |      6 |   20 |           15
  2 |      3 |      8 |   10 |          -10
  3 |      6 |      8 |   -1 |           12
(3 rows)

Query 1 (Directed):

SELECT * FROM pgr_depthFirstSearch (
    'SELECT id, source, target, cost, reverse_cost FROM sample_table ORDER BY id',
    3
);
 seq | depth | start_vid | node | edge | cost | agg_cost 
-----+-------+-----------+------+------+------+----------
   1 |     0 |         3 |    3 |   -1 |    0 |        0
   2 |     1 |         3 |    6 |    1 |   20 |       20
   3 |     1 |         3 |    8 |    2 |   10 |       10
(3 rows)

Query 2 (Directed):

SELECT * FROM pgr_depthFirstSearch (
    'SELECT id, source, target, cost, reverse_cost FROM sample_table ORDER BY id',
    6
);
 seq | depth | start_vid | node | edge | cost | agg_cost 
-----+-------+-----------+------+------+------+----------
   1 |     0 |         6 |    6 |   -1 |    0 |        0
   2 |     1 |         6 |    3 |    1 |   15 |       15
   3 |     2 |         6 |    8 |    2 |   10 |       25
(3 rows)

Query 3 (Directed with max_depth):

SELECT * FROM pgr_depthFirstSearch (
    'SELECT id, source, target, cost, reverse_cost FROM sample_table ORDER BY id',
    6, max_depth := 1
);
 seq | depth | start_vid | node | edge | cost | agg_cost 
-----+-------+-----------+------+------+------+----------
   1 |     0 |         6 |    6 |   -1 |    0 |        0
   2 |     1 |         6 |    3 |    1 |   15 |       15
(2 rows)

Query 4 (Vertex does not exist):

SELECT * FROM pgr_depthFirstSearch (
    'SELECT id, source, target, cost, reverse_cost FROM sample_table ORDER BY id',
    2
);
 seq | depth | start_vid | node | edge | cost | agg_cost 
-----+-------+-----------+------+------+------+----------
   1 |     0 |         2 |    2 |   -1 |    0 |        0
(1 rows)

Query 5 (Undirected):

SELECT * FROM pgr_depthFirstSearch (
    'SELECT id, source, target, cost, reverse_cost FROM sample_table ORDER BY id',
    3, directed := false
);
 seq | depth | start_vid | node | edge | cost | agg_cost 
-----+-------+-----------+------+------+------+----------
   1 |     0 |         3 |    3 |   -1 |    0 |        0
   2 |     1 |         3 |    6 |    1 |   20 |       20
   3 |     2 |         3 |    8 |    3 |   12 |       32
(3 rows)

Query 6 (Undirected):

SELECT * FROM pgr_depthFirstSearch (
    'SELECT id, source, target, cost, reverse_cost FROM sample_table ORDER BY id',
    6, directed := false
);
 seq | depth | start_vid | node | edge | cost | agg_cost 
-----+-------+-----------+------+------+------+----------
   1 |     0 |         6 |    6 |   -1 |    0 |        0
   2 |     1 |         6 |    3 |    1 |   20 |       20
   3 |     2 |         6 |    8 |    2 |   10 |       30
(3 rows)

Query 7 (Undirected with max_depth):

SELECT * FROM pgr_depthFirstSearch (
    'SELECT id, source, target, cost, reverse_cost FROM sample_table ORDER BY id',
    6, max_depth := 1, directed := false
);
 seq | depth | start_vid | node | edge | cost | agg_cost 
-----+-------+-----------+------+------+------+----------
   1 |     0 |         6 |    6 |   -1 |    0 |        0
   2 |     1 |         6 |    3 |    1 |   20 |       20
   3 |     1 |         6 |    8 |    3 |   12 |       12
(3 rows)

Query 8 (Multiple Vertices):

SELECT * FROM pgr_depthFirstSearch (
    'SELECT id, source, target, cost, reverse_cost FROM sample_table ORDER BY id',
    ARRAY[6, 3, 6]
);
 seq | depth | start_vid | node | edge | cost | agg_cost 
-----+-------+-----------+------+------+------+----------
   1 |     0 |         3 |    3 |   -1 |    0 |        0
   2 |     1 |         3 |    6 |    1 |   20 |       20
   3 |     1 |         3 |    8 |    2 |   10 |       10
   4 |     0 |         6 |    6 |   -1 |    0 |        0
   5 |     1 |         6 |    3 |    1 |   15 |       15
   6 |     2 |         6 |    8 |    2 |   10 |       25
(6 rows)

References:

1. "The Boost Graph Library (BGL) - Version 1.72.0 Documentation", https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/index.html
2. "Undirected DFS - Boost Graph Library (Boost 1.72.0 Library Documentation)", https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/undirected_dfs.html
3. "Depth First Search - Boost Graph Library (Boost 1.72.0 Library Documentation)", https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/depth_first_search.html
4. "Depth First Search - Wikipedia, the Free Encyclopedia", https://en.wikipedia.org/wiki/Depth-first_search
5. Explanation in GSoC Detailed Proposal, https://drive.google.com/open?id=16PHHqPQkPakPDHe2pDihwqusOZ1cKvM6