Depth First Search¶

Algorithm introduction¶

Depth-first search explores graph paths by expanding one branch deeply before backtracking.

Compute a classic iterative depth-first search on a directed graph whose node primary key is id. Starting from source_id, each discovered node is visited once, and traversal can be bounded by max_depth.

For more information, see Depth First Search.

Data model¶

To implement the Depth First Search algorithm in GQL, the following data model is used to create a graph type:

Entities are represented by nodes of type Node, with properties id and rating.
Relationships are represented by edges of type Link, with property weight.

For the complete definition of the graph type, see Prepare graph data.

Procedure implementation ¶

To compute Depth First Search results, a procedure is created.

For more information about the procedure, see Procedure implementation. The following section describes the key components of the procedure and how it works.

The procedure takes the following input parameters:

source_id: INT64. ID of the source node to start DFS from.
max_depth: INT64 (default: 9223372036854775807). Maximum depth limit for DFS traversal. Default is effectively unlimited.

Additionally, the following variables are defined within the procedure:

Variable name	Variable type	Description
`done`	Primitive value variable	Flag indicating DFS traversal has finished.
`current_id`	Primitive value variable	Node ID of the node currently being explored.
`current_parent`	Primitive value variable	Parent of the currently explored node in the DFS tree.
`current_depth`	Primitive value variable	Depth of the current node in the DFS tree.
`visit_idx`	Primitive value variable	Step counter for DFS traversal order.
`pick`	Global SumAgg aggregator value variable	Min-heap for selecting the next node to explore (deepest unvisited neighbor).
`entered`	Node-attached SumAgg aggregator value variable	Per-node flag: node has been pushed onto the DFS stack.
`expanded`	Node-attached SumAgg aggregator value variable	Per-node flag: node has been fully explored.
`parent`	Node-attached SumAgg aggregator value variable	Per-node parent in the DFS tree.
`depth`	Node-attached SumAgg aggregator value variable	Per-node DFS depth.
`dfs_table`	Table variable	Output table storing DFS traversal order and tree structure.

The following steps outline the logic of the procedure:

Initialize the source node: set entered, record parent and depth; push onto the simulated stack via pick.
Repeatedly select the deepest unvisited neighbor (pick), mark it entered, set its parent and depth, and push it.
When no unvisited neighbor exists, mark the current node expanded and backtrack.
Return the DFS traversal order (visit_order, vertex_id, parent_id, depth) for all visited nodes.

Steps¶

Run the following code blocks in order in the NebulaGraph Studio CONSOLE. For first-time setup, follow Prepare algorithm sample data to check where to run commands and how the directory is mounted.

1. Prepare graph data ¶

Create a graph type that matches your data model.

'''
CREATE GRAPH TYPE IF NOT EXISTS depth_first_search_graph_type AS {
    NODE Node (LABEL Node {id INT PRIMARY KEY, rating INT}),
    EDGE Link (Node)-[LABEL Link {weight INT, MULTIEDGE KEY()}]->(Node)
}
'''

Download these CSV files and save them with their original names in examples/algorithms/depth_first_search/ under your deployment directory:

depth_first_search_node.csv: Node data.
depth_first_search_edge.csv: Edge data.

Preview the CSV files

depth_first_search_node.csv

id,rating
1,0
2,2
3,1
4,0
5,0
6,2
7,1
8,2
9,0
10,1
11,0
12,2
13,1
14,1
15,0
16,2
17,0
18,1
19,2
20,0
21,2
22,1
23,0
24,1

depth_first_search_edge.csv

src_id,dst_id,weight
1,2,4
1,3,2
1,4,7
1,5,9
2,3,1
2,4,6
2,5,5
2,6,2
3,4,3
3,5,4
3,6,8
4,6,2
4,7,6
4,8,5
5,6,4
5,8,7
5,9,6
6,8,1
6,9,5
6,10,6
7,9,2
7,10,9
8,9,3
8,11,6
8,12,4
9,10,4
9,12,7
9,13,2
10,12,1
10,13,8
10,14,4
11,12,2
11,14,5
11,15,7
12,14,3
12,15,6
12,16,5
13,15,2
13,16,7
14,15,4
14,17,8
14,18,2
15,16,1
15,18,5
15,19,3
16,18,3
16,19,6
17,18,2
17,20,7
17,21,5
18,19,4
18,21,9
18,22,6
19,21,1
19,22,5
20,21,3
20,23,6
20,24,8
21,22,2
21,23,4
21,24,7
22,24,4
23,24,1

Create a temporary graph based on the graph type and load the data files into the temporary graph.

CREATE TEMPORARY GRAPH IF NOT EXISTS #depth_first_search_graph TYPED depth_first_search_graph_type

'''
USE #depth_first_search_graph IMPORT INTO GRAPH {
      NODE (v@Node {id: id, rating: rating}) FROM DATAFILE {
          PATH: "file:///examples/algorithms/depth_first_search/depth_first_search_node.csv",
          FORMAT: "CSV",
          DELIMITER: ','
      },
      EDGE (id: src_id)-[e@Link {weight: weight}]->(id: dst_id) FROM DATAFILE {
          PATH: "file:///examples/algorithms/depth_first_search/depth_first_search_edge.csv",
          FORMAT: "CSV",
          DELIMITER: ','
      }
  }
'''

After the import succeeds, run this query in the console to check the node count:

'''
USE #depth_first_search_graph
MATCH (n)
RETURN count(n) AS node_count
'''

The expected node_count is 24. If it differs, check the files and import results before continuing.

2. Create a procedure ¶

Create a procedure to implement the Depth First Search algorithm. For more information about the procedure, see Procedure implementation.

'''
CREATE OR REPLACE PROCEDURE depth_first_search(
  source_id INT64,
  max_depth INT64 DEFAULT 9223372036854775807
)
RETURNS (visit_order INT64, node_id INT64, parent_id INT64, depth INT64)
COMMENT "Compute a classic iterative depth-first search on a directed graph whose vertex primary key is id. Starting from source_id, each discovered vertex is visited once, and traversal can be bounded by max_depth."
AS {
  VALUE done BOOLEAN = false
  VALUE current_id INT64 = 0
  VALUE current_parent INT64 = 0
  VALUE current_depth INT64 = 0
  VALUE visit_idx INT64 = 0

  VALUE pick TopKAgg<1, depth INT64 DESC, node_id INT64 DESC, parent_id INT64 ASC>

  NODE VALUE entered OrAgg = false
  NODE VALUE expanded OrAgg = false
  NODE VALUE parent MaxAgg<INT64> = 0
  NODE VALUE depth MaxAgg<INT64> = 0

  TABLE dfs_table TYPED TABLE {
    visit_order INT64,
    node_id INT64,
    parent_id INT64,
    depth INT64
  }

  MATCH (n)
  PER NODE (n) {
    SET n.@entered = false
    SET n.@expanded = false
    SET n.@parent = 0
    SET n.@depth = 0
  }

  MATCH (s)
  WHERE s.id = source_id
  PER NODE (s) {
    SET s.@entered = true
    SET s.@expanded = false
    SET s.@parent = source_id
    SET s.@depth = 0
  }

  WHILE done = false THEN {
    SET @pick.clear()

    MATCH (n)
    WHERE n.@entered = true AND n.@expanded = false
    PER NODE (n) {
      SET @pick += RECORD{depth: n.@depth, node_id: n.id, parent_id: n.@parent}
    }

    IF @pick.size() = 0 THEN {
      SET done = true
    }
    ELSE {
      SET current_id = @pick.min().node_id
      SET current_parent = @pick.min().parent_id
      SET current_depth = @pick.min().depth
      SET visit_idx = visit_idx + 1

      MATCH (u)
      WHERE u.id = current_id
      PER NODE (u) {
        SET u.@expanded = true
      }

      EXPORT visit_idx, current_id, current_parent, current_depth INTO dfs_table

      IF current_depth < max_depth THEN {
        MATCH (u)-[e]->(v)
        WHERE u.id = current_id AND v.@entered = false
        PER PATH {
          SET v.@entered += true
        }
        PER NODE (v) {
          SET v.@expanded = false
          SET v.@parent = current_id
          SET v.@depth = current_depth + 1
        }
      }
    }
  }

  FOR r IN dfs_table
  RETURN
    r.visit_order AS visit_order,
    r.node_id AS node_id,
    r.parent_id AS parent_id,
    r.depth AS depth
  ORDER BY visit_order ASC
}
'''

3. Call your procedure ¶

Start depth-first search at node 1 with a maximum depth of 6. Return the visit order, node ID, parent ID, and depth.

USE #depth_first_search_graph CALL depth_first_search(1, 6) RETURN visit_order, node_id, parent_id, depth

Returns:

Expand to view results

+-------------+---------+-----------+-------+
| visit_order | node_id | parent_id | depth |
+-------------+---------+-----------+-------+
| 1           | 1       | 1         | 0     |
| 2           | 5       | 1         | 1     |
| 3           | 9       | 5         | 2     |
| 4           | 13      | 9         | 3     |
| 5           | 16      | 13        | 4     |
| 6           | 19      | 16        | 5     |
| 7           | 22      | 19        | 6     |
| 8           | 21      | 19        | 6     |
| 9           | 18      | 16        | 5     |
| 10          | 15      | 13        | 4     |
| 11          | 12      | 9         | 3     |
| 12          | 14      | 12        | 4     |
| 13          | 17      | 14        | 5     |
| 14          | 20      | 17        | 6     |
| 15          | 10      | 9         | 3     |
| 16          | 8       | 5         | 2     |
| 17          | 11      | 8         | 3     |
| 18          | 6       | 5         | 2     |
| 19          | 4       | 1         | 1     |
| 20          | 7       | 4         | 2     |
| 21          | 3       | 1         | 1     |
| 22          | 2       | 1         | 1     |
+-------------+---------+-----------+-------+

Save results to a file or graph

To save the returned results as CSV files or write them to a graph, see EXPORT. Match the exported fields to the returned columns and target properties.

Depth First Search¶

Algorithm introduction¶

Data model¶

Procedure implementation¶

Steps¶

1. Prepare graph data¶

2. Create a procedure¶

3. Call your procedure¶

Procedure implementation ¶

1. Prepare graph data ¶

2. Create a procedure ¶

3. Call your procedure ¶