# Tree Pattern

Marko A. Rodriguez edited this page Jun 30, 2013 · 10 revisions
##### Clone this wiki locally

The path that a traverser takes through a graph can be see as a tree where the root of the tree is the source of the traversal and the branches are the various paths emanating from that root (respective of the provided path description). Note that a traversal can have multiple sources and thus, the respective traversal tree can have multiple roots. Gremlin provides the ability to collect this traversal tree information via the `tree`-step.

## Creating a Traversal Tree

The example to follow makes use of the toy TinkerPop graph diagrammed here.

``````gremlin> g = TinkerGraphFactory.createTinkerGraph()
==>tinkergraph[vertices:6 edges:6]``````

The `tree`-step makes use of the path information of the step to construct an internal embedded map. This map is the tree representation of the traversal. First, look at the serial paths of a traversal.

``````gremlin> g.v(1).out.out.path
==>[v[1], v[4], v[5]]
==>[v[1], v[4], v[3]]``````

These serial paths provide the requisite information about the tree nature of the traversal. The purpose of `tree` is to capture this inherent structure as a tree data structure.

``````gremlin> g.v(1).out.out.tree.cap
==>{v[1]={v[4]={v[3]={}, v[5]={}}}}``````
``````{
v[1]={
v[4]={
v[3]={},
v[5]={}
}
}
}``````

If closures are provided to `tree`, then the closures are evaluated in a round-robin fashion against the objects of the path.

``````gremlin> g.v(1).out.out.tree{it.name}.cap
==>{marko={josh={lop={}, ripple={}}}}``````
``````{
marko={
josh={
lop={},
ripple={}
}
}
}``````

## Working with a Tree

The tree data structure can be walked using Groovy map notation as `Tree` is a `java.util.Map<T, Tree<T>>`. Note that the leaves of the tree are those maps where the key has an empty map value. For non-Groovy Gremlin implementations, it is possible to, in native Java, simply do: `tree.get("marko").get("josh")`.

``````gremlin> tree = g.v(1).out.out.tree{it.name}.cap.next()
==>marko={josh={lop={}, ripple={}}}
gremlin> tree.marko.josh
==>lop={}
==>ripple={}``````

If a `Tree` is provided to `tree`, then that is the side-effect that can be accessed like any other variable.

``````gremlin> t = new Tree()
gremlin> g.v(1).out.out.tree(t){it.name}
==>v[5]
==>v[3]
gremlin> t
==>marko={josh={lop={}, ripple={}}}``````

Moreover, there are numerous helper methods in `Tree` that can be invoked.

``````gremlin> t.getLeafObjects()
==>lop
==>ripple
gremlin> t.getLeafTrees()
==>{lop={}}
==>{ripple={}}
gremlin> t.getObjectsAtDepth(2)
==>josh
gremlin> t.getObjectsAtDepth(3)
==>lop
==>ripple
gremlin> t.getTreesAtDepth(3)
==>{lop={}, ripple={}}``````

## Multi-Object Trees

The `Tree` data structure is not limited to only vertices in a graph. It is possible to store anything touched in the traversal as an object of the traversal tree.

``````gremlin> g.v(1).optimize(false).outE.inV.out.name.tree.cap
==>{v[1]={e[8][1-knows->4]={v[4]={v[3]={lop={}}, v[5]={ripple={}}}}}}``````
``````{
v[1]={
e[8][1-knows->4]={
v[4]={
v[3]={
lop={}
},
v[5]={
ripple={}
}
}
}
}
}``````

## Looping and Range Filters

It is possible to make use of the `tree`-step during a loop. For the following examples, the Grateful Dead graph will be used.

``````gremlin> g = new TinkerGraph()
==>tinkergraph[vertices:0 edges:0]
As can be seen, it is possible to use `loop` to construct the tree. Moreover, by using a range filter (e.g. `[0..100]`) it is possible to limit the number of paths stored in the tree data structure.
``````gremlin> g.v(89).as('x').out.loop('x'){it.loops < 3}[0..100].tree{it.name}.cap.next()