Trivial Minimum Cycle Ratio Failing

[Andful]

Before filing

• I searched the existing issues and did not find a duplicate.
• I have reproduced the bug against the develop branch or the latest Boost release.
• I have a minimal reproducer (or I will paste my full failing code below).

Boost version

1.93 (hash: bf5e43e0850af9381fc880248ebab801e17c41d8)

Compiler family

• GCC / g++
• Clang / clang++
• MSVC (Visual Studio)
• Intel / oneAPI
• Other (specify below)

g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0

Standard library

• libstdc++
• libc++ (I am not certain)
• MSVC STL
• Other (specify below)

Operating system

• Linux
• macOS
• Windows
• Other (specify below)

Kind of component affected

• Graph data structure (e.g. adjacency_list, adjacency_matrix)
• Algorithm (e.g. dijkstra_shortest_paths, breadth_first_search)
• Property map
• I/O or file-format reader (e.g. read_graphml, read_graphviz)
• Visitor / event hooks
• Other (specify below)

Affected component: howard_cycle_ratio

Steps to reproduce

Commit a56dccbd411acd84f04c64d796b871b4e4bd9598 in Andful/graph adds the failing example.

The example being:

digraph G {
  a->a  [w1=6410, w2=2];
}

I.e. a single self-loop with cost 6410 and time of 2.

The case originates from a MCR benchmark.

Expected behavior

The minimum cycle ratio should be 6410/2 (i.e. 3205)

Actual behavior

The reported minimum cycle ratio is +Inf

Are you willing to help?

• I'd like to submit a fix as a pull request.
• I can help diagnose or test a candidate fix.
• I'm only reporting the issue.

[Andful]

The error seems to be due to this condition evaluating to true.

The computed upper bound is m_bound=3205, and the obtained MCR is mcr=3205. The comparison mcr > m_bound - 1e-08 is true because mcr == m_bound.

There seems to be an incorrect assumption that the MCR is strictly lower than its computed upper bound, and the bug expresses itself when the computed upper bound is equal to the MCR.

I would change the condition to mcr > m_bound. Though I lack the expertize to implement it in a heavily templated "boosty" way, i.e., with the m_cmp function.

[Andful]

Actually, I guess the change would only be to change m_cmp(mcr, m_bound + eps_) to !m_cmp(m_bound, mcr). I can make the pull request with the proposed change and the additional test case if it would be appreciated.