A Graph traversal algorithm alternative to BFS

[Mohsen Raeesi]

Hi everyone,

I wanna to find the all n-distant path between two set of nodes (Source and Destination). As I check by profile() and explain() steps, Tinkerpop always uses BFS but it is not efficient. The efficient approach in my task is start from S and D together and try to find common nodes with distance of n/2.

for example I want to find all meta path "Author-->Paper-->Paper<--Paper<--Author" between two set of Authors ( A1:{x,y} and A2:{p,q} ), that is common references in A1's and A2's papers. assume that all nodes has 10 neighbors. BFS should visit more than 2 * 10,000 nodes to find the result, but the efficient traversal is:

1. find all papers of x,y,p and q: 40 nodes.
2. intersect between the references of these A1's paper and A2's paper: intersect between two set with less than 200 element.

the second approach reduce the traversals significantly, due to starting from limited part of query.

My questions:

1. Is this approach is implemented in Tinkerpop yet?
2. If no, how can I implement it?

Regards,

Mohsen

[Mohsen Raeesi]

Gremlin has no capability for bi-directional traversal?

[Jean-Baptiste Musso]

For DFS, would the following help?

g.withoutStrategies(LazyBarrierStrategy, PathRetractionStrategy)

  .V() ... // proceed with DFS traversal

  

See, somewhere down in that section: http://tinkerpop.apache.org/docs/current/recipes/#duplicate-edge

Quoting: "Remove strategies that will optimize for breadth first searches and thus allow Gremlin to go depth first."

Jean-Baptiste

--
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/e49d8036-46ea-458d-b6f2-fa73167ac82b%40googlegroups.com.

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

[Mohsen Raeesi]

but I don't need DFS, I need "Bi-directional BFS".

It means we start BFS from source and destination at the same time, reducing nodes which should be traversed.

​Regards,​

--
You received this message because you are subscribed to a topic in the Google Groups "Gremlin-users" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/gremlin-users/cJ1aO_aTx3Q/unsubscribe.
To unsubscribe from this group and all its topics, 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/CAC3-3jgTUSj2e7F7wnCiuUzM4_ka0kypNorxnK2ZOxwTQbOMFQ%40mail.gmail.com.

[Robert Dale]

g.V(A1).out().out().fold().as('x').V(A2).out().out().where(within('x'))

Robert Dale

To view this discussion on the web visit https://groups.google.com/d/msgid/gremlin-users/CAMy_dw3tTSOUcL39PFT90byYQhjxsugYvSuqBOF190N2XOpNkQ%40mail.gmail.com.

[Mohsen Raeesi]

Thanks Robert,

Is it possible to do bi-directional BFS transparent by extending a Strategy or something like that?

To view this discussion on the web visit https://groups.google.com/d/msgid/gremlin-users/CABed_4rHCa1L_GxPiZvr2agj%3Dqq901PKc87pzAn114KrNbEHeQ%40mail.gmail.com.