You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tinkerpop.apache.org by sp...@apache.org on 2016/10/14 16:01:30 UTC
svn commit: r1764939 [1/4] - in /tinkerpop/site: docs/3.2.3-SNAPSHOT/images/
docs/3.2.3-SNAPSHOT/recipes/ docs/3.2.3-SNAPSHOT/reference/
docs/3.2.3-SNAPSHOT/upgrade/
javadocs/3.2.3-SNAPSHOT/core/org/apache/tinkerpop/gremlin/process/computer/
javadocs/3...
Author: spmallette
Date: Fri Oct 14 16:01:29 2016
New Revision: 1764939
URL: http://svn.apache.org/viewvc?rev=1764939&view=rev
Log:
Deploy docs for TinkerPop 3.2.3-SNAPSHOT
Added:
tinkerpop/site/docs/3.2.3-SNAPSHOT/images/gremlin-index-time.png (with props)
tinkerpop/site/docs/3.2.3-SNAPSHOT/images/gremlin-max-depth.png (with props)
tinkerpop/site/docs/3.2.3-SNAPSHOT/images/gremlin-tree.png (with props)
tinkerpop/site/docs/3.2.3-SNAPSHOT/images/tree-lca.png (with props)
Modified:
tinkerpop/site/docs/3.2.3-SNAPSHOT/recipes/index.html
tinkerpop/site/docs/3.2.3-SNAPSHOT/reference/index.html
tinkerpop/site/docs/3.2.3-SNAPSHOT/upgrade/index.html
tinkerpop/site/javadocs/3.2.3-SNAPSHOT/core/org/apache/tinkerpop/gremlin/process/computer/package-tree.html
tinkerpop/site/javadocs/3.2.3-SNAPSHOT/core/org/apache/tinkerpop/gremlin/process/traversal/Order.html
tinkerpop/site/javadocs/3.2.3-SNAPSHOT/core/org/apache/tinkerpop/gremlin/process/traversal/package-tree.html
tinkerpop/site/javadocs/3.2.3-SNAPSHOT/core/org/apache/tinkerpop/gremlin/structure/package-tree.html
tinkerpop/site/javadocs/3.2.3-SNAPSHOT/full/constant-values.html
tinkerpop/site/javadocs/3.2.3-SNAPSHOT/full/index-all.html
tinkerpop/site/javadocs/3.2.3-SNAPSHOT/full/org/apache/tinkerpop/gremlin/class-use/LoadGraphWith.html
tinkerpop/site/javadocs/3.2.3-SNAPSHOT/full/org/apache/tinkerpop/gremlin/driver/ser/package-tree.html
tinkerpop/site/javadocs/3.2.3-SNAPSHOT/full/org/apache/tinkerpop/gremlin/package-tree.html
tinkerpop/site/javadocs/3.2.3-SNAPSHOT/full/org/apache/tinkerpop/gremlin/process/computer/class-use/Computer.html
tinkerpop/site/javadocs/3.2.3-SNAPSHOT/full/org/apache/tinkerpop/gremlin/process/computer/package-tree.html
tinkerpop/site/javadocs/3.2.3-SNAPSHOT/full/org/apache/tinkerpop/gremlin/process/computer/traversal/strategy/decoration/VertexProgramStrategy.html
tinkerpop/site/javadocs/3.2.3-SNAPSHOT/full/org/apache/tinkerpop/gremlin/process/computer/traversal/strategy/decoration/class-use/VertexProgramStrategy.html
tinkerpop/site/javadocs/3.2.3-SNAPSHOT/full/org/apache/tinkerpop/gremlin/process/traversal/Order.html
tinkerpop/site/javadocs/3.2.3-SNAPSHOT/full/org/apache/tinkerpop/gremlin/process/traversal/class-use/Traversal.html
tinkerpop/site/javadocs/3.2.3-SNAPSHOT/full/org/apache/tinkerpop/gremlin/process/traversal/package-tree.html
tinkerpop/site/javadocs/3.2.3-SNAPSHOT/full/org/apache/tinkerpop/gremlin/process/traversal/step/branch/ChooseTest.Traversals.html
tinkerpop/site/javadocs/3.2.3-SNAPSHOT/full/org/apache/tinkerpop/gremlin/process/traversal/step/branch/ChooseTest.html
tinkerpop/site/javadocs/3.2.3-SNAPSHOT/full/org/apache/tinkerpop/gremlin/process/traversal/step/map/package-tree.html
tinkerpop/site/javadocs/3.2.3-SNAPSHOT/full/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategy.html
tinkerpop/site/javadocs/3.2.3-SNAPSHOT/full/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RepeatUnrollStrategy.html
tinkerpop/site/javadocs/3.2.3-SNAPSHOT/full/org/apache/tinkerpop/gremlin/server/handler/package-tree.html
tinkerpop/site/javadocs/3.2.3-SNAPSHOT/full/org/apache/tinkerpop/gremlin/structure/class-use/Vertex.html
tinkerpop/site/javadocs/3.2.3-SNAPSHOT/full/org/apache/tinkerpop/gremlin/structure/io/graphson/package-tree.html
tinkerpop/site/javadocs/3.2.3-SNAPSHOT/full/org/apache/tinkerpop/gremlin/structure/package-tree.html
tinkerpop/site/javadocs/3.2.3-SNAPSHOT/full/org/apache/tinkerpop/gremlin/util/function/Lambda.TwoArgLambda.html
Added: tinkerpop/site/docs/3.2.3-SNAPSHOT/images/gremlin-index-time.png
URL: http://svn.apache.org/viewvc/tinkerpop/site/docs/3.2.3-SNAPSHOT/images/gremlin-index-time.png?rev=1764939&view=auto
==============================================================================
Binary file - no diff available.
Propchange: tinkerpop/site/docs/3.2.3-SNAPSHOT/images/gremlin-index-time.png
------------------------------------------------------------------------------
svn:mime-type = application/octet-stream
Added: tinkerpop/site/docs/3.2.3-SNAPSHOT/images/gremlin-max-depth.png
URL: http://svn.apache.org/viewvc/tinkerpop/site/docs/3.2.3-SNAPSHOT/images/gremlin-max-depth.png?rev=1764939&view=auto
==============================================================================
Binary file - no diff available.
Propchange: tinkerpop/site/docs/3.2.3-SNAPSHOT/images/gremlin-max-depth.png
------------------------------------------------------------------------------
svn:mime-type = application/octet-stream
Added: tinkerpop/site/docs/3.2.3-SNAPSHOT/images/gremlin-tree.png
URL: http://svn.apache.org/viewvc/tinkerpop/site/docs/3.2.3-SNAPSHOT/images/gremlin-tree.png?rev=1764939&view=auto
==============================================================================
Binary file - no diff available.
Propchange: tinkerpop/site/docs/3.2.3-SNAPSHOT/images/gremlin-tree.png
------------------------------------------------------------------------------
svn:mime-type = application/octet-stream
Added: tinkerpop/site/docs/3.2.3-SNAPSHOT/images/tree-lca.png
URL: http://svn.apache.org/viewvc/tinkerpop/site/docs/3.2.3-SNAPSHOT/images/tree-lca.png?rev=1764939&view=auto
==============================================================================
Binary file - no diff available.
Propchange: tinkerpop/site/docs/3.2.3-SNAPSHOT/images/tree-lca.png
------------------------------------------------------------------------------
svn:mime-type = application/octet-stream
Modified: tinkerpop/site/docs/3.2.3-SNAPSHOT/recipes/index.html
URL: http://svn.apache.org/viewvc/tinkerpop/site/docs/3.2.3-SNAPSHOT/recipes/index.html?rev=1764939&r1=1764938&r2=1764939&view=diff
==============================================================================
--- tinkerpop/site/docs/3.2.3-SNAPSHOT/recipes/index.html (original)
+++ tinkerpop/site/docs/3.2.3-SNAPSHOT/recipes/index.html Fri Oct 14 16:01:29 2016
@@ -816,6 +816,14 @@ span.line-numbers { border-right: 1px so
<li><a href="#recommendation">Recommendation</a></li>
<li><a href="#shortest-path">Shortest Path</a></li>
<li><a href="#traversal-induced-values">Traversal Induced Values</a></li>
+<li><a href="#tree">Tree</a></li>
+<li>
+<ul class="sectlevel2">
+<li><a href="#_lowest_common_ancestor">Lowest Common Ancestor</a></li>
+<li><a href="#_maximum_depth">Maximum Depth</a></li>
+<li><a href="#_time_based_indexing">Time-based Indexing</a></li>
+</ul>
+</li>
</ul>
</li>
<li><a href="#_implementation_recipes">Implementation Recipes</a></li>
@@ -2037,6 +2045,280 @@ gremlin> g.V().has(<span class="strin
</div>
</div>
</div>
+<div class="sect1">
+<h2 id="tree">Tree</h2>
+<div class="sectionbody">
+<div class="paragraph">
+<p><span class="image"><img src="../images/gremlin-tree.png" alt="gremlin-tree" width="280"></span></p>
+</div>
+<div class="sect2">
+<h3 id="_lowest_common_ancestor">Lowest Common Ancestor</h3>
+<div class="paragraph">
+<p><span class="image" style="float: right"><img src="../images/tree-lca.png" alt="tree-lca" width="230"></span> Given a tree, the <a href="https://en.wikipedia.org/wiki/Lowest_common_ancestor">lowest common ancestor</a>
+is the deepest vertex that is common to two or more other vertices. The diagram to the right depicts the common
+ancestor tree for vertices A and D in the various green shades. The C vertex, the vertex with the darkest green
+shading, is the lowest common ancestor.</p>
+</div>
+<div class="paragraph">
+<p>The following code simply sets up the graph depicted above using "hasParent" for the edge label:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="CodeRay"><code class="groovy language-groovy">gremlin> g.addV(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">A</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="content">a</span><span class="delimiter">'</span></span>).
+ addV(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">B</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="content">b</span><span class="delimiter">'</span></span>).
+ addV(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">C</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="content">c</span><span class="delimiter">'</span></span>).
+ addV(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">D</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="content">d</span><span class="delimiter">'</span></span>).
+ addV(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">E</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="content">e</span><span class="delimiter">'</span></span>).
+ addV(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">F</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="content">f</span><span class="delimiter">'</span></span>).
+ addV(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">G</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="content">g</span><span class="delimiter">'</span></span>).
+ addE(<span class="string"><span class="delimiter">'</span><span class="content">hasParent</span><span class="delimiter">'</span></span>).from(<span class="string"><span class="delimiter">'</span><span class="content">a</span><span class="delimiter">'</span></span>).to(<span class="string"><span class="delimiter">'</span><span class="content">b</span><span class="delimiter">'</span></span>).
+ addE(<span class="string"><span class="delimiter">'</span><span class="content">hasParent</span><span class="delimiter">'</span></span>).from(<span class="string"><span class="delimiter">'</span><span class="content">b</span><span class="delimiter">'</span></span>).to(<span class="string"><span class="delimiter">'</span><span class="content">c</span><span class="delimiter">'</span></span>).
+ addE(<span class="string"><span class="delimiter">'</span><span class="content">hasParent</span><span class="delimiter">'</span></span>).from(<span class="string"><span class="delimiter">'</span><span class="content">d</span><span class="delimiter">'</span></span>).to(<span class="string"><span class="delimiter">'</span><span class="content">c</span><span class="delimiter">'</span></span>).
+ addE(<span class="string"><span class="delimiter">'</span><span class="content">hasParent</span><span class="delimiter">'</span></span>).from(<span class="string"><span class="delimiter">'</span><span class="content">c</span><span class="delimiter">'</span></span>).to(<span class="string"><span class="delimiter">'</span><span class="content">e</span><span class="delimiter">'</span></span>).
+ addE(<span class="string"><span class="delimiter">'</span><span class="content">hasParent</span><span class="delimiter">'</span></span>).from(<span class="string"><span class="delimiter">'</span><span class="content">e</span><span class="delimiter">'</span></span>).to(<span class="string"><span class="delimiter">'</span><span class="content">f</span><span class="delimiter">'</span></span>).
+ addE(<span class="string"><span class="delimiter">'</span><span class="content">hasParent</span><span class="delimiter">'</span></span>).from(<span class="string"><span class="delimiter">'</span><span class="content">g</span><span class="delimiter">'</span></span>).to(<span class="string"><span class="delimiter">'</span><span class="content">f</span><span class="delimiter">'</span></span>).iterate()</code></pre>
+</div>
+</div>
+<div class="paragraph">
+<p>Given that graph, the following traversal will get the lowest common ancestor for two vertices, A and D:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="CodeRay"><code class="groovy language-groovy">gremlin> g.V().has(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>,<span class="string"><span class="delimiter">'</span><span class="content">A</span><span class="delimiter">'</span></span>).
+ repeat(out(<span class="string"><span class="delimiter">'</span><span class="content">hasParent</span><span class="delimiter">'</span></span>)).emit().as(<span class="string"><span class="delimiter">'</span><span class="content">x</span><span class="delimiter">'</span></span>).
+ repeat(__.in(<span class="string"><span class="delimiter">'</span><span class="content">hasParent</span><span class="delimiter">'</span></span>)).emit(has(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>,<span class="string"><span class="delimiter">'</span><span class="content">D</span><span class="delimiter">'</span></span>)).
+ select(<span class="string"><span class="delimiter">'</span><span class="content">x</span><span class="delimiter">'</span></span>).limit(<span class="integer">1</span>).values(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>)
+==>C</code></pre>
+</div>
+</div>
+<div class="paragraph">
+<p>The above traversal is reasonably straightforward to follow in that it simply traverses up the tree from the A vertex
+and then traverses down from each ancestor until it finds the "D" vertex. The first path that uncovers that match is
+the lowest common ancestor.</p>
+</div>
+<div class="paragraph">
+<p>The complexity of finding the lowest common ancestor increases when trying to find the ancestors of three or more
+vertices.</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="CodeRay"><code class="groovy language-groovy">gremlin> input = [<span class="string"><span class="delimiter">'</span><span class="content">A</span><span class="delimiter">'</span></span>,<span class="string"><span class="delimiter">'</span><span class="content">B</span><span class="delimiter">'</span></span>,<span class="string"><span class="delimiter">'</span><span class="content">D</span><span class="delimiter">'</span></span>]
+==>A
+==>B
+==>D
+gremlin> g.V().has(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, input.head()).
+ repeat(out(<span class="string"><span class="delimiter">'</span><span class="content">hasParent</span><span class="delimiter">'</span></span>)).emit().as(<span class="string"><span class="delimiter">'</span><span class="content">x</span><span class="delimiter">'</span></span>). <span class="comment">//</span><b>(1)</b>
+ V().has(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, within(input.tail())). <span class="comment">//</span><b>(2)</b>
+ repeat(out(<span class="string"><span class="delimiter">'</span><span class="content">hasParent</span><span class="delimiter">'</span></span>)).emit(where(eq(<span class="string"><span class="delimiter">'</span><span class="content">x</span><span class="delimiter">'</span></span>))). <span class="comment">//</span><b>(3)</b>
+ group().by(select(<span class="string"><span class="delimiter">'</span><span class="content">x</span><span class="delimiter">'</span></span>)).by(path().count(local).fold()). <span class="comment">//</span><b>(4)</b>
+ unfold().filter(select(values).count(local).is(input.tail().size())). <span class="comment">//</span><b>(5)</b>
+ order().by(select(values).unfold().sum()). <span class="comment">//</span><b>(6)</b>
+ select(keys).limit(<span class="integer">1</span>).valueMap(<span class="predefined-constant">true</span>) <span class="comment">//</span><b>(7)</b>
+==>[<span class="key">label</span>:vertex,<span class="key">name</span>:[C],<span class="key">id</span>:<span class="integer">4</span>]</code></pre>
+</div>
+</div>
+<div class="colist arabic">
+<ol>
+<li>
+<p>The start of the traversal is not so different than the previous one and starts with vertex A.</p>
+</li>
+<li>
+<p>Use a mid-traversal <code>V()</code> to find the child vertices B and D.</p>
+</li>
+<li>
+<p>Traverse up the tree for B and D and find common ancestors that were labeled with "x".</p>
+</li>
+<li>
+<p>Group on the common ancestors where the value of the grouping is the length of the path.</p>
+</li>
+<li>
+<p>The result of the previous step is a <code>Map</code> with a vertex (i.e. common ancestor) for the key and a list of path
+lengths. Unroll the <code>Map</code> and ensure that the number of path lengths are equivalent to the number of children that
+were given to the mid-traversal <code>V()</code>.</p>
+</li>
+<li>
+<p>Order the results based on the sum of the path lengths.</p>
+</li>
+<li>
+<p>Since the results were placed in ascending order, the first result must be the lowest common ancestor.</p>
+</li>
+</ol>
+</div>
+<div class="paragraph">
+<p>As the above traversal utilizes a mid-traversal <code>V()</code>, it cannot be used for OLAP. In OLAP, the pattern changes a bit:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="CodeRay"><code class="groovy language-groovy">gremlin> g.withComputer().V().has(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, within(input)).aggregate(<span class="string"><span class="delimiter">'</span><span class="content">input</span><span class="delimiter">'</span></span>).
+ has(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, input.head()).repeat(out(<span class="string"><span class="delimiter">'</span><span class="content">hasParent</span><span class="delimiter">'</span></span>)).emit().as(<span class="string"><span class="delimiter">'</span><span class="content">x</span><span class="delimiter">'</span></span>).
+ select(<span class="string"><span class="delimiter">'</span><span class="content">input</span><span class="delimiter">'</span></span>).unfold().has(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, within(input.tail())).
+ repeat(out(<span class="string"><span class="delimiter">'</span><span class="content">hasParent</span><span class="delimiter">'</span></span>)).emit(where(eq(<span class="string"><span class="delimiter">'</span><span class="content">x</span><span class="delimiter">'</span></span>))).
+ group().by(select(<span class="string"><span class="delimiter">'</span><span class="content">x</span><span class="delimiter">'</span></span>)).by(path().count(local).fold()).
+ unfold().filter(select(values).count(local).is(input.tail().size())).
+ order().by(select(values).unfold().sum()).
+ select(keys).limit(<span class="integer">1</span>).valueMap(<span class="predefined-constant">true</span>)
+==>[<span class="key">label</span>:,<span class="key">id</span>:<span class="integer">4</span>]</code></pre>
+</div>
+</div>
+</div>
+<div class="sect2">
+<h3 id="_maximum_depth">Maximum Depth</h3>
+<div class="paragraph">
+<p>Finding the maximum depth of a tree starting from a specified root vertex can be determined as follows:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="CodeRay"><code class="groovy language-groovy">gremlin> g.addV(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">A</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="content">a</span><span class="delimiter">'</span></span>).
+ addV(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">B</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="content">b</span><span class="delimiter">'</span></span>).
+ addV(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">C</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="content">c</span><span class="delimiter">'</span></span>).
+ addV(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">D</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="content">d</span><span class="delimiter">'</span></span>).
+ addV(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">E</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="content">e</span><span class="delimiter">'</span></span>).
+ addV(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">F</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="content">f</span><span class="delimiter">'</span></span>).
+ addV(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">G</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="content">g</span><span class="delimiter">'</span></span>).
+ addE(<span class="string"><span class="delimiter">'</span><span class="content">hasParent</span><span class="delimiter">'</span></span>).from(<span class="string"><span class="delimiter">'</span><span class="content">a</span><span class="delimiter">'</span></span>).to(<span class="string"><span class="delimiter">'</span><span class="content">b</span><span class="delimiter">'</span></span>).
+ addE(<span class="string"><span class="delimiter">'</span><span class="content">hasParent</span><span class="delimiter">'</span></span>).from(<span class="string"><span class="delimiter">'</span><span class="content">b</span><span class="delimiter">'</span></span>).to(<span class="string"><span class="delimiter">'</span><span class="content">c</span><span class="delimiter">'</span></span>).
+ addE(<span class="string"><span class="delimiter">'</span><span class="content">hasParent</span><span class="delimiter">'</span></span>).from(<span class="string"><span class="delimiter">'</span><span class="content">d</span><span class="delimiter">'</span></span>).to(<span class="string"><span class="delimiter">'</span><span class="content">c</span><span class="delimiter">'</span></span>).
+ addE(<span class="string"><span class="delimiter">'</span><span class="content">hasParent</span><span class="delimiter">'</span></span>).from(<span class="string"><span class="delimiter">'</span><span class="content">c</span><span class="delimiter">'</span></span>).to(<span class="string"><span class="delimiter">'</span><span class="content">e</span><span class="delimiter">'</span></span>).
+ addE(<span class="string"><span class="delimiter">'</span><span class="content">hasParent</span><span class="delimiter">'</span></span>).from(<span class="string"><span class="delimiter">'</span><span class="content">e</span><span class="delimiter">'</span></span>).to(<span class="string"><span class="delimiter">'</span><span class="content">f</span><span class="delimiter">'</span></span>).
+ addE(<span class="string"><span class="delimiter">'</span><span class="content">hasParent</span><span class="delimiter">'</span></span>).from(<span class="string"><span class="delimiter">'</span><span class="content">g</span><span class="delimiter">'</span></span>).to(<span class="string"><span class="delimiter">'</span><span class="content">f</span><span class="delimiter">'</span></span>).iterate()
+gremlin> g.V().has(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>,<span class="string"><span class="delimiter">'</span><span class="content">F</span><span class="delimiter">'</span></span>).repeat(__.in()).emit().path().count(local).max()
+==><span class="integer">5</span>
+gremlin> g.V().has(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>,<span class="string"><span class="delimiter">'</span><span class="content">C</span><span class="delimiter">'</span></span>).repeat(__.in()).emit().path().count(local).max()
+==><span class="integer">3</span></code></pre>
+</div>
+</div>
+<div class="paragraph">
+<p><span class="image" style="float: right"><img src="../images/gremlin-max-depth.png" alt="gremlin-max-depth" width="350"></span>The traversals shown above are fairly straightforward. The traversal
+beings at a particlar starting vertex, traverse in on the "hasParent" edges emitting all vertices as it goes. It
+calculates the path length and then selects the longest one. While this approach is quite direct, there is room for
+improvement:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="CodeRay"><code class="groovy language-groovy">gremlin> g.V().has(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>,<span class="string"><span class="delimiter">'</span><span class="content">F</span><span class="delimiter">'</span></span>).
+ repeat(__.in()).emit(__.not(inE())).tail(<span class="integer">1</span>).
+ path().count(local)
+==><span class="integer">5</span>
+gremlin> g.V().has(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>,<span class="string"><span class="delimiter">'</span><span class="content">C</span><span class="delimiter">'</span></span>).
+ repeat(__.in()).emit(__.not(inE())).tail(<span class="integer">1</span>).
+ path().count(local)
+==><span class="integer">3</span></code></pre>
+</div>
+</div>
+<div class="paragraph">
+<p>There are two optimizations at play. First, there is no need to emit all the vertices, only the "leaf" vertices (i.e.
+those without incoming edges). Second, all results save the last one can be ignored to that point (i.e. the last one is
+the one at the deepest point in the tree). In this way, the path and path length only need to be calculated for a
+single result.</p>
+</div>
+</div>
+<div class="sect2">
+<h3 id="_time_based_indexing">Time-based Indexing</h3>
+<div class="paragraph">
+<p>Trees can be used for modelling time-oriented data in a graph. Modeling time where there are "year", "month" and "day"
+vertices (or lower granularity as needed) allows the structure of the graph to inherently index data tied to them.</p>
+</div>
+<div class="paragraph">
+<p><span class="image"><img src="../images/gremlin-index-time.png" alt="gremlin-index-time" width="800"></span></p>
+</div>
+<div class="admonitionblock note">
+<table>
+<tr>
+<td class="icon">
+<div class="title">Note</div>
+</td>
+<td class="content">
+This model is discussed further in this Neo4j <a href="https://neo4j.com/blog/modeling-a-multilevel-index-in-neoj4/">blog post</a>.
+Also, there can be other versions of this model that utilize different edge/vertex labelling and property naming
+strategies. The schema depicted here is designed for simplicity.
+</td>
+</tr>
+</table>
+</div>
+<div class="paragraph">
+<p>The Gremlin script below creates the graph depicted in the graph above:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="CodeRay"><code class="groovy language-groovy">gremlin> g.addV(label, <span class="string"><span class="delimiter">'</span><span class="content">year</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">2016</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="content">y2016</span><span class="delimiter">'</span></span>).
+ addV(label, <span class="string"><span class="delimiter">'</span><span class="content">month</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">may</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="content">m05</span><span class="delimiter">'</span></span>).addV(label, <span class="string"><span class="delimiter">'</span><span class="content">month</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">june</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="c
ontent">m06</span><span class="delimiter">'</span></span>).
+ addV(label, <span class="string"><span class="delimiter">'</span><span class="content">day</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">30</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="content">d30</span><span class="delimiter">'</span></span>).addV(label, <span class="string"><span class="delimiter">'</span><span class="content">day</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">31</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="content"
>d31</span><span class="delimiter">'</span></span>).
+ addV(label, <span class="string"><span class="delimiter">'</span><span class="content">day</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">01</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="content">d01</span><span class="delimiter">'</span></span>).
+ addV(label, <span class="string"><span class="delimiter">'</span><span class="content">event</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">A</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="content">eA</span><span class="delimiter">'</span></span>).addV(label, <span class="string"><span class="delimiter">'</span><span class="content">event</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">B</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="content
">eB</span><span class="delimiter">'</span></span>).
+ addV(label, <span class="string"><span class="delimiter">'</span><span class="content">event</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">C</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="content">eC</span><span class="delimiter">'</span></span>).addV(label, <span class="string"><span class="delimiter">'</span><span class="content">event</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">D</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="content
">eD</span><span class="delimiter">'</span></span>).
+ addV(label, <span class="string"><span class="delimiter">'</span><span class="content">event</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>, <span class="string"><span class="delimiter">'</span><span class="content">E</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="content">eE</span><span class="delimiter">'</span></span>).
+ addE(<span class="string"><span class="delimiter">'</span><span class="content">may</span><span class="delimiter">'</span></span>).from(<span class="string"><span class="delimiter">'</span><span class="content">y2016</span><span class="delimiter">'</span></span>).to(<span class="string"><span class="delimiter">'</span><span class="content">m05</span><span class="delimiter">'</span></span>).
+ addE(<span class="string"><span class="delimiter">'</span><span class="content">june</span><span class="delimiter">'</span></span>).from(<span class="string"><span class="delimiter">'</span><span class="content">y2016</span><span class="delimiter">'</span></span>).to(<span class="string"><span class="delimiter">'</span><span class="content">m06</span><span class="delimiter">'</span></span>).
+ addE(<span class="string"><span class="delimiter">'</span><span class="content">day30</span><span class="delimiter">'</span></span>).from(<span class="string"><span class="delimiter">'</span><span class="content">m05</span><span class="delimiter">'</span></span>).to(<span class="string"><span class="delimiter">'</span><span class="content">d30</span><span class="delimiter">'</span></span>).
+ addE(<span class="string"><span class="delimiter">'</span><span class="content">day31</span><span class="delimiter">'</span></span>).from(<span class="string"><span class="delimiter">'</span><span class="content">m05</span><span class="delimiter">'</span></span>).to(<span class="string"><span class="delimiter">'</span><span class="content">d31</span><span class="delimiter">'</span></span>).
+ addE(<span class="string"><span class="delimiter">'</span><span class="content">day01</span><span class="delimiter">'</span></span>).from(<span class="string"><span class="delimiter">'</span><span class="content">m06</span><span class="delimiter">'</span></span>).to(<span class="string"><span class="delimiter">'</span><span class="content">d01</span><span class="delimiter">'</span></span>).
+ addE(<span class="string"><span class="delimiter">'</span><span class="content">has</span><span class="delimiter">'</span></span>).from(<span class="string"><span class="delimiter">'</span><span class="content">d30</span><span class="delimiter">'</span></span>).to(<span class="string"><span class="delimiter">'</span><span class="content">eA</span><span class="delimiter">'</span></span>).
+ addE(<span class="string"><span class="delimiter">'</span><span class="content">has</span><span class="delimiter">'</span></span>).from(<span class="string"><span class="delimiter">'</span><span class="content">d30</span><span class="delimiter">'</span></span>).to(<span class="string"><span class="delimiter">'</span><span class="content">eB</span><span class="delimiter">'</span></span>).
+ addE(<span class="string"><span class="delimiter">'</span><span class="content">has</span><span class="delimiter">'</span></span>).from(<span class="string"><span class="delimiter">'</span><span class="content">d31</span><span class="delimiter">'</span></span>).to(<span class="string"><span class="delimiter">'</span><span class="content">eC</span><span class="delimiter">'</span></span>).
+ addE(<span class="string"><span class="delimiter">'</span><span class="content">has</span><span class="delimiter">'</span></span>).from(<span class="string"><span class="delimiter">'</span><span class="content">d31</span><span class="delimiter">'</span></span>).to(<span class="string"><span class="delimiter">'</span><span class="content">eD</span><span class="delimiter">'</span></span>).
+ addE(<span class="string"><span class="delimiter">'</span><span class="content">has</span><span class="delimiter">'</span></span>).from(<span class="string"><span class="delimiter">'</span><span class="content">d01</span><span class="delimiter">'</span></span>).to(<span class="string"><span class="delimiter">'</span><span class="content">eE</span><span class="delimiter">'</span></span>).
+ addE(<span class="string"><span class="delimiter">'</span><span class="content">next</span><span class="delimiter">'</span></span>).from(<span class="string"><span class="delimiter">'</span><span class="content">d30</span><span class="delimiter">'</span></span>).to(<span class="string"><span class="delimiter">'</span><span class="content">d31</span><span class="delimiter">'</span></span>).
+ addE(<span class="string"><span class="delimiter">'</span><span class="content">next</span><span class="delimiter">'</span></span>).from(<span class="string"><span class="delimiter">'</span><span class="content">d31</span><span class="delimiter">'</span></span>).to(<span class="string"><span class="delimiter">'</span><span class="content">d01</span><span class="delimiter">'</span></span>).
+ addE(<span class="string"><span class="delimiter">'</span><span class="content">next</span><span class="delimiter">'</span></span>).from(<span class="string"><span class="delimiter">'</span><span class="content">m05</span><span class="delimiter">'</span></span>).to(<span class="string"><span class="delimiter">'</span><span class="content">m06</span><span class="delimiter">'</span></span>).iterate()</code></pre>
+</div>
+</div>
+<div class="admonitionblock important">
+<table>
+<tr>
+<td class="icon">
+<div class="title">Important</div>
+</td>
+<td class="content">
+The code example above does not create any indices. Proper index creation, which is specific to the
+graph implementation used, will be critical to the performance of traversals over this structure.
+</td>
+</tr>
+</table>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="CodeRay"><code class="groovy language-groovy">gremlin> g.V().has(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>,<span class="string"><span class="delimiter">'</span><span class="content">2016</span><span class="delimiter">'</span></span>).out().out().out(<span class="string"><span class="delimiter">'</span><span class="content">has</span><span class="delimiter">'</span></span>).values() <span class="comment">//</span><b>(1)</b>
+==>E
+==>C
+==>D
+==>A
+==>B
+gremlin> g.V().has(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>,<span class="string"><span class="delimiter">'</span><span class="content">2016</span><span class="delimiter">'</span></span>).out(<span class="string"><span class="delimiter">'</span><span class="content">may</span><span class="delimiter">'</span></span>).out().out(<span class="string"><span class="delimiter">'</span><span class="content">has</span><span class="delimiter">'</span></span>).values() <span class="comment">//</span><b>(2)</b>
+==>C
+==>D
+==>A
+==>B
+gremlin> g.V().has(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>,<span class="string"><span class="delimiter">'</span><span class="content">2016</span><span class="delimiter">'</span></span>).out(<span class="string"><span class="delimiter">'</span><span class="content">may</span><span class="delimiter">'</span></span>).out(<span class="string"><span class="delimiter">'</span><span class="content">day31</span><span class="delimiter">'</span></span>).out(<span class="string"><span class="delimiter">'</span><span class="content">has</span><span class="delimiter">'</span></span>).values() <span class="comment">//</span><b>(3)</b>
+==>C
+==>D
+gremlin> g.V().has(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>,<span class="string"><span class="delimiter">'</span><span class="content">2016</span><span class="delimiter">'</span></span>).out(<span class="string"><span class="delimiter">'</span><span class="content">may</span><span class="delimiter">'</span></span>).out(<span class="string"><span class="delimiter">'</span><span class="content">day31</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="content">start</span><span class="delimiter">'</span></span>).
+ V().has(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>,<span class="string"><span class="delimiter">'</span><span class="content">2016</span><span class="delimiter">'</span></span>).out(<span class="string"><span class="delimiter">'</span><span class="content">june</span><span class="delimiter">'</span></span>).out(<span class="string"><span class="delimiter">'</span><span class="content">day01</span><span class="delimiter">'</span></span>).as(<span class="string"><span class="delimiter">'</span><span class="content">end</span><span class="delimiter">'</span></span>).
+ emit().repeat(__.in(<span class="string"><span class="delimiter">'</span><span class="content">next</span><span class="delimiter">'</span></span>)).until(where(eq(<span class="string"><span class="delimiter">'</span><span class="content">start</span><span class="delimiter">'</span></span>))).
+ out(<span class="string"><span class="delimiter">'</span><span class="content">has</span><span class="delimiter">'</span></span>).order().by(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>).values(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>) <span class="comment">//</span><b>(4)</b>
+==>C
+==>D
+==>E</code></pre>
+</div>
+</div>
+<div class="colist arabic">
+<ol>
+<li>
+<p>Find all the events in 2016.</p>
+</li>
+<li>
+<p>Find all the events in May of 2016.</p>
+</li>
+<li>
+<p>Find all the events on May 31, 2016.</p>
+</li>
+<li>
+<p>Find all the events between May 31, 2016 and June 1, 2016.</p>
+</li>
+</ol>
+</div>
+</div>
+</div>
+</div>
<h1 id="_implementation_recipes" class="sect0">Implementation Recipes</h1>
<div class="sect1">
<h2 id="style-guide">Style Guide</h2>
@@ -2351,7 +2633,7 @@ submissions!</p>
</div>
<div id="footer">
<div id="footer-text">
-Last updated 2016-10-13 11:25:27 -04:00
+Last updated 2016-10-14 11:59:00 -04:00
</div>
</div>
</body>