Cycle Detection

Description

In 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 simplest concept of a solution for finding a cycle was defined by Robert W. Floyd in his tortoise and hare algorithm, where a hare moves at twice the speed of a tortoise and thus encounters it if there is a cycle. There are many implementations of cycle detection, and among them, the fastest is Professor Donald B. Johnson from the Pennsylvania State University - Finding all the elementary circuits of a directed graph.

There are two cycles in the graph from the examples, each colored differently.

Cycles are not only popular in graph structures but also play an important role in number theory and cryptography. Nevertheless, graph theory concepts are used in other disciplines, and cycle detection is placed as an extremely important tool in initial graph analysis.

Materials

Implementation

Cycle detection is implemented as part of the MAGE project. Be sure to check it out in the link above. ☝️

Use cases

A really interesting use case deployed in one of the vendors is used to actively monitor various online fraudulent activities based on cycle detection. To increase the popularity of their brand and to improve future sales, the seller might create fake transactions to artificially bump up the number of past transactions. Of course, this is unwanted behavior, so every vendor will try to prevent it.