9

I know this was asked several time but I haven't found any reference regarding the last version of Tinkerpop (3.1), featuring many new useful functions we can use in our traversals.

Let's say I have to find a shortest path between nodes 3 and 4. Is this traversal sound?

g.V(3).repeat(out()).until(id().is(4).and().simplePath()).path().limit(1)

Here I'm assuming that when I'm looping a BFS search is executed (thus, the first result is the shortest path) as it seems that this was the case with the loop() function.

Additionally, is there any way to include a previously bound variable (by using an as step) in the until step? More precisely, I'm trying to select two nodes during the traversal, and then finding the shortest path between them, for example,

g.V().match(
__as('e0').out('Feedbacks').as('e1'),
__as('e0').repeat(out('Meets')).until(<I reach e1>).path().<get_length>.as('len')
).select('e0', 'e1', 'len')

Finally, as can be seen from the previous traversal, it's not clear to me how I can get the length of the shortest path. Using something like

g.V(3).repeat(out()).until(id().is(4).and().simplePath()).path().size()

returns the size of the result (number of rows returned), while

g.V(3).repeat(out()).until(id().is(4).and().simplePath()).path().by(__size())

returns an error.

Here is the graph I'm experimenting with, should anybody want to play a bit.

graph = TinkerGraph.open()
e0 = graph.addVertex(T.id, 0, label, "User", "name", "e0")
e1 = graph.addVertex(T.id, 1, label, "User", "name", "e1")
e2 = graph.addVertex(T.id, 2, label, "User", "name", "e2")
e3 = graph.addVertex(T.id, 3, label, "User", "name", "e3")
e4 = graph.addVertex(T.id, 4, label, "User", "name", "e4")
e0.addEdge("Feedbacks", e2)
e0.addEdge("Meets", e1)
e2.addEdge("Feedbacks", e4)
e2.addEdge("Meets", e4)
e3.addEdge("Feedbacks", e0)
e3.addEdge("Meets", e2)
e4.addEdge("Feedbacks", e0)
g = graph.traversal()
Alberto
  • 597
  • 3
  • 17

1 Answers1

14

There's a slightly shorter variant for your shortest path query:

g.V(3).repeat(out().simplePath()).until(hasId(4)).path().limit(1)

Your assumption, that the first path is always the shortest path, is correct. To get the path lengths, you can use count(local):

g.V(3).repeat(out().simplePath()).until(hasId(4)).path().count(local)

UPDATE

Regarding your updated query, this one should solve the problem:

g.V().as("e0").out("Feedbacks").as("e1").select("e0").
      repeat(out("Meets")).until(where(eq("e1"))).path().
      map(union(count(local), constant(-2)).sum()).as("len").
      select("e0","e1","len")

I subtract 2 from the overall path length, because I think that you're only interested in the length of the path traversed by the repeat() block and the out().select() in the beginning should not be included. If that's not the case, then you can simply replace the 3rd line with count(local).as("len")..

Daniel Kuppitz
  • 10,846
  • 1
  • 25
  • 34
  • Thanks @Daniel Kuppitz. While you were writing your answer I modified the question. Will you have a bit of time to check the new request, that is, how i reference to a previously aliased node in the `until()` step? – Alberto Dec 02 '15 at 15:18
  • Sorry for bothering again but.. I'm now trying to merge the results of the two questions by computing the length of the 'Meets' *undirected* (`both('Meets')`)shortest path connecting two vertices connected by a Feedbacks edge. It's not that trivial as I cannot use `simplePath()` inside the `repeat()` because of the `as('e0')`-`select('e0')` patterns, and I cannot select the first path with a `limit(1)` after `until()` since otherwise I loose solutions. Do you have any idea how to tackle this? – Alberto Dec 07 '15 at 10:42
  • 1
    Make your life easier by splitting it into 2 separate queries - first iterate over all `e0` and `e1` and for each paar check if you can find a shortest path. Once a path is found, break out of the iteration. – Daniel Kuppitz Dec 07 '15 at 15:52
  • To combine the queries, you would have to use a custom simple path check. Something like: `g.V().as("e0").out("Feedbacks").as("e1").select("e0").repeat(out("Meets").filter(match(__.as("a").path().as("p"), __.as("p").count(local).as("c"), __.as("p").union(dedup(local).count(local), constant(3)).sum().as("c")))).until(where(eq("e1"))).path().map(union(count(local), constant(-2)).sum()).as("len").select("e0","e1","len")` -- but IMO it's really not necessary ti make it so complicated. – Daniel Kuppitz Dec 07 '15 at 15:54
  • Done! I've followed your first advice and I separated the traversal in two parts obtaining `w = [] for( fb in g.V().as('e0').out('Feedbacks').as('e1').select('e0', 'e1') ){ w.add( g.V(fb.e0). repeat(both('Meets').simplePath()). until( where(id().is(fb.e1.id())) ). path().by('name').next() ) } w`. Thanks again. I owe you a beer (or two :) ). – Alberto Dec 08 '15 at 08:35
  • How to achieve this in python ?I tried g.V(3).repeat(out().simplePath()).until(hasId(4)).path().count(local), it doesnt give me the literal value. – dks551 Oct 22 '19 at 09:38