digraphx package

Submodules

digraphx.min_cycle_ratio module

class digraphx.min_cycle_ratio.CycleRatioAPI(digraph: Mapping[Node, Mapping[Node, Mapping[str, Domain]]], result_type: type)[source]

Bases: ParametricAPI[Node, MutableMapping[str, Domain], Ratio]

distance(ratio: Ratio, edge: MutableMapping[str, Domain]) Ratio[source]

The function calculates the distance based on the ratio and edge information.

Parameters:
  • ratio (Ratio) – The ratio parameter is of type Ratio. It is used in the calculation of the return value

  • edge (MutableMapping[str, Domain]) – 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

Returns:

the result of the expression self.result_type(edge[“cost”]) - ratio * edge[“time”].

zero_cancel(cycle: List[Edge]) Ratio[source]

The zero_cancel function calculates the ratio of the cost to time for a given cycle.

Parameters:

cycle (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

Returns:

a Ratio object.

class digraphx.min_cycle_ratio.MinCycleRatioSolver(digraph: Mapping[Node, Mapping[Node, Mapping[str, Domain]]])[source]

Bases: 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.

run(dist: MutableMapping[Node, Domain], r0: Ratio) Tuple[Ratio, List[Edge]][source]

This function takes a distance mapping and a ratio as input, and returns a ratio and a cycle.

Parameters:
  • dist (MutableMapping[Node, Domain]) – A mutable mapping that maps each node in the graph to a ratio value. This represents the initial distribution of ratios for each node

  • r0 (Ratio) – The parameter r0 is of type Ratio and represents the initial ratio value

Returns:

The function run returns a tuple containing the ratio and cycle.

digraphx.min_cycle_ratio.set_default(digraph: MutableMapping[Node, MutableMapping[Node, MutableMapping[str, Domain]]], weight: str, value: Domain) None[source]

This function sets a default value for a specified weight in a graph.

Parameters:
  • digraph (GraphMut) – 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

  • weight (str) – The weight parameter is a string that represents the weight attribute of the edges in the graph

  • value (Domain) – The value parameter is the default value that will be set for the specified weight attribute in the graph

digraphx.min_parmetric_q module

class digraphx.min_parmetric_q.MinParametricAPI[source]

Bases: Generic[Node, Edge, Ratio]

abstract distance(ratio: Ratio, edge: Edge) Ratio[source]

The distance function calculates the distance between a given ratio and edge.

Parameters:
  • ratio (Ratio) – The ratio parameter is of type Ratio. It represents a ratio or proportion

  • edge (Edge) – The edge parameter represents an edge in a graph. It is of type Edge

abstract zero_cancel(cycle: List[Edge]) Ratio[source]

The zero_cancel function takes a Cycle object as input and returns a Ratio object.

Parameters:

cycle (Cycle) – The cycle parameter is of type Cycle.

class digraphx.min_parmetric_q.MinParametricSolver(digraph: Mapping[Node, Mapping[Node, Edge]], omega: MinParametricAPI[Node, Edge, Ratio])[source]

Bases: Generic[Node, Edge, Ratio]

Minimum Parametric Solver

This class solves the following parametric network problem:

min r s.t. dist[v] - dist[u] <= distrance(e, r)

forall e(u, v) in G(V, E)

A parametric network problem refers to a type of optimization problem that involves finding the optimal solution to a network flow problem as a function of one single parameter.

run(dist: MutableMapping[Node, Domain], ratio: Ratio, update_ok, pick_one_only=False) Tuple[Ratio, List[Edge]][source]

The run function takes in a distance mapping and a ratio, and iteratively finds the minimum ratio and corresponding cycle until the minimum ratio is greater than or equal to the input ratio.

Parameters:
  • dist (MutableMapping[Node, Domain]) – The dist parameter is a mutable mapping where the keys are Node objects and the values are Domain objects. It represents the distance between nodes in a graph

  • ratio (Ratio) – The ratio parameter is a value that represents a ratio or proportion. It is used as a threshold or target value in the algorithm

  • update_ok – The update_ok parameter is a function that determines whether an update to the distance dist[vtx_v] is allowed. It takes two arguments: the current value of dist[vtx_v] and the new value d. It should return True if the update is

Returns:

The function run returns a tuple containing the updated ratio (ratio) and the cycle (cycle).

digraphx.neg_cycle module

This code defines a NegCycleFinder class, which is used to find negative cycles in a given directed graph. The NegCycleFinder class has the following methods:

  1. __init__(self, digraph: MutableMapping[Node, List[Edge]]): The constructor initializes an instance of the NegCycleFinder class with the given directed graph.

  2. relax(self, dist: MutableMapping[Node, Domain], get_weight: Callable[[Edge], Domain]) -> bool: This method performs one iteration of Bellman-Ford algorithm to relax all edges in the graph and update the shortest distances to their neighbors. It returns a boolean value indicating if any changes were made during this iteration.

  3. howard(self, dist: MutableMapping[Node, Domain], get_weight: Callable[[Edge], Domain]) -> Generator[Cycle, None, None]: This method finds negative cycles in the graph using the Howard’s algorithm and returns a generator that yields a list of edges for each cycle.

  4. cycle_list(self, handle: Node) -> Cycle: This method returns a list of edges that form a cycle in the graph, starting from a given node.

  5. is_negative(self, handle: Node, dist: MutableMapping[Node, Domain], get_weight: Callable[[Edge], Domain]) -> bool: This method checks if a cycle is negative by comparing the distances between nodes and the weights of the edges.

Here’s a brief explanation of the algorithms used in this code:

  1. Bellman-Ford Algorithm: It is a shortest path algorithm that can find single source shortest paths in a graph with negative edge weights. It runs in O(V*E) time complexity.

  2. Howard’s Policy Graph Algorithm: It is used to find cycles in a directed graph and is based on the Bellman-Ford Algorithm. It runs in O(V*E + V*E^2) time complexity in the worst case.

class digraphx.neg_cycle.NegCycleFinder(digraph: Mapping[Node, Mapping[Node, Edge]])[source]

Bases: Generic[Node, Edge, Domain]

Negative Cycle Finder by Howard’s method

Howard’s method is a minimum cycle ratio (MCR) algorithm that uses a policy iteration algorithm to find the minimum cycle ratio of a directed graph. The algorithm maintains a set of candidate cycles and iteratively updates the cycle with the minimum ratio until convergence. To detect negative cycles, Howard’s method uses a cycle detection algorithm that is based on the Bellman-Ford relaxation algorithm. Specifically, the algorithm maintains a predecessor graph of the original graph and performs cycle detection on this graph using the Bellman-Ford relaxation algorithm. If a negative cycle is detected, the algorithm terminates and returns the cycle.

cycle_list(handle: Node) List[Edge][source]

The cycle_list function returns a list of edges that form a cycle in a graph, starting from a given node.

Parameters:

handle (Node) – The handle parameter is a reference to a node in a graph. It represents the starting point of the cycle in the list

Returns:

a list called “cycle”.

find_cycle() Generator[Node, None, None][source]

The find_cycle function is used to find a cycle in a policy graph and yields the start node of the cycle.

Yields:

Generator[Node, None, None] – a start node of the cycle

Examples

>>> digraph = {
...     "a0": {"a1": 7, "a2": 5},
...     "a1": {"a0": 0, "a2": 3},
...     "a2": {"a1": 1, "a0": 2},
... }
>>> finder = NegCycleFinder(digraph)
>>> for cycle in finder.find_cycle():
...     print(cycle)
howard(dist: MutableMapping[Node, Domain], get_weight: Callable[[Edge], Domain]) Generator[List[Edge], None, None][source]

The howard function finds negative cycles in a graph and yields a list of cycles.

Parameters:
  • dist (MutableMapping[Node, Domain]) – dist is a mutable mapping that maps each node in the graph to a domain value. The domain value represents the distance or cost from the source node to that particular node

  • get_weight (Callable[[Edge], Domain]) – The get_weight parameter is a callable function that takes an Edge object as input and returns the weight of that edge

Examples

>>> digraph = {
...     "a0": {"a1": 7, "a2": 5},
...     "a1": {"a0": 0, "a2": 3},
...     "a2": {"a1": 1, "a0": 2},
... }
>>> dist = {vtx: 0 for vtx in digraph}
>>> finder = NegCycleFinder(digraph)
>>> has_neg = False
>>> for _ in finder.howard(dist, lambda edge: edge):
...     has_neg = True
...     break
...
>>> has_neg
False
is_negative(handle: Node, dist: MutableMapping[Node, Domain], get_weight: Callable[[Edge], Domain]) bool[source]

The is_negative function checks if a cycle list is negative by comparing the distances between nodes and the weights of the edges.

Parameters:
  • handle (Node) – The handle parameter is a Node object that represents a vertex in a graph. It is used as a starting point to check for negative cycles in the graph

  • dist (MutableMapping[Node, Domain]) – dist is a mutable mapping that maps each node to its corresponding domain value. The domain value represents the distance from the starting node to the current node in a graph

  • get_weight (Callable[[Edge], Domain]) – The get_weight parameter is a callable function that takes an Edge object as input and returns the weight of that edge

Returns:

a boolean value.

pred: Dict[Node, Tuple[Node, Edge]] = {}
relax(dist: MutableMapping[Node, Domain], get_weight: Callable[[Edge], Domain]) bool[source]

The relax function updates the dist and pred dictionaries based on the current distances and weights of edges in a graph.

Parameters:
  • dist (MutableMapping[Node, Domain]) – dist is a mutable mapping that represents the current distances from a source node to all other nodes in a graph. It is a mapping from nodes to their corresponding distances

  • get_weight (Callable[[Edge], Domain]) – The get_weight parameter is a callable function that takes an Edge object as input and returns a value of type Domain. This function is used to calculate the weight or cost associated with an edge in the graph

Returns:

a boolean value indicating whether any changes were made to the dist mapping and pred dictionary.

digraphx.neg_cycle_q module

Negative cycle detection for directed graphs.

  1. Based on Howard’s policy graph algorithm

  2. Looking for more than one negative cycle

class digraphx.neg_cycle_q.NegCycleFinder(digraph: Mapping[Node, Mapping[Node, Edge]])[source]

Bases: Generic[Node, Edge, Domain]

Negative Cycle Finder by Howard’s method

Howard’s method is a minimum cycle ratio (MCR) algorithm that uses a policy iteration algorithm to find the minimum cycle ratio of a directed graph. The algorithm maintains a set of candidate cycles and iteratively updates the cycle with the minimum ratio until convergence. To detect negative cycles, Howard’s method uses a cycle detection algorithm that is based on the Bellman-Ford relaxation algorithm. Specifically, the algorithm maintains a predecessor graph of the original graph and performs cycle detection on this graph using the Bellman-Ford relaxation algorithm. If a negative cycle is detected, the algorithm terminates and returns the cycle.

cycle_list(handle: Node, point_to) List[Edge][source]

The cycle_list function returns a list of edges that form a cycle in a graph, starting from a given node.

Parameters:
  • handle (Node) – The handle parameter is a reference to a node in a graph. It represents the starting point of the cycle in the list

  • point_to – point_to is a dictionary that maps each graph node to the node it points to

Returns:

a list of edges, which represents a cycle in a graph.

find_cycle(point_to) Generator[Node, None, None][source]

The find_cycle function is used to find a cycle in a policy graph and yields the start node of the cycle.

Parameters:

point_to – The point_to parameter is a dictionary that represents the edges of a directed graph. Each key-value pair in the dictionary represents an edge from the key vertex to the value vertex

Yields:

Generator[Node, None, None] – a start node of the cycle

Examples

>>> digraph = {
...     "a0": {"a1": 7, "a2": 5},
...     "a1": {"a0": 0, "a2": 3},
...     "a2": {"a1": 1, "a0": 2},
... }
>>> finder = NegCycleFinder(digraph)
>>> for cycle in finder.find_cycle(finder.pred):
...     print(cycle)
howard_pred(dist: MutableMapping[Node, Domain], get_weight: Callable[[Edge], Domain], update_ok: Callable[[MutableMapping[Node, Domain], Domain], bool]) Generator[List[Edge], None, None][source]

The howard_pred function finds negative cycles in a graph and yields a list of cycles.

Parameters:
  • dist (MutableMapping[Node, Domain]) – dist is a mutable mapping that maps each node in the graph to a domain value. The domain value represents the distance or cost from the source node to that particular node

  • get_weight (Callable[[Edge], Domain]) – The get_weight parameter is a callable function that takes an Edge object as input and returns the weight of that edge

  • update_ok – The update_ok parameter is a callable function that determines whether an update to the distance value of a vertex is allowed. It takes in three arguments: the current distance value of the vertex, the weight of the edge being considered for update, and the current distance value of the vertex at the other

Examples

>>> digraph = {
...     "a0": {"a1": 7, "a2": 5},
...     "a1": {"a0": 0, "a2": 3},
...     "a2": {"a1": 1, "a0": 2},
... }
>>> dist = {vtx: 0 for vtx in digraph}
>>> def update_ok(dist, v) : return True
>>> finder = NegCycleFinder(digraph)
>>> has_neg = False
>>> for _ in finder.howard_pred(dist, lambda edge: edge, update_ok):
...     has_neg = True
...     break
...
>>> has_neg
False
howard_succ(dist: MutableMapping[Node, Domain], get_weight: Callable[[Edge], Domain], update_ok: Callable[[MutableMapping[Node, Domain], Domain], bool]) Generator[List[Edge], None, None][source]

The howard_succ function finds negative cycles in a graph and yields a list of cycles.

Parameters:
  • dist (MutableMapping[Node, Domain]) – dist is a mutable mapping that maps each node in the graph to a domain value. The domain value represents the distance or cost from the source node to that particular node

  • get_weight (Callable[[Edge], Domain]) – The get_weight parameter is a callable function that takes an Edge object as input and returns the weight of that edge

  • update_ok – The update_ok parameter is a callable function that determines whether an update to the distance value of a vertex is allowed. It takes in three arguments: the current distance value of the vertex, the weight of the edge being considered for update, and the current distance value of the vertex at the other

Examples

>>> digraph = {
...     "a0": {"a1": 7, "a2": 5},
...     "a1": {"a0": 0, "a2": 3},
...     "a2": {"a1": 1, "a0": 2},
... }
>>> def update_ok(dist, v) : return True
>>> dist = {vtx: 0 for vtx in digraph}
>>> finder = NegCycleFinder(digraph)
>>> has_neg = False
>>> for _ in finder.howard_succ(dist, lambda edge: edge, update_ok):
...     has_neg = True
...     break
...
>>> has_neg
False
is_negative(handle: Node, dist: MutableMapping[Node, Domain], get_weight: Callable[[Edge], Domain]) bool[source]

The is_negative function checks if a cycle list is negative by comparing the distances between nodes and the weights of the edges.

Parameters:
  • handle (Node) – The handle parameter is a Node object that represents a vertex in a graph. It is used as a starting point to check for negative cycles in the graph

  • dist (MutableMapping[Node, Domain]) – dist is a mutable mapping that maps each node to its corresponding domain value. The domain value represents the distance from the starting node to the current node in a graph

  • get_weight (Callable[[Edge], Domain]) – The get_weight parameter is a callable function that takes an Edge object as input and returns the weight of that edge

Returns:

a boolean value.

pred: Dict[Node, Tuple[Node, Edge]] = {}
relax_pred(dist: MutableMapping[Node, Domain], get_weight: Callable[[Edge], Domain], update_ok: Callable[[MutableMapping[Node, Domain], Domain], bool]) bool[source]

The relax_pred function updates the dist and pred dictionaries based on the current distances and weights of edges in a graph.

Parameters:
  • dist (MutableMapping[Node, Domain]) – dist is a mutable mapping that represents the current distances from a source node to all other nodes in a graph. It is a mapping from nodes to their corresponding distances

  • get_weight (Callable[[Edge], Domain]) – The get_weight parameter is a callable function that takes an Edge object as input and returns a value of type Domain. This function is used to calculate the weight or cost associated with an edge in the graph

  • update_ok – The update_ok parameter is a function that determines whether an update to the distance dist[vtx_v] is allowed. It takes two arguments: the current value of dist[vtx_v] and the new value d. It should return True if the update is

Returns:

a boolean value indicating whether any changes were made to the dist mapping and pred dictionary.

relax_succ(dist: MutableMapping[Node, Domain], get_weight: Callable[[Edge], Domain], update_ok: Callable[[MutableMapping[Node, Domain], Domain], bool]) bool[source]

The relax_succ function updates the dist and succ dictionaries based on the current distances and weights of edges in a graph.

Parameters:
  • dist (MutableMapping[Node, Domain]) – dist is a mutable mapping that represents the current distances from a source node to all other nodes in a graph. It is a mapping from nodes to their corresponding distances

  • get_weight (Callable[[Edge], Domain]) – The get_weight parameter is a callable function that takes an Edge object as input and returns a value of type Domain. This function is used to calculate the weight or cost associated with an edge in the graph

  • update_ok – The update_ok parameter is a function that determines whether an update to the distance dist[vtx_v] is allowed. It takes two arguments: the current value of dist[vtx_v] and the new value d. It should return True if the update is

Returns:

a boolean value indicating whether any changes were made to the dist mapping and pred dictionary.

succ: Dict[Node, Tuple[Node, Edge]] = {}

digraphx.parametric module

class digraphx.parametric.MaxParametricSolver(digraph: Mapping[Node, Mapping[Node, Edge]], omega: ParametricAPI[Node, Edge, Ratio])[source]

Bases: Generic[Node, Edge, Ratio]

Maximum Parametric Solver

This class solves the following parametric network problem:

max r s.t. dist[v] - dist[u] <= distrance(e, r)

forall e(u, v) in G(V, E)

A parametric network problem refers to a type of optimization problem that involves finding the optimal solution to a network flow problem as a function of one single parameter.

run(dist: MutableMapping[Node, Domain], ratio: Ratio) Tuple[Ratio, List[Edge]][source]

The run function takes in a distance mapping and a ratio, and iteratively finds the minimum ratio and corresponding cycle until the minimum ratio is greater than or equal to the input ratio.

Parameters:
  • dist (MutableMapping[Node, Domain]) – The dist parameter is a mutable mapping where the keys are Node objects and the values are Domain objects. It represents the distance between nodes in a graph

  • ratio (Ratio) – The ratio parameter is a value that represents a ratio or proportion. It is used as a threshold or target value in the algorithm

Returns:

The function run returns a tuple containing the updated ratio (ratio) and the cycle (cycle).

class digraphx.parametric.ParametricAPI[source]

Bases: Generic[Node, Edge, Ratio]

abstract distance(ratio: Ratio, edge: Edge) Ratio[source]

The distance function calculates the distance between a given ratio and edge.

Parameters:
  • ratio (Ratio) – The ratio parameter is of type Ratio. It represents a ratio or proportion

  • edge (Edge) – The edge parameter represents an edge in a graph. It is of type Edge

abstract zero_cancel(cycle: List[Edge]) Ratio[source]

The zero_cancel function takes a Cycle object as input and returns a Ratio object.

Parameters:

cycle (Cycle) – The cycle parameter is of type Cycle.

digraphx.skeleton module

This is a skeleton file that can serve as a starting point for a Python console script. To run this script uncomment the following lines in the [options.entry_points] section in setup.cfg:

console_scripts =
     fibonacci = digraphx.skeleton:run

Then run pip install . (or pip install -e . for editable mode) which will install the command fibonacci inside your current environment.

Besides console scripts, the header (i.e. until _logger…) of this file can also be used as template for Python modules.

Note

This file can be renamed depending on your needs or safely removed if not needed.

References

digraphx.skeleton.fib(n)[source]

Fibonacci example function

Parameters:

n (int) – integer

Returns:

n-th Fibonacci number

Return type:

int

digraphx.skeleton.main(args)[source]

Wrapper allowing fib() to be called with string arguments in a CLI fashion

Instead of returning the value from fib(), it prints the result to the stdout in a nicely formatted message.

Parameters:

args (List[str]) – command line parameters as list of strings (for example ["--verbose", "42"]).

digraphx.skeleton.parse_args(args)[source]

Parse command line parameters

Parameters:

args (List[str]) – command line parameters as list of strings (for example ["--help"]).

Returns:

command line parameters namespace

Return type:

argparse.Namespace

digraphx.skeleton.run()[source]

Calls main() passing the CLI arguments extracted from sys.argv

This function can be used as entry point to create console scripts with setuptools.

digraphx.skeleton.setup_logging(loglevel)[source]

Setup basic logging

Parameters:

loglevel (int) – minimum loglevel for emitting messages

digraphx.tiny_digraph module

Module contents