optimizing shortest path query to return only shortest path

[Aparna V]

Hey all,

I am using the following gremlin java code to get shortest path between two vertices v1 and v2 ( from http://gremlindocs.com/#recipes/shortest-path):

GremlinPipeline<Vertex,List> pipe = new GremlinPipeline<Vertex,List>().start(v1).as("x").out("friend").

                                                      loop("x", new PipeFunction<LoopPipe.LoopBundle<Vertex>, Boolean>(){

                                                              public boolean compute(LoopBundle<Vertex> bundle)

                                                              {

                                                                      if(!bundle.getObject().getId().equals(v2.getId()))

                                                                       return true;

                                                                      else

                                                                         return false;

                                                               }

                                                        }).path();

It works fine. With

while(pipe.hasNext())

System.out.println(l.next());

I can see all the paths beteen v1 and v2. As mentioned in http://stackoverflow.com/questions/20564429/find-shortest-path-using-gremlinpipeline, I can get the pop the first resul to get the shortest path.

Trouble is, this query is very slow because it computes all the paths between two vertices. What I would ideally like to do is force a breadth first search and terminate the loop the first time v2 is encountered. That way all possible paths are not explored.

I have  arequirement to compute shortest path from about 100 nodes to 300,000 nodes in my graph.

The time this takes just wont do.

How do I implement a BFS through gremlin java and terminate the loop at the first encounter of v2?

Thanks,

Aparna

[Daniel Kuppitz]

Hi,

the loop step already makes your traversal a BFS. However, it doesn't automatically stop at the first occurence of v2. The following code will do the trick:

final Graph g = TinkerGraphFactory.createTinkerGraph(); // see model

g.getVertex(1).addEdge("knows", g.getVertex(6));

final Vertex v1 = g.getVertex(2);

final Vertex v2 = g.getVertex(6);

final Set<Vertex> x = new HashSet<>(Collections.singleton(v1));

final GremlinPipeline<Object, List> pipe = new GremlinPipeline<>(v1).as("x")

        .both().except(x).store(x).loop("x", new PipeFunction<LoopPipe.LoopBundle<Vertex>, Boolean>() {

            @Override

            public Boolean compute(LoopPipe.LoopBundle<Vertex> bundle) {

                return !x.contains(v2);

            }

        }, new PipeFunction<LoopPipe.LoopBundle<Vertex>, Boolean>() {

            @Override

            public Boolean compute(LoopPipe.LoopBundle<Vertex> bundle) {

                return bundle.getObject() == v2;

            }

        }).path();

for (final List path : pipe) {

    System.out.println(path);

}

Output will be: [v[2], v[1], v[6]]

Note that the path [v[2], v[1], v[3], v[6]] was never reached.

Cheers,

Daniel

--
You received this message because you are subscribed to the Google Groups "Aurelius" group.
To unsubscribe from this group and stop receiving emails from it, send an email to aureliusgraph...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Aparna V]

Works like a charm.

Thanks Daniel!

Aparna

[tushar]

Hi,
   I have a problem.I want to traverse nodes(say 100K) in both DFS and BFS manner upto depth 5.I wrote a code for DFS and it works fine(v is a some vertex):

        GremlinPipeline pipe = new GremlinPipeline();
         pipe.start(v).out().as("x")

        .loop("x", new PipeFunction<LoopPipe.LoopBundle<Vertex>, Boolean>() {

            @Override

            public Boolean compute(LoopPipe.LoopBundle<Vertex> bundle) {

                return bundle.getLoops() <5;

            }

        }).path();

for (Object path : pipe) {

    System.out.println(path);

}

Problem is the counter BFS part(that too upto depth 5).Can you please tell me how to proceed?

Thanks,
Tushar

[Daniel Kuppitz]

Hi Tushar,

your traversal is actually a BFS traversal (that's always the case when you use the loop step). you can turn a BFS loop traversal into a DFS traversal by building the pipeline dynamically. For example:

Init:

gremlin> g = new TinkerGraph()
==>tinkergraph[vertices:0 edges:0]
gremlin> Nov 16, 2014 11:18:48 PM java.util.prefs.FileSystemPreferences syncWorld
WARNING: Couldn't flush user prefs: java.util.prefs.BackingStoreException: Couldn't get file lock.
g.addVertex(1)
==>v[1]
gremlin> g.addVertex(2)
==>v[2]
gremlin> g.addVertex(3)
==>v[3]
gremlin> g.addVertex(4)
==>v[4]
gremlin> g.addVertex(5)
==>v[5]
gremlin> g.v(1).addEdge("link", g.v(2))
==>e[0][1-link->2]
gremlin> g.v(2).addEdge("link", g.v(3))
==>e[1][2-link->3]
gremlin> g.v(1).addEdge("link", g.v(4))
==>e[2][1-link->4]
gremlin> g.v(4).addEdge("link", g.v(5))
==>e[3][4-link->5]

BFS:

gremlin> g.v(1).as("x").sideEffect({ println it }).out().loop("x", { it.loops < 5 }, {true }).iterate()
v[1]
v[2]
v[4]
v[3]
v[5]
==>null

DFS:

gremlin> pipe = g.v(1)._(); (1..<5).each { pipe = pipe.sideEffect({ println it }).out() }; pipe.iterate()
v[1]
v[2]
v[3]
v[4]
v[5]
==>null

Cheers,
Daniel