Floyd's Cycle Algorithm for Fraud Detection in Java Systems

The Floyd Cycle Detection Algorithm (Tortoise and Hare algorithm) is an efficient cycle detection within iterative structures. In addition to linked lists, it is applicable to practical problems such as fraud detection and user workflows where data is duplicated or there are cyclic dependencies in workflows or financial transactions. 

This article illustrates its practical implementation with a fraudulent detection system for banking transactions.

Use Case: Detecting Fraud in Money Transfers

A bank regularly monitors the money transfers among customer accounts. Fraud may involve cycles of money flowing through a number of accounts and returning back to the source (usually to avoid detection or mask the origin of money). By identifying these cycles, banks can be warned of possible laundering actions.

Sample data for this example:

Understanding the Data that was Sampled

1. Transfer from account “abc” to account “bcd.”
2. From account “bcd” to account “cde.”
3. Lastly, “cde” sends to “def.”
4. Moving from account “def” back to account “bcd” creates a loop: bcd → cde → def → bcd.

How to Use Algorithm for Detection

In implementing cycle detection using Floyd's Algorithm, transactions are modeled as a directed graph where:

1. Nodes represent accounts
2. Edges represent money transfers between individual nodes

There are two pointers (slow and fast pointers) used to check for cycles/loops.

Java object mapping account transfer mapping:

class AccountTransferGraph {
    private final Map<String, List<String>> adjacencyMap=new HashMap<>();
    //add a transfer from one account to another
    public void addAccountTransfer(String source,String destination){
        adjacencyMap.computeIfAbsent(source, k -> new ArrayList<>()).add(destination);
    }
    //retrieve all transfers from a given account
    public List<String> getTransfers(String account){
        return adjacencyMap.getOrDefault(account,new ArrayList<>());
    }
    //retrieve all accounts
    public Set<String> getAllAccounts(){
        return adjacencyMap.keySet();
    }
}

Helper class to find cycles from graph created using above Java object:

class FloydCycleDetector{
   public static boolean isCyclePresent(AccountTransferGraph graph,String start){
       String slow=start,fast=start;
       while(true){
           // Move slow pointer one step
           slow = next(graph, slow);

           // Move fast pointer two steps
           fast = next(graph, next(graph, fast));

           // If pointers meet, a cycle is detected
           if (slow != null && slow.equals(fast)) {
               return true;
           }

           // If fast pointer reaches null, no cycle exists
           if (fast == null || slow == null) {
               return false;
           }

       }
   }
    // get next account
    private static String next(AccountTransferGraph graph, String account) {
        List<String> transfers = graph.getTransfers(account);
        return transfers.isEmpty() ? null : transfers.get(0);
    }

}

Test class to validate the above logic:

// Main class to test the algorithm
public class FraudDetectionSystem {
    public static void main(String[] args) {
        //STEP 1: Build the account transfer graph object
        AccountTransferGraph graph = new AccountTransferGraph();

        //STEP 2: add test account transfer data
        graph.addAccountTransfer("a", "b");
        graph.addAccountTransfer("b", "c");
        graph.addAccountTransfer("c", "d");
        graph.addAccountTransfer("d", "b");

        //STEP 3: check for cycles starting from each account
        for (String account : graph.getAllAccounts()) {
            if (FloydCycleDetector.isCyclePresent(graph, account)) {
                System.out.println("Cycle detected starting from account: " + account);
                return;
            }
        }
        System.out.println("No cycles detected.");
    }
}

Code Explanation

The AccountTransferGraph Class represents the relationships between accounts as a directed graph. Here are some of its methods:

• addAcountTransfer(String source, String destination) – Adds a transfer (directed edge) between two accounts
• getTransfers(String account) – Retrieves a list of accounts to which a specific account has transferred money
•  getAllAccounts() – Returns all accounts (nodes) in the graph

Floyd’s Cycle Detection Algorithm

The FloydCycleDetector class uses two pointers:

• Slow pointer (tortoise) – Goes one position at a time.
• Fast pointer (hare) – Goes two positions at a time.

Behavior of the algorithm:

1. If a cycle is present in the graph:
   • The slow pointer, which moves at a steady pace, eventually meets the fast pointer at some point.
2. If there is no cycle/loop present:
   • One of the pointers from the program traverses to the end (null).

Key Method

The isCyclePresent(AccountTransferGraph graph, String start) method is designed to:

• Detect if there’s a cycle starting from the given account
• Use the helper method next() to retrieve the next account in the chain

Test class to validate the above algorithm in Fraud Detection.

The FraudDetectionSystem class integrates the accountTransferGraph, and cycle detection logic:

1. Constructs the graph with transfers
2. Checks each account in the graph for cycles using Floyd’s Algorithm
3. Results if a cycle is detected

Limitations and Possible Improvements

• Detection of single cycles. Floyd's algorithm identifies one cycle. Depth First Search(DFS) should be used in all cases to identify all of them.
• Complex graphs. The algorithm assumes one edge per node. For graphs with multiple edges, some adaptation may be necessary.

Versatile Usage of Floyd’s Cycle Detection Algorithm

This is very popular in providing cycle detection in linked lists and graphs for efficient memory management and avoiding an infinite loop in algorithms. In networking, it identifies the routing loops and optimizes a distributed system model that avoids deadlocks. In bioinformatics, it helps analyze DNA sequences and protein structure simulations by identifying repeat patterns within complex biological data. 

It is also used in AI and ML to prevent training loops from occurring forever in reinforcement learning or to identify cyclic dependencies in graph-based models. Whether in blockchain, operating systems, or cryptography, Floyd's algorithm continues to be a boon to deliver stability and efficiency across diverse realms of computation.

Conclusion

Floyd’s Cycle Detection Algorithm is a simple and effective solution to real-world issues that involve cyclic structure. In the above example, its application to banking fraud detection implies that it can be useful in other use cases. The algorithm can be integrated into systems at various levels to improve operational integrity and efficiency due to its simplicity and efficiency.

The above example code is present in the GitHub repository.

More details regarding the above algorithm can be found at GeeksforGeeks. The Sanfoundry shows the integration of the Floyd cycle detection algorithm in Java applications.