https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91601
Fangrui Song <i at maskray dot me> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |i at maskray dot me
--- Comment #17 from Fangrui Song <i at maskray dot me> ---
The algorithm is Donald B. Johnson's "Finding all the elementary circuits of a
directed graph" (1975). (Hawick and James's just implemented the same algorithm
by changing the representation of graphs).
I am wondering why we enumerate every elementary cycle, find the minimum edge,
reduce edge weighs, and repeat the process.
What do we lose if we don't use the costly algorithm? (The time complexity is
O(n*e*(c+1)). However, many implementations (Boost and gcov.c) do not use a
hash set for the blocked list, and thus I suspect the actual complexity is
higher). Do we have other low-cost approaches? (e.g. repeatedly finding
strongly connected components and reducing)
