{"id":13320,"date":"2017-08-02T15:28:18","date_gmt":"2017-08-02T15:28:18","guid":{"rendered":"http:\/\/www.doanduyhai.com\/blog\/?p=13320"},"modified":"2017-08-08T21:01:03","modified_gmt":"2017-08-08T21:01:03","slug":"gremlin-recipes-5-path-object","status":"publish","type":"post","link":"https:\/\/www.doanduyhai.com\/blog\/?p=13320","title":{"rendered":"Gremlin recipes: 5 &#8211; Path object"},"content":{"rendered":"<p>This blog post is the 5<sup>th<\/sup> from the series <strong>Gremlin Recipes<\/strong>. It is recommended to read the previous blog posts first: <\/p>\n<ol>\n<li><a href=\"https:\/\/www.doanduyhai.com\/blog\/?p=13224\" target=\"_blank\"><strong>Gremlin as a Stream<\/strong><\/a><\/li>\n<li><a href=\"https:\/\/www.doanduyhai.com\/blog\/?p=13260\" target=\"_blank\"><strong>SQL to Gremlin<\/strong><\/a><\/li>\n<li><a href=\"https:\/\/www.doanduyhai.com\/blog\/?p=13285\" target=\"_blank\"><strong>Recommendation Engine traversal<\/strong><\/a><\/li>\n<li><a href=\"https:\/\/www.doanduyhai.com\/blog\/?p=13301\" target=\"_blank\"><strong>Recursive traversals<\/strong><\/a><\/li>\n<\/ol>\n<p><!--more--><\/p>\n<h1>I London_Tube dataset<\/h1>\n<p>To illustrate this series of recipes, you need first to create the schema for <strong>London_Tube<\/strong> and import the data. <\/p>\n<p>The graph schema of this dataset is :<\/p>\n<div id=\"attachment_13322\" style=\"width: 850px\" class=\"wp-caption aligncenter\"><img aria-describedby=\"caption-attachment-13322\" loading=\"lazy\" src=\"https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/LondonTube_Schema-1024x327.png\" alt=\"LondonTube_Schema\" width=\"840\" height=\"268\" class=\"size-large wp-image-13322\" srcset=\"https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/LondonTube_Schema-1024x327.png 1024w, https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/LondonTube_Schema-300x96.png 300w, https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/LondonTube_Schema-768x246.png 768w, https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/LondonTube_Schema-1170x374.png 1170w, https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/LondonTube_Schema.png 1514w\" sizes=\"(max-width: 840px) 100vw, 840px\" \/><p id=\"caption-attachment-13322\" class=\"wp-caption-text\">LondonTube_Schema<\/p><\/div>\n<p>The schema is pretty simple, we have a single vertex label station with the following properties:<\/p>\n<ul>\n<li><strong>name<\/strong>: the station name<\/li>\n<li><strong>lines<\/strong>: a collection of tube lines to which this station belongs<\/li>\n<li><strong>is_rail<\/strong>: whether the staton belongs to the railway system<\/li>\n<li><strong>zone<\/strong>: the zone in which the station belongs to. It is not an integer since zone 2.5 can exists &#8230;<\/li>\n<\/ul>\n<p><span id=\"killrvideo_dataset\"><strong>INSERTING DATA<\/strong><\/span><br \/>\nFirst, open the <strong><a href=\"http:\/\/tinkerpop.apache.org\/docs\/3.1.1-incubating\/tutorials\/the-gremlin-console\/\" target =\"_blank\">Gremlin console<\/a><\/strong> or <strong><a href=\"https:\/\/www.datastax.com\/products\/datastax-studio-and-development-tools#DataStax-Studio\" target=\"_blank\">Datastax Studio<\/a><\/strong> (whichever works fine) and execute the following statements:<\/p>\n<div class=\"accordion \"  ><br \/>\n  <div class=\"accordion-group\">\r\n        <div class=\"accordion-heading\">\r\n        <a class=\"accordion-toggle\" data-toggle=\"collapse\" \r\n        data-parent=\"#accordion2\" href=\"#accordian_item_938\">Open-source Gremlin Console config<\/a>\r\n        <\/div>\r\n         <div id=\"accordian_item_938\" class=\"accordion-body collapse in\">\r\n            <div class=\"accordion-inner\"><\/p>\n<pre class=\"brush: java; title: ; wrap-lines: false; notranslate\" title=\"\">\r\n:remote connect tinkerpop.server conf\/remote.yaml session-manage\r\n:remote config timeout max\r\n:remote console\r\nsystem.graph('London_Tube'). ifNotExists().create()\r\n:remote config alias g London_Tube.g\r\n<\/pre>\n<p><\/div>\r\n         <\/div>\r\n        <\/div><\/div>\n<div class=\"accordion \"  ><br \/>\n  <div class=\"accordion-group\">\r\n        <div class=\"accordion-heading\">\r\n        <a class=\"accordion-toggle\" data-toggle=\"collapse\" \r\n        data-parent=\"#accordion2\" href=\"#accordian_item_942\">KillrVideo schema & data loading<\/a>\r\n        <\/div>\r\n         <div id=\"accordian_item_942\" class=\"accordion-body collapse in\">\r\n            <div class=\"accordion-inner\"><\/p>\n<pre class=\"brush: java; title: ; wrap-lines: false; notranslate\" title=\"\">\r\nschema.clear();\r\nschema.propertyKey(&quot;zone&quot;).Double().single().create();\r\nschema.propertyKey(&quot;line&quot;).Text().single().create();\r\nschema.propertyKey(&quot;name&quot;).Text().single().create();\r\nschema.propertyKey(&quot;id&quot;).Int().single().create();\r\nschema.propertyKey(&quot;is_rail&quot;).Boolean().single().create();\r\nschema.propertyKey(&quot;lines&quot;).Text().multiple().create();\r\nschema.edgeLabel(&quot;connectedTo&quot;).multiple().properties(&quot;line&quot;).create();\r\nschema.vertexLabel(&quot;station&quot;).partitionKey(&quot;id&quot;).properties(&quot;name&quot;, &quot;zone&quot;, &quot;is_rail&quot;, &quot;lines&quot;).create();\r\nschema.vertexLabel(&quot;station&quot;).index(&quot;search&quot;).search().by(&quot;name&quot;).asText().by(&quot;zone&quot;).by(&quot;is_rail&quot;).by(&quot;lines&quot;).asText().add();\r\nschema.vertexLabel(&quot;station&quot;).index(&quot;stationByName&quot;).materialized().by(&quot;name&quot;).add();\r\nschema.vertexLabel(&quot;station&quot;).index(&quot;toStationByLine&quot;).outE(&quot;connectedTo&quot;).by(&quot;line&quot;).add();\r\nschema.vertexLabel(&quot;station&quot;).index(&quot;fromStationByLine&quot;).inE(&quot;connectedTo&quot;).by(&quot;line&quot;).add();\r\nschema.edgeLabel(&quot;connectedTo&quot;).connection(&quot;station&quot;, &quot;station&quot;).add();\r\n\r\nschema.config().option(&quot;tx_autostart&quot;).set(true);\r\n\r\n\/\/ Load data from file london_tube.gryo\r\ngraph.io(IoCore.gryo()).readGraph(&quot;\/path\/to\/london_tube.gryo&quot;);\r\n<\/pre>\n<p><\/div>\r\n         <\/div>\r\n        <\/div><\/div>\n<p>The file <strong>london_tube.gryo<\/strong> can be downloaded <a href=\"https:\/\/drive.google.com\/open?id=0B3qV2Nx-GibgU0pxQS1SbXF0STA\" target=\"_blank\"><strong>here<\/strong><\/a><\/p>\n<h1>II Path object<\/h1>\n<p>In this post we will explore the usage of <strong>Gremlin<\/strong> path object. Let&#8217;s say we want to know the &#8220;path&#8221; between the station <strong>South Kensington<\/strong> and all its neighbours stations. First let&#8217;s create a classical traversal:<\/p>\n<pre class=\"brush: java; title: ; wrap-lines: false; notranslate\" title=\"\">\r\ngremlin&gt;g.V().\r\n  has(&quot;station&quot;, &quot;name&quot;, &quot;South Kensington&quot;). \r\n  union(identity(), both(&quot;connectedTo&quot;))\r\n<\/pre>\n<p>Please notice the usage of <code><strong>both(\"connectedTo\")<\/strong><\/code>. Indeed the direction of the connection between 2 stations does not matter but since <strong>Gremlin<\/strong> is a directed graph we need to use <code><strong>both()<\/strong><\/code>.<\/p>\n<p>The step <code><strong>union(identity(), both(\"connectedTo\"))<\/strong><\/code> will output the original station <strong>South Kensington<\/strong> along side with its neighbours. <\/p>\n<div id=\"attachment_13324\" style=\"width: 850px\" class=\"wp-caption aligncenter\"><img aria-describedby=\"caption-attachment-13324\" loading=\"lazy\" src=\"https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_neighbours-1024x396.png\" alt=\"SouthKensington_neighbours\" width=\"840\" height=\"325\" class=\"size-large wp-image-13324\" srcset=\"https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_neighbours-1024x396.png 1024w, https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_neighbours-300x116.png 300w, https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_neighbours-768x297.png 768w, https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_neighbours-1170x453.png 1170w, https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_neighbours.png 1396w\" sizes=\"(max-width: 840px) 100vw, 840px\" \/><p id=\"caption-attachment-13324\" class=\"wp-caption-text\">SouthKensington_neighbours<\/p><\/div>\n<p>So what is a <em>&#8220;path&#8221;<\/em> in <strong>Gremlin<\/strong> ? According to the JavaDoc:<\/p>\n<blockquote><p>A Path denotes a particular walk through a Graph as defined by a Traversal. In abstraction, any Path implementation maintains two lists: <strong>a list of sets of labels and a list of objects<\/strong>. The list of labels are the labels of the steps traversed. The list of objects are the objects traversed.<\/p><\/blockquote>\n<p>In a nutshell, the path object implements the interface <code><strong>Iterator&lt;Object&gt;<\/strong><\/code><Object>, <code><strong>Object<\/strong><\/code> can be anything among:<\/p>\n<ul>\n<li>all <strong>labels<\/strong> created on the traversal (using the modulator <code><strong>as(\"label\")<\/strong><\/code>)<\/li>\n<li>all <strong>vertices<\/strong> visited by the traversal<\/li>\n<li>all <strong>edges<\/strong> visited by the traversal<\/li>\n<li>all <strong>side-effects<\/strong> or <strong>data structures<\/strong> created during the traversal<\/li>\n<\/ul>\n<p>To display the path that connects <strong>South Kensington<\/strong> to its neighbours:<\/p>\n<pre class=\"brush: java; title: ; wrap-lines: false; notranslate\" title=\"\">\r\ngremlin&gt;g.V().                    \r\n  has(&quot;station&quot;, &quot;name&quot;, &quot;South Kensington&quot;). \/\/ Iterator&lt;Station&gt;\r\n  both(&quot;connectedTo&quot;).                        \/\/ Iterator&lt;Station&gt; \r\n  dedup().\r\n  path()                                      \/\/ Iterator&lt;Path&gt; == Iterator&lt;Iterator&lt;Object&gt;&gt;, Object == Vertex\/Edge ...\r\n==&gt;[v[{~label=station, id=236}], v[{~label=station, id=99}]]\r\n==&gt;[v[{~label=station, id=236}], v[{~label=station, id=146}]]\r\n==&gt;[v[{~label=station, id=236}], v[{~label=station, id=229}]]\r\n<\/pre>\n<p>We can see there are 3 paths that connect <strong>South Kensington<\/strong> to its neighbours. To make the display nicer let&#8217;s <strong>project<\/strong> the path object on their property <em>&#8220;name&#8221;<\/em> to display station names:<\/p>\n<pre class=\"brush: java; title: ; wrap-lines: false; notranslate\" title=\"\">\r\ngremlin&gt;g.V().                    \r\n  has(&quot;station&quot;, &quot;name&quot;, &quot;South Kensington&quot;). \/\/ Iterator&lt;Station&gt;\r\n  both(&quot;connectedTo&quot;).                        \/\/ Iterator&lt;Station&gt; \r\n  dedup().\r\n  path().                                     \/\/ Iterator&lt;Path&gt; == Iterator&lt;Iterator&lt;Object&gt;&gt;, Object == Vertex\/Edge ...\r\n    by(&quot;name&quot;)                                \/\/ Iterator&lt;Iterator&lt;String&gt;&gt;   \r\n==&gt;[South Kensington, Gloucester Road]\r\n==&gt;[South Kensington, Knightsbridge]\r\n==&gt;[South Kensington, Sloane Square]\r\n<\/pre>\n<p>We want Gremlin to help us finding the path between <strong>South Kensington<\/strong> and <strong>Covent Garden<\/strong> using the <strong>Piccadilly<\/strong> line:<\/p>\n<pre class=\"brush: java; title: ; wrap-lines: false; notranslate\" title=\"\">\r\ngremlin&gt;g.V().\r\n  has(&quot;station&quot;, &quot;name&quot;, &quot;South Kensington&quot;).  \r\n  emit().\r\n  repeat(timeLimit(200).both(&quot;connectedTo&quot;).        \/\/ Expand the graph on edge &quot;connectedTo&quot;\r\n   filter(bothE(&quot;connectedTo&quot;).                   \r\n     has(&quot;line&quot;,Search.tokenPrefix(&quot;Piccadilly&quot;))). \/\/ Only retain stations connected by &quot;Piccadilly&quot;\r\n   simplePath()).                                   \/\/ Simple path to avoid cyclic loops\r\n  has(&quot;name&quot;, &quot;Covent Garden&quot;).                     \/\/ Only retain target station &quot;Covent Garden&quot;\r\n  path().unfold()\r\n<\/pre>\n<div id=\"attachment_13326\" style=\"width: 850px\" class=\"wp-caption aligncenter\"><img aria-describedby=\"caption-attachment-13326\" loading=\"lazy\" src=\"https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_CoventGarden-1024x249.png\" alt=\"SouthKensington_CoventGarden\" width=\"840\" height=\"204\" class=\"size-large wp-image-13326\" srcset=\"https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_CoventGarden-1024x249.png 1024w, https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_CoventGarden-300x73.png 300w, https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_CoventGarden-768x187.png 768w, https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_CoventGarden-1170x285.png 1170w, https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_CoventGarden.png 1660w\" sizes=\"(max-width: 840px) 100vw, 840px\" \/><p id=\"caption-attachment-13326\" class=\"wp-caption-text\">SouthKensington_CoventGarden<\/p><\/div>\n<p>We purposely put <code><strong>emit()<\/strong><\/code> before the <code><strong>repeat()<\/strong><\/code> step so that the original <strong>South Kensington<\/strong> station is emitted alongside with all other stations on the journey.<\/p>\n<p>For the <code><strong>repeat()<\/strong><\/code> step, instead of putting a limit in term of number of times we traverse the <em>connectedTo<\/em> edge with the step <code><strong>times(x)<\/strong><\/code>, we rather set a time limit to avoid graph explosion with <code><strong>timeLimit(200)<\/strong><\/code>.<\/p>\n<p>We only collect stations which belong to the <strong>Piccadilly<\/strong> line with the prefix search filtering <code><strong>has(\"line\", Search.tokenPrefix(\"Piccadilly\"))<\/strong><\/code>. This predicate is <strong>DSE<\/strong> specific and is leveraging <a href=\"http:\/\/docs.datastax.com\/en\/dse\/5.1\/dse-dev\/datastax_enterprise\/search\/searchAbout.html\" target=\"_blank\"><strong>DSE Search<\/strong><\/a>. The filtering is performed on adjacent edges &#8220;<em>connectedTo<\/em>&#8221; thus the step <code><strong>filter(bothE(\"connectedTo\") ...)<\/strong><\/code><\/p>\n<p>Finally we filter the target station to match <strong>Covent Garden<\/strong> with the step <code><strong>has(\"name\", \"Covent Garden\")<\/strong><\/code>. If we were to stop our traversal at this step, there will be a single displayed station, which is <strong>Covent Garden<\/strong>.<\/p>\n<p>What we want is different: all the stations of the journey from <strong>South Kensington<\/strong> to <strong>Covent Garden<\/strong> and here <code><strong>path()<\/strong><\/code> step comes in handy.<\/p>\n<p>Since we only visit vertices on our traversal, the step <code><strong>path<\/strong><\/code> is of type <code><strong>Iterator&lt;Iterator&lt;Vertex&gt;&gt;<\/strong><\/code>, the outer <code><strong>Iterator<\/strong><\/code> represents the <code><strong>Traversal<\/strong><\/code> object itself. To access the inner <code><strong>Iterator&lt;Vertex&gt;<\/strong><\/code> we need to use the <code><strong>unfold()<\/strong><\/code> operator.<\/p>\n<p>So consequently <code><strong>path().unfold()<\/strong><\/code> become an <code><strong>Iterator&lt;Station&gt;<\/strong><\/code> and will display all stations from <strong>South Kensington<\/strong> to <strong>Covent Garden<\/strong><\/p>\n<p>We can check the result against the real London tube map<\/p>\n<div id=\"attachment_13328\" style=\"width: 628px\" class=\"wp-caption aligncenter\"><img aria-describedby=\"caption-attachment-13328\" loading=\"lazy\" src=\"https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/London_Tube_Map_Piccadilly.png\" alt=\"London_Tube_Map_Piccadilly\" width=\"618\" height=\"336\" class=\"size-full wp-image-13328\" srcset=\"https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/London_Tube_Map_Piccadilly.png 618w, https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/London_Tube_Map_Piccadilly-300x163.png 300w\" sizes=\"(max-width: 618px) 100vw, 618px\" \/><p id=\"caption-attachment-13328\" class=\"wp-caption-text\">London_Tube_Map_Piccadilly<\/p><\/div>\n<h1>III Finding shortest path<\/h1>\n<p>Now let&#8217;s say we want to go from <strong>South Kensington<\/strong> to <strong>Marble Arch<\/strong>, if we look at the London tube map, there are 2 possible journeys:<\/p>\n<ol>\n<li>the one that minimizes station count going through <strong>Green Park<\/strong> &amp; <strong>Bond Street<\/strong> (5 stations) but we have 2 line changes:<br \/>\n <strong>Picadilly line<\/strong> -> <strong>Jubilee line<\/strong> and then <strong>Jubilee line<\/strong> -> <strong>Central line<\/strong><\/li>\n<li>the one that minimizes the number of line changes going through <strong>Notting Hill Gate<\/strong> but with more stations (6)<\/li>\n<\/ol>\n<div id=\"attachment_13339\" style=\"width: 674px\" class=\"wp-caption aligncenter\"><img aria-describedby=\"caption-attachment-13339\" loading=\"lazy\" src=\"https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_MarbleArch.png\" alt=\"SouthKensington_MarbleArch\" width=\"664\" height=\"600\" class=\"size-full wp-image-13339\" srcset=\"https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_MarbleArch.png 664w, https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_MarbleArch-300x271.png 300w\" sizes=\"(max-width: 664px) 100vw, 664px\" \/><p id=\"caption-attachment-13339\" class=\"wp-caption-text\">SouthKensington_MarbleArch<\/p><\/div>\n<p>So let&#8217;s see how we can ask <strong>Gremlin<\/strong> to find the path that <strong>minimizes station count<\/strong>:<\/p>\n<pre class=\"brush: java; title: ; wrap-lines: false; notranslate\" title=\"\">\r\ngremlin&gt;g.V().\r\n  has(&quot;station&quot;, &quot;name&quot;, &quot;South Kensington&quot;).              \/\/ Iterator&lt;Station&gt;\r\n  emit().\r\n  repeat(both(&quot;connectedTo&quot;).simplePath().timeLimit(400)). \/\/ Iterator&lt;Station&gt;\r\n  has(&quot;name&quot;, &quot;Marble Arch&quot;).                              \/\/ iterator.filter(station -&gt; station.getName().equals(&quot;Marble Arch&quot;))\r\n  order().                                                 \/\/ order all the paths leading to Marble Arch \r\n    by(path().count(local), incr).                         \/\/ by number of elements(station) in each path, ASC\r\n  limit(1).                                                \/\/ take the 1st path == shortest path \r\n  path().unfold()                                          \/\/ Iterator&lt;Station&gt;\r\n<\/pre>\n<div id=\"attachment_13341\" style=\"width: 850px\" class=\"wp-caption aligncenter\"><img aria-describedby=\"caption-attachment-13341\" loading=\"lazy\" src=\"https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_MarbleArch_Path1-1024x250.png\" alt=\"SouthKensington_MarbleArch_Path1\" width=\"840\" height=\"205\" class=\"size-large wp-image-13341\" srcset=\"https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_MarbleArch_Path1-1024x250.png 1024w, https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_MarbleArch_Path1-300x73.png 300w, https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_MarbleArch_Path1-768x188.png 768w, https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_MarbleArch_Path1-1170x286.png 1170w, https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_MarbleArch_Path1.png 1792w\" sizes=\"(max-width: 840px) 100vw, 840px\" \/><p id=\"caption-attachment-13341\" class=\"wp-caption-text\">SouthKensington_MarbleArch_Path1<\/p><\/div>\n<p>Let&#8217;s analyse the above traversal. First <code><strong>repeat(both(\"connectedTo\").simplePath().timeLimit(400))<\/strong><\/code> represent graph expansion in all directions from <strong>South Kensington<\/strong> but time-limited to 400ms. <code><strong>has(\"name\", \"Marble Arch\")<\/strong><\/code> will filter all emitted stations to take only those who are <strong>Marble Arch<\/strong>. <\/p>\n<p>At this stage we have have multiple journeys leading to the same destination. Now the fun begin with the path object. <code><strong>order().by(path().count(local), incr)<\/strong><\/code> will order each found journey by the number of &#8220;object&#8221; found in the path history. The trick here is that <code><strong>path()<\/strong><\/code> represents a collection of path history e.g. <code><strong>Iterator&lt;Iterator&lt;Station&gt;&gt;<\/strong><\/code> and we want to sort them by the station count, thus <code><strong>count(local)<\/strong><\/code>. Taking the 1<sup>st<\/sup> matching path will guarantee us the journey with the minimum station count.<\/p>\n<p>The last <code><strong>path().unfold()<\/strong><\/code> is just for display purpose. We want to show the complete list of stations leading from <strong>South Kensington<\/strong> to <strong>Marble Arch<\/strong><\/p>\n<p>What if we want to minimize the number of line changes instead ? Path again! <strong>Minimizing the number of line changes is equivalent to order all the journeys by the number of distinct line values of the <em>&#8220;connectedTo&#8221;<\/em> edge in each path and then take the minimum<\/strong>. <\/p>\n<pre class=\"brush: java; title: ; wrap-lines: false; notranslate\" title=\"\">\r\ngremlin&gt;g.V().\r\n  has(&quot;station&quot;, &quot;name&quot;, &quot;South Kensington&quot;).\r\n  emit().\r\n  repeat(bothE(&quot;connectedTo&quot;).otherV().simplePath()).        \/\/ instead of both(&quot;connectedTo&quot;), we do bothE(&quot;...&quot;).otherV() to collect edges on the path and save it as &quot;paths&quot;\r\n  until(has(&quot;name&quot;, &quot;Marble Arch&quot;).or().loops().is(eq(6))). \/\/ limit graph expansion to max 6 hops\r\n  has(&quot;name&quot;, &quot;Marble Arch&quot;).\r\n  order().by(\r\n        path().unfold().                                    \/\/ Iterator&lt;Object&gt; where Object == Station &amp; Edge &quot;connectedTo&quot;\r\n        hasLabel(&quot;connectedTo&quot;).                            \/\/ only take edges &quot;connectedTo&quot;\r\n        values(&quot;line&quot;).dedup().count(),                     \/\/ take the line value on the edge, dedup &amp; count\r\n        incr).                                              \/\/ ORDER BY COUNT DISTINCT LINE NUMBER on the path, ASC\r\n    limit(1).\r\n    path().unfold().\r\n    hasLabel(&quot;station&quot;) \r\n<\/pre>\n<p>The beginning of the traversal is quite similar but now instead of doing <code><strong>both(\"connectedTo\")<\/strong><\/code> we did <code><strong>bothE(\"connectedTo\").otherV()<\/strong><\/code>. Semantically it is equivalent but the subtle difference is that now we are visiting also all <em>&#8220;connectedTo&#8221;<\/em> edges in our traversal, not only station vertices, and it is done on purpose.<\/p>\n<p>Instead of using <code><strong>timeLimit(400)<\/strong><\/code> we can also use the <code><strong>until(has(\"name\", \"Marble Arch\").or().loops().is(eq(6)))<\/strong><\/code> step to stop graph expansion whenever we find <strong>Marble Arch<\/strong> or whenever we exceed 6 hops from <strong>South Kensington<\/strong>.<\/p>\n<p>Now the ordering step is important. We unfold the path object, which now becomes an Iterator of Station vertices and <em>&#8220;connectedTo&#8221;<\/em> edges. We want to select only <em>&#8220;connectedTo&#8221;<\/em> edges thus <code><strong>hasLabel(\"connectedTo\")<\/strong><\/code>. Then we extract the <em>&#8220;line&#8221;<\/em> property, deduplicate them and count them. The ordering will be done on this distinct lines count, ASCENDING.<\/p>\n<p>The traversal ends with a <code><strong>path().unfold()<\/strong><\/code> to display nicely the journey, with an additional filtering <code><strong>hasLabel(\"station\")<\/strong><\/code> to remove all the <em>&#8220;connectedTo&#8221;<\/em> edges from the path.<\/p>\n<p>The result is what we expected:<\/p>\n<div id=\"attachment_13343\" style=\"width: 850px\" class=\"wp-caption aligncenter\"><img aria-describedby=\"caption-attachment-13343\" loading=\"lazy\" src=\"https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_MarbleArch_Path2-1024x288.png\" alt=\"SouthKensington_MarbleArch_Path2\" width=\"840\" height=\"236\" class=\"size-large wp-image-13343\" srcset=\"https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_MarbleArch_Path2-1024x288.png 1024w, https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_MarbleArch_Path2-300x84.png 300w, https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_MarbleArch_Path2-768x216.png 768w, https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_MarbleArch_Path2-1170x329.png 1170w, https:\/\/www.doanduyhai.com\/blog\/wp-content\/uploads\/2017\/08\/SouthKensington_MarbleArch_Path2.png 1544w\" sizes=\"(max-width: 840px) 100vw, 840px\" \/><p id=\"caption-attachment-13343\" class=\"wp-caption-text\">SouthKensington_MarbleArch_Path2<\/p><\/div>\n<p>And that&#8217;s all folks! <strong>Do not miss the other Gremlin recipes in this series<\/strong>.<\/p>\n<p>If you have any question about <strong>Gremlin<\/strong>, find me on the <strong><a href=\"http:\/\/datastaxacademy.slack.com\" target=\"_blank\">datastaxacademy.slack.com<\/a><\/strong>, channel <strong>dse-graph<\/strong>. My id is <em>@doanduyhai<\/em>   <\/p>\n","protected":false},"excerpt":{"rendered":"<p>This blog post is the 5th from the series Gremlin Recipes. It is recommended to read the previous blog posts first: Gremlin as a Stream SQL to Gremlin Recommendation Engine traversal Recursive traversals<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[58,10],"tags":[],"_links":{"self":[{"href":"https:\/\/www.doanduyhai.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/13320"}],"collection":[{"href":"https:\/\/www.doanduyhai.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.doanduyhai.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.doanduyhai.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.doanduyhai.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=13320"}],"version-history":[{"count":14,"href":"https:\/\/www.doanduyhai.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/13320\/revisions"}],"predecessor-version":[{"id":13350,"href":"https:\/\/www.doanduyhai.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/13320\/revisions\/13350"}],"wp:attachment":[{"href":"https:\/\/www.doanduyhai.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=13320"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.doanduyhai.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=13320"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.doanduyhai.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=13320"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}