Module loop_detection 

Loop Detection via Y-Coordinate Clustering

This module implements loop detection for Control Flow Graphs using 3D spatial coordinates, specifically the Y-coordinate (loop_nesting level).

Algorithm

Blocks with Y > 0 are inside at least one loop. Blocks with the same Y coordinate at non-zero levels belong to the same loop nesting depth.

Complexity

• Time: O(n) single pass through blocks
• Space: O(l) where l is number of unique loop levels

Example

use geographdb_core::algorithms::loop_detection::{detect_loops, LoopBlock};

let blocks = vec![
    LoopBlock { id: 0, x: 0.0, y: 0.0, z: 0.0 },  // Entry (not in loop)
    LoopBlock { id: 1, x: 1.0, y: 0.0, z: 1.0 },  // Branch (not in loop)
    LoopBlock { id: 2, x: 2.0, y: 1.0, z: 0.0 },  // Inside loop (depth 1)
    LoopBlock { id: 3, x: 3.0, y: 1.0, z: 0.0 },  // Inside loop (depth 1)
    LoopBlock { id: 4, x: 4.0, y: 2.0, z: 0.0 },  // Inside nested loop (depth 2)
];

let loops = detect_loops(&blocks);
assert_eq!(loops.len(), 2);  // Two loop levels detected

Structs

LoopAnalysisResult

Result of loop detection analysis

LoopBlock

A block in the CFG for loop detection

LoopInfo

Information about a detected loop

Functions

analyze_loops

Analyze loop structure of a CFG

calculate_loop_complexity

Calculate loop complexity score

detect_loops

Detect loops in a CFG using Y-coordinate clustering

find_innermost_loop_for_block

Find the innermost loop containing a specific block

get_blocks_at_level

Find all blocks at a specific loop nesting level

get_loop_depth

Get the loop nesting depth for a block

is_in_loop

Check if a block is inside any loop