Fast Triangle Detection and Enumeration in Undirected Graphs: The Aegypti Algorithm

The triangle finding problem is a cornerstone of complex network analysis, serving as the primitive for computing clustering coefficients and transitivity. This paper presents texttt{Aegypti}, a practical algorithm for triangle detection and enumeration in undirected graphs. By combining a descending degree-ordered vertex-iterator with a hybrid strategy that adapts to graph density, texttt{Aegypti} ensures a worst-case runtime of $mathcal{O}(m^{3/2})$ for full enumeration, matching the theoretical limit for listing algorithms. Furthermore, we analyze the detection variant ($texttt{first_triangle}=text{True}$), proving that sorting by non-increasing degree enables immediate termination in dense instances and sub-millisecond detection in scale-free networks. Extensive experiments confirm speedups of $10times$ to $400times$ over NetworkX, establishing texttt{Aegypti} as the fastest pure-Python approach currently available.