Canonical lift¶

canonical_lift(...) selects exactly one lifted instance for every quotient node in a PeriodicComponent, producing a deterministic finite representation of a single strand (a connected component of the infinite lift).

In v0.1.2 you can choose between three placement modes:

• placement='tree': place the deterministic spanning tree with a chosen anchor
• placement='best_anchor': try all valid anchors and pick the best score
• placement='greedy_cut': locally improve the score while preserving connectivity

In [1]:

from pprint import pprint

from pbcgraph import PeriodicDiGraph

from pprint import pprint from pbcgraph import PeriodicDiGraph

Helper: inspect a canonical lift¶

In [2]:

def summarize_canon(component, out):
    print('placement:', out.placement)
    print('score:', out.score)
    print('strand_key:', out.strand_key)
    print('anchor_site:', out.anchor_site)
    print('anchor_shift:', out.anchor_shift)
    print('\nnodes (u, shift):')
    pprint(list(out.nodes))
    print('\nall nodes are in the target strand:', all(
        component.inst_key((u, s)) == out.strand_key for u, s in out.nodes
    ))
    if out.tree_edges is not None:
        print('\ntree edges (parent, child, tvec, key):')
        pprint(list(out.tree_edges))

def summarize_canon(component, out): print('placement:', out.placement) print('score:', out.score) print('strand_key:', out.strand_key) print('anchor_site:', out.anchor_site) print('anchor_shift:', out.anchor_shift) print('\nnodes (u, shift):') pprint(list(out.nodes)) print('\nall nodes are in the target strand:', all( component.inst_key((u, s)) == out.strand_key for u, s in out.nodes )) if out.tree_edges is not None: print('\ntree edges (parent, child, tvec, key):') pprint(list(out.tree_edges))

1) Tree placement and tree_edges¶

This is a small 1D quotient with a periodic cycle. We request return_tree=True to see the spanning-tree edges used to compute potentials.

In [3]:

G = PeriodicDiGraph(dim=1)
G.add_edge('A', 'B', (0,))
G.add_edge('B', 'C', (0,))
G.add_edge('C', 'A', (1,))

c = G.components()[0]
out_tree = c.canonical_lift(seed=('B', (0,)), anchor_shift=(0,), return_tree=True)
summarize_canon(c, out_tree)

G = PeriodicDiGraph(dim=1) G.add_edge('A', 'B', (0,)) G.add_edge('B', 'C', (0,)) G.add_edge('C', 'A', (1,)) c = G.components()[0] out_tree = c.canonical_lift(seed=('B', (0,)), anchor_shift=(0,), return_tree=True) summarize_canon(c, out_tree)

placement: tree
score: 1
strand_key: ()
anchor_site: A
anchor_shift: (0,)

nodes (u, shift):
[('A', (0,)), ('B', (0,)), ('C', (-1,))]

all nodes are in the target strand: True

tree edges (parent, child, tvec, key):
[('A', 'B', (0,), 0), ('A', 'C', (-1,), 0)]

2) best_anchor: same strand, better score¶

Here we intentionally make deterministic potentials very unbalanced. best_anchor tries all anchors that exist in the requested strand inside the anchor cell and chooses the one that minimizes the score.

In [4]:

H = PeriodicDiGraph(dim=1)
H.add_edge('A', 'B', (2,))
H.add_edge('B', 'C', (98,))
H.add_edge('C', 'A', (-99,))  # cycle generator = 1 -> L = Z

c2 = H.components()[0]
out_tree2 = c2.canonical_lift(anchor_shift=(0,), placement='tree', score='l1')
out_best2 = c2.canonical_lift(anchor_shift=(0,), placement='best_anchor', score='l1')

summarize_canon(c2, out_tree2)
print('\n---')
summarize_canon(c2, out_best2)
print('\nbest_anchor improves score:', out_best2.score < out_tree2.score)

H = PeriodicDiGraph(dim=1) H.add_edge('A', 'B', (2,)) H.add_edge('B', 'C', (98,)) H.add_edge('C', 'A', (-99,)) # cycle generator = 1 -> L = Z c2 = H.components()[0] out_tree2 = c2.canonical_lift(anchor_shift=(0,), placement='tree', score='l1') out_best2 = c2.canonical_lift(anchor_shift=(0,), placement='best_anchor', score='l1') summarize_canon(c2, out_tree2) print('\n---') summarize_canon(c2, out_best2) print('\nbest_anchor improves score:', out_best2.score < out_tree2.score)

placement: tree
score: 101
strand_key: ()
anchor_site: A
anchor_shift: (0,)

nodes (u, shift):
[('A', (0,)), ('B', (2,)), ('C', (99,))]

all nodes are in the target strand: True

---
placement: best_anchor
score: 99
strand_key: ()
anchor_site: B
anchor_shift: (0,)

nodes (u, shift):
[('A', (-2,)), ('B', (0,)), ('C', (97,))]

all nodes are in the target strand: True

best_anchor improves score: True

3) greedy_cut: local improvement beyond best_anchor¶

This example has two distinct quotient edges between C and A. The deterministic spanning tree picks one of them, but greedy_cut can locally switch to the alternative periodic relation and reduce the score while keeping the induced internal graph connected.

In [5]:

K = PeriodicDiGraph(dim=1)
K.add_edge('A', 'B', (2,))
K.add_edge('B', 'C', (98,))
K.add_edge('C', 'A', (-100,))
K.add_edge('C', 'A', (-99,))

c3 = K.components()[0]
out_best3 = c3.canonical_lift(anchor_shift=(0,), placement='best_anchor', score='l1')
out_greedy3 = c3.canonical_lift(anchor_shift=(0,), placement='greedy_cut', score='l1')

summarize_canon(c3, out_best3)
print('\n---')
summarize_canon(c3, out_greedy3)
print('\ngreedy_cut improves score:', out_greedy3.score < out_best3.score)

K = PeriodicDiGraph(dim=1) K.add_edge('A', 'B', (2,)) K.add_edge('B', 'C', (98,)) K.add_edge('C', 'A', (-100,)) K.add_edge('C', 'A', (-99,)) c3 = K.components()[0] out_best3 = c3.canonical_lift(anchor_shift=(0,), placement='best_anchor', score='l1') out_greedy3 = c3.canonical_lift(anchor_shift=(0,), placement='greedy_cut', score='l1') summarize_canon(c3, out_best3) print('\n---') summarize_canon(c3, out_greedy3) print('\ngreedy_cut improves score:', out_greedy3.score < out_best3.score)

placement: best_anchor
score: 100
strand_key: ()
anchor_site: B
anchor_shift: (0,)

nodes (u, shift):
[('A', (-2,)), ('B', (0,)), ('C', (98,))]

all nodes are in the target strand: True

---
placement: greedy_cut
score: 99
strand_key: ()
anchor_site: B
anchor_shift: (0,)

nodes (u, shift):
[('A', (-1,)), ('B', (0,)), ('C', (98,))]

all nodes are in the target strand: True

greedy_cut improves score: True

4) Strand keys and the "strand absent in the anchor cell" error¶

If the translation subgroup is a proper sublattice of Z^d, the infinite lift splits into multiple disconnected strands (torsion / interpenetration).

In this case, a requested strand_key might have no representatives in the anchor cell. Then canonical_lift raises CanonicalLiftError.

In [6]:

from pbcgraph.core.exceptions import CanonicalLiftError

T = PeriodicDiGraph(dim=1)
T.add_edge('A', 'A', (2,))  # L = 2Z -> torsion 2 (even/odd strands)

c4 = T.components()[0]
print('torsion invariants:', c4.torsion_invariants)

k0 = c4.inst_key(('A', (0,)))
k1 = c4.inst_key(('A', (1,)))
print('strand key at A@(0):', k0)
print('strand key at A@(1):', k1)

try:
    c4.canonical_lift(strand_key=k1, anchor_shift=(0,))
except CanonicalLiftError as e:
    print('expected error:', e)

# Fix: choose an anchor cell that actually contains the strand.
out_fix = c4.canonical_lift(strand_key=k1, anchor_shift=(1,))
summarize_canon(c4, out_fix)

from pbcgraph.core.exceptions import CanonicalLiftError T = PeriodicDiGraph(dim=1) T.add_edge('A', 'A', (2,)) # L = 2Z -> torsion 2 (even/odd strands) c4 = T.components()[0] print('torsion invariants:', c4.torsion_invariants) k0 = c4.inst_key(('A', (0,))) k1 = c4.inst_key(('A', (1,))) print('strand key at A@(0):', k0) print('strand key at A@(1):', k1) try: c4.canonical_lift(strand_key=k1, anchor_shift=(0,)) except CanonicalLiftError as e: print('expected error:', e) # Fix: choose an anchor cell that actually contains the strand. out_fix = c4.canonical_lift(strand_key=k1, anchor_shift=(1,)) summarize_canon(c4, out_fix)

torsion invariants: (2,)
strand key at A@(0): (0,)
strand key at A@(1): (1,)
expected error: requested strand_key does not intersect the anchor cell
placement: tree
score: 0
strand_key: (1,)
anchor_site: A
anchor_shift: (1,)

nodes (u, shift):
[('A', (1,))]

all nodes are in the target strand: True