Configuration Module

class chipfiring.CFConfig.CFConfig(divisor: CFDivisor, q_name: str)

Bases: object

Represents a configuration c with respect to a fixed vertex q, where c is an element of Z(V~), and V~ = V - {q}. Operations like lending/borrowing can still occur at q, affecting the underlying divisor, but the configuration’s properties (degree, non-negativity) are defined over V~.

Example

>>> vertices = {"A", "B", "C"}
>>> edges = [("A", "B", 1), ("B", "C", 1)]
>>> graph = CFGraph(vertices, edges)
>>> divisor = CFDivisor(graph, [("A", 2), ("B", 1), ("C", 0)])
>>> config_respect_A = CFConfig(divisor, "A")
>>> config_respect_A.get_degree_at("B")
1
>>> config_respect_A.get_degree_sum() # c(B) + c(C) = 1 + 0
1
>>> config_respect_A.is_non_negative()
True

__init__(divisor: CFDivisor, q_name: str)

Initializes a configuration.

Parameters:

• divisor – The CFDivisor object (representing chip counts on all vertices V).

• q_name – The name of the vertex q to be excluded for configuration properties.

Raises:

ValueError – If q_name is not in the divisor’s graph.

Example

>>> vertices = {"A", "B", "C"}
>>> edges = [("A", "B", 1), ("B", "C", 1)]
>>> graph = CFGraph(vertices, edges)
>>> divisor = CFDivisor(graph, [("A", 2), ("B", 1), ("C", 0)])
>>> config = CFConfig(divisor, "A")
>>> config.get_degree_at("B")
1

get_degree_at(vertex_name: str) → int

Returns c(v), the number of chips associated with vertex v in the configuration (v in V~).

Parameters:

vertex_name – The name of the vertex in V~.

Returns:

The number of chips c(v).

Raises:

ValueError – If vertex_name is q or not in V~.

Example

>>> vertices = {"A", "B", "C"}
>>> edges = [("A", "B", 1), ("B", "C", 1)]
>>> graph = CFGraph(vertices, edges)
>>> divisor = CFDivisor(graph, [("A", 2), ("B", 1), ("C", 0)])
>>> config = CFConfig(divisor, "A")
>>> config.get_degree_at("B")
1

is_non_negative() → bool

Checks if the configuration c is non-negative (c(v) >= 0 for all v in V~).

Example

>>> vertices = {"A", "B", "C"}
>>> edges = [("A", "B", 1), ("B", "C", 1)]
>>> graph = CFGraph(vertices, edges)
>>> divisor = CFDivisor(graph, [("A", 2), ("B", 1), ("C", 0)])
>>> config = CFConfig(divisor, "A")
>>> config.is_non_negative()
True

get_degree_sum() → int

Calculates deg(c) = sum_{v in V~} c(v).

Returns:

The sum of the configuration degrees c(v) for v in V~.

Example

>>> vertices = {"A", "B", "C"}
>>> edges = [("A", "B", 1), ("B", "C", 1)]
>>> graph = CFGraph(vertices, edges)
>>> divisor = CFDivisor(graph, [("A", 2), ("B", 1), ("C", 0)])
>>> config = CFConfig(divisor, "A")
>>> config.get_degree_sum()
1

_is_comparable_to(other: CFConfig) → bool

Checks if two configurations are defined on the same graph G and with the same q.

lending_move(vertex_name: str) → None

Performs a lending move at vertex_name on the underlying divisor. This can change D(q) if q is involved, but deg(c) remains based on V~.

borrowing_move(vertex_name: str) → None

Performs a borrowing move at vertex_name on the underlying divisor. This can change D(q) if q is involved, but deg(c) remains based on V~.

set_fire(S_vertex_names: Set[str]) → None

Performs a set firing on S_vertex_names (subset of V~) on the underlying divisor. Chips may be transferred to/from q if q is a neighbor of a vertex in S, affecting D(q), but configuration properties remain focused on V~.

Parameters:

S_vertex_names – A set of names of vertices in V~ to be fired.

Raises:

ValueError – If any name in S_vertex_names is q or not in V~.

Example

>>> vertices = {"A", "B", "C"}
>>> edges = [("A", "B", 1), ("B", "C", 1)]
>>> graph = CFGraph(vertices, edges)
>>> divisor = CFDivisor(graph, [("A", 2), ("B", 1), ("C", 0)])
>>> config = CFConfig(divisor, "A")
>>> config.set_fire({"B", "C"})
>>> config.get_degree_at("B")
0
>>> config.get_degree_at("C")
0

get_out_degree_S(v_name_in_S: str, S_names: Set[str]) → int

Calculates outdeg_S(v) for v in S, where S is a subset of V~ names. outdeg_S(v) is the sum of valencies of edges from v to vertices NOT in S (can include q).

Parameters:

• v_name_in_S – Name of the vertex v in S.

• S_names – Set of names of vertices in the set S (subset of V~).

Returns:

The out-degree of v with respect to S.

Example

>>> vertices = {"A", "B", "C"}
>>> edges = [("A", "B", 1), ("B", "C", 1)]
>>> graph = CFGraph(vertices, edges)
>>> divisor = CFDivisor(graph, [("A", 2), ("B", 1), ("C", 0)])
>>> config = CFConfig(divisor, "A")
>>> config.get_out_degree_S("B", {"B", "C"})
1

is_legal_set_firing(S_names: Set[str]) → bool

Checks if firing the non-empty set S_names (subset of V~) is legal. A firing c –S–> c’ is legal if c’(v) >= 0 for all v in S. :param S_names: A non-empty set of names of vertices in V~ to be fired.

Returns:

True if the set firing is legal, False otherwise.

Raises:

ValueError – If S_names contains q or vertices not in V~.

Example

>>> vertices = {"A", "B", "C"}
>>> edges = [("A", "B", 1), ("B", "C", 1)]
>>> graph = CFGraph(vertices, edges)
>>> divisor = CFDivisor(graph, [("A", 2), ("B", 1), ("C", 0)])
>>> config = CFConfig(divisor, "A")
>>> config.is_legal_set_firing({"B", "C"})
True

is_superstable() → bool

Checks if the configuration c is superstable. c is superstable if c >= 0 (non-negative) and has no legal nonempty set-firings within V~. Note: This method tries all possible nonempty subsets of V~ to check for legal set-firings. This is not efficient for large graphs, but is correct.

Parameters:

None

Returns:

True if the configuration is superstable, False otherwise.

Example

>>> vertices = {"A", "B", "C"}
>>> edges = [("A", "B", 1), ("B", "C", 1)]
>>> graph = CFGraph(vertices, edges)
>>> divisor = CFDivisor(graph, [("A", 2), ("B", 1), ("C", 0)])
>>> config = CFConfig(divisor, "A")
>>> config.is_superstable()
False

get_q_vertex_name() → str

Returns the name of the q vertex.

Example

>>> vertices = {"A", "B", "C"}
>>> edges = [("A", "B", 1), ("B", "C", 1)]
>>> graph = CFGraph(vertices, edges)
>>> divisor = CFDivisor(graph, [("A", 2), ("B", 1), ("C", 0)])
>>> config = CFConfig(divisor, "A")
>>> config.get_q_vertex_name()
"A"

get_q_underlying_degree() → int

Returns D(q), the degree of q in the underlying divisor. Note: This is not c(q), as configurations are not defined at q.

Example

>>> vertices = {"A", "B", "C"}
>>> edges = [("A", "B", 1), ("B", "C", 1)]
>>> graph = CFGraph(vertices, edges)
>>> divisor = CFDivisor(graph, [("A", 2), ("B", 1), ("C", 0)])
>>> config = CFConfig(divisor, "A")
>>> config.get_q_underlying_degree()
2

get_v_tilde_names() → Set[str]

Returns the set of names of vertices in V~ (= V - {q}).

Example

>>> vertices = {"A", "B", "C"}
>>> edges = [("A", "B", 1), ("B", "C", 1)]
>>> graph = CFGraph(vertices, edges)
>>> divisor = CFDivisor(graph, [("A", 2), ("B", 1), ("C", 0)])
>>> config = CFConfig(divisor, "A")
>>> config.get_v_tilde_names()
{"B", "C"}

get_config_degrees_as_dict() → Dict[str, int]

Returns the configuration degrees c(v) for v in V~ as a dictionary {name: degree}.

Example

>>> vertices = {"A", "B", "C"}
>>> edges = [("A", "B", 1), ("B", "C", 1)]
>>> graph = CFGraph(vertices, edges)
>>> divisor = CFDivisor(graph, [("A", 2), ("B", 1), ("C", 0)])
>>> config = CFConfig(divisor, "A")
>>> config.get_config_degrees_as_dict()
{"B": 1, "C": 0}

copy() → CFConfig

Returns a deep copy of this CFConfig object, including a deep copy of the underlying divisor.

Example

>>> vertices = {"A", "B", "C"}
>>> edges = [("A", "B", 1), ("B", "C", 1)]
>>> graph = CFGraph(vertices, edges)
>>> divisor = CFDivisor(graph, [("A", 2), ("B", 1), ("C", 0)])
>>> config = CFConfig(divisor, "A")
>>> config_copy = config.copy()
>>> config_copy.get_degree_at("B")
1