2

I have a big TinkerGraph (~80.000 vertices, ~160.000 edges) and I need to detect if there is a cycle in it using the Apache TinkerPop/Gremlin query language. If any, I would like to obtain the vertices of one of the cycles.

Is there a way to write a O(|V| + |E|) gremlin query to find a cyclic path in a graph?

I tried using the queries from here and here, but they are too slow and they time out. I suspect that they are not O(|V| + |E|), but I am still learning TinkerPop and I can not evaluate the memory/time complexity of the TinkerGraph implementation.

Community
  • 1
  • 1
Federico
  • 1,925
  • 14
  • 19
  • I believe [this](http://stackoverflow.com/questions/40672466/query-to-check-if-there-is-a-cycle-in-a-graph-with-edges-visited-only-once) is a similar question. Maybe that can inspire a solution specific to your problem? – Filipe Teixeira Mar 14 '17 at 10:43
  • I am working on it, thanks. That answer uses several gremlin features that are new to me (e.g. `select(all, ...)`) – Federico Mar 14 '17 at 11:03
  • 4
    That particular answer is also described in more detail [here](http://tinkerpop.apache.org/docs/current/recipes/#cycle-detection) – stephen mallette Mar 14 '17 at 11:10
  • Oh, thanks! I was looking at the old version `3.2.1` – Federico Mar 14 '17 at 11:28

0 Answers0