https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91601
--- Comment #18 from Martin Liška <marxin at gcc dot gnu.org> --- (In reply to Fangrui Song from comment #17) > 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. I basically taken the original patch submission and finished it. > > 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) Do you have a test-case where it is significant? Feel free to provide a patch which can make it faster, I'll appreciate and review it.
