You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@tinkerpop.apache.org by newkek <gi...@git.apache.org> on 2018/08/24 21:23:58 UTC
[GitHub] tinkerpop pull request #921: Add self loop example to Cycle Detection recipe...
GitHub user newkek opened a pull request:
https://github.com/apache/tinkerpop/pull/921
Add self loop example to Cycle Detection recipe.
Not sure if it is worth it but I figured out that self loops weren't detected in the given example.
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/newkek/incubator-tinkerpop cycles-recipe-self-loops
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/tinkerpop/pull/921.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 #921
----
commit 87ce35824dac27f6bba9329aeb88b49940187c55
Author: Kevin Gallardo <ke...@...>
Date: 2018-08-24T21:18:43Z
Add self loop example to Cycle Detection recipe.
----
---
[GitHub] tinkerpop issue #921: Add self loop example to Cycle Detection recipe.
Posted by dkuppitz <gi...@git.apache.org>.
Github user dkuppitz commented on the issue:
https://github.com/apache/tinkerpop/pull/921
VOTE +1
---
[GitHub] tinkerpop pull request #921: Add self loop example to Cycle Detection recipe...
Posted by dkuppitz <gi...@git.apache.org>.
Github user dkuppitz commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/921#discussion_r213065687
--- Diff: docs/src/recipes/cycle-detection.asciidoc ---
@@ -48,6 +48,25 @@ the length of the cycle is known to be three and there is no need to exceed that
cycle. It returned three, because there was one for each vertex that started the cycle (i.e. one for `A`, one for `B`
and one for `C`). This next line introduce deduplication to only return unique cycles.
+Note that these traversals won't detect self-loops (vertices directly connected to themselves).
+To do so, you would need to `.emit()` a Traverser before the repeat()-loop.
+
+[gremlin-groovy]
+----
+g.addV().property(id,'a').as('a').
+ addV().property(id,'b').as('b').
+ addV().property(id,'c').as('c').
+ addV().property(id,'d').as('d').
+ addE('knows').from('a').to('b').
+ addE('knows').from('b').to('c').
+ addE('knows').from('c').to('a').
+ addE('knows').from('a').to('d').
+ addE('knows').from('c').to('d').
+ addE('self').from('a').to('a').iterate()
+g.V().as('a').emit().repeat(out().simplePath()).times(2).
+ where(out().as('a')).path()
--- End diff --
Really just readability. To me `[a,self,a]` looks better than just `[a,a]`.
---
[GitHub] tinkerpop pull request #921: Add self loop example to Cycle Detection recipe...
Posted by dkuppitz <gi...@git.apache.org>.
Github user dkuppitz commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/921#discussion_r212807145
--- Diff: docs/src/recipes/cycle-detection.asciidoc ---
@@ -48,6 +48,25 @@ the length of the cycle is known to be three and there is no need to exceed that
cycle. It returned three, because there was one for each vertex that started the cycle (i.e. one for `A`, one for `B`
and one for `C`). This next line introduce deduplication to only return unique cycles.
+Note that these traversals won't detect self-loops (vertices directly connected to themselves).
+To do so, you would need to `.emit()` a Traverser before the repeat()-loop.
+
+[gremlin-groovy]
+----
+g.addV().property(id,'a').as('a').
+ addV().property(id,'b').as('b').
+ addV().property(id,'c').as('c').
+ addV().property(id,'d').as('d').
+ addE('knows').from('a').to('b').
+ addE('knows').from('b').to('c').
+ addE('knows').from('c').to('a').
+ addE('knows').from('a').to('d').
+ addE('knows').from('c').to('d').
+ addE('self').from('a').to('a').iterate()
+g.V().as('a').emit().repeat(out().simplePath()).times(2).
+ where(out().as('a')).path()
--- End diff --
I would tweaks the traversal a little bit to make the output easier to grasp:
```
gremlin> g.V().as('a').
......1> emit().
......2> repeat(outE().inV().simplePath()).
......3> times(2).
......4> outE().inV().where(eq('a')).
......5> path().
......6> by(id).
......7> by(label)
==>[a,self,a]
==>[a,knows,b,knows,c,knows,a]
==>[b,knows,c,knows,a,knows,b]
==>[c,knows,a,knows,b,knows,c]
```
---
[GitHub] tinkerpop pull request #921: Add self loop example to Cycle Detection recipe...
Posted by newkek <gi...@git.apache.org>.
Github user newkek commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/921#discussion_r213361478
--- Diff: docs/src/recipes/cycle-detection.asciidoc ---
@@ -48,6 +48,31 @@ the length of the cycle is known to be three and there is no need to exceed that
cycle. It returned three, because there was one for each vertex that started the cycle (i.e. one for `A`, one for `B`
and one for `C`). This next line introduce deduplication to only return unique cycles.
+Note that these traversals won't detect self-loops (vertices directly connected to themselves).
+To do so, you would need to `.emit()` a Traverser before the repeat()-loop.
+
+[gremlin-groovy]
+----
+g.addV().property(id,'a').as('a').
+ addV().property(id,'b').as('b').
+ addV().property(id,'c').as('c').
+ addV().property(id,'d').as('d').
+ addE('knows').from('a').to('b').
+ addE('knows').from('b').to('c').
+ addE('knows').from('c').to('a').
+ addE('knows').from('a').to('d').
+ addE('knows').from('c').to('d').
+ addE('self').from('a').to('a').iterate()
+g.V().as('a').
+ emit().
+ repeat(outE().inV().simplePath()).
+ times(2).
+ outE().inV().where(eq('a')).
+ path().
+ by(id).
+ by(label)
+----
+
--- End diff --
Hm the issue with the Traversal below is that it improves things further by formatting results more and doing unidirectional traversing on an unrestricted path length. Since the examples get more complicated as you progress through the document, if I put this self loop traversal under the more complicated one it feels like going backwards. Additionally the traversal below refers to the modern graph, whereas the first one and this self-loop one are similar, wdyt?
---
[GitHub] tinkerpop pull request #921: Add self loop example to Cycle Detection recipe...
Posted by newkek <gi...@git.apache.org>.
Github user newkek commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/921#discussion_r213426961
--- Diff: docs/src/recipes/cycle-detection.asciidoc ---
@@ -48,6 +48,31 @@ the length of the cycle is known to be three and there is no need to exceed that
cycle. It returned three, because there was one for each vertex that started the cycle (i.e. one for `A`, one for `B`
and one for `C`). This next line introduce deduplication to only return unique cycles.
+Note that these traversals won't detect self-loops (vertices directly connected to themselves).
+To do so, you would need to `.emit()` a Traverser before the repeat()-loop.
+
+[gremlin-groovy]
+----
+g.addV().property(id,'a').as('a').
+ addV().property(id,'b').as('b').
+ addV().property(id,'c').as('c').
+ addV().property(id,'d').as('d').
+ addE('knows').from('a').to('b').
+ addE('knows').from('b').to('c').
+ addE('knows').from('c').to('a').
+ addE('knows').from('a').to('d').
+ addE('knows').from('c').to('d').
+ addE('self').from('a').to('a').iterate()
+g.V().as('a').
+ emit().
+ repeat(outE().inV().simplePath()).
+ times(2).
+ outE().inV().where(eq('a')).
+ path().
+ by(id).
+ by(label)
+----
+
--- End diff --
Okay. well no strong opinion here I can change it for that
---
[GitHub] tinkerpop pull request #921: Add self loop example to Cycle Detection recipe...
Posted by dkuppitz <gi...@git.apache.org>.
Github user dkuppitz commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/921#discussion_r213364785
--- Diff: docs/src/recipes/cycle-detection.asciidoc ---
@@ -48,6 +48,31 @@ the length of the cycle is known to be three and there is no need to exceed that
cycle. It returned three, because there was one for each vertex that started the cycle (i.e. one for `A`, one for `B`
and one for `C`). This next line introduce deduplication to only return unique cycles.
+Note that these traversals won't detect self-loops (vertices directly connected to themselves).
+To do so, you would need to `.emit()` a Traverser before the repeat()-loop.
+
+[gremlin-groovy]
+----
+g.addV().property(id,'a').as('a').
+ addV().property(id,'b').as('b').
+ addV().property(id,'c').as('c').
+ addV().property(id,'d').as('d').
+ addE('knows').from('a').to('b').
+ addE('knows').from('b').to('c').
+ addE('knows').from('c').to('a').
+ addE('knows').from('a').to('d').
+ addE('knows').from('c').to('d').
+ addE('self').from('a').to('a').iterate()
+g.V().as('a').
+ emit().
+ repeat(outE().inV().simplePath()).
+ times(2).
+ outE().inV().where(eq('a')).
+ path().
+ by(id).
+ by(label)
+----
+
--- End diff --
I mean just put the paragraph that starts with
> The above case assumed that ...
above your new block that starts with
> Note that these ...
That would make more sense, no?
---
[GitHub] tinkerpop pull request #921: Add self loop example to Cycle Detection recipe...
Posted by newkek <gi...@git.apache.org>.
Github user newkek commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/921#discussion_r213448492
--- Diff: docs/src/recipes/cycle-detection.asciidoc ---
@@ -48,6 +48,31 @@ the length of the cycle is known to be three and there is no need to exceed that
cycle. It returned three, because there was one for each vertex that started the cycle (i.e. one for `A`, one for `B`
and one for `C`). This next line introduce deduplication to only return unique cycles.
+Note that these traversals won't detect self-loops (vertices directly connected to themselves).
+To do so, you would need to `.emit()` a Traverser before the repeat()-loop.
+
+[gremlin-groovy]
+----
+g.addV().property(id,'a').as('a').
+ addV().property(id,'b').as('b').
+ addV().property(id,'c').as('c').
+ addV().property(id,'d').as('d').
+ addE('knows').from('a').to('b').
+ addE('knows').from('b').to('c').
+ addE('knows').from('c').to('a').
+ addE('knows').from('a').to('d').
+ addE('knows').from('c').to('d').
+ addE('self').from('a').to('a').iterate()
+g.V().as('a').
+ emit().
+ repeat(outE().inV().simplePath()).
+ times(2).
+ outE().inV().where(eq('a')).
+ path().
+ by(id).
+ by(label)
+----
+
--- End diff --
Done
---
[GitHub] tinkerpop pull request #921: Add self loop example to Cycle Detection recipe...
Posted by newkek <gi...@git.apache.org>.
Github user newkek commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/921#discussion_r213372950
--- Diff: docs/src/recipes/cycle-detection.asciidoc ---
@@ -48,6 +48,31 @@ the length of the cycle is known to be three and there is no need to exceed that
cycle. It returned three, because there was one for each vertex that started the cycle (i.e. one for `A`, one for `B`
and one for `C`). This next line introduce deduplication to only return unique cycles.
+Note that these traversals won't detect self-loops (vertices directly connected to themselves).
+To do so, you would need to `.emit()` a Traverser before the repeat()-loop.
+
+[gremlin-groovy]
+----
+g.addV().property(id,'a').as('a').
+ addV().property(id,'b').as('b').
+ addV().property(id,'c').as('c').
+ addV().property(id,'d').as('d').
+ addE('knows').from('a').to('b').
+ addE('knows').from('b').to('c').
+ addE('knows').from('c').to('a').
+ addE('knows').from('a').to('d').
+ addE('knows').from('c').to('d').
+ addE('self').from('a').to('a').iterate()
+g.V().as('a').
+ emit().
+ repeat(outE().inV().simplePath()).
+ times(2).
+ outE().inV().where(eq('a')).
+ path().
+ by(id).
+ by(label)
+----
+
--- End diff --
```
The above case assumed that the need was to only detect cycles over a path length of three.
It also respected the directionality of the edges by only considering outgoing ones.
Also note that this traversal won't detect self-loops [....]
--
[self-loop code example]
--
What would need to change to detect cycles of arbitrary length over both incoming and
outgoing edges, in the modern graph?
--
[bi-directional code example]
--
[...]
```
Is that what you meant?
---
[GitHub] tinkerpop pull request #921: Add self loop example to Cycle Detection recipe...
Posted by dkuppitz <gi...@git.apache.org>.
Github user dkuppitz commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/921#discussion_r213148817
--- Diff: docs/src/recipes/cycle-detection.asciidoc ---
@@ -48,6 +48,31 @@ the length of the cycle is known to be three and there is no need to exceed that
cycle. It returned three, because there was one for each vertex that started the cycle (i.e. one for `A`, one for `B`
and one for `C`). This next line introduce deduplication to only return unique cycles.
+Note that these traversals won't detect self-loops (vertices directly connected to themselves).
+To do so, you would need to `.emit()` a Traverser before the repeat()-loop.
+
+[gremlin-groovy]
+----
+g.addV().property(id,'a').as('a').
+ addV().property(id,'b').as('b').
+ addV().property(id,'c').as('c').
+ addV().property(id,'d').as('d').
+ addE('knows').from('a').to('b').
+ addE('knows').from('b').to('c').
+ addE('knows').from('c').to('a').
+ addE('knows').from('a').to('d').
+ addE('knows').from('c').to('d').
+ addE('self').from('a').to('a').iterate()
+g.V().as('a').
+ emit().
+ repeat(outE().inV().simplePath()).
+ times(2).
+ outE().inV().where(eq('a')).
+ path().
+ by(id).
+ by(label)
+----
+
--- End diff --
Cool, much better. What I didn't notice in the first place, was that the paragraph below really only refers to the previous code snippets. I think you should move it above you changes.
---
[GitHub] tinkerpop pull request #921: Add self loop example to Cycle Detection recipe...
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit closed the pull request at:
https://github.com/apache/tinkerpop/pull/921
---
[GitHub] tinkerpop pull request #921: Add self loop example to Cycle Detection recipe...
Posted by newkek <gi...@git.apache.org>.
Github user newkek commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/921#discussion_r212996772
--- Diff: docs/src/recipes/cycle-detection.asciidoc ---
@@ -48,6 +48,25 @@ the length of the cycle is known to be three and there is no need to exceed that
cycle. It returned three, because there was one for each vertex that started the cycle (i.e. one for `A`, one for `B`
and one for `C`). This next line introduce deduplication to only return unique cycles.
+Note that these traversals won't detect self-loops (vertices directly connected to themselves).
+To do so, you would need to `.emit()` a Traverser before the repeat()-loop.
+
+[gremlin-groovy]
+----
+g.addV().property(id,'a').as('a').
+ addV().property(id,'b').as('b').
+ addV().property(id,'c').as('c').
+ addV().property(id,'d').as('d').
+ addE('knows').from('a').to('b').
+ addE('knows').from('b').to('c').
+ addE('knows').from('c').to('a').
+ addE('knows').from('a').to('d').
+ addE('knows').from('c').to('d').
+ addE('self').from('a').to('a').iterate()
+g.V().as('a').emit().repeat(out().simplePath()).times(2).
+ where(out().as('a')).path()
--- End diff --
@dkuppitz what is the added value of `outE().inV()` compared to `out()`?
---
[GitHub] tinkerpop pull request #921: Add self loop example to Cycle Detection recipe...
Posted by dkuppitz <gi...@git.apache.org>.
Github user dkuppitz commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/921#discussion_r213398454
--- Diff: docs/src/recipes/cycle-detection.asciidoc ---
@@ -48,6 +48,31 @@ the length of the cycle is known to be three and there is no need to exceed that
cycle. It returned three, because there was one for each vertex that started the cycle (i.e. one for `A`, one for `B`
and one for `C`). This next line introduce deduplication to only return unique cycles.
+Note that these traversals won't detect self-loops (vertices directly connected to themselves).
+To do so, you would need to `.emit()` a Traverser before the repeat()-loop.
+
+[gremlin-groovy]
+----
+g.addV().property(id,'a').as('a').
+ addV().property(id,'b').as('b').
+ addV().property(id,'c').as('c').
+ addV().property(id,'d').as('d').
+ addE('knows').from('a').to('b').
+ addE('knows').from('b').to('c').
+ addE('knows').from('c').to('a').
+ addE('knows').from('a').to('d').
+ addE('knows').from('c').to('d').
+ addE('self').from('a').to('a').iterate()
+g.V().as('a').
+ emit().
+ repeat(outE().inV().simplePath()).
+ times(2).
+ outE().inV().where(eq('a')).
+ path().
+ by(id).
+ by(label)
+----
+
--- End diff --
Yep.
---
[GitHub] tinkerpop pull request #921: Add self loop example to Cycle Detection recipe...
Posted by newkek <gi...@git.apache.org>.
Github user newkek commented on a diff in the pull request:
https://github.com/apache/tinkerpop/pull/921#discussion_r212996121
--- Diff: docs/src/recipes/cycle-detection.asciidoc ---
@@ -48,6 +48,25 @@ the length of the cycle is known to be three and there is no need to exceed that
cycle. It returned three, because there was one for each vertex that started the cycle (i.e. one for `A`, one for `B`
and one for `C`). This next line introduce deduplication to only return unique cycles.
+Note that these traversals won't detect self-loops (vertices directly connected to themselves).
+To do so, you would need to `.emit()` a Traverser before the repeat()-loop.
+
+[gremlin-groovy]
+----
+g.addV().property(id,'a').as('a').
+ addV().property(id,'b').as('b').
+ addV().property(id,'c').as('c').
+ addV().property(id,'d').as('d').
+ addE('knows').from('a').to('b').
+ addE('knows').from('b').to('c').
+ addE('knows').from('c').to('a').
+ addE('knows').from('a').to('d').
+ addE('knows').from('c').to('d').
+ addE('self').from('a').to('a').iterate()
+g.V().as('a').emit().repeat(out().simplePath()).times(2).
+ where(out().as('a')).path()
--- End diff --
Good point!
---