Use Gremlin to find the shortest path in a graph, avoiding a given list of vertices?

Question

I need to use Gremlin to find the shortest path between two nodes (vertices), while avoiding the list of given vertices.

I already have:

v.bothE.bothV.loop(2){!it.object.equals(y)}.paths>>1

To get the shortest path.

I tried something like:

v.bothE.bothV.filter{it.name!="ignored"}.loop(3){!it.object.equals(y)}.paths>>1

but it does not work.

HELP HELP !!!

Answer 1

The second solution you have looks right. However, to understand what you are trying to achieve. If x and y are the vertices that you want to find for the shortest path and the vertices to ignore during the traversal, if it has the property name: "ignored", the request is as follows:

 x.both.filter{it.name!="ignored"}.loop(2){!it.object.equals(y)}.paths>>1 

If the "list of given vertices" that you want to filter is actually a list, then the traversal is described as such:

 list = [ ... ] // construct some list x.both.except(list).loop(2){!it.object.equals(y)}.paths>>1 

In addition, I try to use the range filter only to be safe, as this will go into an infinite loop if you forget → 1 :)

 x.both.except(list).loop(2){!it.object.equals(y)}[1].paths>>1 

In addition, if there is potential for the lack of a path, then to avoid an infinitely long search, you can make a loop restriction (for example, no more than 4 steps):

 x.both.except(list).loop(2){!it.object.equals(y) & it.loop < 5}.filter{it.object.equals(y)}.paths>>1 

Note why you need the last filter step before the paths. There are two reasons why a cycle occurs. So you may not be at y when you exit the loop (instead, you exit the loop because it.loops <5).

Here's a solution for the Grateful Dead graph distributed with Gremlin. First, create the code where we load the graph and define two vertices x and y:

 gremlin> g = new TinkerGraph() ==>tinkergraph[vertices:0 edges:0] gremlin> g.loadGraphML('data/graph-example-2.xml') ==>null gremlin> x = gv(89) ==>v[89] gremlin> y = gv(100) ==>v[100] gremlin> x.name ==>DARK STAR gremlin> y.name ==>BROWN EYED WOMEN 

Now your workaround. Note that there is no name: the property is “ignored”, so instead I changed it to take into account the number of times each song played along the way. Thus, the shortest path of songs was reproduced more than 10 times:

 gremlin> x.both.filter{it.performances > 10}.loop(2){!it.object.equals(y)}.paths>>1 ==>v[89] ==>v[26] ==>v[100] 

If you are using Gremlin 1.2+, you can use path closure to provide the names of these vertices (for example), and not just raw vertex objects:

 gremlin> x.both.filter{it.performances > 10}.loop(2){!it.object.equals(y)}.paths{it.name}>>1 ==>DARK STAR ==>PROMISED LAND ==>BROWN EYED WOMEN 

Hope this helps.

Good luck Marco.