finding the longest path in a very dense graph

[tala...@gmail.com]

Supposing i have a graph of geo-points that are very densely connected, I am attempting to find loops around a city block. The problem is that queries such as using `simplePath()` still end up having so many possibilities it becomes a near-intractable problem. Short of remodelling the graph and how vertices are connected, is there a nice gremlin traversal that can find me the longest cyclic path around a given city block (input as a lon/lat, say)

g.V().has('gps', Geo.point(x,y)).as('p').repeat(both().simplePath()).until(is('p')).path()

g.V().has('gps', Geo.point(x,y)).as('x').repeat(both()).until(cyclicPath()).path().by('gps')

There is a search index (DSE search/Solr) on the GPS coordinates but these types of traversals still timeout

Script evaluation exceeded the configured threshold of realtime_evaluation_timeout at 180000 ms for the request

[Daniel Kuppitz]

The longest path, based on the number of hops, will be the last one you can find.

g.V().has('gps', Geo.point(x, y)).as('x').

  repeat(both().simplePath()).

    emit(where(both().as('x'))).

  both().where(eq('x')).tail(1).

  path()

There's no way to make this query perform well in OLTP, unless you have a very tiny (sub)graph. So, depending on what you see as a "city block" in your graph, you should probably extract that first as a subgraph and then apply the longest path query (in memory).

Cheers,

Daniel

--
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/7107483e-b3cd-49bb-a030-7234c45ac891%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.