Algorithm Module

chipfiring.algo.EWD(graph: CFGraph, divisor: CFDivisor, optimized: bool = False, visualize: bool = False, q_name: str | None = None) → Tuple[bool, CFDivisor | None, CFOrientation | None, EWDVisualizer | None][source]

Determine if a given chip-firing configuration is winnable using the Efficient Winnability Detection (EWD) algorithm.

The EWD algorithm iteratively applies Dhar’s algorithm to find and fire maximal legal firing sets until no more such sets can be found or the configuration becomes q-reduced with respect to a chosen vertex q.

If q_name is supplied, that vertex is used as q. Otherwise q defaults deterministically to the minimum-degree vertex in the initial configuration.

Parameters:

graph – The chip-firing graph (CFGraph instance).
divisor – The initial chip distribution (CFDivisor instance).
optimized – Whether to run EWD in optimized mode. (default: False). Note: if you choose to run in optimized mode, you might not get the associated induced orientation and q-reduced divisor because of the shortcuts taken by the algorithm to determine winnability.
visualize – Whether to visualize the EWD algorithm. (default: False).
q_name – Optional name of the distinguished vertex. If omitted, EWD preserves its historical behavior and chooses a minimum-degree vertex. The input divisor is never modified.

Returns:

Boolean indicating if the configuration is winnable
The q-reduced divisor (or None if not applicable)
The final orientation of edges tracking fire spread (or None if not applicable)
The visualizer object if visualize is True, else None.

Return type:

A tuple containing

Raises:

ValueError – If the graph is empty or disconnected, or if q_name is not a graph vertex.
RuntimeError – If the final orientation is not full (some edges remain unoriented).

Example

>>> # Create a simple graph
>>> vertices = {"Alice", "Bob", "Charlie", "Elise"}
>>> edges = [
...     ("Alice", "Bob", 1),
...     ("Bob", "Charlie", 1),
...     ("Charlie", "Elise", 1),
...     ("Alice", "Elise", 2),
...     ("Alice", "Charlie", 1),
... ]
>>> graph = CFGraph(vertices, edges)
>>> # Create a winnable divisor
>>> divisor = CFDivisor(graph, [("Alice", 2), ("Bob", -3), ("Charlie", 4), ("Elise", -1)])
>>> # Run EWD algorithm
>>> is_winnable, q_reduced, orientation, _ = EWD(graph, divisor)
>>> is_winnable  # This configuration is winnable
True
>>> # Check q-reduced divisor
>>> [(v.name, q_reduced.get_degree(v.name)) for v in sorted(q_reduced.degrees.keys(), key=lambda v: v.name)]
[('Alice', 2), ('Bob', 0), ('Charlie', 0), ('Elise', 0)]
>>> # Check orientation is a CFOrientation object
>>> isinstance(orientation, CFOrientation)
True
>>> # Example with optimized mode
>>> non_winnable = CFDivisor(graph, [("Alice", -2), ("Bob", 0), ("Charlie", 0), ("Elise", 0)])
>>> is_win, reduced, orient, _ = EWD(graph, non_winnable, optimized=True)
>>> is_win  # Total degree is negative, so not winnable
False
>>> reduced is None and orient is None  # Optimized mode returns None for these
True

chipfiring.algo.linear_equivalence(divisor1: CFDivisor, divisor2: CFDivisor) → bool[source]

Check if two divisors are linearly equivalent.

Two divisors are linearly equivalent if they can be transformed into each other by a sequence of lending and borrowing moves.

This is checked by determining the winnability of their difference divisor (divisor1 - divisor2).

Parameters:

divisor1 – The first CFDivisor object.
divisor2 – The second CFDivisor object.

Returns:

True if the divisors are linearly equivalent, False otherwise.

Raises:

ValueError – If a nontrivial comparison is attempted on a disconnected graph.

Example

>>> # Create a simple graph
>>> vertices = {"v1", "v2", "v3"}
>>> edges = [("v1", "v2", 1), ("v2", "v3", 1), ("v1", "v3", 1)]
>>> graph = CFGraph(vertices, edges)
>>> # Create two divisors
>>> divisor1 = CFDivisor(graph, [("v1", 3), ("v2", 1), ("v3", 0)])
>>> divisor2 = CFDivisor(graph, [("v1", 1), ("v2", 2), ("v3", 1)])  # Obtained by firing v1
>>> # Check linear equivalence
>>> linear_equivalence(divisor1, divisor2)  # These should be linearly equivalent
True
>>> # Same total degree but not linearly equivalent
>>> divisor3 = CFDivisor(graph, [("v1", 0), ("v2", 0), ("v3", 4)])
>>> linear_equivalence(divisor1, divisor3)  # These have same total degree but aren't equivalent
False
>>> # Different total degree
>>> divisor4 = CFDivisor(graph, [("v1", 3), ("v2", 2), ("v3", 0)])  # Total degree 5
>>> linear_equivalence(divisor1, divisor4)  # Different total degree means not equivalent
False
>>> # Identical divisors
>>> linear_equivalence(divisor1, divisor1)  # Same divisor is trivially equivalent
True

chipfiring.algo.is_winnable(divisor: CFDivisor) → bool[source]

Check if a given chip-firing configuration is winnable.

This function uses the Efficient Winnability Detection (EWD) algorithm to determine if the given chip-firing configuration is winnable.

Parameters:: divisor – The initial chip distribution (CFDivisor instance).
Returns:: True if the configuration is winnable, False otherwise.
Raises:: ValueError – If the divisor is defined on an empty or disconnected graph.

Example

>>> # Create a simple graph
>>> vertices = {"v1", "v2", "v3"}
>>> edges = [("v1", "v2", 1), ("v2", "v3", 1), ("v1", "v3", 1)]
>>> graph = CFGraph(vertices, edges)
>>> # Winnable example - total degree > 0
>>> winnable = CFDivisor(graph, [("v1", 1), ("v2", 2), ("v3", 1)])
>>> is_winnable(winnable)
True
>>> # Non-winnable example - negative total degree
>>> non_winnable = CFDivisor(graph, [("v1", 0), ("v2", 0), ("v3", -2)])
>>> is_winnable(non_winnable)
False
>>> # Zero divisor is winnable
>>> zero_divisor = CFDivisor(graph, [("v1", 0), ("v2", 0), ("v3", 0)])
>>> is_winnable(zero_divisor)
True

chipfiring.algo._resolve_reduction_q_name(divisor: CFDivisor, q_name: str | None) → str | None[source]: Preserve the historical most-indebted default with a stable tie-break.

chipfiring.algo.q_reduction_with_root(divisor: CFDivisor, q_name: str | None = None) → Tuple[CFDivisor, str][source]

Return a q-reduced divisor together with the root used.

Use this helper when q_name is omitted and the result will later be checked with is_q_reduced(); q-reducedness is always relative to a specific root.

chipfiring.algo.q_reduction(divisor: CFDivisor, q_name: str | None = None) → CFDivisor[source]

Perform a q-reduction on the given divisor.

The result is linearly equivalent to divisor, is nonnegative away from q, and admits no legal firing of a nonempty subset of vertices excluding q. The reduction may use both lending and borrowing moves.

Parameters:

divisor – The initial chip distribution (CFDivisor instance).
q_name – Optional name of q. If omitted, the historical most-indebted vertex heuristic is used, with vertex name as a deterministic tie-break. Use q_reduction_with_root() if the chosen root is needed later.

Returns:

The q-reduced divisor.

Raises:

ValueError – If the graph is empty or disconnected, if q_name is not a graph vertex, or if EWD does not produce a valid q-reduced divisor.

Example

>>> # Create a simple graph
>>> vertices = {"Alice", "Bob", "Charlie", "Elise"}
>>> edges = [
...     ("Alice", "Bob", 1),
...     ("Bob", "Charlie", 1),
...     ("Charlie", "Elise", 1),
...     ("Alice", "Elise", 2),
...     ("Alice", "Charlie", 1),
... ]
>>> graph = CFGraph(vertices, edges)
>>> # Create a divisor
>>> divisor = CFDivisor(graph, [("Alice", 2), ("Bob", -3), ("Charlie", 4), ("Elise", -1)])
>>> # Get q-reduced divisor
>>> reduced = q_reduction(divisor, q_name="Bob")
>>> # Check degrees of reduced divisor
>>> [(v.name, reduced.get_degree(v.name)) for v in sorted(reduced.degrees.keys(), key=lambda v: v.name)]
[('Alice', 2), ('Bob', 0), ('Charlie', 0), ('Elise', 0)]

chipfiring.algo.is_q_reduced(divisor: CFDivisor, q_name: str | None = None) → bool[source]

Check if the given divisor is q-reduced.

A divisor is q-reduced if it is nonnegative away from q and no nonempty subset of vertices excluding q can legally fire.

Parameters:

divisor – The initial chip distribution (CFDivisor instance).
q_name – Optional name of q. If omitted, the historical most-indebted vertex heuristic is applied to this divisor. Because q-reducedness is root-relative, pass the root returned by q_reduction_with_root() when checking a reduction result.

Returns:

True if the divisor is q-reduced, False otherwise.

Raises:

ValueError – If the graph is empty or disconnected, or if q_name is not a graph vertex.

Example

>>> # Create a simple graph
>>> vertices = {"Alice", "Bob", "Charlie", "Elise"}
>>> edges = [
...     ("Alice", "Bob", 1),
...     ("Bob", "Charlie", 1),
...     ("Charlie", "Elise", 1),
...     ("Alice", "Elise", 2),
...     ("Alice", "Charlie", 1),
... ]
>>> graph = CFGraph(vertices, edges)
>>> # Create a q-reduced divisor
>>> q_reduced = CFDivisor(graph, [("Alice", 2), ("Bob", 0), ("Charlie", 0), ("Elise", 0)])
>>> is_q_reduced(q_reduced, q_name="Bob")
True
>>> # Create a non-q-reduced divisor
>>> non_reduced = CFDivisor(graph, [("Alice", 2), ("Bob", -3), ("Charlie", 4), ("Elise", -1)])
>>> # The divisor changes under q-reduction, so it is not q-reduced.
>>> is_q_reduced(non_reduced, q_name="Bob")
False