Graph Module
- class chipfiring.CFGraph.Vertex(name: str)[source]
Bases:
objectRepresents 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
- class chipfiring.CFGraph.Edge(v1: Vertex, v2: Vertex)[source]
Bases:
objectRepresents 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
- class chipfiring.CFGraph.CFGraph(vertices: Set[str], edges: List[Tuple[str, str, int]])[source]
Bases:
objectRepresents 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:
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[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.