Graph Module

class chipfiring.CFGraph.Vertex(name: str)

Bases: object

Represents a vertex in the graph.

Example

>>> v1 = Vertex("A")
>>> v2 = Vertex("B")
>>> v3 = Vertex("A")
>>> v1 == v3  # Same name means equal vertices
True
>>> v1 != v2
True
>>> v1 < v2  # Ordering is based on name
True
>>> str(v1)
'A'
>>> vertex_set = {v1, v2, v3}  # v1 and v3 are considered equal
>>> len(vertex_set)
2

__init__(name: str)

class chipfiring.CFGraph.Edge(v1: Vertex, v2: Vertex)

Bases: object

Represents an edge in the graph.

Example

>>> v1 = Vertex("A")
>>> v2 = Vertex("B")
>>> v3 = Vertex("C")
>>> e1 = Edge(v1, v2)
>>> e2 = Edge(v2, v1)  # Same edge, different order
>>> e3 = Edge(v1, v3)
>>> e1 == e2  # Edge equality ignores order of vertices
True
>>> e1 != e3
False
>>> str(e1)
'A-B'
>>> edge_set = {e1, e2, e3}  # e1 and e2 are considered equal
>>> len(edge_set)
2

__init__(v1: Vertex, v2: Vertex)

class chipfiring.CFGraph.CFGraph(vertices: Set[str], edges: List[Tuple[str, str, int]])

Bases: object

Represents a chip-firing graph with multiple edges possible between vertices.

Example

>>> vertices = {"A", "B", "C"}
>>> edges = [("A", "B", 2), ("B", "C", 1)]
>>> graph = CFGraph(vertices, edges)
>>> len(graph.vertices)
3
>>> graph.total_valence  # 2 edges A-B, 1 edge B-C
3
>>> graph.get_valence("A")
2
>>> graph.get_valence("B")  # 2 from A-B, 1 from B-C
3
>>> graph.get_valence("C")
1

__init__(vertices: Set[str], edges: List[Tuple[str, str, int]])

Initialize the graph with a set of vertex names and a list of edge tuples.

Parameters:

• vertices – Set of vertex names (strings)

• edges – List of tuples (v1_name, v2_name, valence) where v1_name and v2_name are strings and valence is a positive integer representing the number of edges between the vertices

Raises:

ValueError – If duplicate vertex names are provided

Example

>>> vertices = {"A", "B", "C"}
>>> edges = [("A", "B", 2), ("B", "C", 1)]
>>> graph = CFGraph(vertices, edges)
>>> # Check we have the expected number of vertices
>>> len(graph.vertices)
3
>>> # Check the total valence (number of edges)
>>> graph.total_valence
3
>>> # With duplicate edges, valences are merged
>>> edges_with_dup = [("A", "B", 2), ("A", "B", 3)]
>>> with_dup_graph = CFGraph(vertices, edges_with_dup)  # Issues warning
>>> with_dup_graph.graph[Vertex("A")][Vertex("B")]
5

is_loopless(v1_name: str, v2_name: str) → bool

Check if an edge connects a vertex to itself.

Parameters:

• v1_name – Name of first vertex

• v2_name – Name of second vertex

Returns:

True if v1_name != v2_name (not a self-loop), False otherwise

Example

>>> vertices = {"A", "B"}
>>> graph = CFGraph(vertices, [])
>>> graph.is_loopless("A", "B")  # Different vertices
True
>>> graph.is_loopless("A", "A")  # Same vertex (self-loop)
False

add_edges(edges: List[Tuple[str, str, int]]) → None

Add multiple edges to the graph.

Parameters:

edges – List of tuples (v1_name, v2_name, valence) where v1_name and v2_name are strings and valence is a positive integer representing the number of edges between the vertices

Example

>>> vertices = {"A", "B", "C"}
>>> graph = CFGraph(vertices, [])
>>> graph.add_edges([("A", "B", 2), ("B", "C", 1), ("A", "C", 3)])
>>> graph.graph[Vertex("A")][Vertex("B")]
2
>>> graph.graph[Vertex("B")][Vertex("C")]
1
>>> graph.graph[Vertex("A")][Vertex("C")]
3
>>> # With duplicate edges, a warning is issued
>>> graph.add_edges([("A", "B", 3)])  # Issues warning
>>> graph.graph[Vertex("A")][Vertex("B")]  # 2 + 3 = 5
5

add_edge(v1_name: str, v2_name: str, valence: int) → None

Add edges between vertices with names v1_name and v2_name.

Parameters:

• v1_name – Name of first vertex

• v2_name – Name of second vertex

• valence – Number of edges to add between the vertices

Raises:

• ValueError – If trying to add a self-loop

• ValueError – If valence is not positive

• ValueError – If either vertex is not in the graph

Example

>>> vertices = {"A", "B", "C"}
>>> graph = CFGraph(vertices, [])
>>> # Add a single edge with valence 2
>>> graph.add_edge("A", "B", 2)
>>> graph.graph[Vertex("A")][Vertex("B")]
2
>>> graph.graph[Vertex("B")][Vertex("A")]  # Undirected graph
2
>>> # Adding to an existing edge increases valence
>>> graph.add_edge("A", "B", 3)
>>> graph.graph[Vertex("A")][Vertex("B")]  # 2 + 3 = 5
5
>>> # Invalid operations
>>> try:
...     graph.add_edge("A", "A", 1)  # Self-loop
... except ValueError:
...     print("Self-loops not allowed")
Self-loops not allowed
>>> try:
...     graph.add_edge("A", "D", 1)  # D not in graph
... except ValueError:
...     print("Vertex not in graph")
Vertex not in graph

get_valence(v_name: str) → int

Get the total valence (sum of all edge valences) for a vertex.

Parameters:

v_name – Name of the vertex

Returns:

The total valence of the vertex

Raises:

ValueError – If the vertex is not in the graph

Example

>>> vertices = {"A", "B", "C"}
>>> edges = [("A", "B", 2), ("B", "C", 1), ("A", "C", 3)]
>>> graph = CFGraph(vertices, edges)
>>> graph.get_valence("A")  # 2 from A-B, 3 from A-C
5
>>> graph.get_valence("B")  # 2 from A-B, 1 from B-C
3
>>> graph.get_valence("C")  # 1 from B-C, 3 from A-C
4
>>> try:
...     graph.get_valence("D")  # D not in graph
... except ValueError:
...     print("Vertex not in graph")
Vertex not in graph

get_genus() → int

Get the genus of the graph, which is defined as E - V + 1.

Returns:

The genus of the graph

Example

>>> vertices = {"A", "B", "C"}
>>> edges = [("A", "B", 2), ("B", "C", 1), ("A", "C", 1)]
>>> graph = CFGraph(vertices, edges)
>>> # Total edges = 4, Vertices = 3
>>> # Genus = |E| - |V| + 1 = 4 - 3 + 1 = 2
>>> graph.get_genus()
2

remove_vertex(vertex_name: str) → CFGraph

Create a copy of the graph without the specified vertex.

Parameters:

vertex_name – The name of the vertex to remove

Returns:

A new CFGraph object without the specified vertex

Raises:

ValueError – If the vertex name is not found in the graph

Example

>>> vertices = {"A", "B", "C", "D"}
>>> edges = [("A", "B", 2), ("B", "C", 1), ("C", "D", 3), ("A", "D", 2)]
>>> graph = CFGraph(vertices, edges)
>>> # Remove vertex C
>>> new_graph = graph.remove_vertex("C")
>>> # Check the new graph has the correct vertices
>>> len(new_graph.vertices)
3
>>> # Check edges are preserved correctly
>>> new_graph.graph[Vertex("A")][Vertex("B")]
2
>>> new_graph.graph[Vertex("A")][Vertex("D")]
2
>>> # Check valences
>>> new_graph.get_valence("A")  # 2 from A-B, 2 from A-D
4
>>> new_graph.get_valence("B")  # 2 from A-B
2
>>> new_graph.get_valence("D")  # 2 from A-D
2

classmethod from_dict(data: Dict[str, Any]) → CFGraph

Creates a CFGraph instance from a dictionary representation.

Parameters:

data – A dictionary with ‘vertices’ (list of names) and ‘edges’ (list of [v1_name, v2_name, valence] tuples).

Returns:

A CFGraph instance.

to_dict() → Dict[str, Any]

Converts the CFGraph instance to a dictionary representation.

Returns:

A dictionary with ‘vertices’ and ‘edges’.

get_vertex_by_name(name: str) → Vertex | None

Find a vertex in the graph by its name.