Algorithms

Paths

pbcgraph.alg.paths.shortest_path_quotient

shortest_path_quotient(
    G: PeriodicDiGraphLike,
    source: NodeId,
    target: NodeId,
    *,
    connectivity: Optional[Connectivity] = None,
) -> List[NodeId]

Shortest path in the quotient graph (BFS).

Parameters:

Name	Type	Description	Default
G	PeriodicDiGraphLike	A periodic graph container (structural protocol).	required
source	NodeId	Source quotient node id.	required
target	NodeId	Target quotient node id.	required
connectivity	Optional[Connectivity]	Connectivity mode: - None: container-dependent default * is_undirected=False -> 'directed' * is_undirected=True -> 'weak' - 'directed': respect edge directions (successors only). - 'weak': ignore directions (successors plus predecessors).	None

Returns:

Type	Description
List[NodeId]	A list of quotient node ids (including source and target).

Raises:

Type	Description
ValueError	If no path exists, or if an invalid connectivity is requested.
KeyError	If source or target is not in the graph.

Components

pbcgraph.alg.components.components

components(
    G: PeriodicDiGraphLike,
) -> List[PeriodicComponent]

Return PeriodicComponent objects for each quotient component.

Notes

• For undirected containers (is_undirected=True): components are the usual undirected components (the container stores both directions per undirected edge).
• For directed containers: v0.1 uses weak connectivity (direction ignored).

Parameters:

Name	Type	Description	Default
G	PeriodicDiGraphLike	A periodic graph container (structural protocol).	required

Returns:

Type	Description
List[PeriodicComponent]	List of PeriodicComponent objects in deterministic order.
List[PeriodicComponent]	The order follows the graph's deterministic node iteration
List[PeriodicComponent]	(G.nodes(...)), so the first component is the one containing the
List[PeriodicComponent]	smallest node under the container's stable ordering.

Lifts

pbcgraph.alg.lift.lift_patch

lift_patch(
    G: PeriodicDiGraphLike,
    seed: NodeInst,
    *,
    radius: Optional[int] = None,
    box: Optional[Tuple[Tuple[int, int], ...]] = None,
    box_rel: Optional[Tuple[Tuple[int, int], ...]] = None,
    include_edges: bool = True,
    max_nodes: Optional[int] = None,
    node_order: Optional[Callable[[NodeInst], Any]] = None,
    edge_order: Optional[
        Callable[[Tuple[Any, ...]], Any]
    ] = None,
) -> LiftPatch

Extract a finite patch of the lifted graph around a seed.

The traversal uses weak connectivity in the infinite lift: from an instance it considers both outgoing and incoming quotient edges.

Notes

The returned patch is directed if G.is_undirected == False, and undirected otherwise. Use LiftPatch.to_networkx(as_undirected=True, ...) to obtain undirected views of directed patches.

Parameters:

Name	Type	Description	Default
G	PeriodicDiGraphLike	A periodic graph container.	required
seed	NodeInst	Seed instance (u, shift).	required
radius	Optional[int]	Optional BFS radius in the lifted graph.	None
box	Optional[Tuple[Tuple[int, int], ...]]	Optional absolute half-open bounds per coordinate.	None
box_rel	Optional[Tuple[Tuple[int, int], ...]]	Optional bounds relative to seed.shift.	None
include_edges	bool	Whether to include edges between included nodes.	True
max_nodes	Optional[int]	If provided, raise if the patch would include more than max_nodes nodes.	None
node_order	Optional[Callable[[NodeInst], Any]]	Optional key function for ordering node instances.	None
edge_order	Optional[Callable[[Tuple[Any, ...]], Any]]	Optional key function for ordering edge records.	None

Returns:

Name	Type	Description
A	LiftPatch	class:~pbcgraph.alg.lift.LiftPatch.

Raises:

Type	Description
LiftPatchError	On invalid inputs or if max_nodes is exceeded.

pbcgraph.alg.lift.LiftPatch dataclass

A finite patch extracted from the infinite lift.

Attributes:

Name	Type	Description
nodes	Tuple[NodeInst, ...]	Node instances (u, shift) in canonical order.
edges	Tuple[Union[PatchEdgeRec, PatchMultiEdgeRec], ...]	Edges between included node instances. For simple containers: (u_inst, v_inst, attrs). For multigraph containers: (u_inst, v_inst, key, attrs). For directed patches, (u_inst, v_inst) is ordered. For undirected patches, endpoints are in canonical order.
seed	NodeInst	Seed node instance.
radius	Optional[int]	BFS radius in the lifted graph (weak connectivity), if used.
box	Optional[Tuple[Tuple[int, int], ...]]	Effective absolute box constraint after intersection, if used.

is_multigraph property

is_multigraph: bool

Whether the patch edges include keys.

is_directed property

is_directed: bool

Whether the patch edges are directed.

to_networkx

to_networkx(
    *,
    as_undirected: Optional[bool] = None,
    undirected_mode: Literal[
        "multigraph", "orig_edges"
    ] = "multigraph",
) -> Union[
    nx.Graph, nx.DiGraph, nx.MultiGraph, nx.MultiDiGraph
]

Export the patch as a NetworkX graph.

Notes

• By default, directed patches export as directed NetworkX graphs, and undirected patches export as undirected.
• For directed patches, as_undirected=True provides an undirected view:
  • undirected_mode='multigraph' returns a MultiGraph where each directed edge becomes a distinct undirected multiedge, with direction metadata stored under the __pbcgraph__ edge attribute.
  • undirected_mode='orig_edges' returns a simple Graph where each undirected adjacency stores orig_edges=[...] snapshots under the __pbcgraph__ edge attribute.

pbcgraph.alg.lift.canonical_lift

canonical_lift(
    component: Any,
    *,
    strand_key: Optional[Hashable] = None,
    seed: Optional[NodeInst] = None,
    anchor_shift: Optional[TVec] = None,
    placement: Literal[
        "tree", "best_anchor", "greedy_cut"
    ] = "tree",
    score: Literal["l1", "l2"] = "l1",
    return_tree: bool = False,
    node_order: Optional[Callable[[NodeId], Any]] = None,
    edge_order: Optional[
        Callable[[Tuple[Any, ...]], Any]
    ] = None,
) -> CanonicalLift

Construct a deterministic finite representation of one strand.

v0.1.2 step4 implements placement='tree', placement='best_anchor', and placement='greedy_cut'.

Parameters:

Name	Type	Description	Default
component	Any	A :class:~pbcgraph.component.PeriodicComponent.	required
strand_key	Optional[Hashable]	Optional explicit strand key.	None
seed	Optional[NodeInst]	Optional seed instance (u, shift).	None
anchor_shift	Optional[TVec]	Optional anchor cell shift.	None
placement	Literal['tree', 'best_anchor', 'greedy_cut']	Placement mode ('tree' in step2).	'tree'
score	Literal['l1', 'l2']	Score metric: 'l1' or 'l2'.	'l1'
return_tree	bool	If True, include spanning-tree edge records.	False
node_order	Optional[Callable[[NodeId], Any]]	Optional ordering key for quotient node ids.	None
edge_order	Optional[Callable[[Tuple[Any, ...]], Any]]	Optional ordering key for periodic edges (reserved).	None

Returns:

Name	Type	Description
A	CanonicalLift	class:~pbcgraph.alg.lift.CanonicalLift.

Raises:

Type	Description
CanonicalLiftError	On invalid inputs or if the requested strand does not intersect the anchor cell.

pbcgraph.alg.lift.CanonicalLift dataclass

A deterministic finite representation of a single strand.

Attributes:

Name	Type	Description
nodes	Tuple[NodeInst, ...]	Node instances (u, shift) in canonical order. Contains exactly one instance for every quotient node in the component.
strand_key	Hashable	Target strand (coset) key in Z^d / L.
anchor_site	NodeId	Quotient node chosen to be placed in anchor_shift.
anchor_shift	TVec	Anchor cell translation vector.
placement	str	Placement mode used to construct the lift.
score	Union[int, float]	Placement score (smaller is better; 0 is best).
tree_edges	Optional[Tuple[TreeEdgeRec, ...]]	Optional spanning-tree edge records for debugging.

Lattice utilities

The canonical imports are in pbcgraph.lattice. Existing imports through pbcgraph.alg and pbcgraph.alg.lattice refer to the same factory and class.

pbcgraph.lattice.snf_decomposition

snf_decomposition(
    generators: Sequence[TVec], dim: int
) -> SNFDecomposition

Compute SNF decomposition for the sublattice generated by generators.

Parameters:

Name	Type	Description	Default
generators	Sequence[TVec]	Translation vectors generating L (as a Z-span).	required
dim	int	Ambient lattice dimension.	required

Returns:

Type	Description
SNFDecomposition	SNFDecomposition with U, U_inv, diag, and rank.

Notes

Generators are treated as columns of a matrix M (d x k).

pbcgraph.lattice.SNFDecomposition dataclass

Smith Normal Form decomposition for a sublattice L subset Z^d.

Attributes:

Name	Type	Description
dim	int	Ambient lattice dimension d.
rank	int	Rank of the sublattice L (number of non-zero diagonal entries).
diag	Tuple[int, ...]	Tuple of length rank with the (non-zero) SNF diagonal entries (invariant factors). Empty tuple if there are no generators.
U	Tuple[Tuple[int, ...], ...]	Unimodular change-of-basis matrix (left transform).
U_inv	Tuple[Tuple[int, ...], ...]	Inverse of U over the integers.

Notes

Use snf_decomposition to obtain a valid decomposition. The frozen dataclass constructor does not validate or certify arbitrary values of U, diag, or U_inv; the methods assume a valid decomposition. A decomposition is detached from any graph and has no freshness guard. Dataclass equality compares fields, not embedded subgroups; use same_subgroup for the latter.

apply_U

apply_U(x: TVec) -> Tuple[int, ...]

Compute y = U * x for a column vector x.

contains

contains(vector: TVec) -> bool

Decide exact membership in the represented subgroup of Z^dim.

Parameters:

Name	Type	Description	Default
vector	TVec	A correctly sized, ordered, one-dimensional integer sequence. Tuples, lists, ranges, 1D NumPy integer arrays, object arrays of Integral values, and sequences of NumPy signed/unsigned integers are supported. Python and NumPy bools and all non-Integral entries (including floats) are rejected. Accepted coordinates are converted to Python ints before arithmetic; no rounding or flattening is performed.	required

Returns:

Type	Description
bool	A Python bool. For y = U * vector, membership requires
bool	y[i] % diag[i] == 0 for i < rank and y[i] == 0 otherwise.
bool	Rank zero contains only zero. Full rank still requires residues
bool	to vanish for nonprimitive subgroups.

Raises:

Type	Description
ValueError	If the vector has wrong length/shape or invalid entries, or is a scalar, None, unsized iterator, mapping or set. Input is validated at every rank.

same_subgroup

same_subgroup(other: SNFDecomposition) -> bool

Compare embedded integer subgroups in one ambient frame.

Parameters:

Name	Type	Description	Default
other	SNFDecomposition	Another valid decomposition in the same coordinates.	required

Returns:

Type	Description
bool	A Python bool, true exactly when both embedded subgroups agree.
bool	Rank, invariant factors, rational spans and independently chosen
bool	SNF coordinate keys alone do not establish equality. No rotation
bool	or ambient basis change is selected automatically.

Raises:

Type	Description
TypeError	If other is not an SNFDecomposition.
ValueError	If the ambient dimensions differ, including rank zero.

Notes

The vectors diag[i] * column_i(U_inv), for i < rank, generate the subgroup. Testing both bases for membership in the other subgroup proves both inclusions. No SNF or inverse is recomputed.