# Source code for digraphx.min_cycle_ratio

```
from fractions import Fraction
from typing import Generic, Mapping, MutableMapping, Tuple, TypeVar
from .neg_cycle import Cycle, Domain, Edge, Node
from .parametric import MaxParametricSolver, ParametricAPI
Ratio = TypeVar("Ratio", Fraction, float)
Graph = Mapping[Node, Mapping[Node, Mapping[str, Domain]]]
GraphMut = MutableMapping[Node, MutableMapping[Node, MutableMapping[str, Domain]]]
[docs]
def set_default(digraph: GraphMut, weight: str, value: Domain) -> None:
"""
This function sets a default value for a specified weight in a graph.
:param digraph: The parameter `digraph` is of type `GraphMut`, which is likely a mutable graph data
structure. It represents a graph where each node has a dictionary of neighbors and their
corresponding edge attributes
:type digraph: GraphMut
:param weight: The `weight` parameter is a string that represents the weight attribute of the edges in the graph
:type weight: str
:param value: The `value` parameter is the default value that will be set for the specified weight attribute in the graph
:type value: Domain
"""
for _, neighbors in digraph.items():
for _, e in neighbors.items():
if e.get(weight, None) is None:
e[weight] = value
# The `CycleRatioAPI` class is a parametric API that calculates the ratio of a cycle based on the cost
# and time of its edges.
[docs]
class CycleRatioAPI(ParametricAPI[Node, MutableMapping[str, Domain], Ratio]):
def __init__(
self,
digraph: Mapping[Node, Mapping[Node, Mapping[str, Domain]]],
result_type: type,
) -> None:
"""
This function initializes an object with two parameters, `digraph` and `result_type`, and assigns them to instance
variables.
:param digraph: A mapping of nodes to a mapping of nodes to a mapping of strings to domains. It
represents a graph structure where each node is connected to other nodes through edges, and each
edge has associated attributes represented by strings and domains
:type digraph: Mapping[Node, Mapping[Node, Mapping[str, Domain]]]
:param result_type: The parameter `result_type` is a type. It is used to specify the type of the variable `result_type`. The type
can be any valid Python type, such as `int`, `str`, `list`, etc
:type result_type: type
"""
self.digraph: Mapping[Node, Mapping[Node, Mapping[str, Domain]]] = digraph
self.result_type = result_type
[docs]
def distance(self, ratio: Ratio, edge: MutableMapping[str, Domain]) -> Ratio:
"""
The function calculates the distance based on the ratio and edge information.
:param ratio: The ratio parameter is of type Ratio. It is used in the calculation of the return value
:type ratio: Ratio
:param edge: The `edge` parameter is a mutable mapping (dictionary-like object) that contains
information about a specific edge in a graph. It has two keys: "cost" and "time". The value
associated with the "cost" key represents the cost of traversing the edge, while the value
associated with
:type edge: MutableMapping[str, Domain]
:return: the result of the expression `self.result_type(edge["cost"]) - ratio * edge["time"]`.
"""
return self.result_type(edge["cost"]) - ratio * edge["time"]
[docs]
def zero_cancel(self, cycle: Cycle) -> Ratio:
"""
The `zero_cancel` function calculates the ratio of the cost to time for a given cycle.
:param cycle: The `cycle` parameter is of type `Cycle`. It represents a cycle, which is a sequence
of edges in a graph that starts and ends at the same vertex. Each edge in the cycle is a dictionary
with keys "cost" and "time", representing the cost and time associated with that edge
:type cycle: Cycle
:return: a Ratio object.
"""
total_cost = sum(edge["cost"] for edge in cycle)
total_time = sum(edge["time"] for edge in cycle)
return self.result_type(total_cost) / total_time
# The `MinCycleRatioSolver` class is a solver for the minimum cycle ratio problem in directed graphs.
[docs]
class MinCycleRatioSolver(Generic[Node, Edge, Ratio]):
"""Minimum Cycle Ratio Solver
This class solves the following parametric network problem:
max r
s.t. dist[v] - dist[u] <= cost(u, v) - ratio * time(u, v)
for all (u, v) in E
The minimum cycle ratio (MCR) problem is a fundamental problem in the
analysis of directed graphs. Given a directed graph, the MCR problem seeks to
find the cycle with the minimum ratio of the sum of edge weights to the
number of edges in the cycle. In other words, the MCR problem seeks to find
the "tightest" cycle in the graph, where the tightness of a cycle is measured
by the ratio of the total weight of the cycle to its length.
The MCR problem has many applications in the analysis of discrete event
systems, such as digital circuits and communication networks. It is closely
related to other problems in graph theory, such as the shortest path problem
and the maximum flow problem. Efficient algorithms for solving the MCR
problem are therefore of great practical importance.
"""
def __init__(self, digraph: Graph) -> None:
"""
The function initializes an instance of a class with a graph object.
:param digraph: The `digraph` parameter is a mapping of nodes to a mapping of nodes to any type of value. It
represents a graph where each node is associated with a set of neighboring nodes and their
corresponding values
:type digraph: Graph
"""
self.digraph: Graph = digraph
[docs]
def run(self, dist: MutableMapping[Node, Domain], r0: Ratio) -> Tuple[Ratio, Cycle]:
"""
This function takes a distance mapping and a ratio as input, and returns a ratio and a cycle.
:param dist: A mutable mapping that maps each node in the graph to a ratio value. This represents
the initial distribution of ratios for each node
:type dist: MutableMapping[Node, Domain]
:param r0: The parameter `r0` is of type `Ratio` and represents the initial ratio value
:type r0: Ratio
:return: The function `run` returns a tuple containing the ratio and cycle.
"""
omega = CycleRatioAPI(self.digraph, type(r0))
solver = MaxParametricSolver(self.digraph, omega)
ratio, cycle = solver.run(dist, r0)
return ratio, cycle
```