API Reference¶

Solver¶

Enhanced Min Ratio Cycle Solver with improved features and robustness.

This module provides a comprehensive implementation of minimum cost-to-time ratio cycle detection with the following enhancements: - Better error handling and validation - Performance optimizations for sparse graphs - Structured logging and metrics - Configuration management - Multiple solving modes and options - Comprehensive debugging utilities

class min_ratio_cycle.solver.Edge(u: int, v: int, cost: float | int | Fraction, time: float | int | Fraction)[source]¶

Bases: object

Directed edge with cost and (strictly positive) transit time.

For exact solver, both cost and time should be integers or rational numbers. For numeric solver, floats are acceptable.

cost: float | int | Fraction¶

time: float | int | Fraction¶

u: int¶

v: int¶

class min_ratio_cycle.solver.LogLevel(value, names=None, *, module=None, qualname=None, type=None, start=1, boundary=None)[source]¶

Bases: Enum

Logging level enumeration.

DEBUG = 4¶

ERROR = 1¶

INFO = 3¶

NONE = 0¶

WARN = 2¶

class min_ratio_cycle.solver.MinRatioCycleSolver(n_vertices: int, config: SolverConfig | None = None)[source]¶

Bases: object

Enhanced minimum cost-to-time ratio cycle solver.

Features: - Automatic mode selection (exact vs numeric) - Sparse graph optimizations - Comprehensive error handling - Performance monitoring - Configurable behavior - Debugging utilities

add_edge(u: int, v: int, cost: float | int | Fraction, time: float | int | Fraction) → None[source]¶

Add a directed edge u -> v with given cost and time.

Parameters:

u – Vertex indices (must be in [0, n_vertices))
v – Vertex indices (must be in [0, n_vertices))
cost – Edge cost (can be negative)
time – Edge time (must be positive)

add_edges(edges: list[tuple[int, int, float | int, float | int]]) → None[source]¶: Add multiple edges at once for efficiency.

clear_edges() → None[source]¶: Remove all edges from the graph.

create_interactive_plot() → matplotlib.pyplot.Figure[source]¶: Create an interactive matplotlib plot of the current graph.

detect_issues() → list[dict[str, str]][source]¶: Detect potential issues that might cause solve failures.

get_debug_info() → str[source]¶: Get comprehensive debug information.

get_graph_properties() → dict[str, Any][source]¶: Get comprehensive graph properties.

health_check() → dict[str, Any][source]¶: Run comprehensive health check.

remove_edge(u: int, v: int) → bool[source]¶

Remove an edge between vertices u and v.

Returns:: True if edge was removed, False if not found

sensitivity_analysis(edge_perturbations: list[dict[int, tuple[float, float]]]) → list[SolverResult][source]¶

Perform edge weight perturbation analysis.

Parameters:: edge_perturbations – List of scenarios, each mapping an edge index to a (delta_cost, delta_time) tuple. For each scenario the graph is perturbed and the solver is run again.
Returns:: List of SolverResult objects, one per scenario.

solve(mode: SolverMode | str = SolverMode.AUTO, target_ratio: float | None = None, **kwargs) → SolverResult[source]¶

Find minimum cost-to-time ratio cycle.

Parameters:

mode – Solving mode (auto, exact, numeric, approximate)
target_ratio – Stop if better ratio found (early termination)
**kwargs – Additional parameters passed to specific solvers

Returns:

SolverResult with cycle, costs, and metadata

stability_region(epsilon: float = 0.01) → dict[int, bool][source]¶

Estimate stability of the optimal cycle under small perturbations.

Each edge is perturbed by epsilon fraction of its cost and time and the solver is executed again. If the optimal cycle remains unchanged the edge is considered stable.

Parameters:: epsilon – Relative perturbation size (default 1%).
Returns:: Mapping from edge index to a boolean indicating stability.

visualize_solution(show_cycle: bool = True, layout: str = 'spring') → tuple[matplotlib.pyplot.Figure, matplotlib.pyplot.Axes][source]¶

Visualize the current graph and optionally highlight the solution.

Parameters:

show_cycle – If True highlight the most recent solution cycle.
layout – Layout function name from networkx (e.g. "spring").

Returns:

Matplotlib Figure and Axes objects.

class min_ratio_cycle.solver.SolverConfig(numeric_max_iter: int = 60, numeric_tolerance: float = 1e-12, numeric_cycle_slack: float = 1e-15, exact_max_denominator: int | None = None, exact_max_steps: int | None = None, sparse_threshold: float = 0.1, enable_preprocessing: bool = True, enable_early_termination: bool = True, validate_cycles: bool = True, repair_cycles: bool = True, log_level: LogLevel = LogLevel.INFO, collect_metrics: bool = True, use_kahan_summation: bool = True, max_solve_time: float | None = None, max_memory_mb: int | None = None)[source]¶

Bases: object

Configuration for the solver.

collect_metrics: bool = True¶

enable_early_termination: bool = True¶

enable_preprocessing: bool = True¶

exact_max_denominator: int | None = None¶

exact_max_steps: int | None = None¶

log_level: LogLevel = 3¶

max_memory_mb: int | None = None¶

max_solve_time: float | None = None¶

numeric_cycle_slack: float = 1e-15¶

numeric_max_iter: int = 60¶

numeric_tolerance: float = 1e-12¶

repair_cycles: bool = True¶

sparse_threshold: float = 0.1¶

use_kahan_summation: bool = True¶

validate_cycles: bool = True¶

class min_ratio_cycle.solver.SolverMetrics(solve_time: float = 0.0, iterations: int = 0, mode_used: str = '', preprocessing_time: float = 0.0, graph_properties: dict[str, ~typing.Any] = <factory>, memory_peak: int | None = None)[source]¶

Bases: object

Metrics collected during solving.

graph_properties: dict[str, Any]¶

iterations: int = 0¶

memory_peak: int | None = None¶

mode_used: str = ''¶

preprocessing_time: float = 0.0¶

solve_time: float = 0.0¶

class min_ratio_cycle.solver.SolverMode(value, names=None, *, module=None, qualname=None, type=None, start=1, boundary=None)[source]¶

Bases: Enum

Solver mode enumeration.

APPROXIMATE = 'approximate'¶

AUTO = 'auto'¶

EXACT = 'exact'¶

NUMERIC = 'numeric'¶

class min_ratio_cycle.solver.SolverResult(cycle: list[int], sum_cost: float | Fraction, sum_time: float | Fraction, ratio: float | Fraction, success: bool = True, error_message: str = '', metrics: SolverMetrics | None = None, config_used: SolverConfig | None = None)[source]¶

Bases: object

Result from solver with additional metadata.

config_used: SolverConfig | None = None¶

cycle: list[int]¶

error_message: str = ''¶

metrics: SolverMetrics | None = None¶

ratio: float | Fraction¶

success: bool = True¶

sum_cost: float | Fraction¶

sum_time: float | Fraction¶

Convenience function to solve min ratio cycle problem.

Parameters:

edges – List of (u, v, cost, time) tuples
n_vertices – Number of vertices (auto-detected if None)
mode – Solver mode
config – Solver configuration

Returns:

SolverResult with solution

Analytics¶

Statistical analysis utilities for solver results.

min_ratio_cycle.analytics.compare_solutions(values1: Iterable[float], values2: Iterable[float]) → float[source]¶

Return Welch’s t statistic comparing two samples.

Parameters:

values1 (Iterable[float]) – First sequence of observations.
values2 (Iterable[float]) – Second sequence of observations.

Returns:

Welch’s t statistic. math.inf is returned when the denominator is zero.

Return type:

float

Raises:

ValueError – If either sample contains fewer than two values.