You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@tinkerpop.apache.org by dkuppitz <gi...@git.apache.org> on 2018/06/21 20:20:20 UTC
[GitHub] tinkerpop pull request #882: TINKERPOP-1990 Add a shortestPath() step
GitHub user dkuppitz opened a pull request:
https://github.com/apache/tinkerpop/pull/882
TINKERPOP-1990 Add a shortestPath() step
Implemented `ShortestPathVertexProgram` and `ShortestPathVertexProgramStep`.
`docker/build.sh -t -i -n -d` passed.
VOTE: +1
I can wait for TINKERPOP-1991 before I merge it or merge it into `master/` now and then go from there with TINKERPOP-1991, I don't care.
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/apache/tinkerpop TINKERPOP-1990
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/tinkerpop/pull/882.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #882
----
commit 8a43eaadfdb4ab662f955cc4a1cde6bf5739f7db
Author: Daniel Kuppitz <da...@...>
Date: 2018-05-23T12:46:34Z
TINKERPOP-1990 Implemented `ShortestPathVertexProgram` and `ShortestPathVertexProgramStep`.
----
---
[GitHub] tinkerpop pull request #882: TINKERPOP-1990 Add a shortestPath() step
Posted by spmallette <gi...@git.apache.org>.
Github user spmallette commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/882#discussion_r206194431
--- Diff: gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/remote/RemoteGraph.java ---
@@ -60,6 +60,10 @@
test = "org.apache.tinkerpop.gremlin.process.traversal.step.map.PageRankTest",
method = "*",
reason = "hmmmm")
+@Graph.OptOut(
+ test = "org.apache.tinkerpop.gremlin.process.traversal.step.map.ShortestPathTest",
+ method = "*",
+ reason = "hmmmm")
--- End diff --
I'm going to update the "hmmm" to https://issues.apache.org/jira/browse/TINKERPOP-1976 - please do the same in your PR. :smile:
---
[GitHub] tinkerpop pull request #882: TINKERPOP-1990 Add a shortestPath() step
Posted by spmallette <gi...@git.apache.org>.
Github user spmallette commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/882#discussion_r207509387
--- Diff: gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java ---
@@ -2451,6 +2452,24 @@ else if (value instanceof Traversal)
return this.asAdmin().addStep((Step<E, E>) new PeerPressureVertexProgramStep(this.asAdmin()));
}
+ /**
+ * Executes a Shortest Path algorithm over the graph.
+ *
+ * @return the traversal with the appended {@link ShortestPathVertexProgramStep}
+ * @see <a href="http://tinkerpop.apache.org/docs/${project.version}/reference/#shortestpath-step" target="_blank">Reference Documentation - ShortestPath Step</a>
+ */
+ public default GraphTraversal<S, Path> shortestPath() {
+ if (this.asAdmin().getEndStep() instanceof GraphStep) {
--- End diff --
`connectedComponent()` seems to work without adding that `identity()` step:
```text
gremlin> graph = TinkerFactory.createModern()
==>tinkergraph[vertices:6 edges:6]
gremlin> g = graph.traversal().withComputer()
==>graphtraversalsource[tinkergraph[vertices:6 edges:6], graphcomputer]
gremlin> g.V().has('name',within('marko','vadas','lop','josh')).connectedComponent()
==>v[1]
==>v[3]
==>v[2]
==>v[4]
```
Not sure what's different....but now i'm questioning what i have in `connectedComponent()` again on something related.
---
[GitHub] tinkerpop pull request #882: TINKERPOP-1990 Add a shortestPath() step
Posted by spmallette <gi...@git.apache.org>.
Github user spmallette commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/882#discussion_r207183855
--- Diff: docs/src/recipes/shortest-path.asciidoc ---
@@ -136,3 +158,44 @@ g.withSack(0.0).V().as("from"). <1>
<7> Order the output by the start vertex id and then the end vertex id (for better readability).
<8> Deduplicate vertex pairs (the shortest path from `v[1]` to `v[6]` is the same as the path from `v[6]` to `v[1]`).
+Again, this can be translated into an OLAP query using the `shortestPath()` step.
+
+[gremlin-groovy,existing]
+----
+result = g.withComputer().V().
+ shortestPath().
+ with(ShortestPath.distance, 'weight').
+ with(ShortestPath.includeEdges, true).
+ filter(count(local).is(gt(1))).
+ group().
+ by(project('from','to').
+ by(limit(local, 1)).
+ by(tail(local, 1))).
+ unfold().
+ order().
+ by(select(keys).select('from').id()).
+ by(select(keys).select('to').id()).toList()
+----
+
+The obvious difference in the result is the absence of property values in the OLAP result. Since OLAP traversers are not
+allowed to leave the local star graph, it's not possible to have the exact same result in an OLAP query. However, the determined
+shortest paths can be passed back into the OLTP `GraphTraversalSource`, which can then be used to query the values.
+
+[gremlin-groovy,existing]
+----
+g.withSideEffect('v', []). <1>
+ inject(result.toArray()).as('kv').select(values).
+ unfold().
+ map(unfold().as('v_or_e').
+ coalesce(V().where(eq('v_or_e')).store('v'),
+ select('v').tail(local, 1).bothE().where(eq('v_or_e'))).
+ values('name','weight').
+ fold()).
+ group().
+ by(select('kv').select(keys)).unfold().
+ order().
+ by(select(keys).select('from').id()).
+ by(select(keys).select('to').id()).toList()
+----
+
+<1> The side-effect `v` is used to keep track of the last processed vertex, hence it needs to be an order-preserving list. Without this explicit definition `v` would become a `BulkSet` which doesn't preserve the insert order.
--- End diff --
interesting
---
[GitHub] tinkerpop issue #882: TINKERPOP-1990 Add a shortestPath() step
Posted by FlorianHockmann <gi...@git.apache.org>.
Github user FlorianHockmann commented on the issue:
https://github.com/apache/tinkerpop/pull/882
Just wondered: Does the _Shortest Path_ recipe still make sense with the new `shortestPath()` step? And should the section in the reference docs about shortest paths and the recipe link to each other?
---
[GitHub] tinkerpop pull request #882: TINKERPOP-1990 Add a shortestPath() step
Posted by spmallette <gi...@git.apache.org>.
Github user spmallette commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/882#discussion_r207197353
--- Diff: gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java ---
@@ -2451,6 +2452,24 @@ else if (value instanceof Traversal)
return this.asAdmin().addStep((Step<E, E>) new PeerPressureVertexProgramStep(this.asAdmin()));
}
+ /**
+ * Executes a Shortest Path algorithm over the graph.
+ *
+ * @return the traversal with the appended {@link ShortestPathVertexProgramStep}
+ * @see <a href="http://tinkerpop.apache.org/docs/${project.version}/reference/#shortestpath-step" target="_blank">Reference Documentation - ShortestPath Step</a>
+ */
+ public default GraphTraversal<S, Path> shortestPath() {
+ if (this.asAdmin().getEndStep() instanceof GraphStep) {
--- End diff --
So, what does this mean exactly? Like, if you did `g.V().has('name','marko')` it wouldn't filter "marko" vertex without you throwing an `identity()` in there?
---
[GitHub] tinkerpop pull request #882: TINKERPOP-1990 Add a shortestPath() step
Posted by spmallette <gi...@git.apache.org>.
Github user spmallette commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/882#discussion_r207191097
--- Diff: gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traversal.java ---
@@ -496,15 +496,17 @@ public default void reset() {
public void setGraph(final Graph graph);
public default boolean equals(final Traversal.Admin<S, E> other) {
- final List<Step> steps = this.getSteps();
- final List<Step> otherSteps = other.getSteps();
- if (steps.size() == otherSteps.size()) {
- for (int i = 0; i < steps.size(); i++) {
- if (!steps.get(i).equals(otherSteps.get(i))) {
- return false;
+ if (this.getClass().equals(other.getClass())) {
--- End diff --
I guess this changes makes sense. Are you sure there was no reason why we didn't have it that way to begin with? Just playing devil's advocate, but should `Traversal` equality in some way be based on the steps the traversal contains rather than the class it has?
---
[GitHub] tinkerpop issue #882: TINKERPOP-1990 Add a shortestPath() step
Posted by spmallette <gi...@git.apache.org>.
Github user spmallette commented on the issue:
https://github.com/apache/tinkerpop/pull/882
VOTE +1
---
[GitHub] tinkerpop pull request #882: TINKERPOP-1990 Add a shortestPath() step
Posted by twilmes <gi...@git.apache.org>.
Github user twilmes commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/882#discussion_r201547477
--- Diff: gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathVertexProgram.java ---
@@ -0,0 +1,557 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.tinkerpop.gremlin.process.computer.search.path;
+
+import org.apache.commons.configuration.Configuration;
+import org.apache.tinkerpop.gremlin.process.computer.*;
--- End diff --
Looks like the IDE wild-carded a few of these imports
---
[GitHub] tinkerpop pull request #882: TINKERPOP-1990 Add a shortestPath() step
Posted by spmallette <gi...@git.apache.org>.
Github user spmallette commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/882#discussion_r206210239
--- Diff: docs/src/reference/the-traversal.asciidoc ---
@@ -2489,6 +2489,62 @@ link:++http://tinkerpop.apache.org/javadocs/x.y.z/core/org/apache/tinkerpop/grem
link:++http://tinkerpop.apache.org/javadocs/x.y.z/core/org/apache/tinkerpop/gremlin/structure/Column.html++[`Column`],
link:++http://tinkerpop.apache.org/javadocs/x.y.z/core/org/apache/tinkerpop/gremlin/process/traversal/Pop.html++[`Pop`]
+[[shortestpath-step]]
+=== ShortestPath step
+
+The `shortestPath()`-step provides an easy way to find shortest non-cyclic paths in a graph. It is configurable
+using the `with()`-modulator with the options given below.
+
+[width="100%",cols="3,3,15,5",options="header"]
+|=========================================================
+| Key | Type | Description | Default
+| `target` | `Traversal` | Sets a filter traversal for the end vertices (e.g. `__.has('name','marko')`). | all vertices (`__.identity()`)
+| `edges` | `Traversal` or `Direction` | Sets a `Traversal` that emits the edges to traverse from the current vertex or the `Direction` to traverse during the shortest path discovery. | `Direction.BOTH`
+| `distance` | `Traversal` or `String` | Sets the `Traversal` that calculates the distance for the current edge or the name of an edge property to use for the distance calculations. | `__.constant(1)`
+| `maxDistance` | `Number` | Sets the distance limit for all shortest paths. | none
+| `includeEdges` | `Boolean` | Whether to include edges in the result or not. | `false`
+|=========================================================
+
+[gremlin-groovy,modern]
+----
+a = g.withComputer()
--- End diff --
oh - sorry - i didn't see that. maybe just don't put it all in one block? reserve that last one as its own example with some introductory text to separate and explain what its doing?
---
[GitHub] tinkerpop pull request #882: TINKERPOP-1990 Add a shortestPath() step
Posted by dkuppitz <gi...@git.apache.org>.
Github user dkuppitz commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/882#discussion_r207375700
--- Diff: gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java ---
@@ -2451,6 +2452,24 @@ else if (value instanceof Traversal)
return this.asAdmin().addStep((Step<E, E>) new PeerPressureVertexProgramStep(this.asAdmin()));
}
+ /**
+ * Executes a Shortest Path algorithm over the graph.
+ *
+ * @return the traversal with the appended {@link ShortestPathVertexProgramStep}
+ * @see <a href="http://tinkerpop.apache.org/docs/${project.version}/reference/#shortestpath-step" target="_blank">Reference Documentation - ShortestPath Step</a>
+ */
+ public default GraphTraversal<S, Path> shortestPath() {
+ if (this.asAdmin().getEndStep() instanceof GraphStep) {
--- End diff --
Oh, totally forgot about this corner case (that's something you should test in `ConnectedComponentVP` too). And right, if you only have `g.V().has(...)` followed by a VP step, your VP won't see any halted traversers and thus behave like it was just `g.V()`. I spent quite some time trying to fix that properly, but couldn't come up with anything.
---
[GitHub] tinkerpop issue #882: TINKERPOP-1990 Add a shortestPath() step
Posted by spmallette <gi...@git.apache.org>.
Github user spmallette commented on the issue:
https://github.com/apache/tinkerpop/pull/882
I just issued #897 - note my comments there about TINKERPOP-1991. I think we should just leave that alone for 3.4.0 and come back to it. I also think we should disregard my comments about pushing these off to 3.5.0...we will save a lot of headache with these steps so i think there are better here now than later.
@dkuppitz could you please rebase. i can review this next week in more detail.
---
[GitHub] tinkerpop issue #882: TINKERPOP-1990 Add a shortestPath() step
Posted by spmallette <gi...@git.apache.org>.
Github user spmallette commented on the issue:
https://github.com/apache/tinkerpop/pull/882
@dkuppitz could you rebase this one more time please?
---
[GitHub] tinkerpop pull request #882: TINKERPOP-1990 Add a shortestPath() step
Posted by dkuppitz <gi...@git.apache.org>.
Github user dkuppitz commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/882#discussion_r206207720
--- Diff: docs/src/reference/the-traversal.asciidoc ---
@@ -2489,6 +2489,62 @@ link:++http://tinkerpop.apache.org/javadocs/x.y.z/core/org/apache/tinkerpop/grem
link:++http://tinkerpop.apache.org/javadocs/x.y.z/core/org/apache/tinkerpop/gremlin/structure/Column.html++[`Column`],
link:++http://tinkerpop.apache.org/javadocs/x.y.z/core/org/apache/tinkerpop/gremlin/process/traversal/Pop.html++[`Pop`]
+[[shortestpath-step]]
+=== ShortestPath step
+
+The `shortestPath()`-step provides an easy way to find shortest non-cyclic paths in a graph. It is configurable
+using the `with()`-modulator with the options given below.
+
+[width="100%",cols="3,3,15,5",options="header"]
+|=========================================================
+| Key | Type | Description | Default
+| `target` | `Traversal` | Sets a filter traversal for the end vertices (e.g. `__.has('name','marko')`). | all vertices (`__.identity()`)
+| `edges` | `Traversal` or `Direction` | Sets a `Traversal` that emits the edges to traverse from the current vertex or the `Direction` to traverse during the shortest path discovery. | `Direction.BOTH`
+| `distance` | `Traversal` or `String` | Sets the `Traversal` that calculates the distance for the current edge or the name of an edge property to use for the distance calculations. | `__.constant(1)`
+| `maxDistance` | `Number` | Sets the distance limit for all shortest paths. | none
+| `includeEdges` | `Boolean` | Whether to include edges in the result or not. | `false`
+|=========================================================
+
+[gremlin-groovy,modern]
+----
+a = g.withComputer()
--- End diff --
I know, but we also never mixed two traversal sources in a single code block. Better suggestions?
---
[GitHub] tinkerpop pull request #882: TINKERPOP-1990 Add a shortestPath() step
Posted by spmallette <gi...@git.apache.org>.
Github user spmallette commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/882#discussion_r207183373
--- Diff: docs/src/recipes/shortest-path.asciidoc ---
@@ -48,6 +48,17 @@ course, it is possible for there to be more than one path in the graph of the sa
length three), but this example is not considering that.
<2> It might be interesting to know the path lengths for all paths between vertex "1" and "5".
<3> Alternatively, one might wish to do a path length distribution over all the paths.
+<4> The preferred way to get a shortest path in OLAP is the `shortestPath()` step.
--- End diff --
hmm - `<4>` doesn't refer to anything in the code above. did you mean to add that callout?
---
[GitHub] tinkerpop pull request #882: TINKERPOP-1990 Add a shortestPath() step
Posted by dkuppitz <gi...@git.apache.org>.
Github user dkuppitz commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/882#discussion_r207373358
--- Diff: docs/src/recipes/shortest-path.asciidoc ---
@@ -48,6 +48,17 @@ course, it is possible for there to be more than one path in the graph of the sa
length three), but this example is not considering that.
<2> It might be interesting to know the path lengths for all paths between vertex "1" and "5".
<3> Alternatively, one might wish to do a path length distribution over all the paths.
+<4> The preferred way to get a shortest path in OLAP is the `shortestPath()` step.
--- End diff --
Ah, forgot to remove it, that's from when OLTP and OLAP were still mixed in one block.
---
[GitHub] tinkerpop pull request #882: TINKERPOP-1990 Add a shortestPath() step
Posted by dkuppitz <gi...@git.apache.org>.
Github user dkuppitz commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/882#discussion_r207374407
--- Diff: gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traversal.java ---
@@ -496,15 +496,17 @@ public default void reset() {
public void setGraph(final Graph graph);
public default boolean equals(final Traversal.Admin<S, E> other) {
- final List<Step> steps = this.getSteps();
- final List<Step> otherSteps = other.getSteps();
- if (steps.size() == otherSteps.size()) {
- for (int i = 0; i < steps.size(); i++) {
- if (!steps.get(i).equals(otherSteps.get(i))) {
- return false;
+ if (this.getClass().equals(other.getClass())) {
--- End diff --
I don't think so. The main reason why I had to change it was that traversals without steps were considered equal using the old method. That means all `TrueTraversal`, `ConstantTraversal`, `ValueTraversal`, etc. instances were equal compared to each other.
---
[GitHub] tinkerpop issue #882: TINKERPOP-1990 Add a shortestPath() step
Posted by spmallette <gi...@git.apache.org>.
Github user spmallette commented on the issue:
https://github.com/apache/tinkerpop/pull/882
Let's get #909 merged, rebase this, add GLV tests and then merge this one (doing the same for #897 )
---
[GitHub] tinkerpop issue #882: TINKERPOP-1990 Add a shortestPath() step
Posted by spmallette <gi...@git.apache.org>.
Github user spmallette commented on the issue:
https://github.com/apache/tinkerpop/pull/882
I will try to find some time to do TINKERPOP-1991 and see what is involved. If it's a mess then maybe we don't try to shove TINKERPOP-1991 into 3.4.0 and await 3.5.0 then just merge `shortestPath()` and `connectedComponent()` for 3.4.0. I'd say that if we get stuck without TINKERPOP-1991 we probably shouldn't add anymore algorithms until 3.5.0 so as to not further pollute the core Gremlin space. thinky think....
---
[GitHub] tinkerpop pull request #882: TINKERPOP-1990 Add a shortestPath() step
Posted by dkuppitz <gi...@git.apache.org>.
Github user dkuppitz commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/882#discussion_r207377923
--- Diff: docs/src/recipes/shortest-path.asciidoc ---
@@ -136,3 +158,44 @@ g.withSack(0.0).V().as("from"). <1>
<7> Order the output by the start vertex id and then the end vertex id (for better readability).
<8> Deduplicate vertex pairs (the shortest path from `v[1]` to `v[6]` is the same as the path from `v[6]` to `v[1]`).
+Again, this can be translated into an OLAP query using the `shortestPath()` step.
+
+[gremlin-groovy,existing]
+----
+result = g.withComputer().V().
+ shortestPath().
+ with(ShortestPath.distance, 'weight').
+ with(ShortestPath.includeEdges, true).
+ filter(count(local).is(gt(1))).
+ group().
+ by(project('from','to').
+ by(limit(local, 1)).
+ by(tail(local, 1))).
+ unfold().
+ order().
+ by(select(keys).select('from').id()).
+ by(select(keys).select('to').id()).toList()
+----
+
+The obvious difference in the result is the absence of property values in the OLAP result. Since OLAP traversers are not
+allowed to leave the local star graph, it's not possible to have the exact same result in an OLAP query. However, the determined
+shortest paths can be passed back into the OLTP `GraphTraversalSource`, which can then be used to query the values.
+
+[gremlin-groovy,existing]
+----
+g.withSideEffect('v', []). <1>
+ inject(result.toArray()).as('kv').select(values).
+ unfold().
+ map(unfold().as('v_or_e').
+ coalesce(V().where(eq('v_or_e')).store('v'),
+ select('v').tail(local, 1).bothE().where(eq('v_or_e'))).
+ values('name','weight').
+ fold()).
+ group().
+ by(select('kv').select(keys)).unfold().
+ order().
+ by(select(keys).select('from').id()).
+ by(select(keys).select('to').id()).toList()
+----
+
+<1> The side-effect `v` is used to keep track of the last processed vertex, hence it needs to be an order-preserving list. Without this explicit definition `v` would become a `BulkSet` which doesn't preserve the insert order.
--- End diff --
I was surprised that the elements didn't get dereferenced automatically (`result` contains `ReferencePath` objects holding `ReferenceVertex` and `ReferenceEdge` instances). If they were automatically reattached, the `map` step would be as simple as this:
```
map(unfold().values('name','weight').fold())
```
---
[GitHub] tinkerpop issue #882: TINKERPOP-1990 Add a shortestPath() step
Posted by spmallette <gi...@git.apache.org>.
Github user spmallette commented on the issue:
https://github.com/apache/tinkerpop/pull/882
good question @FlorianHockmann - seems like the recipe shouldn't be removed but perhaps updated to reflect this step??
---
[GitHub] tinkerpop pull request #882: TINKERPOP-1990 Add a shortestPath() step
Posted by spmallette <gi...@git.apache.org>.
Github user spmallette commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/882#discussion_r206182822
--- Diff: docs/src/reference/the-traversal.asciidoc ---
@@ -2489,6 +2489,62 @@ link:++http://tinkerpop.apache.org/javadocs/x.y.z/core/org/apache/tinkerpop/grem
link:++http://tinkerpop.apache.org/javadocs/x.y.z/core/org/apache/tinkerpop/gremlin/structure/Column.html++[`Column`],
link:++http://tinkerpop.apache.org/javadocs/x.y.z/core/org/apache/tinkerpop/gremlin/process/traversal/Pop.html++[`Pop`]
+[[shortestpath-step]]
+=== ShortestPath step
+
+The `shortestPath()`-step provides an easy way to find shortest non-cyclic paths in a graph. It is configurable
+using the `with()`-modulator with the options given below.
+
+[width="100%",cols="3,3,15,5",options="header"]
+|=========================================================
+| Key | Type | Description | Default
+| `target` | `Traversal` | Sets a filter traversal for the end vertices (e.g. `__.has('name','marko')`). | all vertices (`__.identity()`)
+| `edges` | `Traversal` or `Direction` | Sets a `Traversal` that emits the edges to traverse from the current vertex or the `Direction` to traverse during the shortest path discovery. | `Direction.BOTH`
+| `distance` | `Traversal` or `String` | Sets the `Traversal` that calculates the distance for the current edge or the name of an edge property to use for the distance calculations. | `__.constant(1)`
+| `maxDistance` | `Number` | Sets the distance limit for all shortest paths. | none
+| `includeEdges` | `Boolean` | Whether to include edges in the result or not. | `false`
+|=========================================================
+
+[gremlin-groovy,modern]
+----
+a = g.withComputer()
--- End diff --
I don't know that we should start doing "a" here...we don't reference the `GraphTraversalSource` any other way than "g" anywhere else in the docs.
---
[GitHub] tinkerpop issue #882: TINKERPOP-1990 Add a shortestPath() step
Posted by dkuppitz <gi...@git.apache.org>.
Github user dkuppitz commented on the issue:
https://github.com/apache/tinkerpop/pull/882
Done.
---
[GitHub] tinkerpop pull request #882: TINKERPOP-1990 Add a shortestPath() step
Posted by spmallette <gi...@git.apache.org>.
Github user spmallette commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/882#discussion_r206111874
--- Diff: gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/ShortestPathVertexProgramStep.java ---
@@ -0,0 +1,174 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.tinkerpop.gremlin.process.computer.traversal.step.map;
+
+import org.apache.tinkerpop.gremlin.process.computer.*;
--- End diff --
nit: You have some wildcard imports here....
---
[GitHub] tinkerpop pull request #882: TINKERPOP-1990 Add a shortestPath() step
Posted by spmallette <gi...@git.apache.org>.
Github user spmallette commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/882#discussion_r206188786
--- Diff: gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/search/path/ShortestPathVertexProgram.java ---
@@ -0,0 +1,581 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.tinkerpop.gremlin.process.computer.search.path;
+
+import org.apache.commons.configuration.Configuration;
+import org.apache.tinkerpop.gremlin.process.computer.GraphComputer;
+import org.apache.tinkerpop.gremlin.process.computer.Memory;
+import org.apache.tinkerpop.gremlin.process.computer.MemoryComputeKey;
+import org.apache.tinkerpop.gremlin.process.computer.MessageScope;
+import org.apache.tinkerpop.gremlin.process.computer.Messenger;
+import org.apache.tinkerpop.gremlin.process.computer.VertexComputeKey;
+import org.apache.tinkerpop.gremlin.process.computer.VertexProgram;
+import org.apache.tinkerpop.gremlin.process.computer.traversal.TraversalVertexProgram;
+import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.ProgramVertexProgramStep;
+import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.VertexProgramStep;
+import org.apache.tinkerpop.gremlin.process.computer.util.AbstractVertexProgramBuilder;
+import org.apache.tinkerpop.gremlin.process.traversal.Operator;
+import org.apache.tinkerpop.gremlin.process.traversal.Path;
+import org.apache.tinkerpop.gremlin.process.traversal.Step;
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.ImmutablePath;
+import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.IndexedTraverserSet;
+import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.TraverserSet;
+import org.apache.tinkerpop.gremlin.process.traversal.util.PureTraversal;
+import org.apache.tinkerpop.gremlin.structure.Direction;
+import org.apache.tinkerpop.gremlin.structure.Edge;
+import org.apache.tinkerpop.gremlin.structure.Element;
+import org.apache.tinkerpop.gremlin.structure.Graph;
+import org.apache.tinkerpop.gremlin.structure.Vertex;
+import org.apache.tinkerpop.gremlin.structure.VertexProperty;
+import org.apache.tinkerpop.gremlin.structure.util.StringFactory;
+import org.apache.tinkerpop.gremlin.structure.util.reference.ReferenceFactory;
+import org.apache.tinkerpop.gremlin.util.NumberHelper;
+import org.javatuples.Pair;
+import org.javatuples.Triplet;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.function.Function;
+
+/**
+ * @author Daniel Kuppitz (http://gremlin.guru)
--- End diff --
It would be nice to see more javadoc and inline comments in here. I'd like to know more about "why" in a lot of the stuff i see here, especially in `execute()`, `storeState()` and `loadState()`. Similar to the inline comments i have in `connectedComponent()` - https://github.com/apache/tinkerpop/pull/897/files#diff-b0b5f3644f5f656c492f3f6ddae2c7feR117 it would be also nice to know why halted traversers are setup the way that they are if you figured that out somehow because it's still mysterious to me.
---
[GitHub] tinkerpop pull request #882: TINKERPOP-1990 Add a shortestPath() step
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit closed the pull request at:
https://github.com/apache/tinkerpop/pull/882
---