Laplacian Module

class chipfiring.CFLaplacian.CFLaplacian(graph: CFGraph)

Bases: object

Represents the Laplacian operator for a chip-firing graph.

__init__(graph: CFGraph)

Initialize the Laplacian with a CFGraph.

Parameters:

graph – A CFGraph object representing the graph.

Example

>>> vertices = {"v1", "v2", "v3"}
>>> edges = [("v1", "v2", 1), ("v2", "v3", 1), ("v1", "v3", 1)]
>>> graph = CFGraph(vertices, edges)
>>> laplacian = CFLaplacian(graph)

_construct_matrix() → Dict[Vertex, Dict[Vertex, int]]

Construct the Laplacian matrix representation for the graph.

Returns:

A dictionary where each key is a Vertex, and the value is another dictionary representing the row of the Laplacian matrix for that vertex. The inner dictionary maps neighboring Vertices to their corresponding negative edge valence, and the vertex itself maps to its total valence.

Example

>>> vertices = {"a", "b", "c"}
>>> edges = [("a", "b", 2), ("b", "c", 3)]
>>> graph = CFGraph(vertices, edges)
>>> laplacian = CFLaplacian(graph)
>>> matrix = laplacian._construct_matrix()
>>> # The matrix would look like:
>>> #    a  b  c
>>> # a [2 -2  0]
>>> # b [-2 5 -3]
>>> # c [0 -3  3]

apply(divisor: CFDivisor, firing_script: CFiringScript) → CFDivisor

Apply the Laplacian to a firing script and add the result to an initial divisor.

Calculates D’ = D - L * s, where D is the initial divisor, L is the Laplacian, s is the firing script vector, and D’ is the resulting divisor.

Parameters:

• divisor – The initial CFDivisor object representing chip counts.

• firing_script – The CFiringScript object representing the net firings.

Returns:

A new CFDivisor object representing the chip configuration after applying the firing script via the Laplacian.

Example

>>> vertices = {"v1", "v2", "v3"}
>>> edges = [("v1", "v2", 1), ("v2", "v3", 1), ("v1", "v3", 1)]
>>> graph = CFGraph(vertices, edges)
>>> degrees = [("v1", 5), ("v2", 0), ("v3", -2)]
>>> divisor = CFDivisor(graph, degrees)
>>> script = {"v1": 1, "v2": -1}  # v1 fires once, v2 borrows once
>>> firing_script = CFiringScript(graph, script)
>>> laplacian = CFLaplacian(graph)
>>> result = laplacian.apply(divisor, firing_script)
>>> result.get_degree("v1")
2
>>> result.get_degree("v2")
3
>>> result.get_degree("v3")
-2

get_matrix_entry(v_name: str, w_name: str) → int

Get the value of the Laplacian matrix at entry (v, w).

Parameters:

• v_name – The name of the row vertex.

• w_name – The name of the column vertex.

Returns:

The integer value of the Laplacian matrix L[v][w].

Raises:

ValueError – If v_name or w_name are not in the graph.

Example

>>> vertices = {"a", "b", "c"}
>>> edges = [("a", "b", 2), ("b", "c", 3)]
>>> graph = CFGraph(vertices, edges)
>>> laplacian = CFLaplacian(graph)
>>> laplacian.get_matrix_entry("a", "a")
2  # Diagonal entry: valence of vertex a
>>> laplacian.get_matrix_entry("b", "b")
5  # Diagonal entry: valence of vertex b (2+3)
>>> laplacian.get_matrix_entry("a", "b")
-2  # Off-diagonal: negative valence between a and b
>>> laplacian.get_matrix_entry("a", "c")
0   # Off-diagonal: a and c are not neighbors

get_reduced_matrix(q: Vertex) → Dict[Vertex, Dict[Vertex, int]]

Get the reduced Laplacian matrix for a given vertex q.

Parameters:

q – The vertex to reduce the matrix with respect to.

Returns:

A dictionary representing the reduced Laplacian matrix.

Example

>>> vertices = {"A", "B", "C"}
>>> edges = [("A", "B", 2), ("B", "C", 1), ("A", "C", 1)]
>>> # The full Laplacian matrix is:
>>> #    A  B  C
>>> # A [3 -2 -1]
>>> # B [-2 3 -1]
>>> # C [-1 -1 2]
>>> # Reducing with respect to B, we get:
>>> #    A  C
>>> # A [3 -1]
>>> # C [-1 2]

solve_partial_system(degrees_at_v_tilde: Dict[Vertex, int], q_vertex: Vertex) → Dict[Vertex, int]

Solve the system L_q * x = b_q for a chip-firing context.

Parameters:

• degrees_at_v_tilde – Dictionary of degrees at non-q vertices

• q_vertex – The q-vertex (excluded from the system)

Returns:

Dictionary of resulting degrees at non-q vertices after solving

apply_reduced_matrix_inv_floor_optimization(divisor: CFDivisor, reduced_matrix: Dict[Vertex, Dict[Vertex, int]], q: Vertex) → List[Tuple[str, int]]

Apply the reduced Laplacian matrix to a divisor according to the formula: c’ = c - floor(inv(L_q) @ c) where L_q is the reduced Laplacian with respect to q, and c is the part of the divisor not on q.

Parameters:

• divisor – The initial CFDivisor object representing chip counts.

• reduced_matrix – The reduced Laplacian matrix (L_q) to apply. Keys are Vertex objects (all vertices except q).

• q – The vertex the matrix was reduced with respect to.

Returns:

A list of tuples representing the new divisor (c’) for vertices not equal to q.

Raises:

ValueError – If the reduced_matrix is empty or not invertible.

Example: # NOTE: This example might need updating based on the new formula.

>>> vertices = {"A", "B", "C"}
>>> edges = [("A", "B", 2), ("B", "C", 1), ("A", "C", 1)]
>>> graph = CFGraph(vertices, edges)
>>> laplacian = CFLaplacian(graph)
>>> q_vertex = Vertex("B")
>>> reduced_lap_dict = laplacian.get_reduced_matrix(q_vertex)
>>> # Reduced Laplacian L_B (for A, C):
>>> #    A  C
>>> # A [3 -1]
>>> # C [-1 2]
>>> # inv(L_B) = [[2/5, 1/5], [1/5, 3/5]]
>>> initial_degrees_dict = {"A": 3, "C": 0} # Divisor c, on vertices not B
>>> divisor_obj = CFDivisor(graph, [("A", 3), ("B", 10), ("C", 0)]) # Full divisor D
>>> # c = [3, 0] for A, C
>>> # inv(L_B) @ c = [2/5*3 + 1/5*0, 1/5*3 + 3/5*0] = [6/5, 3/5] = [1.2, 0.6]
>>> # floor(inv(L_B) @ c) = [1, 0]
>>> # c' = c - floor(inv(L_B) @ c) = [3-1, 0-0] = [2, 0]
>>> # result = laplacian.apply_reduced_matrix_inv_floor_optimization(divisor_obj, reduced_lap_dict, q_vertex)
>>> # dict(result)
{'A': 2, 'C': 0}