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 $10\times$ to $400\times$ over NetworkX, establishing \texttt{Aegypti} as the fastest pure-Python approach currently available.