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