The goal of this prototype is to implement a simple algorithm for detecting simple cycles within a graph.

Let G = (V,E) be a directed graph (G) consists of a finite set of vertices (V) and a finite set of edges (E). Each edge describes a relationship v₁ → v₂ where v₁ and v₂ are distinct members of V.

Within G a cycle of length l is a sequence of vertices [v₀,v₁,…,v_l] where v_i]-1 → _i] for i = 1, 2, …., l-1 and v_l → v₁.

The cycle is simple when each vertex in [v₀,v₁,…,v_l] are distinct, so that v_i ≠ v_j for i ≠ j.

The Neo4J library provides two methods for detecting cycles: cyphter queries and the APOC library.

Cypther is a declarative query language supported by neo4j. ¹⁾.

The following code was provided on Stack Overflow ²⁾ as an example where l=15:

MATCH p=(n)-[*1..15]->(n) RETURN nodes(p)

However, as noted in the stack overflow discussion, this simple example has many limitations:

1. The query is expensive for larger graphs, with the cost growing exponentially as the graph size and l are increased.
2. It will return cycles consisting of a single vertex. To avoid this a minimum depth of 2 is required.
3. It detects cycles that include duplicate vertices. A more complex query is necessary to eliminate duplicates for the detection of simple graphs.

For detecting cycles in a more convenient and better performing way the APOC library provides the apoc.nodes.cycles procedure for detecting all path cycles from a node list. ³⁾

The signature for the procedure is as follows:

apoc.nodes.cycles(nodes :: LIST? OF NODE?, config = {} :: MAP?) :: (path :: PATH?)

The documentation provides the following example:

CREATE (m1:Start {bar: 'alpha'}) with m1 CREATE (m1)-[:DEPENDS_ON {id: 0}]->(m2:Module {bar: 'one'})-[:DEPENDS_ON {id: 1}]->(m3:Module {bar: 'two'})-[:DEPENDS_ON {id: 2}]->(m1)  WITH m1, m2, m3 CREATE (m1)-[:DEPENDS_ON {id: 3}]->(m2), (m2)-[:ANOTHER {id: 4}]->(m3), (m2)-[:DEPENDS_ON {id: 5}]->(m3) CREATE (m1)-[:DEPENDS_ON {id: 6}]->(:Module {bar: 'seven'})-[:DEPENDS_ON {id: 7}]->(:Module {bar: 'eight'})-[:DEPENDS_ON {id: 8}]->(m1);
CREATE (m1:Start {bar: 'beta'}) with m1 CREATE (m1)-[:MY_REL {id: 9}]->(m2:Module {bar: 'three'})-[:MY_REL  {id: 10}]->(m3:Module {bar: 'four'})-[:MY_REL {id: 11}]->(m1);
CREATE (m1:Start {bar: 'gamma'}) with m1 CREATE (m1)-[:DEPENDS_ON {id: 12}]->(m2:Module {bar: 'five'})-[:DEPENDS_ON {id: 13}]->(m3:Module {bar: 'six'});
CREATE (m1:Start {bar: 'delta'}) with m1 CREATE (m1)-[:DEPENDS_ON {id: 20}]->(m1);
CREATE (m1:Start {bar: 'epsilon'}) with m1 CREATE (m1)-[:DEPTH_ONE {id: 30}]->(:Module {bar: 'seven'})-[:DEPTH_ONE {id: 31}]->(m1);

MATCH (m1:Start) WITH collect(m1) as nodes CALL apoc.nodes.cycles(nodes) YIELD path RETURN path

The Apache Tinkerpop documentation provides a recipe for Cycle Detection ⁴⁾.

The following code detects cycles of arbitrary length.

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())

This code takes advantage of the Gremlin simplePath step to ensure that no vertex is repeated within the cycle ⁵⁾.

One limitation for this approach is that it will detect duplicate cycles that contain the same edges but with a different starting position. For example: A→B→C→A, B→C→A→B & C→A→B→C. The documentation provides several methods for detecting these duplicates with different trade-offs concerning complexity, speed and memory.

* Golumbic, M. C. (2004). Algorithmic Graph Theory and Perfect Graphs (2nd ed., Chapter 1 - Graph Theoretic Foundations). North Holland Publishing Company, a Subsidiary of Eslevier.