Transitive Closure in Gremlin 3.x?

239 views
Skip to first unread message

Martin Häusler

unread,
Jan 21, 2018, 10:01:45 AM1/21/18
to Gremlin-users
Hello everyone,

I need to calculate the transitive reachability closure of a vertex and an edge label. For example, if you consider a social graph where each vertex represents a person and friendship is indicated by the label "friend", I need to calculate all friends-of-my-friends transitively.

In Tinkerpop 3.x, this needs to be formulated as a "repeat-until" loop (please correct me if I'm wrong here):

g.traversal().V("start vertex id").repeat().out("friend").until(untilCriterion)

However, I'm having difficulties formulating the "until" criterion. It is something like "until all reachable vertices have been emitted".

Any help on this would be much appreciated.

Best,

Martin

Martin Häusler

unread,
Jan 21, 2018, 10:15:54 AM1/21/18
to Gremlin-users
The solution should be something like discussed here:

... except for Gremlin 3.x. Right now I just can't figure out how to do it in the 3.x API.

Martin Häusler

unread,
Feb 12, 2018, 1:34:17 PM2/12/18
to Gremlin-users
Okay I've figured it out. I had a wrong line of thought there. In a TinkerPop traversal, it's perfectly fine to have an "infinite" loop, like:

g.traversal()
    .V(startVertex)
    .repeat(out("friend")).until(t -> false)

... because the traversal will terminate upon exhaustion of the graph anyways! Be careful with loops though. I think you might need to use a side effect and carry along a hash set of already traversed vertices to deal with loops in the graph structure.

Robert Dale

unread,
Feb 12, 2018, 1:44:26 PM2/12/18
to gremli...@googlegroups.com
You might want to look at cyclicPath() [1] and simplePath() [2].  There are also good examples of using these in loops in Recipes[3].



Robert Dale

--
You received this message because you are subscribed to the Google Groups "Gremlin-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gremlin-users+unsubscribe@googlegroups.com.
 To view this discussion on the web visit https://groups.google.com/d/msgid/gremlin-users/41f182d9-a797-41be-bbaf-81c89b51326d%40googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

Martin Häusler

unread,
Feb 12, 2018, 1:48:34 PM2/12/18
to Gremlin-users
I had a quick look at the docs. The way I understand it is that you can use "simplePath()" to eliminate traversers that contain a cyclic path, is that correct? If so, then that's really awesome! I need to experiment more with this. I still find several of the TinkerPop 3.x traversal steps to be named in a rather awkward fashion which makes it difficult to search for them.

Thanks for the pointer!

Martin


Am Montag, 12. Februar 2018 19:44:26 UTC+1 schrieb Robert Dale:
You might want to look at cyclicPath() [1] and simplePath() [2].  There are also good examples of using these in loops in Recipes[3].



Robert Dale

On Mon, Feb 12, 2018 at 1:34 PM, Martin Häusler <alanda...@gmail.com> wrote:
Okay I've figured it out. I had a wrong line of thought there. In a TinkerPop traversal, it's perfectly fine to have an "infinite" loop, like:

g.traversal()
    .V(startVertex)
    .repeat(out("friend")).until(t -> false)

... because the traversal will terminate upon exhaustion of the graph anyways! Be careful with loops though. I think you might need to use a side effect and carry along a hash set of already traversed vertices to deal with loops in the graph structure.


Am Sonntag, 21. Januar 2018 16:15:54 UTC+1 schrieb Martin Häusler:
The solution should be something like discussed here:

... except for Gremlin 3.x. Right now I just can't figure out how to do it in the 3.x API.

--
You received this message because you are subscribed to the Google Groups "Gremlin-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gremlin-user...@googlegroups.com.
Reply all
Reply to author
Forward
0 new messages