Dhar Algorithm Module

class chipfiring.CFDhar.DharAlgorithm(graph: CFGraph, initial_divisor: CFDivisor, q_name: str, visualizer=None)

Bases: object

Implements Dhar’s algorithm for finding maximal legal firing sets on a graph.

Dhar’s algorithm uses a “burning process” to identify vertices that can be legally fired together. It starts a fire at a distinguished vertex q and determines which vertices burn based on chip configuration.

Example

>>> # Create a simple graph
>>> vertices = {"A", "B", "C", "D"}
>>> edges = [("A", "B", 1), ("B", "C", 1), ("C", "D", 1), ("D", "A", 1), ("A", "C", 1)]
>>> graph = CFGraph(vertices, edges)
>>> # Create a chip configuration (as a CFDivisor)
>>> divisor = CFDivisor(graph, [("A", 3), ("B", 2), ("C", 1), ("D", 2)])
>>> # Initialize the algorithm with "A" as the distinguished vertex
>>> dhar = DharAlgorithm(graph, divisor, "A")
>>> # Run the algorithm to find maximal legal firing set
>>> firing_set_names, orientation = dhar.run()
>>> # Check which vertices are in the firing set (excluding A)
>>> sorted(list(firing_set_names))
['B', 'C', 'D']
>>> # Verify orientation is a CFOrientation object
>>> isinstance(orientation, CFOrientation)
True

__init__(graph: CFGraph, initial_divisor: CFDivisor, q_name: str, visualizer=None)

Initialize Dhar’s Algorithm for finding a maximal legal firing set.

Parameters:

• graph – A CFGraph object representing the graph.

• initial_divisor – A CFDivisor object representing the initial chip configuration on G. This divisor will be modified by the algorithm (e.g., by send_debt_to_q).

• q_name – The name of the distinguished vertex (fire source).

• visualizer – An optional EWDVisualizer instance for visualization.

Raises:

ValueError – If q_name is not found in the graph.

Example

>>> # Create a simple graph
>>> vertices = {"A", "B", "C", "D"}
>>> edges = [("A", "B", 1), ("B", "C", 1), ("C", "D", 1), ("D", "A", 1)]
>>> graph = CFGraph(vertices, edges)
>>> # Create a chip configuration
>>> divisor = CFDivisor(graph, [("A", 2), ("B", 1), ("C", 0), ("D", 1)])
>>> # Initialize the algorithm with "A" as the distinguished vertex
>>> dhar = DharAlgorithm(graph, divisor, "A")
>>> dhar.q_vertex.name # q_vertex is now part of CFConfig
'A'
>>> # Unburnt vertices initially (all except q from CFConfig)
>>> sorted(list(dhar.configuration.get_v_tilde_names()))
['B', 'C', 'D']
>>> # Invalid distinguished vertex
>>> try:
...     DharAlgorithm(graph, divisor, "E")
... except ValueError as e:
...     print(str(e))
Vertex q='E' not found in the graph of the divisor.

outdegree_S(vertex: Vertex, S: Set[Vertex]) → int

Calculate the number of edges from a vertex to vertices in set S. S can be any subset of V (including q). This is used for calculating edges to burnt set.

Parameters:

• vertex – A Vertex object

• S – A set of Vertex objects

Returns:

The number of edges from vertex to vertices in S.

Example

>>> vertices = {"A", "B", "C", "D"}
>>> edges = [("A", "B", 1), ("B", "C", 1), ("C", "D", 1), ("D", "A", 1)]
>>> graph = CFGraph(vertices, edges)
>>> dhar = DharAlgorithm(graph, divisor, "A")
>>> dhar.outdegree_S(Vertex("A"), {Vertex("B"), Vertex("C")})
1
>>> dhar.outdegree_S(Vertex("A"), {Vertex("B"), Vertex("C"), Vertex("D")})
2
>>> dhar.outdegree_S(Vertex("A"), {Vertex("B"), Vertex("C"), Vertex("D"), Vertex("A")})
2
>>> dhar.outdegree_S(Vertex("A"), {Vertex("A")})
0

send_debt_to_q() → None

Concentrate all debt at the distinguished vertex q, making all non-q vertices out of debt. This method modifies self.configuration (and its underlying divisor) so all c(v) for v in V~ are non-negative.

Example

>>> vertices = {"A", "B", "C", "D"}
>>> edges = [("A", "B", 1), ("B", "C", 1), ("C", "D", 1), ("D", "A", 1)]
>>> graph = CFGraph(vertices, edges)
>>> divisor = CFDivisor(graph, [("A", 2), ("B", -1), ("C", -2), ("D", 1)])
>>> dhar = DharAlgorithm(graph, divisor, "A") # dhar.configuration now wraps divisor
>>> # Check initial configuration values in V~
>>> dhar.configuration.get_degree_at("B")
-1
>>> dhar.configuration.get_degree_at("C")
-2
>>> initial_q_degree = dhar.configuration.get_q_underlying_degree() # D(A)
>>> # Send debt to q (A)
>>> dhar.send_debt_to_q()
>>> # Verify all non-q vertices have non-negative values
>>> dhar.configuration.get_degree_at("B") >= 0
True
>>> dhar.configuration.get_degree_at("C") >= 0
True
>>> dhar.configuration.get_degree_at("D") >= 0
True
>>> # The distinguished vertex q takes on the debt
>>> dhar.configuration.get_q_underlying_degree() < initial_q_degree # D(A) should decrease
True

run() → Tuple[Set[str], CFOrientation]

Run Dhar’s Algorithm to find a maximal legal firing set.

Returns:

• A set of names of unburnt vertices (V~_unburnt) representing the maximal legal firing set.

• A CFOrientation object tracking the burning directions.

Return type:

A tuple containing

Example

>>> vertices = {"A", "B", "C", "D"}
>>> edges = [("A", "B", 1), ("B", "C", 1), ("C", "D", 1), ("D", "A", 1)]
>>> graph = CFGraph(vertices, edges)
>>> divisor = CFDivisor(graph, [("A", 3), ("B", 2), ("C", 1), ("D", 2)])
>>> dhar = DharAlgorithm(graph, divisor, "A")
>>> unburnt_names, orientation = dhar.run()
>>> sorted(list(unburnt_names))
['B', 'C', 'D']
>>> isinstance(orientation, CFOrientation)
True
>>> # Example with debt and burning
>>> from chipfiring import CFOrientation, OrientationState # For doctest
>>> divisor2 = CFDivisor(graph, [("A", 3), ("B", 0), ("C", 0), ("D", 2)])
>>> dhar2 = DharAlgorithm(graph, divisor2, "A")
>>> unburnt_names2, orientation2 = dhar2.run()
>>> 'B' not in unburnt_names2 # B burns
True
>>> # Check orientation from A to B. Since B burns due to A, A is source, B is sink.
>>> orientation2.get_orientation("A", "B") == ('A', 'B')
True

get_maximal_legal_firing_set() → Set[str]

Runs Dhar’s algorithm and returns only the set of unburnt vertex names (maximal legal firing set).

Returns:

A set of names of unburnt vertices (V~_unburnt).

Example

>>> vertices = {"A", "B", "C", "D"}
>>> edges = [("A", "B", 1), ("B", "C", 1), ("C", "D", 1), ("D", "A", 1)]
>>> graph = CFGraph(vertices, edges)
>>> divisor = CFDivisor(graph, [("A", 3), ("B", 2), ("C", 1), ("D", 2)])
>>> dhar = DharAlgorithm(graph, divisor, "A")
>>> dhar.get_maximal_legal_firing_set()
{'B', 'C', 'D'}

legal_set_fire(unburnt_vertex_names: Set[str])

Performs a set firing operation on the provided set of unburnt vertex names (from V~). This modifies the underlying divisor of the CFConfig object.

Parameters:

unburnt_vertex_names – A set of names of vertices in V~ (typically the result of self.run()).

Example

>>> vertices = {"A", "B", "C"}
>>> edges = [("A", "B", 1), ("B", "C", 1), ("A", "C", 2)]
>>> graph = CFGraph(vertices, edges)
>>> divisor = CFDivisor(graph, [("A", 0), ("B", 2), ("C", 3)]) # q=A, c(B)=2, c(C)=3
>>> dhar = DharAlgorithm(graph, divisor, "A")
>>> # Assume run() determined {"B", "C"} as unburnt_vertex_names
>>> unburnt_to_fire = {"B", "C"}
>>> dhar.legal_set_fire(unburnt_to_fire)
>>> # B fires to A (q). C fires to A (q).
>>> # Initial: D(A)=0, D(B)=2, D(C)=3
>>> # B fires to A (1 chip): D(B) -> 2-1=1, D(A) -> 0+1=1
>>> # C fires to A (2 chips): D(C) -> 3-2=1, D(A) -> 1+2=3
>>> # Final configuration on V~ (B,C)
>>> dhar.configuration.get_degree_at("B") # c(B)
1
>>> dhar.configuration.get_degree_at("C") # c(C)
1
>>> # Underlying degree of q
>>> dhar.configuration.get_q_underlying_degree() # D(A)
3