Skip to content

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

pbcgraph.alg.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).