[jira] [Commented] (TINKERPOP-1990) Add a shortestPath() step
[
https://issues.apache.org/jira/browse/TINKERPOP-1990?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16576345#comment-16576345
]
ASF GitHub Bot commented on TINKERPOP-1990:
---
Github user asfgit closed the pull request at:
https://github.com/apache/tinkerpop/pull/882
> Add a shortestPath() step
> -
>
> Key: TINKERPOP-1990
> URL: https://issues.apache.org/jira/browse/TINKERPOP-1990
> Project: TinkerPop
> Issue Type: Improvement
> Components: process
>Reporter: Daniel Kuppitz
>Assignee: Daniel Kuppitz
>Priority: Major
>
> Implement {{ShortestPathVertexProgram}} and a {{shortestPath()}} step.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (TINKERPOP-1990) Add a shortestPath() step
[
https://issues.apache.org/jira/browse/TINKERPOP-1990?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16576341#comment-16576341
]
ASF GitHub Bot commented on TINKERPOP-1990:
---
Github user spmallette commented on the issue:
https://github.com/apache/tinkerpop/pull/882
VOTE +1
> Add a shortestPath() step
> -
>
> Key: TINKERPOP-1990
> URL: https://issues.apache.org/jira/browse/TINKERPOP-1990
> Project: TinkerPop
> Issue Type: Improvement
> Components: process
>Reporter: Daniel Kuppitz
>Assignee: Daniel Kuppitz
>Priority: Major
>
> Implement {{ShortestPathVertexProgram}} and a {{shortestPath()}} step.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (TINKERPOP-1990) Add a shortestPath() step
[
https://issues.apache.org/jira/browse/TINKERPOP-1990?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16573384#comment-16573384
]
ASF GitHub Bot commented on TINKERPOP-1990:
---
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 )
> Add a shortestPath() step
> -
>
> Key: TINKERPOP-1990
> URL: https://issues.apache.org/jira/browse/TINKERPOP-1990
> Project: TinkerPop
> Issue Type: Improvement
> Components: process
>Reporter: Daniel Kuppitz
>Assignee: Daniel Kuppitz
>Priority: Major
>
> Implement {{ShortestPathVertexProgram}} and a {{shortestPath()}} step.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (TINKERPOP-1990) Add a shortestPath() step
[
https://issues.apache.org/jira/browse/TINKERPOP-1990?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16568096#comment-16568096
]
ASF GitHub Bot commented on TINKERPOP-1990:
---
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) new
PeerPressureVertexProgramStep(this.asAdmin()));
}
+/**
+ * Executes a Shortest Path algorithm over the graph.
+ *
+ * @return the traversal with the appended {@link
ShortestPathVertexProgramStep}
+ * @see http://tinkerpop.apache.org/docs/${project.version}/reference/#shortestpath-step;
target="_blank">Reference Documentation - ShortestPath Step
+ */
+public default GraphTraversal 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 differentbut now i'm questioning what i have in
`connectedComponent()` again on something related.
> Add a shortestPath() step
> -
>
> Key: TINKERPOP-1990
> URL: https://issues.apache.org/jira/browse/TINKERPOP-1990
> Project: TinkerPop
> Issue Type: Improvement
> Components: process
>Reporter: Daniel Kuppitz
>Assignee: Daniel Kuppitz
>Priority: Major
>
> Implement {{ShortestPathVertexProgram}} and a {{shortestPath()}} step.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (TINKERPOP-1990) Add a shortestPath() step
[
https://issues.apache.org/jira/browse/TINKERPOP-1990?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16567489#comment-16567489
]
ASF GitHub Bot commented on TINKERPOP-1990:
---
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) new
PeerPressureVertexProgramStep(this.asAdmin()));
}
+/**
+ * Executes a Shortest Path algorithm over the graph.
+ *
+ * @return the traversal with the appended {@link
ShortestPathVertexProgramStep}
+ * @see http://tinkerpop.apache.org/docs/${project.version}/reference/#shortestpath-step;
target="_blank">Reference Documentation - ShortestPath Step
+ */
+public default GraphTraversal 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.
> Add a shortestPath() step
> -
>
> Key: TINKERPOP-1990
> URL: https://issues.apache.org/jira/browse/TINKERPOP-1990
> Project: TinkerPop
> Issue Type: Improvement
> Components: process
>Reporter: Daniel Kuppitz
>Assignee: Daniel Kuppitz
>Priority: Major
>
> Implement {{ShortestPathVertexProgram}} and a {{shortestPath()}} step.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (TINKERPOP-1990) Add a shortestPath() step
[
https://issues.apache.org/jira/browse/TINKERPOP-1990?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16567487#comment-16567487
]
ASF GitHub Bot commented on TINKERPOP-1990:
---
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 other) {
-final List steps = this.getSteps();
-final List 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.
> Add a shortestPath() step
> -
>
> Key: TINKERPOP-1990
> URL: https://issues.apache.org/jira/browse/TINKERPOP-1990
> Project: TinkerPop
> Issue Type: Improvement
> Components: process
>Reporter: Daniel Kuppitz
>Assignee: Daniel Kuppitz
>Priority: Major
>
> Implement {{ShortestPathVertexProgram}} and a {{shortestPath()}} step.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (TINKERPOP-1990) Add a shortestPath() step
[
https://issues.apache.org/jira/browse/TINKERPOP-1990?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=1656#comment-1656
]
ASF GitHub Bot commented on TINKERPOP-1990:
---
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) new
PeerPressureVertexProgramStep(this.asAdmin()));
}
+/**
+ * Executes a Shortest Path algorithm over the graph.
+ *
+ * @return the traversal with the appended {@link
ShortestPathVertexProgramStep}
+ * @see http://tinkerpop.apache.org/docs/${project.version}/reference/#shortestpath-step;
target="_blank">Reference Documentation - ShortestPath Step
+ */
+public default GraphTraversal 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?
> Add a shortestPath() step
> -
>
> Key: TINKERPOP-1990
> URL: https://issues.apache.org/jira/browse/TINKERPOP-1990
> Project: TinkerPop
> Issue Type: Improvement
> Components: process
>Reporter: Daniel Kuppitz
>Assignee: Daniel Kuppitz
>Priority: Major
>
> Implement {{ShortestPathVertexProgram}} and a {{shortestPath()}} step.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (TINKERPOP-1990) Add a shortestPath() step
[
https://issues.apache.org/jira/browse/TINKERPOP-1990?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16566649#comment-16566649
]
ASF GitHub Bot commented on TINKERPOP-1990:
---
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 other) {
-final List steps = this.getSteps();
-final List 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?
> Add a shortestPath() step
> -
>
> Key: TINKERPOP-1990
> URL: https://issues.apache.org/jira/browse/TINKERPOP-1990
> Project: TinkerPop
> Issue Type: Improvement
> Components: process
>Reporter: Daniel Kuppitz
>Assignee: Daniel Kuppitz
>Priority: Major
>
> Implement {{ShortestPathVertexProgram}} and a {{shortestPath()}} step.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (TINKERPOP-1990) Add a shortestPath() step
[
https://issues.apache.org/jira/browse/TINKERPOP-1990?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16566620#comment-16566620
]
ASF GitHub Bot commented on TINKERPOP-1990:
---
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?
> Add a shortestPath() step
> -
>
> Key: TINKERPOP-1990
> URL: https://issues.apache.org/jira/browse/TINKERPOP-1990
> Project: TinkerPop
> Issue Type: Improvement
> Components: process
>Reporter: Daniel Kuppitz
>Assignee: Daniel Kuppitz
>Priority: Major
>
> Implement {{ShortestPathVertexProgram}} and a {{shortestPath()}} step.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (TINKERPOP-1990) Add a shortestPath() step
[
https://issues.apache.org/jira/browse/TINKERPOP-1990?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16565866#comment-16565866
]
ASF GitHub Bot commented on TINKERPOP-1990:
---
Github user dkuppitz commented on the issue:
https://github.com/apache/tinkerpop/pull/882
Done.
> Add a shortestPath() step
> -
>
> Key: TINKERPOP-1990
> URL: https://issues.apache.org/jira/browse/TINKERPOP-1990
> Project: TinkerPop
> Issue Type: Improvement
> Components: process
>Reporter: Daniel Kuppitz
>Assignee: Daniel Kuppitz
>Priority: Major
>
> Implement {{ShortestPathVertexProgram}} and a {{shortestPath()}} step.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (TINKERPOP-1990) Add a shortestPath() step
[
https://issues.apache.org/jira/browse/TINKERPOP-1990?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16562448#comment-16562448
]
ASF GitHub Bot commented on TINKERPOP-1990:
---
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??
> Add a shortestPath() step
> -
>
> Key: TINKERPOP-1990
> URL: https://issues.apache.org/jira/browse/TINKERPOP-1990
> Project: TinkerPop
> Issue Type: Improvement
> Components: process
>Reporter: Daniel Kuppitz
>Assignee: Daniel Kuppitz
>Priority: Major
>
> Implement {{ShortestPathVertexProgram}} and a {{shortestPath()}} step.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (TINKERPOP-1990) Add a shortestPath() step
[
https://issues.apache.org/jira/browse/TINKERPOP-1990?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16562439#comment-16562439
]
ASF GitHub Bot commented on TINKERPOP-1990:
---
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?
> Add a shortestPath() step
> -
>
> Key: TINKERPOP-1990
> URL: https://issues.apache.org/jira/browse/TINKERPOP-1990
> Project: TinkerPop
> Issue Type: Improvement
> Components: process
>Reporter: Daniel Kuppitz
>Assignee: Daniel Kuppitz
>Priority: Major
>
> Implement {{ShortestPathVertexProgram}} and a {{shortestPath()}} step.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (TINKERPOP-1990) Add a shortestPath() step
[
https://issues.apache.org/jira/browse/TINKERPOP-1990?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16562034#comment-16562034
]
ASF GitHub Bot commented on TINKERPOP-1990:
---
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?
> Add a shortestPath() step
> -
>
> Key: TINKERPOP-1990
> URL: https://issues.apache.org/jira/browse/TINKERPOP-1990
> Project: TinkerPop
> Issue Type: Improvement
> Components: process
>Reporter: Daniel Kuppitz
>Assignee: Daniel Kuppitz
>Priority: Major
>
> Implement {{ShortestPathVertexProgram}} and a {{shortestPath()}} step.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (TINKERPOP-1990) Add a shortestPath() step
[
https://issues.apache.org/jira/browse/TINKERPOP-1990?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16562032#comment-16562032
]
ASF GitHub Bot commented on TINKERPOP-1990:
---
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?
> Add a shortestPath() step
> -
>
> Key: TINKERPOP-1990
> URL: https://issues.apache.org/jira/browse/TINKERPOP-1990
> Project: TinkerPop
> Issue Type: Improvement
> Components: process
>Reporter: Daniel Kuppitz
>Assignee: Daniel Kuppitz
>Priority: Major
>
> Implement {{ShortestPathVertexProgram}} and a {{shortestPath()}} step.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (TINKERPOP-1990) Add a shortestPath() step
[
https://issues.apache.org/jira/browse/TINKERPOP-1990?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16562021#comment-16562021
]
ASF GitHub Bot commented on TINKERPOP-1990:
---
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 = "h")
+@Graph.OptOut(
+test =
"org.apache.tinkerpop.gremlin.process.traversal.step.map.ShortestPathTest",
+method = "*",
+reason = "h")
--- 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:
> Add a shortestPath() step
> -
>
> Key: TINKERPOP-1990
> URL: https://issues.apache.org/jira/browse/TINKERPOP-1990
> Project: TinkerPop
> Issue Type: Improvement
> Components: process
>Reporter: Daniel Kuppitz
>Assignee: Daniel Kuppitz
>Priority: Major
>
> Implement {{ShortestPathVertexProgram}} and a {{shortestPath()}} step.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (TINKERPOP-1990) Add a shortestPath() step
[ https://issues.apache.org/jira/browse/TINKERPOP-1990?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16562013#comment-16562013 ] ASF GitHub Bot commented on TINKERPOP-1990: --- 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. > Add a shortestPath() step > - > > Key: TINKERPOP-1990 > URL:
[jira] [Commented] (TINKERPOP-1990) Add a shortestPath() step
[
https://issues.apache.org/jira/browse/TINKERPOP-1990?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16562003#comment-16562003
]
ASF GitHub Bot commented on TINKERPOP-1990:
---
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.
> Add a shortestPath() step
> -
>
> Key: TINKERPOP-1990
> URL: https://issues.apache.org/jira/browse/TINKERPOP-1990
> Project: TinkerPop
> Issue Type: Improvement
> Components: process
>Reporter: Daniel Kuppitz
>Assignee: Daniel Kuppitz
>Priority: Major
>
> Implement {{ShortestPathVertexProgram}} and a {{shortestPath()}} step.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (TINKERPOP-1990) Add a shortestPath() step
[
https://issues.apache.org/jira/browse/TINKERPOP-1990?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16561846#comment-16561846
]
ASF GitHub Bot commented on TINKERPOP-1990:
---
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
> Add a shortestPath() step
> -
>
> Key: TINKERPOP-1990
> URL: https://issues.apache.org/jira/browse/TINKERPOP-1990
> Project: TinkerPop
> Issue Type: Improvement
> Components: process
>Reporter: Daniel Kuppitz
>Assignee: Daniel Kuppitz
>Priority: Major
>
> Implement {{ShortestPathVertexProgram}} and a {{shortestPath()}} step.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (TINKERPOP-1990) Add a shortestPath() step
[
https://issues.apache.org/jira/browse/TINKERPOP-1990?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16560294#comment-16560294
]
ASF GitHub Bot commented on TINKERPOP-1990:
---
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.
> Add a shortestPath() step
> -
>
> Key: TINKERPOP-1990
> URL: https://issues.apache.org/jira/browse/TINKERPOP-1990
> Project: TinkerPop
> Issue Type: Improvement
> Components: process
>Reporter: Daniel Kuppitz
>Assignee: Daniel Kuppitz
>Priority: Major
>
> Implement {{ShortestPathVertexProgram}} and a {{shortestPath()}} step.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (TINKERPOP-1990) Add a shortestPath() step
[
https://issues.apache.org/jira/browse/TINKERPOP-1990?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16539457#comment-16539457
]
ASF GitHub Bot commented on TINKERPOP-1990:
---
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
> Add a shortestPath() step
> -
>
> Key: TINKERPOP-1990
> URL: https://issues.apache.org/jira/browse/TINKERPOP-1990
> Project: TinkerPop
> Issue Type: Improvement
> Components: process
>Reporter: Daniel Kuppitz
>Assignee: Daniel Kuppitz
>Priority: Major
>
> Implement {{ShortestPathVertexProgram}} and a {{shortestPath()}} step.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (TINKERPOP-1990) Add a shortestPath() step
[
https://issues.apache.org/jira/browse/TINKERPOP-1990?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16519792#comment-16519792
]
ASF GitHub Bot commented on TINKERPOP-1990:
---
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
> Add a shortestPath() step
> -
>
> Key: TINKERPOP-1990
> URL: https://issues.apache.org/jira/browse/TINKERPOP-1990
> Project: TinkerPop
> Issue Type: Improvement
> Components: process
>Reporter: Daniel Kuppitz
>Assignee: Daniel Kuppitz
>Priority: Major
>
> Implement {{ShortestPathVertexProgram}} and a {{shortestPath()}} step.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (TINKERPOP-1990) Add a shortestPath() step
[
https://issues.apache.org/jira/browse/TINKERPOP-1990?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16519740#comment-16519740
]
ASF GitHub Bot commented on TINKERPOP-1990:
---
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
Date: 2018-05-23T12:46:34Z
TINKERPOP-1990 Implemented `ShortestPathVertexProgram` and
`ShortestPathVertexProgramStep`.
> Add a shortestPath() step
> -
>
> Key: TINKERPOP-1990
> URL: https://issues.apache.org/jira/browse/TINKERPOP-1990
> Project: TinkerPop
> Issue Type: Improvement
> Components: process
>Reporter: Daniel Kuppitz
>Assignee: Daniel Kuppitz
>Priority: Major
>
> Implement {{ShortestPathVertexProgram}} and a {{shortestPath()}} step.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
