compute all cycles in a graph

[haris qureshi]

Good Day,

I am working on directed, non-relational graph; or we can say all
vertices have same relation with each other. in our domain we call it
an "event Graph" or marked "Petri net"

I want to compute all possible cycles/circuits in a graph. Meaning
that, starting from one vertex back to that vertex through a directed
path without repeating any vertex. Where length of cycles is
arbitrary; some cycles contains say 3 vertices others may contain 5
and so on.

I used the command in Gremlin console

g.V.out.loop(1){it.loops< 7}.paths

it gives all the possible paths, but

Now, the problem is: it traverse up to 7 vertices and keep on
repeating the vertices. For instances...

[v[1], v[2], v[1], v[2], v[1], v[2], v[1]] , on the other hand I want
only [v[1], v[2]]

Similarly, it gives object like;

[v[1], v[6], v[3], v[5], v[1], v[6], v[3]], now again v[6] and v[3]
are repeated.

also it compute non-cycles such as

[v[1], v[6], v[3], v[4], v[3], v[4], v[7]], it is not a cycle since
v[3] is duplicated before returning to v[1].

Regards

Haris

[Marko Rodriguez]

Hey,

Off the top of my head, you can probably do something with either:

1. simplePath (filters out paths that repeat)
2. it.path in your loop{} construct so you can examine the path and emit it if meets your needs or filter it if it doesn't. (read about emit-closures).

HTH,
Marko.

http://markorodriguez.com

[haris qureshi]

Thank you very much Marko,

1. simplePath is good, but if applied after the loop as;
g.V.out.loop(1){it.loops< 7}.simplePath.paths

it gives "null" because somehow all outputs have a repetition like

[v[1], v[2], v[1], v[2], v[1], v[2], v[1]]

and if applied before loop, while explicitly mentioning

g.V.out.out.out.simplePath.paths

then; since length of cycles is arbitrary, therefore it will neglect
two vertex cycle and will give only 3 vertex cycle.

I am a manufacturing guy and kinda layman towards programming, kindly
mention if any, what is the way to use simplePath inside a loop.

2. to use it.path inside a loop, please tell me, what criteria I
should use, say; v(1)!= v(1) or v(x)!=v(x) or how?

Actually, I need to stop a loop as soon as there is any repetition,
instead of examining it once it has pass through all 7 vertices.

Can I use like this

g.V.out.loop(1){it.path.simplePath}.paths

or in similar way

Regards

Haris

[Marko Rodriguez]

Hey,

it.path inside a loop{} will return the path thus far as a List. You will probably want to write a method that takes that List and does what you want with it (boolean check or something). If it meets your criteria, emit it. Using the emit-closure of the loop{}.

You can play and figure it out... Do something like:

g.V.out.loop(1){it.loops < 7}{println it.path; true}.paths

Good luck,
Marko.

http://markorodriguez.com