How to detect all possible cycles in a directed graph?

[Denis Papathanasiou]

I have a directed graph in which all vertices are connected, ultimately,
to a single root vertex.

I want to examine all the paths from the root to each of the leaves,
and count the number of paths with cycles.

I came up with this, after reading the gremlin docs:

g.V.out.simplePath.filter{ it.path == null }.count()

and also tried this variation:

g.V.out.cyclicPath.filter{ it != null }.count()

In both cases, I though if the response was zero, then I didn't have
any cycles.

But then, I deliberately added a cycle, and retried both.

Both gave me 0 again, which is clearly wrong.

Then I realized g.V.out produces just all the individual edges between
vertices, and I wasn't getting the full set of paths that I need.

After reading this thread[1] and looking at this recipe[2], I realized
I need something with a loop(), to capture all the possible paths.

Ideally, since I do have a root vertex to start from, it would be a
variation of this:

g.v(A).out.loop(1){it.loops<=N && !(it.object.id in [A,B])}.filter{it.id==B}.path

where A is the id of the root vertex, but for all possible B, with an
indeterminate depth of N.

Is there a single expression for something like that?

[1] https://groups.google.com/d/topic/gremlin-users/UeFPpdz73h4/discussion
[2] http://www.tinkerpop.com/docs/wikidocs/gremlin/2.1.0/Finding-All-Paths-Between-2-Vertices.html

[HadoopMarc]

Hi Denis,

I did not test it, but wondered if the following would work, as it was not part of your attempts:

g.V(A).repeat(out()).times(N).cyclicPath().count()

Regards,   Marc


[Daniel Kuppitz]

To find all cyclic paths of arbitrary length in a graph, you can do:

g.V().as("a").repeat(both().simplePath()).emit(loops().is(gt(1))).both().where(eq("a")).path()

This will produce a lot of duplicates though, as it will return the same cycle several times with different starting point. To filter those duplicates you can do:

g.V().as("a").repeat(both().simplePath()).emit(loops().is(gt(1))).both().where(eq("a")).path().

  dedup().by(unfold().order().by(id).dedup().fold())

Here it is in action over the modern graph: http://www.gremlinbin.com/bin/view/57210d98e0dca

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-user...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/gremlin-users/e52b7f19-58ac-47e8-9813-ff3185a148d3%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Denis Papathanasiou]

Marc and Daniel,

Thank you for those suggestions.

It seems that the version of gremlin packaged with titan 0.5.4 does not
support many of those commands, especially repeat().

While I was able to upgrade to titan 1.0.0, that version of gremlin
no longer allows the loadGML() method, so I need to time to rework my
source data into a form that I can access.

I should be able to have that converted and functional
soon, but in the meantime, I was wondering whether or not
cyclicPath()/simplePath()/etc. distinguish between a loop in a graph
(i.e., wherein a vertex has an edge pointing back to itself) versus a
true cycle?