graph_coloring_balance can loop forever on an equal-ratio coloring cycle

Bug Description

wp.utils.graph_coloring_balance() can loop forever while alternating between two valid color assignments whose maximum-to-minimum group-size ratio is unchanged.

This is related to #816, but the fix in 42e374713557e3a1a85f23286ff1b02334eb15ea only exits when the ratio becomes strictly worse:

if (prev_max_min_ratio > 0 && prev_max_min_ratio < max_min_ratio) {
    return max_min_ratio;
}

An equal-ratio cycle bypasses that condition.

Minimal reproducer

import warp as wp

wp.init()

edges = wp.array(
    [
        [0, 5], [1, 5], [2, 5], [4, 5],
        [0, 6], [1, 6], [2, 6], [4, 6],
        [5, 6],
    ],
    dtype=wp.int32,
    device="cpu",
)
colors = wp.array([0, 0, 0, 1, 0, 2, 1], dtype=wp.int32, device="cpu")

print("before:", colors.numpy().tolist(), flush=True)
wp.utils.graph_coloring_balance(
    edges,
    colors,
    color_count=3,
    target_max_min_ratio=1.1,
)
print("after:", colors.numpy().tolist(), flush=True)

Run with a timeout:

$ timeout --signal=KILL 5s python -u repro.py
before: [0, 0, 0, 1, 0, 2, 1]
Killed
$ echo $?
137

The coloring is valid. Internally, the group sizes alternate indefinitely:

1. [4, 2, 1]: no color-0 node can move to color 2, so node 3 moves from color 1 to color 2.
2. [4, 1, 2]: no color-0 node can move to color 1, so node 3 moves from color 2 back to color 1.
3. The maximum/minimum ratio remains 4.0, so the strict ratio-regression guard does not terminate.

Expected behavior

The balancing operation should always terminate, returning the best valid coloring it found when the target ratio is unreachable. Cycle detection, a bounded iteration count, or another monotonic progress condition would prevent this class of hang without assuming every equal-ratio step is unproductive.

Downstream impact

This intermittently hangs Isaac Lab's Newton VBD builder during simulation reset until its 1000-second test timeout kills the worker. The same stack occurred in three recent blocking CI jobs:

• IsaacLab run 33963394703, job 101299175644
• IsaacLab run 34153472219, job 101840450098
• IsaacLab run 34155394372, job 101846147021

Isaac Lab has a temporary downstream workaround in isaac-sim/IsaacLab#7826, which disables the optional balancing pass for Newton VBD until this is fixed upstream.

System Information

• Warp: 1.17.0
• Python: 3.12
• Reproduced on Linux x86_64; the minimal reproducer runs on the CPU
• Downstream CI: Linux x86_64 with NVIDIA L40S