Algorithm Module

chipfiring.algo.EWD(graph: CFGraph, divisor: CFDivisor, optimized: bool = False, visualize: bool = False) → 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.

The vertex ‘q’ is chosen as the vertex with the minimum degree (most debt) 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).

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 divisor has no degrees mapping, making it impossible to determine the initial vertex ‘q’.
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

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:

A tuple containing a boolean indicating if the divisors are linearly equivalent, and the q-reduced divisor if they are.

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.

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.q_reduction(divisor: CFDivisor) → CFDivisor[source]

Perform a q-reduction on the given divisor.

A q-reduction is a sequence of legal chip firings that results in a divisor where no set of vertices excluding q can legally fire.

Parameters:: divisor – The initial chip distribution (CFDivisor instance).
Returns:: The q-reduced divisor.
Raises:: ValueError – If the EWD algorithm doesn’t 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)
>>> # 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) → bool[source]

Check if the given divisor is q-reduced.

A divisor is q-reduced if no subset of vertices excluding q can legally fire.

Parameters:: divisor – The initial chip distribution (CFDivisor instance).
Returns:: True if the divisor is q-reduced, False otherwise.

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)
True
>>> # Create a non-q-reduced divisor
>>> non_reduced = CFDivisor(graph, [("Alice", 2), ("Bob", -3), ("Charlie", 4), ("Elise", -1)])
>>> # This should still be true since q-reduction just transforms it to itself
>>> is_q_reduced(non_reduced)
True