# cycles

## #

AbstractIn graph theory, a cycle represents a path within the graph where only starting and ending nodes are similar. Furthermore, cycles can be double-connected links between neighboring nodes or self-loops. The cycles detection algorithm implemented within MAGE works on an undirected graph and has **no guarantee** of node order in the output. The implemented algorithm (Gibb) is described in the 1982 MIT report called "Algorithmic approaches to circuit enumeration problems and applications" ^{1}. The problem is not solvable in polynomial time. It is based on finding all subsets of fundamental cycles which takes about O(2^(|E|-|V|+1)) time where E represents a set of edges and V represents a set of vertices of the given graph.

^{1} Algorithmic approaches to circuit enumeration problems and applications, Boon Chai Lee

Trait | Value |
---|---|

Module type | algorithm |

Implementation | C++ |

Graph direction | undirected |

Edge weights | unweighted |

Parallelism | sequential |

## #

Procedures`get()`

#

#### #

Output:`cycle_id`

âž¡ Incremental cycle ID of a certain vertex. There is no guarantee on how nodes are going to be ordered within cycle. The cycle can be represented with a minimum of one ID, where it stands for self-loop.`node`

âž¡ Vertex object with all properties which is going to be related to the cycle ID it belongs to.

#### #

Usage:`CALL cycles.get()YIELD cycle_id, node;`

## #

Example- Step 1: Input graph
- Step 2: Cypher load commands
- Step 3: Running command
- Step 4: Results

`MERGE (a:Node {id: 0}) MERGE (b:Node {id: 1}) CREATE (a)-[:RELATION]->(b);MERGE (a:Node {id: 0}) MERGE (b:Node {id: 2}) CREATE (a)-[:RELATION]->(b);MERGE (a:Node {id: 1}) MERGE (b:Node {id: 2}) CREATE (a)-[:RELATION]->(b);MERGE (a:Node {id: 2}) MERGE (b:Node {id: 3}) CREATE (a)-[:RELATION]->(b);MERGE (a:Node {id: 2}) MERGE (b:Node {id: 4}) CREATE (a)-[:RELATION]->(b);MERGE (a:Node {id: 3}) MERGE (b:Node {id: 4}) CREATE (a)-[:RELATION]->(b);`

`CALL cycles.get()YIELD cycle_id, node;`

`+-----------------+-----------------+| cycle_id | node |+-----------------+-----------------+| 0 | (:Node {id: 2}) || 0 | (:Node {id: 0}) || 0 | (:Node {id: 1}) || 1 | (:Node {id: 4}) || 1 | (:Node {id: 2}) || 1 | (:Node {id: 3}) |+-----------------+-----------------+`