Depth First vs. Breadth First

Depth-first traverse is concerned with traversing down an entire path as specified by a path expression before turning to the next legal path. On the other hand breadth-first traverse is concerned with traversing legal paths in parallel where at each step, all legal steps can are computed before moving onto the next step of the path. Gremlin provides support for both types of traversals.

• Depth-First Traversal
• Breadth-First Traversal

Depth-First Traversal

Gremlin is naturally a depth-first traversal language. Any typical path expression that is evaluate with occur in a depth-first manner. For example:

 gremlin> $_g := tg:open()
==>tinkergraph[vertices:0]
gremlin> g:load('data/graph-example-1.xml')
==>true
gremlin> $_ := g:id-v(1)
==>v[1]
gremlin> ./outE[@label='created']/inV/inE[@label='created']/outV
==>v[1]
==>v[4]
==>v[6]

In the expression

./outE[@label='created']/inV/inE[@label='created']/outV

vertex 1 is passed to step outE which yields three outgoing edges (see Defining a Property Graph for diagram of graph). The first of these outgoing edges is then passed into inV which produces one vertex (vertex 3). That one vertex is then passed to inE which yields three edges. The first of those three edges it then passed two outV which yields back vertex 1. At which point, the path expression is complete for the full depth of the expression. The evaluate then goes onto the remaining two edges created from the first outE and the process continues until all legal branches of the path expression have been evaluated.

Breadth-First Traversal

In a breadth-first traversal, all results for each step of the process are gathered before the next step is evaluated. The equivalent breadth-first traversal for the previous co-created expression is as follows.

./outE[@label='created']/gather[0]/inV/gather[0]/inE[@label='created']/gather[0]/outV/gather[0]

The gather step is used to aggregate all the results of a step into a list. Given that gather exhausts all the objects of the previous step and emits a list, [0] is used to unroll that list and pass it to the next step.

With gather, the generated list can be analyzed by a step and determined which part of the path to continue along. For example.

gremlin> step print
	   g:print('processing: ' + .)
	   .
	   end
==>true
gremlin> ./outE/gather/print/inV
processing: [e[7][1-knows->2], e[9][1-created->3], e[8][1-knows->4]]
==>v[2]
==>v[3]
==>v[4]