Orientation Module

class chipfiring.CFOrientation.OrientationState(value)

Bases: Enum

Represents the possible states of an edge orientation.

NO_ORIENTATION = 0

SOURCE_TO_SINK = 1

SINK_TO_SOURCE = 2

class chipfiring.CFOrientation.CFOrientation(graph: CFGraph, orientations: List[Tuple[str, str]])

Bases: object

Represents an orientation of edges in a chip-firing graph.

__init__(graph: CFGraph, orientations: List[Tuple[str, str]])

Initialize the orientation with a graph and list of oriented edges.

Parameters:

• graph – A CFGraph object representing the underlying graph

• orientations – List of tuples (source_name, sink_name) where source_name and sink_name are strings representing vertex names. Each tuple indicates that the edge is oriented from source to sink.

Raises:

• ValueError – If an edge specified in orientations does not exist in the graph

• ValueError – If multiple orientations are specified for the same edge

Example

>>> vertices = {"A", "B", "C"}
>>> edges = [("A", "B", 2), ("B", "C", 1), ("A", "C", 1)]
>>> graph = CFGraph(vertices, edges)
>>> orientations = [("A", "B"), ("B", "C")]
>>> orientation = CFOrientation(graph, orientations)

check_fullness() → bool

Check if all edges have an orientation and update is_full.

Returns:

True if all edges have an orientation, False otherwise

Example

>>> vertices = {"v1", "v2", "v3"}
>>> edges = [("v1", "v2", 1), ("v2", "v3", 1), ("v1", "v3", 1)]
>>> graph = CFGraph(vertices, edges)
>>> orientation = CFOrientation(graph, [("v1", "v2")])
>>> orientation.check_fullness()
False
>>> # Now complete the orientation
>>> from chipfiring.CFOrientation import Vertex, OrientationState
>>> v2, v3 = Vertex("v2"), Vertex("v3")
>>> orientation.set_orientation(v2, v3, OrientationState.SOURCE_TO_SINK)
>>> v1, v3 = Vertex("v1"), Vertex("v3")
>>> orientation.set_orientation(v1, v3, OrientationState.SOURCE_TO_SINK)
>>> orientation.check_fullness()
True

set_orientation(source: Vertex, sink: Vertex, state: OrientationState) → None

Helper method to set orientation and update in/out degrees.

Parameters:

• source – Source vertex

• sink – Sink vertex

• state – New orientation state

Example

>>> vertices = {"A", "B", "C"}
>>> edges = [("A", "B", 2), ("B", "C", 1), ("A", "C", 1)]
>>> graph = CFGraph(vertices, edges)
>>> orientation = CFOrientation(graph, [])
>>> from chipfiring.CFOrientation import OrientationState, Vertex
>>> v_a = Vertex("A")
>>> v_b = Vertex("B")
>>> orientation.set_orientation(v_a, v_b, OrientationState.SOURCE_TO_SINK)
>>> orientation.get_out_degree("A")
2  # A-B edge has valence 2
>>> orientation.get_in_degree("B")
2

get_orientation(v1_name: str, v2_name: str) → Tuple[str, str] | None

Get the orientation of an edge between two vertices.

Parameters:

• v1_name – Name of first vertex

• v2_name – Name of second vertex

Returns:

Tuple (source_name, sink_name) indicating the orientation, or None if the edge exists but has no orientation

Raises:

ValueError – If the edge does not exist

Example

>>> vertices = {"v1", "v2", "v3"}
>>> edges = [("v1", "v2", 1), ("v2", "v3", 1), ("v1", "v3", 1)]
>>> graph = CFGraph(vertices, edges)
>>> orientations = [("v1", "v2"), ("v2", "v3"), ("v1", "v3")]
>>> orientation = CFOrientation(graph, orientations)
>>> orientation.get_orientation("v1", "v2")
('v1', 'v2')
>>> orientation.get_orientation("v2", "v1")  # Order doesn't matter
('v1', 'v2')
>>> # For a partially oriented graph:
>>> partial = CFOrientation(graph, [("v1", "v2")])
>>> partial.get_orientation("v1", "v2")
('v1', 'v2')
>>> partial.get_orientation("v2", "v3")
None

is_source(vertex_name: str, neighbor_name: str) → bool | None

Check if a vertex is the source of an oriented edge.

Parameters:

• vertex_name – Name of the vertex to check

• neighbor_name – Name of the neighboring vertex

Returns:

True if the vertex is the source of the edge, False if the vertex is the sink of the edge, None if the edge exists but has no orientation

Raises:

ValueError – If the edge does not exist

Example

>>> vertices = {"v1", "v2", "v3"}
>>> edges = [("v1", "v2", 1), ("v2", "v3", 1), ("v1", "v3", 1)]
>>> graph = CFGraph(vertices, edges)
>>> orientations = [("v1", "v2"), ("v2", "v3"), ("v1", "v3")]
>>> orientation = CFOrientation(graph, orientations)
>>> orientation.is_source("v1", "v2")
True
>>> orientation.is_source("v2", "v1")
False
>>> # For an unoriented edge
>>> partial = CFOrientation(graph, [("v1", "v2")])
>>> partial.is_source("v2", "v3")
None

is_sink(vertex_name: str, neighbor_name: str) → bool | None

Check if a vertex is the sink of an oriented edge.

Parameters:

• vertex_name – Name of the vertex to check

• neighbor_name – Name of the neighboring vertex

Returns:

True if the vertex is the sink of the edge, False if the vertex is the source of the edge, None if the edge exists but has no orientation

Raises:

ValueError – If the edge does not exist

Example

>>> vertices = {"v1", "v2", "v3"}
>>> edges = [("v1", "v2", 1), ("v2", "v3", 1), ("v1", "v3", 1)]
>>> graph = CFGraph(vertices, edges)
>>> orientations = [("v1", "v2"), ("v2", "v3"), ("v1", "v3")]
>>> orientation = CFOrientation(graph, orientations)
>>> orientation.is_sink("v1", "v2")
False
>>> orientation.is_sink("v2", "v1")
True
>>> # For an unoriented edge
>>> partial = CFOrientation(graph, [("v1", "v2")])
>>> partial.is_sink("v2", "v3")
None

get_in_degree(vertex_name: str) → int

Get the in-degree of a vertex, which is the sum of valences of edges oriented into the vertex.

Parameters:

vertex_name – Name of the vertex to get the in-degree for

Returns:

The in-degree of the vertex

Raises:

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

Example

>>> vertices = {"v1", "v2", "v3"}
>>> edges = [("v1", "v2", 1), ("v2", "v3", 1), ("v1", "v3", 1)]
>>> graph = CFGraph(vertices, edges)
>>> orientations = [("v1", "v2"), ("v2", "v3"), ("v1", "v3")]
>>> orientation = CFOrientation(graph, orientations)
>>> orientation.get_in_degree("v1")
0
>>> orientation.get_in_degree("v2")
1  # from v1
>>> orientation.get_in_degree("v3")
2  # from v1, v2

get_out_degree(vertex_name: str) → int

Get the out-degree of a vertex, which is the sum of valences of edges oriented out of the vertex.

Parameters:

vertex_name – Name of the vertex to get the out-degree for

Returns:

The out-degree of the vertex

Raises:

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

Example

>>> vertices = {"v1", "v2", "v3"}
>>> edges = [("v1", "v2", 1), ("v2", "v3", 1), ("v1", "v3", 1)]
>>> graph = CFGraph(vertices, edges)
>>> orientations = [("v1", "v2"), ("v2", "v3"), ("v1", "v3")]
>>> orientation = CFOrientation(graph, orientations)
>>> orientation.get_out_degree("v1")
2
>>> orientation.get_out_degree("v2")
1  # to v3
>>> orientation.get_out_degree("v3")
0

reverse() → CFOrientation

Return a new CFOrientation object with all edge orientations reversed.

Raises:

RuntimeError – If the current orientation is not full (i.e., contains unoriented edges).

Returns:

A new CFOrientation object representing the reversed orientation.

Example

>>> vertices = {"v1", "v2", "v3"}
>>> edges = [("v1", "v2", 1), ("v2", "v3", 1), ("v1", "v3", 1)]
>>> graph = CFGraph(vertices, edges)
>>> orientations = [("v1", "v2"), ("v2", "v3"), ("v1", "v3")]
>>> orientation = CFOrientation(graph, orientations)
>>> reversed_orientation = orientation.reverse()
>>> reversed_orientation.get_orientation("v1", "v2")
('v2', 'v1')
>>> reversed_orientation.get_orientation("v2", "v3")
('v3', 'v2')
>>> reversed_orientation.get_orientation("v1", "v3")
('v3', 'v1')

divisor() → CFDivisor

Returns the divisor associated with the orientation; by definition, for each vertex v, the degree of v in the divisor is the in-degree of v in the orientation minus 1.

Raises:

RuntimeError – If the current orientation is not full (i.e., contains unoriented edges).

Returns:

A new CFDivisor object representing the calculated divisor.

Example

>>> vertices = {"v1", "v2", "v3"}
>>> edges = [("v1", "v2", 1), ("v2", "v3", 1), ("v1", "v3", 1)]
>>> graph = CFGraph(vertices, edges)
>>> orientations = [("v1", "v2"), ("v2", "v3"), ("v1", "v3")]
>>> orientation = CFOrientation(graph, orientations)
>>> div = orientation.divisor()
>>> div.get_degree("v1")
-1  # in-degree 0 - 1
>>> div.get_degree("v2")
0   # in-degree 1 - 1
>>> div.get_degree("v3")
1   # in-degree 2 - 1

canonical_divisor() → CFDivisor

Returns the canonical divisor associated with the graph; by definition, the canonical divisor of an orientation is equal to the divisor of the orientation plus the divisor of the reverse of the orientation. After simplifying, we get that for each vertex v, the degree of v in the canonical divisor is the valence of v minus 2.

Returns:

A new CFDivisor object representing the canonical divisor.

Example

>>> vertices = {"a", "b", "c"}
>>> edges = [("a", "b", 2), ("b", "c", 3)]  # Multi-graph
>>> graph = CFGraph(vertices, edges)
>>> orientation = CFOrientation(graph, [])  # Orientation doesn't matter
>>> canonical = orientation.canonical_divisor()
>>> canonical.get_degree("a")
0   # valence 2 - 2
>>> canonical.get_degree("b")
3   # valence 5 - 2
>>> canonical.get_degree("c")
1   # valence 3 - 2

to_dict() → Dict[str, Any]

Converts the CFOrientation instance to a dictionary representation.

Returns:

A dictionary with ‘graph’ and ‘orientations’.

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

Creates a CFOrientation instance from a dictionary representation.

Parameters:

data – A dictionary with ‘graph’ (CFGraph representation) and ‘orientations’ (list of [source_name, sink_name] tuples).

Returns:

A CFOrientation instance.