utils_shortest.py

"""Fast shortest-cycle wrapper using girth HybridMWC."""
import os, sys
_root = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
if _root not in sys.path:
    sys.path.append(_root)
_girth = os.path.join(_root, 'girth')
if _girth not in sys.path and os.path.isdir(_girth):
    sys.path.append(_girth)

from hybrid_mwc import hybrid_mwc_length
import networkx as nx

from typing import Tuple, Set

def shortest_cycle(G: nx.Graph, bound: float | None = None, seeds: set[int] | None = None) -> Tuple[Set[tuple], float]:
    """Return length of shortest cycle in G (undirected, weighted).

    If *bound* is given (≈ current gamma/2 inside loop modulus), it is passed
    to BMSSP so the search terminates early.  Currently the girth wrapper
    does not expose a bound parameter; included for future use.
    """
    return hybrid_mwc_length(G, use_euler_lca=True, bound=bound, source_seeds=seeds, return_edges=True)