`skcriteria.utils.cycle_removal` module

Utility to remove cycles from Networkx graphs.

skcriteria.utils.cycle_removal.generate_acyclic_graphs(graph, *, strategy='random', max_graphs=10, seed=None)[source]

Generate multiple acyclic graphs by removing edges from cycles.

This function creates multiple directed acyclic graphs (DAGs) from a potentially cyclic input graph by strategically removing edges that participate in cycles. Different strategies can be used to select which edges to remove, and multiple attempts generate diverse solutions.

Parameters:

graph (networkx.DiGraph) – The input directed graph, which may contain cycles.
strategy (str or callable, default "random") – Edge selection strategy for cycle breaking: - “random”: Select edges uniformly at random - “weighted”: Select edges proportional to their cycle frequency - callable: Custom edge selection function with signature func(cycle, edge_freq, rng) -> edge_tuple
max_graphs (int, default 10) – Maximum number of acyclic graphs to generate. The function may return fewer graphs if it cannot generate enough unique solutions.
seed (int, optional) – Random seed for reproducible results. If None, results will vary between runs.

Returns:

A list of tuples where each tuple contains: - acyclic_graph (networkx.DiGraph): A directed acyclic graph - removed_edges (set): Set of edges that were removed to break cycles

If the input graph is already acyclic, returns a single tuple with the original graph and an empty set of removed edges.

Return type:

list of tuple

Raises:

ValueError – If the strategy parameter is not recognized and not a callable function.

Notes

The algorithm works by:

Cycle Detection: Find all simple cycles in the input graph
Edge Selection: For each cycle, select an edge to remove based on the chosen strategy
Graph Modification: Create a new graph with selected edges removed
Validation: Check if the resulting graph is acyclic
Iteration: Repeat with different random choices to generate multiple solutions

The function attempts up to 2 * max_graphs iterations to generate the requested number of acyclic graphs. This provides robustness against cases where the random selection produces duplicate solutions.

Strategy Details:

Random: Each edge in each cycle has equal probability of removal
Weighted: Edges appearing in more cycles are more likely to be
removed

Performance Considerations:

Time complexity depends on the number of cycles and their lengths
Memory usage scales with the number of generated graphs
For large graphs with many cycles, consider reducing max_graphs

Examples

>>> import networkx as nx
>>>
>>> # Create a cyclic graph
>>> G = nx.DiGraph([(1, 2), (2, 3), (3, 1), (1, 4)])
>>>
>>> # Generate acyclic graphs using random strategy
>>> results = generate_acyclic_graphs(G, strategy="random", max_graphs=5)
>>> len(results)
5
>>>
>>> # Check that results are acyclic
>>> for dag, removed in results:
...     print(f"Acyclic: {nx.is_directed_acyclic_graph(dag)}")
...     print(f"Removed edges: {removed}")
Acyclic: True
Removed edges: {(3, 1)}
Acyclic: True
Removed edges: {(2, 3)}
...

>>> # Use weighted strategy for more systematic edge removal
>>> results_weighted = generate_acyclic_graphs(
...     G, strategy="weighted", max_graphs=3, seed=42
... )
>>>
>>> # Already acyclic graph
>>> dag = nx.DiGraph([(1, 2), (2, 3)])
>>> results_acyclic = generate_acyclic_graphs(dag)
>>> len(results_acyclic)
1
>>> results_acyclic[0][1]  # No edges removed
set()

skcriteria.utils.cycle_removal module

`skcriteria.utils.cycle_removal` module