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

Question

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

I already have:

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

To get my shortest path.

I was attempting something like:

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

but it does not seem to work.

Please HELP!!!

Answer 1

The second solution you have looks correct. However, to be clear on what you are trying to accomplish. If x and y are the vertices that you want to find the shortest path between and a vertex to ignore during the traversal if it has the property name:"ignored", then the query is:

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

If the "list of given vertices" you want filtered 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

Moreover, I tend to use a range filter just to be safe as this will go into an infinite loop if you forget the >>1 :)

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

Also, if there is a potential for no path, then to avoid an infinitely long search, you can do a loop limit (e.g. 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 the last filter step before paths is needed. There are two reasons the loop is broken out of. Thus, you might not be at y when you break out of the loop (instead, you broke out of the loop because it.loops < 5).

Here is you solution implemented over the Grateful Dead graph distributed with Gremlin. First some set up 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 = g.v(89) 
==>v[89]
gremlin> y = g.v(100) 
==>v[100]
gremlin> x.name
==>DARK STAR
gremlin> y.name
==>BROWN EYED WOMEN

Now your traversal. Note that there is not name:"ignored" property, so instead, I altered it to account for the number of performances of each song along the path. Thus, shortest path of songs played more than 10 times in concert:

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

If you use Gremlin 1.2+, then you can use a path closure to provide the names of those vertices (for example) instead of just the 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

I hope that helps.

Good luck! Marko.