Graph Module

class chipfiring.CFGraph.Vertex(name: str)[source]

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)[source]
class chipfiring.CFGraph.Edge(v1: Vertex, v2: Vertex)[source]

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
True
>>> str(e1)
'A-B'
>>> edge_set = {e1, e2, e3}  # e1 and e2 are considered equal
>>> len(edge_set)
2
__init__(v1: Vertex, v2: Vertex)[source]
class chipfiring.CFGraph.CFGraph(vertices: Set[str], edges: List[Tuple[str, str, int]])[source]

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]])[source]

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
__eq__(other) → bool[source]

Return whether two graphs are the same labeled multigraph.

Two graphs are equal when they have the same vertex names and the same edge multiplicity between every pair of vertices. Equality is structural, so independently constructed or deserialized graphs compare equal; the two objects need not be the same instance.

Example

>>> first = CFGraph({"A", "B", "C"}, [("A", "B", 2), ("B", "C", 1)])
>>> second = CFGraph({"A", "B", "C"}, [("B", "C", 1), ("A", "B", 2)])
>>> first == second
True
>>> first is second
False
>>> first == CFGraph({"A", "B", "C"}, [("A", "B", 1), ("B", "C", 1)])
False
>>> first == CFGraph({"A", "B"}, [("A", "B", 2)])
False
__hash__() → int[source]

Hash on the vertex set, which is fixed once a graph is constructed.

Equal graphs share a vertex set, so equal graphs hash equally. Edges may still be added after construction; keying on the vertex set keeps the hash stable across those additions.

is_connected() → bool[source]

Return whether every vertex is reachable from every other vertex.

Empty and single-vertex graphs are connected by convention.

Example

>>> connected = CFGraph({"a", "b"}, [("a", "b", 1)])
>>> connected.is_connected()
True
>>> disconnected = CFGraph({"a", "b"}, [])
>>> disconnected.is_connected()
False
is_loopless(v1_name: str, v2_name: str) → bool[source]

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[source]

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[source]

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:

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[source]

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[source]

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[source]

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[source]

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][source]

Converts the CFGraph instance to a dictionary representation.

Returns:

A dictionary with ‘vertices’ and ‘edges’.

get_vertex_by_name(name: str) → Vertex | None[source]

Find a vertex in the graph by its name.