Overview

Graph traversal is a search technique used to visit and explore all the nodes of a graph systematically. The primary goal of graph traversal is to uncover and examine the structure and connections of the graph. There are two common strategies for graph traversal:

• Breadth-First Seach (BFS)
• Depth-First Search (DFS)

The Breadth-First Search (BFS) algorithm explores a graph layer by layer and follows these steps:

1. Create a queue (first in, first out) to keep track of visited nodes.
2. Start from a selected node, enqueue it into the queue, and mark it as visited.
3. Dequeue a node from the front of the queue, enqueue all its unvisited neighbors into the queue and mark them as visited.
4. Repeat step 3 until the queue is empty.

Below is an example of traversing the graph using the BFS approach, starting from node A and assuming to visit neighbors in alphabetical order (A~Z):

Considerations

• Only nodes that are in the same connected component as the start node can be traversed. Nodes in different connect components will not be included in the traversal results.

Example Graph

To create this graph:

// Runs each row separately in order in an empty graphset
insert().into(@default).nodes([{_id:"A"}, {_id:"B"}, {_id:"C"}, {_id:"D"}, {_id:"E"}, {_id:"F"}, {_id:"G"}])
insert().into(@default).edges([{_from:"G", _to:"D"}, {_from:"A", _to:"D"}, {_from:"A", _to:"B"}, {_from:"B", _to:"E"}, {_from:"E", _to:"F"}, {_from:"F", _to:"C"}, {_from:"C", _to:"A"}])

Creating HDC Graph

To load the entire graph to the HDC server hdc-server-1 as hdc_trv:

CALL hdc.graph.create("hdc-server-1", "hdc_trv", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
})

hdc.graph.create("hdc_trv", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
}).to("hdc-server-1")

Parameters

Algorithm name: traverse

File Writeback

CALL algo.traverse.write("hdc_trv", {
  params: {
    return_id_uuid: "id",
    ids: ['A'],
    direction: 'out',
    traverse_type: 'bfs'
  },
  return_params: {
    file: {
      filename: "visited_nodes"
    }
  }
})

algo(traverse).params({
  projection: "hdc_trv",
  return_id_uuid: "id",
  ids: ['A'],
  direction: 'out',
  traverse_type: 'bfs'
}).write({
  file: {
    filename: "visited_nodes"
  }
})

Result:

node,parent
D,A
F,E
B,A
A,A
E,B
C,F