You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@tinkerpop.apache.org by mpollmeier <gi...@git.apache.org> on 2017/09/15 01:08:13 UTC
[GitHub] tinkerpop pull request #715: change behaviour of repeat step to be depth fir...
GitHub user mpollmeier opened a pull request:
https://github.com/apache/tinkerpop/pull/715
change behaviour of repeat step to be depth first search (DFS)
OLTP traversals are normally DFS unless there is you use a barrier
step. This wasn't the case for `repeat` though, and this PR fixes that.
Related discussion: https://groups.google.com/forum/#!topic/gremlin-users/gLSLxH_K-wE
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/mpollmeier/tinkerpop mp/make-repeat-step-dfs
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/tinkerpop/pull/715.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 #715
----
commit c69ce5a67aea39d25dfbcbc7d545b54f0389109b
Author: Michael Pollmeier <mi...@michaelpollmeier.com>
Date: 2017-09-15T01:03:02Z
change behaviour of repeat step to be depth first search (DFS)
OLTP traversals are normally DFS unless there is you use a barrier
step. This wasn't the case for `repeat` though, and this PR fixes that.
Related discussion: https://groups.google.com/forum/#!topic/gremlin-users/gLSLxH_K-wE
----
---
[GitHub] tinkerpop issue #715: change behaviour of repeat step to be depth first sear...
Posted by mpollmeier <gi...@git.apache.org>.
Github user mpollmeier commented on the issue:
https://github.com/apache/tinkerpop/pull/715
That's likely because of the RepeatUnrollStrategy, which kicks in when there's a foreseeable number of iterations. Needs to be changed as well I guess.
-----Original Message-----
From: Daniel Kuppitz <no...@github.com>
To: apache/tinkerpop <ti...@noreply.github.com>
Cc: Michael Pollmeier <mi...@michaelpollmeier.com>, Author <au...@noreply.github.com>
Sent: Sat, 16 Sep 2017 1:53
Subject: Re: [apache/tinkerpop] change behaviour of repeat step to be depth first search (DFS) (#715)
Using the modern graph:
```
gremlin> g.V().emit().repeat(both()).times(3).limit(15).path()
==>[v[1]]
==>[v[1],v[3]]
==>[v[1],v[2]]
==>[v[1],v[4]]
==>[v[1],v[3],v[1]]
==>[v[1],v[3],v[1],v[3]]
==>[v[1],v[3],v[1],v[2]]
==>[v[1],v[3],v[1],v[4]]
==>[v[1],v[3],v[4]]
==>[v[1],v[3],v[4],v[5]]
==>[v[1],v[3],v[4],v[3]]
==>[v[1],v[3],v[4],v[1]]
==>[v[1],v[3],v[6]]
==>[v[1],v[3],v[6],v[3]]
==>[v[1],v[2],v[1]]
```
^ This doesn't look like DFS to me. Row 3 and 4 should come much later.
--
You are receiving this because you authored the thread.
Reply to this email directly or view it on GitHub:
https://github.com/apache/tinkerpop/pull/715#issuecomment-329789246
---
[GitHub] tinkerpop issue #715: TINKERPOP-1822: change behaviour of repeat step to be ...
Posted by mpollmeier <gi...@git.apache.org>.
Github user mpollmeier commented on the issue:
https://github.com/apache/tinkerpop/pull/715
superseded by https://github.com/apache/tinkerpop/pull/838
---
[GitHub] tinkerpop issue #715: TINKERPOP-1822: change behaviour of repeat step to be ...
Posted by krlohnes <gi...@git.apache.org>.
Github user krlohnes commented on the issue:
https://github.com/apache/tinkerpop/pull/715
Okay, I have that fixed, I'll hopefully have something in the next few weeks that I've tested thoroughly.
---
[GitHub] tinkerpop issue #715: TINKERPOP-1822: change behaviour of repeat step to be ...
Posted by krlohnes <gi...@git.apache.org>.
Github user krlohnes commented on the issue:
https://github.com/apache/tinkerpop/pull/715
Last comment for tonight, it looks like that while loop works with TinkerGraph and a simple query. I believe the more complex query I wrote for the application I'm working on may have an issue. But for the k-ary tree I provided previously, that seems to work.
```
tgraph = TinkerGraph.open()
tg = tgraph.traversal(SpeedRacerTraversalSource.class)
v0 = tgraph.addVertex().property("level", "0:0").vertex
v1_0 = tgraph.addVertex().property("level", "1:0").vertex
v1_1 = tgraph.addVertex().property("level", "1:1").vertex
v1_2 = tgraph.addVertex().property("level", "1:2").vertex
v1_3 = tgraph.addVertex().property("level", "1:3").vertex
v0.addEdge("child", v1_0, "num", 0)
v0.addEdge("child", v1_2, "num", 2)
v0.addEdge("child", v1_1, "num", 1)
v0.addEdge("child", v1_3, "num", 3)
gremlin> tg.V().has("level", "0:0").repeatDF(__.out("child").order().by(__.inE("child").values("num"), incr)).emitDF()
loops: 0
v[2]
==>v[2]
loops: 0
v[4]
==>v[4]
loops: 0
v[6]
==>v[6]
loops: 0
v[8]
gremlin> tg.V().has("level", "0:0").repeatDF(__.out("child").order().by(__.inE("child").values("num"), incr)).emitDF()
loops: 0
v[2]
==>v[2]
loops: 0
v[4]
==>v[4]
loops: 0
v[6]
==>v[6]
loops: 0
v[8]
==>v[8]
```
---
[GitHub] tinkerpop issue #715: change behaviour of repeat step to be depth first sear...
Posted by mpollmeier <gi...@git.apache.org>.
Github user mpollmeier commented on the issue:
https://github.com/apache/tinkerpop/pull/715
`emit` modifies the behaviour of the repeat traversal, and I am unsure why that is. Let me explain what I know and hopefully you or someone else can fill the blanks.
Let's take my toy graph `v5 <- v3 <- v1 <- v0 -> v2 -> v4 -> v6` since it's easier to see where you are with a simple println of the vertex. Without emit, this PR does what it's supposed to do: DFS. First the even numbers, then the odds.
```
graph = TinkerGraph.open()
v0 = graph.addVertex("l0")
v1 = graph.addVertex("l1")
v2 = graph.addVertex("l1")
v3 = graph.addVertex("l2")
v4 = graph.addVertex("l2")
v5 = graph.addVertex("l3")
v6 = graph.addVertex("l3")
v0.addEdge("e", v2)
v2.addEdge("e", v4)
v4.addEdge("e", v6)
v0.addEdge("e", v1)
v1.addEdge("e", v3)
v3.addEdge("e", v5)
graph.traversal().V(v0).repeat(sideEffect{println("inside repeat at " + it)}.out()).times(3)
inside repeat at v[0]
inside repeat at v[2]
inside repeat at v[4]
==>v[6]
inside repeat at v[1]
inside repeat at v[3]
==>v[5]
```
However if I add an `emit()` it becomes BFS again:
```
graph.traversal().V(v0).emit().repeat(sideEffect{println("inside repeat at " + it)}.out()).times(3)
==>v[0]
inside repeat at v[0]
==>v[2]
inside repeat at v[2]
==>v[1]
inside repeat at v[1]
==>v[4]
inside repeat at v[4]
==>v[6]
==>v[3]
inside repeat at v[3]
==>v[5]
```
I tried to understand it in the debugger, and the core difference seems to be the behaviour of `this.starts.hasNext()` in `RepeatEndStep.standardAlgorithm`, which is an `ExpandableStepIterator`.
* without emit, `hasNext` finds that `this.hostStep.getPreviousStep().hasNext()` is true, because it asks it's `previousStep` (which is a `VertexStep(OUT)`), which in turns has some results for `processNextStart`.
* with emit, the above chain returns false, which in turn leads to a NoSuchElementException, which short-circuits and `while (true)` loop, which results in losing DFS semantics.
I don't know where these different semantics derive from.
---
[GitHub] tinkerpop pull request #715: TINKERPOP-1822: change behaviour of repeat step...
Posted by mpollmeier <gi...@git.apache.org>.
Github user mpollmeier closed the pull request at:
https://github.com/apache/tinkerpop/pull/715
---
[GitHub] tinkerpop issue #715: TINKERPOP-1822: change behaviour of repeat step to be ...
Posted by krlohnes <gi...@git.apache.org>.
Github user krlohnes commented on the issue:
https://github.com/apache/tinkerpop/pull/715
So it's not quite fixed. I changed the while loop to
```
int i = 0;
while (this.starts.hasNext()) {
if (i==0) {
stashedStarts.push(this.starts.next());
} else {
stashedStarts.add(this.starts.next());
}
i++;
}
```
Which sort of works, but only if the the edges are inserted in the right order. I'm still trying to figure out if it's possible to order the starts properly.
---
[GitHub] tinkerpop issue #715: TINKERPOP-1822: change behaviour of repeat step to be ...
Posted by mpollmeier <gi...@git.apache.org>.
Github user mpollmeier commented on the issue:
https://github.com/apache/tinkerpop/pull/715
@krlohnes thanks for jumping in! This is still an open issue for me, so I'll test your suggestion as soon as I find some time. Let me know how your testing goes, maybe we can get this one over the line.
---
[GitHub] tinkerpop issue #715: change behaviour of repeat step to be depth first sear...
Posted by dkuppitz <gi...@git.apache.org>.
Github user dkuppitz commented on the issue:
https://github.com/apache/tinkerpop/pull/715
Using the modern graph:
```
gremlin> g.V().emit().repeat(both()).times(3).limit(15).path()
==>[v[1]]
==>[v[1],v[3]]
==>[v[1],v[2]]
==>[v[1],v[4]]
==>[v[1],v[3],v[1]]
==>[v[1],v[3],v[1],v[3]]
==>[v[1],v[3],v[1],v[2]]
==>[v[1],v[3],v[1],v[4]]
==>[v[1],v[3],v[4]]
==>[v[1],v[3],v[4],v[5]]
==>[v[1],v[3],v[4],v[3]]
==>[v[1],v[3],v[4],v[1]]
==>[v[1],v[3],v[6]]
==>[v[1],v[3],v[6],v[3]]
==>[v[1],v[2],v[1]]
```
^ This doesn't look like DFS to me. Row 3 and 4 should come much later.
---
[GitHub] tinkerpop pull request #715: TINKERPOP-1822: change behaviour of repeat step...
Posted by krlohnes <gi...@git.apache.org>.
Github user krlohnes commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/715#discussion_r169194905
--- Diff: gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/branch/RepeatStep.java ---
@@ -271,7 +274,17 @@ public RepeatEndStep(final Traversal.Admin traversal) {
protected Iterator<Traverser.Admin<S>> standardAlgorithm() throws NoSuchElementException {
final RepeatStep<S> repeatStep = (RepeatStep<S>) this.getTraversal().getParent();
while (true) {
- final Traverser.Admin<S> start = this.starts.next();
+ final Traverser.Admin<S> start;
+ if (this.starts.hasNext()) {
+ start = this.starts.next();
+ } else {
+ start = this.stashedStarts.pop();
+ }
+ // to make this step depth first search (DFS), we're stashing the remainder for later
+ while (this.starts.hasNext()) {
+ stashedStarts.add(this.starts.next());
--- End diff --
I think this should be `push` rather than `add` so you maintain a consistent `stack` behavior for a DFS.
---
[GitHub] tinkerpop issue #715: change behaviour of repeat step to be depth first sear...
Posted by dkuppitz <gi...@git.apache.org>.
Github user dkuppitz commented on the issue:
https://github.com/apache/tinkerpop/pull/715
It's not. It can't be unrolled, since I'm using emit().
---
[GitHub] tinkerpop issue #715: TINKERPOP-1822: change behaviour of repeat step to be ...
Posted by krlohnes <gi...@git.apache.org>.
Github user krlohnes commented on the issue:
https://github.com/apache/tinkerpop/pull/715
@mpollmeier Sure thing! One thing that I've noticed is that currently, `emit` doesn't emit in the order I'd expect for multiple children. e.g. for a simple k-ary tree with 4 nodes, though it seems to work with a binary tree. The following has `emit` vs `store` + `cap`. `cap` produces the order that I'd expect from emit.
```
v0 = graph.addVertex().property("level", "0:0").vertex
v1_0 = graph.addVertex().property("level", "1:0").vertex
v1_1 = graph.addVertex().property("level", "1:1").vertex
v1_2 = graph.addVertex().property("level", "1:2").vertex
v1_3 = graph.addVertex().property("level", "1:3").vertex
v0.addEdge("child", v1_0, "num", 0)
v0.addEdge("child", v1_1, "num", 1)
v0.addEdge("child", v1_2, "num", 2)
v0.addEdge("child", v1_3, "num", 3)
gremlin> g.V().has("level", "0:0").repeat(__.out("child").order().by(__.inE("child").values("num"))).emit()
==>v[2]
==>v[8]
==>v[6]
==>v[4]
gremlin> g.V().has("level", "0:0").repeatDF(__.out("child").order().by(__.inE("child").values("num")).store("res")).cap("res")
==>[v[2],v[4],v[6],v[8]]
```
I'll look in to it when I have a few minutes, but I figured I'd update here in case someone has a thought about it or I'm missing something obvious.
---
[GitHub] tinkerpop issue #715: change behaviour of repeat step to be depth first sear...
Posted by robertdale <gi...@git.apache.org>.
Github user robertdale commented on the issue:
https://github.com/apache/tinkerpop/pull/715
@mpollmeier Making it official. Please update the title to start with `TINKERPOP-1822`
---