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/12 18:47:59 UTC
svn commit: r1764499 [2/23] - in /tinkerpop/site:
docs/3.2.3-SNAPSHOT/dev/developer/ docs/3.2.3-SNAPSHOT/dev/io/
docs/3.2.3-SNAPSHOT/dev/provider/ docs/3.2.3-SNAPSHOT/images/
docs/3.2.3-SNAPSHOT/recipes/ docs/3.2.3-SNAPSHOT/reference/
docs/3.2.3-SNAPSH...
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=1764499&r1=1764498&r2=1764499&view=diff
==============================================================================
--- tinkerpop/site/docs/3.2.3-SNAPSHOT/recipes/index.html (original)
+++ tinkerpop/site/docs/3.2.3-SNAPSHOT/recipes/index.html Wed Oct 12 18:47:56 2016
@@ -801,9 +801,6 @@ span.line-numbers { border-right: 1px so
<li>
<ul class="sectlevel1">
<li><a href="#between-vertices">Between Vertices</a></li>
-<li><a href="#shortest-path">Shortest Path</a></li>
-<li><a href="#if-then-based-grouping">If-Then Based Grouping</a></li>
-<li><a href="#cycle-detection">Cycle Detection</a></li>
<li><a href="#centrality">Centrality</a></li>
<li>
<ul class="sectlevel2">
@@ -813,6 +810,10 @@ span.line-numbers { border-right: 1px so
<li><a href="#eigenvector-centrality">Eigenvector Centrality</a></li>
</ul>
</li>
+<li><a href="#cycle-detection">Cycle Detection</a></li>
+<li><a href="#if-then-based-grouping">If-Then Based Grouping</a></li>
+<li><a href="#pagination">Pagination</a></li>
+<li><a href="#shortest-path">Shortest Path</a></li>
<li><a href="#traversal-induced-values">Traversal Induced Values</a></li>
</ul>
</li>
@@ -1023,214 +1024,274 @@ return <code>false</code> in those cases
</div>
</div>
<div class="sect1">
-<h2 id="shortest-path">Shortest Path</h2>
+<h2 id="centrality">Centrality</h2>
<div class="sectionbody">
<div class="paragraph">
-<p><span class="image"><img src="../images/shortest-path.png" alt="shortest-path" width="300"></span></p>
+<p>There are many measures of <a href="https://en.wikipedia.org/wiki/Centrality">centrality</a> which are meant to help identify
+the most important vertices in a graph. As these measures are common in graph theory, this section attempts to
+demonstrate how some of these different indicators can be calculated using Gremlin.</p>
</div>
+<div class="sect2">
+<h3 id="degree-centrality">Degree Centrality</h3>
<div class="paragraph">
-<p>When working with a graph, it is often necessary to identify the
-<a href="https://en.wikipedia.org/wiki/Shortest_path_problem">shortest path</a> between two identified vertices. The following
-is a simple example that identifies the shortest path between vertex "1" and vertex "5" while traversing over out edges:</p>
+<p><a href="https://en.wikipedia.org/wiki/Centrality#Degree_centrality">Degree centrality</a> is a measure of the number of
+edges associated to each vertex.</p>
</div>
<div class="listingblock">
<div class="content">
-<pre class="CodeRay"><code class="groovy language-groovy">gremlin> graph = TinkerGraph.open()
-==>tinkergraph[<span class="key">vertices</span>:<span class="integer">0</span> <span class="key">edges</span>:<span class="integer">0</span>]
-gremlin> v1 = graph.addVertex(T.id, <span class="integer">1</span>)
-==>v[<span class="integer">1</span>]
-gremlin> v2 = graph.addVertex(T.id, <span class="integer">2</span>)
-==>v[<span class="integer">2</span>]
-gremlin> v3 = graph.addVertex(T.id, <span class="integer">3</span>)
-==>v[<span class="integer">3</span>]
-gremlin> v4 = graph.addVertex(T.id, <span class="integer">4</span>)
-==>v[<span class="integer">4</span>]
-gremlin> v5 = graph.addVertex(T.id, <span class="integer">5</span>)
-==>v[<span class="integer">5</span>]
-gremlin> v1.addEdge(<span class="string"><span class="delimiter">"</span><span class="content">knows</span><span class="delimiter">"</span></span>, v2)
-==>e[<span class="integer">0</span>][<span class="integer">1</span>-knows-><span class="integer">2</span>]
-gremlin> v2.addEdge(<span class="string"><span class="delimiter">"</span><span class="content">knows</span><span class="delimiter">"</span></span>, v4)
-==>e[<span class="integer">1</span>][<span class="integer">2</span>-knows-><span class="integer">4</span>]
-gremlin> v4.addEdge(<span class="string"><span class="delimiter">"</span><span class="content">knows</span><span class="delimiter">"</span></span>, v5)
-==>e[<span class="integer">2</span>][<span class="integer">4</span>-knows-><span class="integer">5</span>]
-gremlin> v2.addEdge(<span class="string"><span class="delimiter">"</span><span class="content">knows</span><span class="delimiter">"</span></span>, v3)
-==>e[<span class="integer">3</span>][<span class="integer">2</span>-knows-><span class="integer">3</span>]
-gremlin> v3.addEdge(<span class="string"><span class="delimiter">"</span><span class="content">knows</span><span class="delimiter">"</span></span>, v4)
-==>e[<span class="integer">4</span>][<span class="integer">3</span>-knows-><span class="integer">4</span>]
-gremlin> g = graph.traversal()
-==>graphtraversalsource[tinkergraph[<span class="key">vertices</span>:<span class="integer">5</span> <span class="key">edges</span>:<span class="integer">5</span>], standard]
-gremlin> g.V(<span class="integer">1</span>).repeat(out().simplePath()).until(hasId(<span class="integer">5</span>)).path().limit(<span class="integer">1</span>) <span class="comment">//</span><b>(1)</b>
-==>[v[<span class="integer">1</span>],v[<span class="integer">2</span>],v[<span class="integer">4</span>],v[<span class="integer">5</span>]]
-gremlin> g.V(<span class="integer">1</span>).repeat(out().simplePath()).until(hasId(<span class="integer">5</span>)).path().count(local) <span class="comment">//</span><b>(2)</b>
-==><span class="integer">4</span>
-==><span class="integer">5</span>
-gremlin> g.V(<span class="integer">1</span>).repeat(out().simplePath()).until(hasId(<span class="integer">5</span>)).path().
- group().by(count(local)).next() <span class="comment">//</span><b>(3)</b>
-==><span class="integer">4</span>=[[v[<span class="integer">1</span>], v[<span class="integer">2</span>], v[<span class="integer">4</span>], v[<span class="integer">5</span>]]]
-==><span class="integer">5</span>=[[v[<span class="integer">1</span>], v[<span class="integer">2</span>], v[<span class="integer">3</span>], v[<span class="integer">4</span>], v[<span class="integer">5</span>]]]</code></pre>
+<pre class="CodeRay"><code class="groovy language-groovy">gremlin> g.V().group().by().by(bothE().count()) <span class="comment">//</span><b>(1)</b>
+==>[v[<span class="integer">1</span>]:<span class="integer">3</span>,v[<span class="integer">2</span>]:<span class="integer">1</span>,v[<span class="integer">3</span>]:<span class="integer">3</span>,v[<span class="integer">4</span>]:<span class="integer">3</span>,v[<span class="integer">5</span>]:<span class="integer">1</span>,v[<span class="integer">6</span>]:<span class="integer">1</span>]
+gremlin> g.V().group().by().by(inE().count()) <span class="comment">//</span><b>(2)</b>
+==>[v[<span class="integer">1</span>]:<span class="integer">0</span>,v[<span class="integer">2</span>]:<span class="integer">1</span>,v[<span class="integer">3</span>]:<span class="integer">3</span>,v[<span class="integer">4</span>]:<span class="integer">1</span>,v[<span class="integer">5</span>]:<span class="integer">1</span>,v[<span class="integer">6</span>]:<span class="integer">0</span>]
+gremlin> g.V().group().by().by(outE().count()) <span class="comment">//</span><b>(3)</b>
+==>[v[<span class="integer">1</span>]:<span class="integer">3</span>,v[<span class="integer">2</span>]:<span class="integer">0</span>,v[<span class="integer">3</span>]:<span class="integer">0</span>,v[<span class="integer">4</span>]:<span class="integer">2</span>,v[<span class="integer">5</span>]:<span class="integer">0</span>,v[<span class="integer">6</span>]:<span class="integer">1</span>]
+gremlin> g.V().project(<span class="string"><span class="delimiter">"</span><span class="content">v</span><span class="delimiter">"</span></span>,<span class="string"><span class="delimiter">"</span><span class="content">degree</span><span class="delimiter">"</span></span>).by().by(bothE().count()) <span class="comment">//</span><b>(4)</b>
+==>[<span class="key">v</span>:v[<span class="integer">1</span>],<span class="key">degree</span>:<span class="integer">3</span>]
+==>[<span class="key">v</span>:v[<span class="integer">2</span>],<span class="key">degree</span>:<span class="integer">1</span>]
+==>[<span class="key">v</span>:v[<span class="integer">3</span>],<span class="key">degree</span>:<span class="integer">3</span>]
+==>[<span class="key">v</span>:v[<span class="integer">4</span>],<span class="key">degree</span>:<span class="integer">3</span>]
+==>[<span class="key">v</span>:v[<span class="integer">5</span>],<span class="key">degree</span>:<span class="integer">1</span>]
+==>[<span class="key">v</span>:v[<span class="integer">6</span>],<span class="key">degree</span>:<span class="integer">1</span>]
+gremlin> g.V().project(<span class="string"><span class="delimiter">"</span><span class="content">v</span><span class="delimiter">"</span></span>,<span class="string"><span class="delimiter">"</span><span class="content">degree</span><span class="delimiter">"</span></span>).by().by(bothE().count()). <span class="comment">//</span><b>(5)</b>
+ order().by(select(<span class="string"><span class="delimiter">"</span><span class="content">degree</span><span class="delimiter">"</span></span>), decr).
+ limit(<span class="integer">4</span>)
+==>[<span class="key">v</span>:v[<span class="integer">1</span>],<span class="key">degree</span>:<span class="integer">3</span>]
+==>[<span class="key">v</span>:v[<span class="integer">3</span>],<span class="key">degree</span>:<span class="integer">3</span>]
+==>[<span class="key">v</span>:v[<span class="integer">4</span>],<span class="key">degree</span>:<span class="integer">3</span>]
+==>[<span class="key">v</span>:v[<span class="integer">2</span>],<span class="key">degree</span>:<span class="integer">1</span>]</code></pre>
</div>
</div>
<div class="colist arabic">
<ol>
<li>
-<p>The traversal starts at vertex with the identifier of "1" and repeatedly traverses on out edges "until" it finds a
-vertex with an identifier of "5". The inclusion of <code>simplePath</code> within the <code>repeat</code> is present to filter out repeated
-paths. The traversal terminates with <code>limit</code> in this case as the first path returned will be the shortest one. Of
-course, it is possible for there to be more than one path in the graph of the same length (i.e. two or more paths of
-length three), but this example is not considering that.</p>
+<p>Calculation of degree centrality which counts all incident edges on each vertex to include those that are both
+incoming and outgoing.</p>
</li>
<li>
-<p>It might be interesting to know the path lengths for all paths between vertex "1" and "5".</p>
+<p>Calculation of in-degree centrality which only counts incoming edges to a vertex.</p>
</li>
<li>
-<p>Alternatively, one might wish to do a path length distribution over all the paths.</p>
+<p>Calculation of out-degree centrality which only counts outgoing edges from a vertex.</p>
+</li>
+<li>
+<p>The previous examples all produce a single <code>Map</code> as their output. While that is a desireable output, producing a
+stream of <code>Map</code> objects can allow some greater flexibility.</p>
+</li>
+<li>
+<p>For example, use of a stream enables use of an ordered limit that can be executed in a distributed fashion in
+OLAP traversals.</p>
</li>
</ol>
</div>
+<div class="admonitionblock note">
+<table>
+<tr>
+<td class="icon">
+<div class="title">Note</div>
+</td>
+<td class="content">
+The <a href="http://tinkerpop.apache.org/docs/3.2.3-SNAPSHOT/reference/#group-step">group</a> step takes up to two separate
+<a href="http://tinkerpop.apache.org/docs/3.2.3-SNAPSHOT/reference/#by-step">by</a> modulators. The first <code>by()</code> tells <code>group()</code>
+what the key in the resulting <code>Map</code> will be (i.e. the value to group on). In the above examples, the <code>by()</code> is empty
+and as a result, the grouping will be on the incoming <code>Vertex</code> object itself. The second <code>by()</code> is the value to be
+stored in the <code>Map</code> for each key.
+</td>
+</tr>
+</table>
+</div>
+</div>
+<div class="sect2">
+<h3 id="betweeness-centrality">Betweeness Centrality</h3>
<div class="paragraph">
-<p>The previous example defines the length of the path by the number of vertices in the path, but the "path" might also
-be measured by data within the graph itself. The following example use the same graph structure as the previous example,
-but includes a "weight" on the edges, that will be used to help determine the "cost" of a particular path:</p>
+<p><a href="https://en.wikipedia.org/wiki/Betweenness_centrality">Betweeness centrality</a> is a measure of the number of times
+a vertex is found between the <a href="#shortest-path">shortest path</a> of each vertex pair in a graph. Consider the following
+graph for demonstration purposes:</p>
+</div>
+<div class="paragraph">
+<p><span class="image"><img src="../images/betweeness-example.png" alt="betweeness-example" width="600"></span></p>
</div>
<div class="listingblock">
<div class="content">
-<pre class="CodeRay"><code class="groovy language-groovy">gremlin> graph = TinkerGraph.open()
-==>tinkergraph[<span class="key">vertices</span>:<span class="integer">0</span> <span class="key">edges</span>:<span class="integer">0</span>]
-gremlin> v1 = graph.addVertex(T.id, <span class="integer">1</span>)
-==>v[<span class="integer">1</span>]
-gremlin> v2 = graph.addVertex(T.id, <span class="integer">2</span>)
+<pre class="CodeRay"><code class="groovy language-groovy">gremlin> a = graph.addVertex(<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>)
+==>v[<span class="integer">0</span>]
+gremlin> b = graph.addVertex(<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>)
==>v[<span class="integer">2</span>]
-gremlin> v3 = graph.addVertex(T.id, <span class="integer">3</span>)
-==>v[<span class="integer">3</span>]
-gremlin> v4 = graph.addVertex(T.id, <span class="integer">4</span>)
+gremlin> c = graph.addVertex(<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>)
==>v[<span class="integer">4</span>]
-gremlin> v5 = graph.addVertex(T.id, <span class="integer">5</span>)
-==>v[<span class="integer">5</span>]
-gremlin> v1.addEdge(<span class="string"><span class="delimiter">"</span><span class="content">knows</span><span class="delimiter">"</span></span>, v2, <span class="string"><span class="delimiter">"</span><span class="content">weight</span><span class="delimiter">"</span></span>, <span class="float">1.25</span>)
-==>e[<span class="integer">0</span>][<span class="integer">1</span>-knows-><span class="integer">2</span>]
-gremlin> v2.addEdge(<span class="string"><span class="delimiter">"</span><span class="content">knows</span><span class="delimiter">"</span></span>, v4, <span class="string"><span class="delimiter">"</span><span class="content">weight</span><span class="delimiter">"</span></span>, <span class="float">1.5</span>)
-==>e[<span class="integer">1</span>][<span class="integer">2</span>-knows-><span class="integer">4</span>]
-gremlin> v4.addEdge(<span class="string"><span class="delimiter">"</span><span class="content">knows</span><span class="delimiter">"</span></span>, v5, <span class="string"><span class="delimiter">"</span><span class="content">weight</span><span class="delimiter">"</span></span>, <span class="float">0.25</span>)
-==>e[<span class="integer">2</span>][<span class="integer">4</span>-knows-><span class="integer">5</span>]
-gremlin> v2.addEdge(<span class="string"><span class="delimiter">"</span><span class="content">knows</span><span class="delimiter">"</span></span>, v3, <span class="string"><span class="delimiter">"</span><span class="content">weight</span><span class="delimiter">"</span></span>, <span class="float">0.25</span>)
-==>e[<span class="integer">3</span>][<span class="integer">2</span>-knows-><span class="integer">3</span>]
-gremlin> v3.addEdge(<span class="string"><span class="delimiter">"</span><span class="content">knows</span><span class="delimiter">"</span></span>, v4, <span class="string"><span class="delimiter">"</span><span class="content">weight</span><span class="delimiter">"</span></span>, <span class="float">0.25</span>)
-==>e[<span class="integer">4</span>][<span class="integer">3</span>-knows-><span class="integer">4</span>]
-gremlin> g = graph.traversal()
-==>graphtraversalsource[tinkergraph[<span class="key">vertices</span>:<span class="integer">5</span> <span class="key">edges</span>:<span class="integer">5</span>], standard]
-gremlin> g.V(<span class="integer">1</span>).repeat(out().simplePath()).until(hasId(<span class="integer">5</span>)).path().
- group().by(count(local)).next() <span class="comment">//</span><b>(1)</b>
-==><span class="integer">4</span>=[[v[<span class="integer">1</span>], v[<span class="integer">2</span>], v[<span class="integer">4</span>], v[<span class="integer">5</span>]]]
-==><span class="integer">5</span>=[[v[<span class="integer">1</span>], v[<span class="integer">2</span>], v[<span class="integer">3</span>], v[<span class="integer">4</span>], v[<span class="integer">5</span>]]]
-gremlin> g.V(<span class="integer">1</span>).repeat(outE().inV().simplePath()).until(hasId(<span class="integer">5</span>)).
- path().by(coalesce(values(<span class="string"><span class="delimiter">'</span><span class="content">weight</span><span class="delimiter">'</span></span>),
- constant(<span class="float">0.0</span>))).
- map(unfold().sum()) <span class="comment">//</span><b>(2)</b>
-==><span class="float">3.00</span>
-==><span class="float">2.00</span>
-gremlin> g.V(<span class="integer">1</span>).repeat(outE().inV().simplePath()).until(hasId(<span class="integer">5</span>)).
- path().by(constant(<span class="float">0.0</span>)).by(<span class="string"><span class="delimiter">'</span><span class="content">weight</span><span class="delimiter">'</span></span>).map(unfold().sum()) <span class="comment">//</span><b>(3)</b>
-==><span class="float">3.00</span>
-==><span class="float">2.00</span>
-gremlin> g.V(<span class="integer">1</span>).repeat(outE().inV().simplePath()).until(hasId(<span class="integer">5</span>)).
- path().as(<span class="string"><span class="delimiter">'</span><span class="content">p</span><span class="delimiter">'</span></span>).
- map(unfold().coalesce(values(<span class="string"><span class="delimiter">'</span><span class="content">weight</span><span class="delimiter">'</span></span>),
- constant(<span class="float">0.0</span>)).sum()).as(<span class="string"><span class="delimiter">'</span><span class="content">cost</span><span class="delimiter">'</span></span>).
- select(<span class="string"><span class="delimiter">'</span><span class="content">cost</span><span class="delimiter">'</span></span>,<span class="string"><span class="delimiter">'</span><span class="content">p</span><span class="delimiter">'</span></span>) <span class="comment">//</span><b>(4)</b>
-==>[<span class="key">cost</span>:<span class="float">3.00</span>,<span class="key">p</span>:[v[<span class="integer">1</span>],e[<span class="integer">0</span>][<span class="integer">1</span>-knows-><span class="integer">2</span>],v[<span class="integer">2</span>],e[<span class="integer">1</span>][<span class="integer">2</span>-knows-><span class="integer">4</span>],v[<span class="integer">4</span>],e[<span class="integer">2</span>][<span class="integer">4</span>-knows-><span class="integer">5</span>],v[<span class="integer">5</span>]]]
-==>[<span class="key">cost</span>:<span class="float">2.00</span>,<span class="key">p</span>:[v[<span class="integer">1</span>],e[<span class="integer">0</span>][<span class="integer">1</span>-knows-><span class="integer">2</span>],v[<span class="integer">2</span>],e[<span class="integer">3</span>][<span class="integer">2</span>-knows-><span class="integer">3</span>],v[<span class="integer">3</span>],e[<span class="integer">4</span>][<span class="integer">3</span>-knows-><span class="integer">4</span>],v[<span class="integer">4</span>],e[<span class="integer">2</span>][<span class="integer">4</span>-knows-><span class="integer">5</span>],v[<span class="integer">5</span>]]]</code></pre>
+gremlin> d = graph.addVertex(<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>)
+==>v[<span class="integer">6</span>]
+gremlin> e = graph.addVertex(<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>)
+==>v[<span class="integer">8</span>]
+gremlin> a.addEdge(<span class="string"><span class="delimiter">'</span><span class="content">next</span><span class="delimiter">'</span></span>,b)
+==>e[<span class="integer">10</span>][<span class="integer">0</span>-next-><span class="integer">2</span>]
+gremlin> b.addEdge(<span class="string"><span class="delimiter">'</span><span class="content">next</span><span class="delimiter">'</span></span>,c)
+==>e[<span class="integer">11</span>][<span class="integer">2</span>-next-><span class="integer">4</span>]
+gremlin> c.addEdge(<span class="string"><span class="delimiter">'</span><span class="content">next</span><span class="delimiter">'</span></span>,d)
+==>e[<span class="integer">12</span>][<span class="integer">4</span>-next-><span class="integer">6</span>]
+gremlin> d.addEdge(<span class="string"><span class="delimiter">'</span><span class="content">next</span><span class="delimiter">'</span></span>,e)
+==>e[<span class="integer">13</span>][<span class="integer">6</span>-next-><span class="integer">8</span>]
+gremlin> g.withSack(<span class="integer">0</span>).V().store(<span class="string"><span class="delimiter">"</span><span class="content">x</span><span class="delimiter">"</span></span>).repeat(both().simplePath()).emit().path(). <span class="comment">//</span><b>(1)</b>
+ group().by(project(<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>).by(limit(local, <span class="integer">1</span>)). <span class="comment">//</span><b>(2)</b>
+ by(tail(local, <span class="integer">1</span>))).
+ by(order().by(count(local))). <span class="comment">//</span><b>(3)</b>
+ select(values).as(<span class="string"><span class="delimiter">"</span><span class="content">shortestPaths</span><span class="delimiter">"</span></span>). <span class="comment">//</span><b>(4)</b>
+ select(<span class="string"><span class="delimiter">"</span><span class="content">x</span><span class="delimiter">"</span></span>).unfold().as(<span class="string"><span class="delimiter">"</span><span class="content">v</span><span class="delimiter">"</span></span>). <span class="comment">//</span><b>(5)</b>
+ select(<span class="string"><span class="delimiter">"</span><span class="content">shortestPaths</span><span class="delimiter">"</span></span>). <span class="comment">//</span><b>(6)</b>
+ map(unfold().filter(unfold().where(eq(<span class="string"><span class="delimiter">"</span><span class="content">v</span><span class="delimiter">"</span></span>))).count()). <span class="comment">//</span><b>(7)</b>
+ sack(sum).sack().as(<span class="string"><span class="delimiter">"</span><span class="content">betweeness</span><span class="delimiter">"</span></span>). <span class="comment">//</span><b>(8)</b>
+ select(<span class="string"><span class="delimiter">"</span><span class="content">v</span><span class="delimiter">"</span></span>,<span class="string"><span class="delimiter">"</span><span class="content">betweeness</span><span class="delimiter">"</span></span>)
+==>[<span class="key">v</span>:v[<span class="integer">0</span>],<span class="key">betweeness</span>:<span class="integer">8</span>]
+==>[<span class="key">v</span>:v[<span class="integer">2</span>],<span class="key">betweeness</span>:<span class="integer">14</span>]
+==>[<span class="key">v</span>:v[<span class="integer">4</span>],<span class="key">betweeness</span>:<span class="integer">16</span>]
+==>[<span class="key">v</span>:v[<span class="integer">6</span>],<span class="key">betweeness</span>:<span class="integer">14</span>]
+==>[<span class="key">v</span>:v[<span class="integer">8</span>],<span class="key">betweeness</span>:<span class="integer">8</span>]</code></pre>
</div>
</div>
<div class="colist arabic">
<ol>
<li>
-<p>Note that the shortest path as determined by the structure of the graph is the same.</p>
+<p>Defines a Gremlin <a href="http://tinkerpop.apache.org/docs/3.2.3-SNAPSHOT/reference/#sack-step">sack</a> with a value of zero,
+which represents the initial betweeness score for each vertex, and traverses on both incoming and outgoing edges
+avoiding <a href="#cycle-detection">cyclic paths</a>.</p>
</li>
<li>
-<p>Calculate the "cost" of the path as determined by the weight on the edges. As the "weight" data is on the edges
-between the vertices, it is necessary to change the contents of the <code>repeat</code> step to use <code>outE().inV()</code> so that the
-edge is included in the path. The path is then post-processed with a <code>by</code> modulator that extracts the "weight" value.
-The traversal uses <code>coalesce</code> as there is a mixture of vertices and edges in the path and the traversal is only
-interested in edge elements that can return a "weight" property. The final part of the traversal executes a map
-function over each path, unfolding it and summing the weights.</p>
+<p>Group each path by the first and last vertex.</p>
</li>
<li>
-<p>The same traversal as the one above it, but avoids the use of <code>coalesce</code> with the use of two <code>by</code> modulators. The
-<code>by</code> modulator is applied in a round-robin fashion, so the first <code>by</code> will always apply to a vertex (as it is the first
-item in every path) and the second <code>by</code> will always apply to an edge (as it always follows the vertex in the path).</p>
+<p>Reduce the list of paths to the shortest path between the first and last vertex by ordering on their lengths.</p>
</li>
<li>
-<p>The output of the previous examples of the "cost" wasn’t terribly useful as it didn’t include which path had the
-calculated cost. With some slight modifications given the use of <code>select</code> it becomes possible to include the path in
-the output. Note that the path with the lowest "cost" actually has a longer path length as determined by the graph
-structure.</p>
+<p>Recall that at this point, there is a <code>Map</code> keyed by first and last vertex and with a value of just the shortest
+path. Extract the shortest path with <code>select(values)</code>, since that’s the only portion required for the remainder of
+the traversal.</p>
+</li>
+<li>
+<p>The "x" key contains the list of vertices stored from step 1 - unfold that list into "v" for later use. This step
+will unwrap the vertex that is stored in the <code>Traverser</code> as
+<a href="http://tinkerpop.apache.org/javadocs/3.2.3-SNAPSHOT/full/org/apache/tinkerpop/gremlin/process/traversal/step/util/BulkSet.html">BulkSet</a>
+so that it can be used directly in the <code>Traversal</code>.</p>
+</li>
+<li>
+<p>Iterate the set of shortest paths. At this point, it is worth noting that the traversal is iterating each vertex
+in "v" and for each vertex in "v" it is iterating each <code>Path</code> in "shortestpaths".</p>
+</li>
+<li>
+<p>For each path, transform it to a count of the number of times that "v" from step 5 is encountered.</p>
+</li>
+<li>
+<p>Sum the counts for each vertex using <code>sack()</code>, normalize the value and label it as the "betweeness" to be the score.</p>
</li>
</ol>
</div>
</div>
-</div>
-<div class="sect1">
-<h2 id="if-then-based-grouping">If-Then Based Grouping</h2>
-<div class="sectionbody">
+<div class="sect2">
+<h3 id="closeness-centrality">Closeness Centrality</h3>
<div class="paragraph">
-<p>Consider the following traversal over the "modern" toy graph:</p>
+<p><a href="https://en.wikipedia.org/wiki/Centrality">Closeness centrality</a> is a measure of the distance of one vertex to all
+other reachable vertices in the graph.</p>
</div>
<div class="listingblock">
<div class="content">
-<pre class="CodeRay"><code class="groovy language-groovy">gremlin> g.V().hasLabel(<span class="string"><span class="delimiter">'</span><span class="content">person</span><span class="delimiter">'</span></span>).groupCount().by(<span class="string"><span class="delimiter">'</span><span class="content">age</span><span class="delimiter">'</span></span>)
-==>[<span class="integer">32</span>:<span class="integer">1</span>,<span class="integer">35</span>:<span class="integer">1</span>,<span class="integer">27</span>:<span class="integer">1</span>,<span class="integer">29</span>:<span class="integer">1</span>]</code></pre>
+<pre class="CodeRay"><code class="groovy language-groovy">gremlin> g.withSack(<span class="float">1f</span>).V().repeat(both().simplePath()).emit().path(). <span class="comment">//</span><b>(1)</b>
+ group().by(project(<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>).by(limit(local, <span class="integer">1</span>)). <span class="comment">//</span><b>(2)</b>
+ by(tail(local, <span class="integer">1</span>))).
+ by(order().by(count(local))). <span class="comment">//</span><b>(3)</b>
+ select(values).unfold(). <span class="comment">//</span><b>(4)</b>
+ project(<span class="string"><span class="delimiter">"</span><span class="content">v</span><span class="delimiter">"</span></span>,<span class="string"><span class="delimiter">"</span><span class="content">length</span><span class="delimiter">"</span></span>).
+ by(limit(local, <span class="integer">1</span>)). <span class="comment">//</span><b>(5)</b>
+ by(count(local).sack(div).sack()). <span class="comment">//</span><b>(6)</b>
+ group().by(select(<span class="string"><span class="delimiter">"</span><span class="content">v</span><span class="delimiter">"</span></span>)).by(select(<span class="string"><span class="delimiter">"</span><span class="content">length</span><span class="delimiter">"</span></span>).sum()) <span class="comment">//</span><b>(7)</b>
+==>[v[<span class="integer">1</span>]:<span class="float">2.1666666666666665</span>,v[<span class="integer">2</span>]:<span class="float">1.6666666666666665</span>,v[<span class="integer">3</span>]:<span class="float">2.1666666666666665</span>,v[<span class="integer">4</span>]:<span class="float">2.1666666666666665</span>,v[<span class="integer">5</span>]:<span class="float">1.6666666666666665</span>,v[<span class="integer">6</span>]:<span class="float">1.6666666666666665</span>]</code></pre>
</div>
</div>
-<div class="paragraph">
-<p>The result is an age distribution that simply shows that every "person" in the graph is of a different age. In some
-cases, this result is exactly what is needed, but sometimes a grouping may need to be transformed to provide a
-different picture of the result. For example, perhaps a grouping on the value "age" would be better represented by
-a domain concept such as "young", "old" and "very old".</p>
-</div>
-<div class="listingblock">
-<div class="content">
-<pre class="CodeRay"><code class="groovy language-groovy">gremlin> g.V().hasLabel(<span class="string"><span class="delimiter">"</span><span class="content">person</span><span class="delimiter">"</span></span>).groupCount().by(values(<span class="string"><span class="delimiter">"</span><span class="content">age</span><span class="delimiter">"</span></span>).choose(
- is(lt(<span class="integer">28</span>)),constant(<span class="string"><span class="delimiter">"</span><span class="content">young</span><span class="delimiter">"</span></span>),
- choose(is(lt(<span class="integer">30</span>)),
- constant(<span class="string"><span class="delimiter">"</span><span class="content">old</span><span class="delimiter">"</span></span>),
- constant(<span class="string"><span class="delimiter">"</span><span class="content">very old</span><span class="delimiter">"</span></span>))))
-==>[<span class="key">young</span>:<span class="integer">1</span>,<span class="key">old</span>:<span class="integer">1</span>,very <span class="key">old</span>:<span class="integer">2</span>]</code></pre>
+<div class="colist arabic">
+<ol>
+<li>
+<p>Defines a Gremlin <a href="http://tinkerpop.apache.org/docs/3.2.3-SNAPSHOT/reference/#sack-step">sack</a> with a value of one,
+and traverses on both incoming and outgoing edges avoiding <a href="#cycle-detection">cyclic paths</a>.</p>
+</li>
+<li>
+<p>Group each path by the first and last vertex.</p>
+</li>
+<li>
+<p>Reduce the list of paths to the shortest path between the first and last vertex by ordering on their lengths.</p>
+</li>
+<li>
+<p>Recall that at this point, there is a <code>Map</code> keyed by first and last vertex and with a value of just the shortest
+path. Extract the shortest path with <code>select(values)</code>, since that’s the only portion required for the remainder of
+the traversal.</p>
+</li>
+<li>
+<p>The first <code>by()</code> modulator for <code>project()</code> extracts the first vertex in the path.</p>
+</li>
+<li>
+<p>The second <code>by()</code> modulator for <code>project()</code> extracts the path length and divides that distance by the value of
+the <code>sack()</code> which was initialized to 1 at the start of the traversal.</p>
+</li>
+<li>
+<p>Group the resulting <code>Map</code> objects on "v" and sum their lengths to get the centrality score for each.</p>
+</li>
+</ol>
</div>
</div>
+<div class="sect2">
+<h3 id="eigenvector-centrality">Eigenvector Centrality</h3>
<div class="paragraph">
-<p>Note that the <code>by</code> modulator has been altered from simply taking a string key of "age" to take a <code>Traversal</code>. That
-inner <code>Traversal</code> utilizes <code>choose</code> which is like an <code>if-then-else</code> clause. The <code>choose</code> is nested and would look
-like the following in Java:</p>
+<p>A calculation of <a href="https://en.wikipedia.org/wiki/Centrality#Eigenvector_centrality">eigenvector centrality</a> uses the
+relative importance of adjacent vertices to help determine their centrality. In other words, unlike
+<a href="#degree-centrality">degree centrality</a> the vertex with the greatest number of incident edges does not necessarily
+give it the highest rank. Consider the following example using the Grateful Dead graph:</p>
</div>
<div class="listingblock">
<div class="content">
-<pre class="CodeRay"><code class="java language-java"><span class="keyword">if</span> (age < <span class="integer">28</span>) {
- <span class="keyword">return</span> <span class="string"><span class="delimiter">"</span><span class="content">young</span><span class="delimiter">"</span></span>;
-} <span class="keyword">else</span> {
- <span class="keyword">if</span> (age < <span class="integer">30</span>) {
- <span class="keyword">return</span> <span class="string"><span class="delimiter">"</span><span class="content">old</span><span class="delimiter">"</span></span>;
- } <span class="keyword">else</span> {
- <span class="keyword">return</span> <span class="string"><span class="delimiter">"</span><span class="content">very old</span><span class="delimiter">"</span></span>;
- }
-}</code></pre>
-</div>
-</div>
-<div class="paragraph">
-<p>The use of <code>choose</code> is a good intutive choice for this <code>Traversal</code> as it is a natural mapping to <code>if-then-else</code>, but
-there is another option to consider with <code>coalesce</code>:</p>
+<pre class="CodeRay"><code class="groovy language-groovy">gremlin> graph.io(graphml()).readGraph(<span class="string"><span class="delimiter">'</span><span class="content">data/grateful-dead.xml</span><span class="delimiter">'</span></span>)
+gremlin> g.V().repeat(groupCount(<span class="string"><span class="delimiter">'</span><span class="content">m</span><span class="delimiter">'</span></span>).by(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>).out()).times(<span class="integer">5</span>).cap(<span class="string"><span class="delimiter">'</span><span class="content">m</span><span class="delimiter">'</span></span>). <span class="comment">//</span><b>(1)</b>
+ order(local).by(values, decr).limit(local, <span class="integer">10</span>).next() <span class="comment">//</span><b>(2)</b>
+==>PLAYING IN THE BAND=<span class="integer">8758598</span>
+==>ME AND MY UNCLE=<span class="integer">8214246</span>
+==>JACK STRAW=<span class="integer">8173882</span>
+==>EL PASO=<span class="integer">7666994</span>
+==>TRUCKING=<span class="integer">7643494</span>
+==>PROMISED LAND=<span class="integer">7339027</span>
+==>CHINA CAT SUNFLOWER=<span class="integer">7322213</span>
+==>CUMBERLAND BLUES=<span class="integer">6730838</span>
+==>RAMBLE ON ROSE=<span class="integer">6676667</span>
+==>LOOKS LIKE RAIN=<span class="integer">6674121</span>
+gremlin> g.V().repeat(groupCount(<span class="string"><span class="delimiter">'</span><span class="content">m</span><span class="delimiter">'</span></span>).by(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>).out().timeLimit(<span class="integer">100</span>)).times(<span class="integer">5</span>).cap(<span class="string"><span class="delimiter">'</span><span class="content">m</span><span class="delimiter">'</span></span>). <span class="comment">//</span><b>(3)</b>
+ order(local).by(values, decr).limit(local, <span class="integer">10</span>).next()
+==>PLAYING IN THE BAND=<span class="integer">8758598</span>
+==>ME AND MY UNCLE=<span class="integer">8214246</span>
+==>JACK STRAW=<span class="integer">8173882</span>
+==>EL PASO=<span class="integer">7666994</span>
+==>TRUCKING=<span class="integer">7643494</span>
+==>PROMISED LAND=<span class="integer">7339027</span>
+==>CHINA CAT SUNFLOWER=<span class="integer">7322213</span>
+==>CUMBERLAND BLUES=<span class="integer">6730838</span>
+==>RAMBLE ON ROSE=<span class="integer">6676667</span>
+==>LOOKS LIKE RAIN=<span class="integer">6674121</span></code></pre>
</div>
-<div class="listingblock">
-<div class="content">
-<pre class="CodeRay"><code class="groovy language-groovy">gremlin> g.V().hasLabel(<span class="string"><span class="delimiter">"</span><span class="content">person</span><span class="delimiter">"</span></span>).
- groupCount().by(values(<span class="string"><span class="delimiter">"</span><span class="content">age</span><span class="delimiter">"</span></span>).
- coalesce(is(lt(<span class="integer">28</span>)).constant(<span class="string"><span class="delimiter">"</span><span class="content">young</span><span class="delimiter">"</span></span>),
- is(lt(<span class="integer">30</span>)).constant(<span class="string"><span class="delimiter">"</span><span class="content">old</span><span class="delimiter">"</span></span>),
- constant(<span class="string"><span class="delimiter">"</span><span class="content">very old</span><span class="delimiter">"</span></span>)))
-==>[<span class="key">young</span>:<span class="integer">1</span>,<span class="key">old</span>:<span class="integer">1</span>,very <span class="key">old</span>:<span class="integer">2</span>]</code></pre>
</div>
+<div class="colist arabic">
+<ol>
+<li>
+<p>The traversal iterates through each vertex in the graph and for each one repeatedly group counts each vertex that
+passes through using the vertex as the key. The <code>Map</code> of this group count is stored in a variable named "m". The
+<code>out()</code> traversal is repeated thirty times or until the paths are exhausted. Five iterations should provide enough
+time to converge on a solution. Calling <code>cap('m')</code> at the end simply extracts the <code>Map</code> side-effect stored in "m".</p>
+</li>
+<li>
+<p>The entries in the <code>Map</code> are then iterated and sorted with the top ten most central vertices presented as output.</p>
+</li>
+<li>
+<p>The previous examples can be expanded on a little bit by including a
+<a href="http://tinkerpop.apache.org/docs/current/reference/#timelimit-step">time limit</a>. The <code>timeLimit()</code> prevents the
+traversal from taking longer than one hundred milliseconds to execute (the previous example takes considerably longer
+than that). While the answer provided with the <code>timeLimit()</code> is not the absolute ranking, it does provide a relative
+ranking that closely matches the absolute one. The use of <code>timeLimit()</code> in certain algorithms (e.g. recommendations)
+can shorten the time required to get a reasonable and usable result.</p>
+</li>
+</ol>
</div>
-<div class="paragraph">
-<p>The answer is the same, but this traversal removes the nested <code>choose</code>, which makes it easier to read.</p>
</div>
</div>
</div>
@@ -1306,65 +1367,132 @@ arbitrary length over both incoming and
</div>
</div>
<div class="sect1">
-<h2 id="centrality">Centrality</h2>
+<h2 id="if-then-based-grouping">If-Then Based Grouping</h2>
<div class="sectionbody">
<div class="paragraph">
-<p>There are many measures of <a href="https://en.wikipedia.org/wiki/Centrality">centrality</a> which are meant to help identify
-the most important vertices in a graph. As these measures are common in graph theory, this section attempts to
-demonstrate how some of these different indicators can be calculated using Gremlin.</p>
+<p>Consider the following traversal over the "modern" toy graph:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="CodeRay"><code class="groovy language-groovy">gremlin> g.V().hasLabel(<span class="string"><span class="delimiter">'</span><span class="content">person</span><span class="delimiter">'</span></span>).groupCount().by(<span class="string"><span class="delimiter">'</span><span class="content">age</span><span class="delimiter">'</span></span>)
+==>[<span class="integer">32</span>:<span class="integer">1</span>,<span class="integer">35</span>:<span class="integer">1</span>,<span class="integer">27</span>:<span class="integer">1</span>,<span class="integer">29</span>:<span class="integer">1</span>]</code></pre>
+</div>
</div>
-<div class="sect2">
-<h3 id="degree-centrality">Degree Centrality</h3>
<div class="paragraph">
-<p><a href="https://en.wikipedia.org/wiki/Centrality#Degree_centrality">Degree centrality</a> is a measure of the number of
-edges associated to each vertex.</p>
+<p>The result is an age distribution that simply shows that every "person" in the graph is of a different age. In some
+cases, this result is exactly what is needed, but sometimes a grouping may need to be transformed to provide a
+different picture of the result. For example, perhaps a grouping on the value "age" would be better represented by
+a domain concept such as "young", "old" and "very old".</p>
</div>
<div class="listingblock">
<div class="content">
-<pre class="CodeRay"><code class="groovy language-groovy">gremlin> g.V().group().by().by(bothE().count()) <span class="comment">//</span><b>(1)</b>
-==>[v[<span class="integer">1</span>]:<span class="integer">3</span>,v[<span class="integer">2</span>]:<span class="integer">1</span>,v[<span class="integer">3</span>]:<span class="integer">3</span>,v[<span class="integer">4</span>]:<span class="integer">3</span>,v[<span class="integer">5</span>]:<span class="integer">1</span>,v[<span class="integer">6</span>]:<span class="integer">1</span>]
-gremlin> g.V().group().by().by(inE().count()) <span class="comment">//</span><b>(2)</b>
-==>[v[<span class="integer">1</span>]:<span class="integer">0</span>,v[<span class="integer">2</span>]:<span class="integer">1</span>,v[<span class="integer">3</span>]:<span class="integer">3</span>,v[<span class="integer">4</span>]:<span class="integer">1</span>,v[<span class="integer">5</span>]:<span class="integer">1</span>,v[<span class="integer">6</span>]:<span class="integer">0</span>]
-gremlin> g.V().group().by().by(outE().count()) <span class="comment">//</span><b>(3)</b>
-==>[v[<span class="integer">1</span>]:<span class="integer">3</span>,v[<span class="integer">2</span>]:<span class="integer">0</span>,v[<span class="integer">3</span>]:<span class="integer">0</span>,v[<span class="integer">4</span>]:<span class="integer">2</span>,v[<span class="integer">5</span>]:<span class="integer">0</span>,v[<span class="integer">6</span>]:<span class="integer">1</span>]
-gremlin> g.V().project(<span class="string"><span class="delimiter">"</span><span class="content">v</span><span class="delimiter">"</span></span>,<span class="string"><span class="delimiter">"</span><span class="content">degree</span><span class="delimiter">"</span></span>).by().by(bothE().count()) <span class="comment">//</span><b>(4)</b>
-==>[<span class="key">v</span>:v[<span class="integer">1</span>],<span class="key">degree</span>:<span class="integer">3</span>]
-==>[<span class="key">v</span>:v[<span class="integer">2</span>],<span class="key">degree</span>:<span class="integer">1</span>]
-==>[<span class="key">v</span>:v[<span class="integer">3</span>],<span class="key">degree</span>:<span class="integer">3</span>]
-==>[<span class="key">v</span>:v[<span class="integer">4</span>],<span class="key">degree</span>:<span class="integer">3</span>]
-==>[<span class="key">v</span>:v[<span class="integer">5</span>],<span class="key">degree</span>:<span class="integer">1</span>]
-==>[<span class="key">v</span>:v[<span class="integer">6</span>],<span class="key">degree</span>:<span class="integer">1</span>]
-gremlin> g.V().project(<span class="string"><span class="delimiter">"</span><span class="content">v</span><span class="delimiter">"</span></span>,<span class="string"><span class="delimiter">"</span><span class="content">degree</span><span class="delimiter">"</span></span>).by().by(bothE().count()). <span class="comment">//</span><b>(5)</b>
- order().by(select(<span class="string"><span class="delimiter">"</span><span class="content">degree</span><span class="delimiter">"</span></span>), decr).
- limit(<span class="integer">4</span>)
-==>[<span class="key">v</span>:v[<span class="integer">1</span>],<span class="key">degree</span>:<span class="integer">3</span>]
-==>[<span class="key">v</span>:v[<span class="integer">3</span>],<span class="key">degree</span>:<span class="integer">3</span>]
-==>[<span class="key">v</span>:v[<span class="integer">4</span>],<span class="key">degree</span>:<span class="integer">3</span>]
-==>[<span class="key">v</span>:v[<span class="integer">2</span>],<span class="key">degree</span>:<span class="integer">1</span>]</code></pre>
+<pre class="CodeRay"><code class="groovy language-groovy">gremlin> g.V().hasLabel(<span class="string"><span class="delimiter">"</span><span class="content">person</span><span class="delimiter">"</span></span>).groupCount().by(values(<span class="string"><span class="delimiter">"</span><span class="content">age</span><span class="delimiter">"</span></span>).choose(
+ is(lt(<span class="integer">28</span>)),constant(<span class="string"><span class="delimiter">"</span><span class="content">young</span><span class="delimiter">"</span></span>),
+ choose(is(lt(<span class="integer">30</span>)),
+ constant(<span class="string"><span class="delimiter">"</span><span class="content">old</span><span class="delimiter">"</span></span>),
+ constant(<span class="string"><span class="delimiter">"</span><span class="content">very old</span><span class="delimiter">"</span></span>))))
+==>[<span class="key">young</span>:<span class="integer">1</span>,<span class="key">old</span>:<span class="integer">1</span>,very <span class="key">old</span>:<span class="integer">2</span>]</code></pre>
+</div>
+</div>
+<div class="paragraph">
+<p>Note that the <code>by</code> modulator has been altered from simply taking a string key of "age" to take a <code>Traversal</code>. That
+inner <code>Traversal</code> utilizes <code>choose</code> which is like an <code>if-then-else</code> clause. The <code>choose</code> is nested and would look
+like the following in Java:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="CodeRay"><code class="java language-java"><span class="keyword">if</span> (age < <span class="integer">28</span>) {
+ <span class="keyword">return</span> <span class="string"><span class="delimiter">"</span><span class="content">young</span><span class="delimiter">"</span></span>;
+} <span class="keyword">else</span> {
+ <span class="keyword">if</span> (age < <span class="integer">30</span>) {
+ <span class="keyword">return</span> <span class="string"><span class="delimiter">"</span><span class="content">old</span><span class="delimiter">"</span></span>;
+ } <span class="keyword">else</span> {
+ <span class="keyword">return</span> <span class="string"><span class="delimiter">"</span><span class="content">very old</span><span class="delimiter">"</span></span>;
+ }
+}</code></pre>
+</div>
+</div>
+<div class="paragraph">
+<p>The use of <code>choose</code> is a good intutive choice for this <code>Traversal</code> as it is a natural mapping to <code>if-then-else</code>, but
+there is another option to consider with <code>coalesce</code>:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="CodeRay"><code class="groovy language-groovy">gremlin> g.V().hasLabel(<span class="string"><span class="delimiter">"</span><span class="content">person</span><span class="delimiter">"</span></span>).
+ groupCount().by(values(<span class="string"><span class="delimiter">"</span><span class="content">age</span><span class="delimiter">"</span></span>).
+ coalesce(is(lt(<span class="integer">28</span>)).constant(<span class="string"><span class="delimiter">"</span><span class="content">young</span><span class="delimiter">"</span></span>),
+ is(lt(<span class="integer">30</span>)).constant(<span class="string"><span class="delimiter">"</span><span class="content">old</span><span class="delimiter">"</span></span>),
+ constant(<span class="string"><span class="delimiter">"</span><span class="content">very old</span><span class="delimiter">"</span></span>)))
+==>[<span class="key">young</span>:<span class="integer">1</span>,<span class="key">old</span>:<span class="integer">1</span>,very <span class="key">old</span>:<span class="integer">2</span>]</code></pre>
+</div>
+</div>
+<div class="paragraph">
+<p>The answer is the same, but this traversal removes the nested <code>choose</code>, which makes it easier to read.</p>
+</div>
+</div>
+</div>
+<div class="sect1">
+<h2 id="pagination">Pagination</h2>
+<div class="sectionbody">
+<div class="paragraph">
+<p><span class="image" style="float: left"><img src="../images/gremlin-paging.png" alt="gremlin-paging" width="330"></span>In most database applications, it is oftentimes desireable to return
+discrete blocks of data for a query rather than all of the data that the total results would contain. This approach to
+returning data is referred to as "pagination" and typically involves a situation where the client executing the query
+can specify the start position and end position (or the amount of data to return in lieu of the end position)
+representing the block of data to return. In this way, one could return the first ten records of one hundred, then the
+second ten records and so on, until potentially all one hundred were returned.</p>
+</div>
+<div class="paragraph">
+<p>In Gremlin, a basic approach to paging would look something like the following:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="CodeRay"><code class="groovy language-groovy">gremlin> g.V().hasLabel(<span class="string"><span class="delimiter">'</span><span class="content">person</span><span class="delimiter">'</span></span>).fold() <span class="comment">//</span><b>(1)</b>
+==>[v[<span class="integer">1</span>],v[<span class="integer">2</span>],v[<span class="integer">4</span>],v[<span class="integer">6</span>]]
+gremlin> g.V().hasLabel(<span class="string"><span class="delimiter">'</span><span class="content">person</span><span class="delimiter">'</span></span>).fold().as(<span class="string"><span class="delimiter">'</span><span class="content">persons</span><span class="delimiter">'</span></span>,<span class="string"><span class="delimiter">'</span><span class="content">count</span><span class="delimiter">'</span></span>).
+ select(<span class="string"><span class="delimiter">'</span><span class="content">persons</span><span class="delimiter">'</span></span>,<span class="string"><span class="delimiter">'</span><span class="content">count</span><span class="delimiter">'</span></span>).
+ by(range(local, <span class="integer">0</span>, <span class="integer">2</span>)).
+ by(count(local)) <span class="comment">//</span><b>(2)</b>
+==>[<span class="key">persons</span>:[v[<span class="integer">1</span>],v[<span class="integer">2</span>]],<span class="key">count</span>:<span class="integer">4</span>]
+gremlin> g.V().hasLabel(<span class="string"><span class="delimiter">'</span><span class="content">person</span><span class="delimiter">'</span></span>).fold().as(<span class="string"><span class="delimiter">'</span><span class="content">persons</span><span class="delimiter">'</span></span>,<span class="string"><span class="delimiter">'</span><span class="content">count</span><span class="delimiter">'</span></span>).
+ select(<span class="string"><span class="delimiter">'</span><span class="content">persons</span><span class="delimiter">'</span></span>,<span class="string"><span class="delimiter">'</span><span class="content">count</span><span class="delimiter">'</span></span>).
+ by(range(local, <span class="integer">2</span>, <span class="integer">4</span>)).
+ by(count(local)) <span class="comment">//</span><b>(3)</b>
+==>[<span class="key">persons</span>:[v[<span class="integer">4</span>],v[<span class="integer">6</span>]],<span class="key">count</span>:<span class="integer">4</span>]</code></pre>
</div>
</div>
<div class="colist arabic">
<ol>
<li>
-<p>Calculation of degree centrality which counts all incident edges on each vertex to include those that are both
-incoming and outgoing.</p>
+<p>Gets all the "person" vertices.</p>
</li>
<li>
-<p>Calculation of in-degree centrality which only counts incoming edges to a vertex.</p>
+<p>Gets the first two "person" vertices and includes the total number of vertices so that the client knows how many
+it has to page through.</p>
</li>
<li>
-<p>Calculation of out-degree centrality which only counts outgoing edges from a vertex.</p>
-</li>
-<li>
-<p>The previous examples all produce a single <code>Map</code> as their output. While that is a desireable output, producing a
-stream of <code>Map</code> objects can allow some greater flexibility.</p>
-</li>
-<li>
-<p>For example, use of a stream enables use of an ordered limit that can be executed in a distributed fashion in
-OLAP traversals.</p>
+<p>Gets the final two "person" vertices.</p>
</li>
</ol>
</div>
+<div class="paragraph">
+<p>From a functional perspective, the above example shows a fairly standard paging model. Unfortunately, there is a
+problem. To get the total number of vertices, the traversal must first <code>fold()</code> them, which iterates out
+the traversal bringing them all into memory. If the number of "person" vertices is large, that step could lead to a
+long running traversal and perhaps one that would simply run out of memory prior to completion. There is no shortcut
+to getting a total count without doing a full iteration of the traversal. If the requirement for a total count is
+removed then the traversals become more simple:</p>
+</div>
+<div class="listingblock">
+<div class="content">
+<pre class="CodeRay"><code class="groovy language-groovy">gremlin> g.V().hasLabel(<span class="string"><span class="delimiter">'</span><span class="content">person</span><span class="delimiter">'</span></span>).range(<span class="integer">0</span>,<span class="integer">2</span>)
+==>v[<span class="integer">1</span>]
+==>v[<span class="integer">2</span>]
+gremlin> g.V().hasLabel(<span class="string"><span class="delimiter">'</span><span class="content">person</span><span class="delimiter">'</span></span>).range(<span class="integer">2</span>,<span class="integer">4</span>)
+==>v[<span class="integer">4</span>]
+==>v[<span class="integer">6</span>]</code></pre>
+</div>
+</div>
<div class="admonitionblock note">
<table>
<tr>
@@ -1372,211 +1500,182 @@ OLAP traversals.</p>
<div class="title">Note</div>
</td>
<td class="content">
-The <a href="http://tinkerpop.apache.org/docs/3.2.3-SNAPSHOT/reference/#group-step">group</a> step takes up to two separate
-<a href="http://tinkerpop.apache.org/docs/3.2.3-SNAPSHOT/reference/#by-step">by</a> modulators. The first <code>by()</code> tells <code>group()</code>
-what the key in the resulting <code>Map</code> will be (i.e. the value to group on). In the above examples, the <code>by()</code> is empty
-and as a result, the grouping will be on the incoming <code>Vertex</code> object itself. The second <code>by()</code> is the value to be
-stored in the <code>Map</code> for each key.
+The first traversal above could also be written as <code>g.V().hasLabel('person').limit(2)</code>.
</td>
</tr>
</table>
</div>
-</div>
-<div class="sect2">
-<h3 id="betweeness-centrality">Betweeness Centrality</h3>
<div class="paragraph">
-<p><a href="https://en.wikipedia.org/wiki/Betweenness_centrality">Betweeness centrality</a> is a measure of the number of times
-a vertex is found between the <a href="#shortest-path">shortest path</a> of each vertex pair in a graph. Consider the following
-graph for demonstration purposes:</p>
+<p>In this case, there is no way to know the total count so the only way to know if the end of the results have been
+reached is to count the results from each paged result to see if there’s less than the number expected or simply zero
+results. In that case, further requests for additional pages would be uncessary. Of course, this approach is not
+free of problems either. Most graph databases will not optimize the <code>range()</code> step, meaning that the second traversal
+will repeat the iteration of the first two vertices to get to the second set of two vertices. In other words, for the
+second traversal, the graph will still read four vertices even though there was only a request for two.</p>
</div>
<div class="paragraph">
-<p><span class="image"><img src="../images/betweeness-example.png" alt="betweeness-example" width="600"></span></p>
+<p>The only way to completely avoid that problem is to re-use the same traversal instance:</p>
</div>
<div class="listingblock">
<div class="content">
-<pre class="CodeRay"><code class="groovy language-groovy">gremlin> a = graph.addVertex(<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>)
-==>v[<span class="integer">0</span>]
-gremlin> b = graph.addVertex(<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>)
+<pre class="CodeRay"><code class="groovy language-groovy">gremlin> t = g.V().hasLabel(<span class="string"><span class="delimiter">'</span><span class="content">person</span><span class="delimiter">'</span></span>);<span class="type">[]</span>
+gremlin> t.next(<span class="integer">2</span>)
+==>v[<span class="integer">1</span>]
==>v[<span class="integer">2</span>]
-gremlin> c = graph.addVertex(<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>)
+gremlin> t.next(<span class="integer">2</span>)
==>v[<span class="integer">4</span>]
-gremlin> d = graph.addVertex(<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>)
-==>v[<span class="integer">6</span>]
-gremlin> e = graph.addVertex(<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>)
-==>v[<span class="integer">8</span>]
-gremlin> a.addEdge(<span class="string"><span class="delimiter">'</span><span class="content">next</span><span class="delimiter">'</span></span>,b)
-==>e[<span class="integer">10</span>][<span class="integer">0</span>-next-><span class="integer">2</span>]
-gremlin> b.addEdge(<span class="string"><span class="delimiter">'</span><span class="content">next</span><span class="delimiter">'</span></span>,c)
-==>e[<span class="integer">11</span>][<span class="integer">2</span>-next-><span class="integer">4</span>]
-gremlin> c.addEdge(<span class="string"><span class="delimiter">'</span><span class="content">next</span><span class="delimiter">'</span></span>,d)
-==>e[<span class="integer">12</span>][<span class="integer">4</span>-next-><span class="integer">6</span>]
-gremlin> d.addEdge(<span class="string"><span class="delimiter">'</span><span class="content">next</span><span class="delimiter">'</span></span>,e)
-==>e[<span class="integer">13</span>][<span class="integer">6</span>-next-><span class="integer">8</span>]
-gremlin> g.withSack(<span class="integer">0</span>).V().store(<span class="string"><span class="delimiter">"</span><span class="content">x</span><span class="delimiter">"</span></span>).repeat(both().simplePath()).emit().path(). <span class="comment">//</span><b>(1)</b>
- group().by(project(<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>).by(limit(local, <span class="integer">1</span>)). <span class="comment">//</span><b>(2)</b>
- by(tail(local, <span class="integer">1</span>))).
- by(order().by(count(local))). <span class="comment">//</span><b>(3)</b>
- select(values).as(<span class="string"><span class="delimiter">"</span><span class="content">shortestPaths</span><span class="delimiter">"</span></span>). <span class="comment">//</span><b>(4)</b>
- select(<span class="string"><span class="delimiter">"</span><span class="content">x</span><span class="delimiter">"</span></span>).unfold().as(<span class="string"><span class="delimiter">"</span><span class="content">v</span><span class="delimiter">"</span></span>). <span class="comment">//</span><b>(5)</b>
- select(<span class="string"><span class="delimiter">"</span><span class="content">shortestPaths</span><span class="delimiter">"</span></span>). <span class="comment">//</span><b>(6)</b>
- map(unfold().filter(unfold().where(eq(<span class="string"><span class="delimiter">"</span><span class="content">v</span><span class="delimiter">"</span></span>))).count()). <span class="comment">//</span><b>(7)</b>
- sack(sum).sack().as(<span class="string"><span class="delimiter">"</span><span class="content">betweeness</span><span class="delimiter">"</span></span>). <span class="comment">//</span><b>(8)</b>
- select(<span class="string"><span class="delimiter">"</span><span class="content">v</span><span class="delimiter">"</span></span>,<span class="string"><span class="delimiter">"</span><span class="content">betweeness</span><span class="delimiter">"</span></span>)
-==>[<span class="key">v</span>:v[<span class="integer">0</span>],<span class="key">betweeness</span>:<span class="integer">8</span>]
-==>[<span class="key">v</span>:v[<span class="integer">2</span>],<span class="key">betweeness</span>:<span class="integer">14</span>]
-==>[<span class="key">v</span>:v[<span class="integer">4</span>],<span class="key">betweeness</span>:<span class="integer">16</span>]
-==>[<span class="key">v</span>:v[<span class="integer">6</span>],<span class="key">betweeness</span>:<span class="integer">14</span>]
-==>[<span class="key">v</span>:v[<span class="integer">8</span>],<span class="key">betweeness</span>:<span class="integer">8</span>]</code></pre>
+==>v[<span class="integer">6</span>]</code></pre>
</div>
</div>
-<div class="colist arabic">
-<ol>
-<li>
-<p>Defines a Gremlin <a href="http://tinkerpop.apache.org/docs/3.2.3-SNAPSHOT/reference/#sack-step">sack</a> with a value of zero,
-which represents the initial betweeness score for each vertex, and traverses on both incoming and outgoing edges
-avoiding <a href="#cycle-detection">cyclic paths</a>.</p>
-</li>
-<li>
-<p>Group each path by the first and last vertex.</p>
-</li>
-<li>
-<p>Reduce the list of paths to the shortest path between the first and last vertex by ordering on their lengths.</p>
-</li>
-<li>
-<p>Recall that at this point, there is a <code>Map</code> keyed by first and last vertex and with a value of just the shortest
-path. Extract the shortest path with <code>select(values)</code>, since that’s the only portion required for the remainder of
-the traversal.</p>
-</li>
-<li>
-<p>The "x" key contains the list of vertices stored from step 1 - unfold that list into "v" for later use. This step
-will unwrap the vertex that is stored in the <code>Traverser</code> as
-<a href="http://tinkerpop.apache.org/javadocs/3.2.3-SNAPSHOT/full/org/apache/tinkerpop/gremlin/process/traversal/step/util/BulkSet.html">BulkSet</a>
-so that it can be used directly in the <code>Traversal</code>.</p>
-</li>
-<li>
-<p>Iterate the set of shortest paths. At this point, it is worth noting that the traversal is iterating each vertex
-in "v" and for each vertex in "v" it is iterating each <code>Path</code> in "shortestpaths".</p>
-</li>
-<li>
-<p>For each path, transform it to a count of the number of times that "v" from step 5 is encountered.</p>
-</li>
-<li>
-<p>Sum the counts for each vertex using <code>sack()</code>, normalize the value and label it as the "betweeness" to be the score.</p>
-</li>
-</ol>
</div>
</div>
-<div class="sect2">
-<h3 id="closeness-centrality">Closeness Centrality</h3>
+<div class="sect1">
+<h2 id="shortest-path">Shortest Path</h2>
+<div class="sectionbody">
<div class="paragraph">
-<p><a href="https://en.wikipedia.org/wiki/Centrality">Closeness centrality</a> is a measure of the distance of one vertex to all
-other reachable vertices in the graph.</p>
+<p><span class="image"><img src="../images/shortest-path.png" alt="shortest-path" width="300"></span></p>
+</div>
+<div class="paragraph">
+<p>When working with a graph, it is often necessary to identify the
+<a href="https://en.wikipedia.org/wiki/Shortest_path_problem">shortest path</a> between two identified vertices. The following
+is a simple example that identifies the shortest path between vertex "1" and vertex "5" while traversing over out edges:</p>
</div>
<div class="listingblock">
<div class="content">
-<pre class="CodeRay"><code class="groovy language-groovy">gremlin> g.withSack(<span class="float">1f</span>).V().repeat(both().simplePath()).emit().path(). <span class="comment">//</span><b>(1)</b>
- group().by(project(<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>).by(limit(local, <span class="integer">1</span>)). <span class="comment">//</span><b>(2)</b>
- by(tail(local, <span class="integer">1</span>))).
- by(order().by(count(local))). <span class="comment">//</span><b>(3)</b>
- select(values).unfold(). <span class="comment">//</span><b>(4)</b>
- project(<span class="string"><span class="delimiter">"</span><span class="content">v</span><span class="delimiter">"</span></span>,<span class="string"><span class="delimiter">"</span><span class="content">length</span><span class="delimiter">"</span></span>).
- by(limit(local, <span class="integer">1</span>)). <span class="comment">//</span><b>(5)</b>
- by(count(local).sack(div).sack()). <span class="comment">//</span><b>(6)</b>
- group().by(select(<span class="string"><span class="delimiter">"</span><span class="content">v</span><span class="delimiter">"</span></span>)).by(select(<span class="string"><span class="delimiter">"</span><span class="content">length</span><span class="delimiter">"</span></span>).sum()) <span class="comment">//</span><b>(7)</b>
-==>[v[<span class="integer">1</span>]:<span class="float">2.1666666666666665</span>,v[<span class="integer">2</span>]:<span class="float">1.6666666666666665</span>,v[<span class="integer">3</span>]:<span class="float">2.1666666666666665</span>,v[<span class="integer">4</span>]:<span class="float">2.1666666666666665</span>,v[<span class="integer">5</span>]:<span class="float">1.6666666666666665</span>,v[<span class="integer">6</span>]:<span class="float">1.6666666666666665</span>]</code></pre>
+<pre class="CodeRay"><code class="groovy language-groovy">gremlin> graph = TinkerGraph.open()
+==>tinkergraph[<span class="key">vertices</span>:<span class="integer">0</span> <span class="key">edges</span>:<span class="integer">0</span>]
+gremlin> v1 = graph.addVertex(T.id, <span class="integer">1</span>)
+==>v[<span class="integer">1</span>]
+gremlin> v2 = graph.addVertex(T.id, <span class="integer">2</span>)
+==>v[<span class="integer">2</span>]
+gremlin> v3 = graph.addVertex(T.id, <span class="integer">3</span>)
+==>v[<span class="integer">3</span>]
+gremlin> v4 = graph.addVertex(T.id, <span class="integer">4</span>)
+==>v[<span class="integer">4</span>]
+gremlin> v5 = graph.addVertex(T.id, <span class="integer">5</span>)
+==>v[<span class="integer">5</span>]
+gremlin> v1.addEdge(<span class="string"><span class="delimiter">"</span><span class="content">knows</span><span class="delimiter">"</span></span>, v2)
+==>e[<span class="integer">0</span>][<span class="integer">1</span>-knows-><span class="integer">2</span>]
+gremlin> v2.addEdge(<span class="string"><span class="delimiter">"</span><span class="content">knows</span><span class="delimiter">"</span></span>, v4)
+==>e[<span class="integer">1</span>][<span class="integer">2</span>-knows-><span class="integer">4</span>]
+gremlin> v4.addEdge(<span class="string"><span class="delimiter">"</span><span class="content">knows</span><span class="delimiter">"</span></span>, v5)
+==>e[<span class="integer">2</span>][<span class="integer">4</span>-knows-><span class="integer">5</span>]
+gremlin> v2.addEdge(<span class="string"><span class="delimiter">"</span><span class="content">knows</span><span class="delimiter">"</span></span>, v3)
+==>e[<span class="integer">3</span>][<span class="integer">2</span>-knows-><span class="integer">3</span>]
+gremlin> v3.addEdge(<span class="string"><span class="delimiter">"</span><span class="content">knows</span><span class="delimiter">"</span></span>, v4)
+==>e[<span class="integer">4</span>][<span class="integer">3</span>-knows-><span class="integer">4</span>]
+gremlin> g = graph.traversal()
+==>graphtraversalsource[tinkergraph[<span class="key">vertices</span>:<span class="integer">5</span> <span class="key">edges</span>:<span class="integer">5</span>], standard]
+gremlin> g.V(<span class="integer">1</span>).repeat(out().simplePath()).until(hasId(<span class="integer">5</span>)).path().limit(<span class="integer">1</span>) <span class="comment">//</span><b>(1)</b>
+==>[v[<span class="integer">1</span>],v[<span class="integer">2</span>],v[<span class="integer">4</span>],v[<span class="integer">5</span>]]
+gremlin> g.V(<span class="integer">1</span>).repeat(out().simplePath()).until(hasId(<span class="integer">5</span>)).path().count(local) <span class="comment">//</span><b>(2)</b>
+==><span class="integer">4</span>
+==><span class="integer">5</span>
+gremlin> g.V(<span class="integer">1</span>).repeat(out().simplePath()).until(hasId(<span class="integer">5</span>)).path().
+ group().by(count(local)).next() <span class="comment">//</span><b>(3)</b>
+==><span class="integer">4</span>=[[v[<span class="integer">1</span>], v[<span class="integer">2</span>], v[<span class="integer">4</span>], v[<span class="integer">5</span>]]]
+==><span class="integer">5</span>=[[v[<span class="integer">1</span>], v[<span class="integer">2</span>], v[<span class="integer">3</span>], v[<span class="integer">4</span>], v[<span class="integer">5</span>]]]</code></pre>
</div>
</div>
<div class="colist arabic">
<ol>
<li>
-<p>Defines a Gremlin <a href="http://tinkerpop.apache.org/docs/3.2.3-SNAPSHOT/reference/#sack-step">sack</a> with a value of one,
-and traverses on both incoming and outgoing edges avoiding <a href="#cycle-detection">cyclic paths</a>.</p>
-</li>
-<li>
-<p>Group each path by the first and last vertex.</p>
-</li>
-<li>
-<p>Reduce the list of paths to the shortest path between the first and last vertex by ordering on their lengths.</p>
-</li>
-<li>
-<p>Recall that at this point, there is a <code>Map</code> keyed by first and last vertex and with a value of just the shortest
-path. Extract the shortest path with <code>select(values)</code>, since that’s the only portion required for the remainder of
-the traversal.</p>
-</li>
-<li>
-<p>The first <code>by()</code> modulator for <code>project()</code> extracts the first vertex in the path.</p>
+<p>The traversal starts at vertex with the identifier of "1" and repeatedly traverses on out edges "until" it finds a
+vertex with an identifier of "5". The inclusion of <code>simplePath</code> within the <code>repeat</code> is present to filter out repeated
+paths. The traversal terminates with <code>limit</code> in this case as the first path returned will be the shortest one. Of
+course, it is possible for there to be more than one path in the graph of the same length (i.e. two or more paths of
+length three), but this example is not considering that.</p>
</li>
<li>
-<p>The second <code>by()</code> modulator for <code>project()</code> extracts the path length and divides that distance by the value of
-the <code>sack()</code> which was initialized to 1 at the start of the traversal.</p>
+<p>It might be interesting to know the path lengths for all paths between vertex "1" and "5".</p>
</li>
<li>
-<p>Group the resulting <code>Map</code> objects on "v" and sum their lengths to get the centrality score for each.</p>
+<p>Alternatively, one might wish to do a path length distribution over all the paths.</p>
</li>
</ol>
</div>
-</div>
-<div class="sect2">
-<h3 id="eigenvector-centrality">Eigenvector Centrality</h3>
<div class="paragraph">
-<p>A calculation of <a href="https://en.wikipedia.org/wiki/Centrality#Eigenvector_centrality">eigenvector centrality</a> uses the
-relative importance of adjacent vertices to help determine their centrality. In other words, unlike
-<a href="#degree-centrality">degree centrality</a> the vertex with the greatest number of incident edges does not necessarily
-give it the highest rank. Consider the following example using the Grateful Dead graph:</p>
+<p>The previous example defines the length of the path by the number of vertices in the path, but the "path" might also
+be measured by data within the graph itself. The following example use the same graph structure as the previous example,
+but includes a "weight" on the edges, that will be used to help determine the "cost" of a particular path:</p>
</div>
<div class="listingblock">
<div class="content">
-<pre class="CodeRay"><code class="groovy language-groovy">gremlin> graph.io(graphml()).readGraph(<span class="string"><span class="delimiter">'</span><span class="content">data/grateful-dead.xml</span><span class="delimiter">'</span></span>)
-gremlin> g.V().repeat(groupCount(<span class="string"><span class="delimiter">'</span><span class="content">m</span><span class="delimiter">'</span></span>).by(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>).out()).times(<span class="integer">5</span>).cap(<span class="string"><span class="delimiter">'</span><span class="content">m</span><span class="delimiter">'</span></span>). <span class="comment">//</span><b>(1)</b>
- order(local).by(values, decr).limit(local, <span class="integer">10</span>).next() <span class="comment">//</span><b>(2)</b>
-==>PLAYING IN THE BAND=<span class="integer">8758598</span>
-==>ME AND MY UNCLE=<span class="integer">8214246</span>
-==>JACK STRAW=<span class="integer">8173882</span>
-==>EL PASO=<span class="integer">7666994</span>
-==>TRUCKING=<span class="integer">7643494</span>
-==>PROMISED LAND=<span class="integer">7339027</span>
-==>CHINA CAT SUNFLOWER=<span class="integer">7322213</span>
-==>CUMBERLAND BLUES=<span class="integer">6730838</span>
-==>RAMBLE ON ROSE=<span class="integer">6676667</span>
-==>LOOKS LIKE RAIN=<span class="integer">6674121</span>
-gremlin> g.V().repeat(groupCount(<span class="string"><span class="delimiter">'</span><span class="content">m</span><span class="delimiter">'</span></span>).by(<span class="string"><span class="delimiter">'</span><span class="content">name</span><span class="delimiter">'</span></span>).out().timeLimit(<span class="integer">100</span>)).times(<span class="integer">5</span>).cap(<span class="string"><span class="delimiter">'</span><span class="content">m</span><span class="delimiter">'</span></span>). <span class="comment">//</span><b>(3)</b>
- order(local).by(values, decr).limit(local, <span class="integer">10</span>).next()
-==>PLAYING IN THE BAND=<span class="integer">8758598</span>
-==>ME AND MY UNCLE=<span class="integer">8214246</span>
-==>JACK STRAW=<span class="integer">8173882</span>
-==>EL PASO=<span class="integer">7666994</span>
-==>TRUCKING=<span class="integer">7643494</span>
-==>PROMISED LAND=<span class="integer">7339027</span>
-==>CHINA CAT SUNFLOWER=<span class="integer">7322213</span>
-==>CUMBERLAND BLUES=<span class="integer">6730838</span>
-==>RAMBLE ON ROSE=<span class="integer">6676667</span>
-==>LOOKS LIKE RAIN=<span class="integer">6674121</span></code></pre>
+<pre class="CodeRay"><code class="groovy language-groovy">gremlin> graph = TinkerGraph.open()
+==>tinkergraph[<span class="key">vertices</span>:<span class="integer">0</span> <span class="key">edges</span>:<span class="integer">0</span>]
+gremlin> v1 = graph.addVertex(T.id, <span class="integer">1</span>)
+==>v[<span class="integer">1</span>]
+gremlin> v2 = graph.addVertex(T.id, <span class="integer">2</span>)
+==>v[<span class="integer">2</span>]
+gremlin> v3 = graph.addVertex(T.id, <span class="integer">3</span>)
+==>v[<span class="integer">3</span>]
+gremlin> v4 = graph.addVertex(T.id, <span class="integer">4</span>)
+==>v[<span class="integer">4</span>]
+gremlin> v5 = graph.addVertex(T.id, <span class="integer">5</span>)
+==>v[<span class="integer">5</span>]
+gremlin> v1.addEdge(<span class="string"><span class="delimiter">"</span><span class="content">knows</span><span class="delimiter">"</span></span>, v2, <span class="string"><span class="delimiter">"</span><span class="content">weight</span><span class="delimiter">"</span></span>, <span class="float">1.25</span>)
+==>e[<span class="integer">0</span>][<span class="integer">1</span>-knows-><span class="integer">2</span>]
+gremlin> v2.addEdge(<span class="string"><span class="delimiter">"</span><span class="content">knows</span><span class="delimiter">"</span></span>, v4, <span class="string"><span class="delimiter">"</span><span class="content">weight</span><span class="delimiter">"</span></span>, <span class="float">1.5</span>)
+==>e[<span class="integer">1</span>][<span class="integer">2</span>-knows-><span class="integer">4</span>]
+gremlin> v4.addEdge(<span class="string"><span class="delimiter">"</span><span class="content">knows</span><span class="delimiter">"</span></span>, v5, <span class="string"><span class="delimiter">"</span><span class="content">weight</span><span class="delimiter">"</span></span>, <span class="float">0.25</span>)
+==>e[<span class="integer">2</span>][<span class="integer">4</span>-knows-><span class="integer">5</span>]
+gremlin> v2.addEdge(<span class="string"><span class="delimiter">"</span><span class="content">knows</span><span class="delimiter">"</span></span>, v3, <span class="string"><span class="delimiter">"</span><span class="content">weight</span><span class="delimiter">"</span></span>, <span class="float">0.25</span>)
+==>e[<span class="integer">3</span>][<span class="integer">2</span>-knows-><span class="integer">3</span>]
+gremlin> v3.addEdge(<span class="string"><span class="delimiter">"</span><span class="content">knows</span><span class="delimiter">"</span></span>, v4, <span class="string"><span class="delimiter">"</span><span class="content">weight</span><span class="delimiter">"</span></span>, <span class="float">0.25</span>)
+==>e[<span class="integer">4</span>][<span class="integer">3</span>-knows-><span class="integer">4</span>]
+gremlin> g = graph.traversal()
+==>graphtraversalsource[tinkergraph[<span class="key">vertices</span>:<span class="integer">5</span> <span class="key">edges</span>:<span class="integer">5</span>], standard]
+gremlin> g.V(<span class="integer">1</span>).repeat(out().simplePath()).until(hasId(<span class="integer">5</span>)).path().
+ group().by(count(local)).next() <span class="comment">//</span><b>(1)</b>
+==><span class="integer">4</span>=[[v[<span class="integer">1</span>], v[<span class="integer">2</span>], v[<span class="integer">4</span>], v[<span class="integer">5</span>]]]
+==><span class="integer">5</span>=[[v[<span class="integer">1</span>], v[<span class="integer">2</span>], v[<span class="integer">3</span>], v[<span class="integer">4</span>], v[<span class="integer">5</span>]]]
+gremlin> g.V(<span class="integer">1</span>).repeat(outE().inV().simplePath()).until(hasId(<span class="integer">5</span>)).
+ path().by(coalesce(values(<span class="string"><span class="delimiter">'</span><span class="content">weight</span><span class="delimiter">'</span></span>),
+ constant(<span class="float">0.0</span>))).
+ map(unfold().sum()) <span class="comment">//</span><b>(2)</b>
+==><span class="float">3.00</span>
+==><span class="float">2.00</span>
+gremlin> g.V(<span class="integer">1</span>).repeat(outE().inV().simplePath()).until(hasId(<span class="integer">5</span>)).
+ path().by(constant(<span class="float">0.0</span>)).by(<span class="string"><span class="delimiter">'</span><span class="content">weight</span><span class="delimiter">'</span></span>).map(unfold().sum()) <span class="comment">//</span><b>(3)</b>
+==><span class="float">3.00</span>
+==><span class="float">2.00</span>
+gremlin> g.V(<span class="integer">1</span>).repeat(outE().inV().simplePath()).until(hasId(<span class="integer">5</span>)).
+ path().as(<span class="string"><span class="delimiter">'</span><span class="content">p</span><span class="delimiter">'</span></span>).
+ map(unfold().coalesce(values(<span class="string"><span class="delimiter">'</span><span class="content">weight</span><span class="delimiter">'</span></span>),
+ constant(<span class="float">0.0</span>)).sum()).as(<span class="string"><span class="delimiter">'</span><span class="content">cost</span><span class="delimiter">'</span></span>).
+ select(<span class="string"><span class="delimiter">'</span><span class="content">cost</span><span class="delimiter">'</span></span>,<span class="string"><span class="delimiter">'</span><span class="content">p</span><span class="delimiter">'</span></span>) <span class="comment">//</span><b>(4)</b>
+==>[<span class="key">cost</span>:<span class="float">3.00</span>,<span class="key">p</span>:[v[<span class="integer">1</span>],e[<span class="integer">0</span>][<span class="integer">1</span>-knows-><span class="integer">2</span>],v[<span class="integer">2</span>],e[<span class="integer">1</span>][<span class="integer">2</span>-knows-><span class="integer">4</span>],v[<span class="integer">4</span>],e[<span class="integer">2</span>][<span class="integer">4</span>-knows-><span class="integer">5</span>],v[<span class="integer">5</span>]]]
+==>[<span class="key">cost</span>:<span class="float">2.00</span>,<span class="key">p</span>:[v[<span class="integer">1</span>],e[<span class="integer">0</span>][<span class="integer">1</span>-knows-><span class="integer">2</span>],v[<span class="integer">2</span>],e[<span class="integer">3</span>][<span class="integer">2</span>-knows-><span class="integer">3</span>],v[<span class="integer">3</span>],e[<span class="integer">4</span>][<span class="integer">3</span>-knows-><span class="integer">4</span>],v[<span class="integer">4</span>],e[<span class="integer">2</span>][<span class="integer">4</span>-knows-><span class="integer">5</span>],v[<span class="integer">5</span>]]]</code></pre>
</div>
</div>
[... 62 lines stripped ...]