didericis
082ee31966
Stress-tests the iterated preprocessing algorithm on random maximal-outerplanar triangulations: terminates on n<=60 within bounded steps, occasionally hits step cap at n=80 with random edge choice. Scaffolds the user-proposed v_c-rotation algorithm and documents the monovariant findings (lexicographic depth signature is weakly but not strictly decreasing under preprocessing). Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
185 lines
6.5 KiB
Python
185 lines
6.5 KiB
Python
"""Test the user's proposed v_c rotation algorithm.
|
|
|
|
Algorithm:
|
|
1) Find edge e_0 = (v_c, v_0) between depth-d and depth-(d-1) faces.
|
|
2) List edges incident to v_c in clockwise embedding order.
|
|
3) Edge-switch each in sequence until reaching an outer-cycle edge.
|
|
|
|
Two implementations / interpretations to try:
|
|
(A) clockwise from e_0 toward one side (whichever has fewer chord edges to traverse)
|
|
(B) clockwise unconditionally, possibly going around v_c
|
|
"""
|
|
import sys, os
|
|
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
|
|
import math
|
|
import networkx as nx
|
|
from stress_test_termination import (
|
|
compute_depths, apply_switch, check_balanced, face_edges
|
|
)
|
|
|
|
|
|
def clockwise_edges_at(v, faces, chords, outer_edges, n):
|
|
"""Return all edges incident to v in clockwise order (starting at
|
|
angle 90 degrees and going to angle 0, -90, ...).
|
|
|
|
Derives the edge set from the current faces, so it works after
|
|
edge switches have changed the chord structure."""
|
|
incident = set()
|
|
for f in faces:
|
|
fe = face_edges(f)
|
|
for e in fe:
|
|
if v in e:
|
|
incident.add(e)
|
|
|
|
# Compute angle for each incident edge
|
|
def angle(e):
|
|
other = [u for u in e if u != v][0]
|
|
# Position of `other` on the polygon
|
|
a = (90 - other * 360 / n) % 360
|
|
return a
|
|
|
|
# Get edges sorted by clockwise embedding (decreasing angle from v)
|
|
# Actually since CW = decreasing angle, sort by -angle.
|
|
return sorted(incident, key=lambda e: -angle(e))
|
|
|
|
|
|
def find_edge_d_dm1(faces, depth):
|
|
d_max = max(depth.values())
|
|
for F_idx, F in enumerate(faces):
|
|
if depth[F_idx] != d_max:
|
|
continue
|
|
for e in face_edges(F):
|
|
others = [j for j in range(len(faces))
|
|
if j != F_idx and e in face_edges(faces[j])]
|
|
if others and depth[others[0]] == d_max - 1:
|
|
return F_idx, others[0], e
|
|
return None
|
|
|
|
|
|
def v_c_rotation_step(faces, chords, outer_edges, n, direction='cw'):
|
|
"""Apply the user's algorithm: find edge e_0 = (v_c, v_0), rotate
|
|
around v_c in `direction` until hitting outer edge.
|
|
|
|
Returns (new_faces, new_chords, switches_done).
|
|
"""
|
|
outer_set = {frozenset(e) for e in outer_edges}
|
|
depth = compute_depths(faces, outer_set)
|
|
if max(depth.values()) == 0:
|
|
return faces, chords, []
|
|
|
|
res = find_edge_d_dm1(faces, depth)
|
|
if res is None:
|
|
return faces, chords, []
|
|
F_idx, Fp_idx, e0 = res
|
|
F = faces[F_idx]
|
|
Fp = faces[Fp_idx]
|
|
|
|
# Pick v_c (and v_0 = the other endpoint)
|
|
u, v = tuple(e0)
|
|
# Try both choices of v_c and use the one that gives a shorter sequence
|
|
best = None
|
|
for v_c, v_0 in [(u, v), (v, u)]:
|
|
cw = clockwise_edges_at(v_c, faces, chords, outer_edges, n)
|
|
# Rotate cw so that e0 is first
|
|
e0_fs = frozenset(e0)
|
|
idx = cw.index(e0_fs)
|
|
rotated_cw = cw[idx:] + cw[:idx]
|
|
if direction == 'ccw':
|
|
# Reverse direction (but keep e0 first)
|
|
rotated_cw = [e0_fs] + list(reversed(cw[:idx] + cw[idx + 1:]))
|
|
|
|
# Sequence: switch each until we hit an outer edge
|
|
seq = []
|
|
for e in rotated_cw:
|
|
if e in outer_set:
|
|
break
|
|
seq.append(e)
|
|
if best is None or len(seq) < len(best[2]):
|
|
best = (v_c, v_0, seq)
|
|
|
|
v_c, v_0, seq = best
|
|
switches = []
|
|
cur_faces, cur_chords = list(faces), list(chords)
|
|
for e in seq:
|
|
# Find face containing F that has e as one of its edges, then third vertex
|
|
u, v = tuple(e)
|
|
# Find the two faces sharing e
|
|
sharing = [i for i, f in enumerate(cur_faces) if e in face_edges(f)]
|
|
if len(sharing) != 2:
|
|
print(f' edge {tuple(e)} has {len(sharing)} adjacent faces; skipping')
|
|
break
|
|
f1, f2 = cur_faces[sharing[0]], cur_faces[sharing[1]]
|
|
w = [vert for vert in f1 if vert not in (u, v)][0]
|
|
x = [vert for vert in f2 if vert not in (u, v)][0]
|
|
if w == x:
|
|
print(f' edge {tuple(e)} would create self-loop; skipping')
|
|
break
|
|
cur_faces = apply_switch(cur_faces, (u, v), (w, x))
|
|
switches.append((tuple(e), (w, x)))
|
|
|
|
return cur_faces, cur_chords, switches
|
|
|
|
|
|
def run_v_c_algorithm(faces, chords, outer_edges, n, max_rounds=20, verbose=True):
|
|
outer_set = {frozenset(e) for e in outer_edges}
|
|
cur = list(faces)
|
|
cur_chords = list(chords)
|
|
total = 0
|
|
for round_ in range(max_rounds):
|
|
depth = compute_depths(cur, outer_set)
|
|
d_max = max(depth.values())
|
|
if verbose:
|
|
print(f'Round {round_}: max depth = {d_max}, '
|
|
f'#faces = {len(cur)}')
|
|
if d_max == 0:
|
|
print(f'TERMINATED in {round_} rounds, {total} total switches.')
|
|
return cur, total
|
|
new_cur, new_chords, switches = v_c_rotation_step(
|
|
cur, cur_chords, outer_edges, n)
|
|
if not switches:
|
|
print(' No switches available; stuck.')
|
|
return cur, total
|
|
if verbose:
|
|
print(f' did {len(switches)} switches: {switches[:3]}'
|
|
f'{"..." if len(switches) > 3 else ""}')
|
|
cur = new_cur
|
|
cur_chords = new_chords
|
|
total += len(switches)
|
|
print(f'Hit max_rounds={max_rounds}, final max depth = '
|
|
f'{max(compute_depths(cur, outer_set).values())}')
|
|
return cur, total
|
|
|
|
|
|
if __name__ == '__main__':
|
|
# 9-vertex example
|
|
print('=== 9-vertex example ===')
|
|
n9 = 9
|
|
outer9 = [(i, (i + 1) % n9) for i in range(n9)]
|
|
chords9 = [(0, 2), (0, 3), (3, 5), (3, 6), (0, 6), (6, 8)]
|
|
faces9 = [
|
|
(0, 1, 2), (0, 2, 3), (3, 4, 5), (3, 5, 6),
|
|
(6, 7, 8), (6, 8, 0), (0, 3, 6),
|
|
]
|
|
run_v_c_algorithm(faces9, chords9, outer9, n9)
|
|
|
|
print('\n=== 24-vertex example ===')
|
|
n24 = 24
|
|
|
|
def arm(a, b):
|
|
return [
|
|
(a, a + 1, a + 2), (a, a + 2, b), (a + 2, a + 3, a + 4),
|
|
(a + 2, a + 4, b), (a + 4, a + 5, a + 6), (a + 4, a + 6, b),
|
|
(a + 6, a + 7, b),
|
|
]
|
|
outer24 = [(i, (i + 1) % n24) for i in range(n24)]
|
|
chords24 = [(0, 8), (8, 16), (0, 16)]
|
|
faces24 = [(0, 8, 16)]
|
|
for (a, b) in [(0, 8), (8, 16), (16, 24)]:
|
|
fs = arm(a, b)
|
|
fs = [tuple(0 if v == 24 else v for v in vt) for vt in fs]
|
|
faces24.extend(fs)
|
|
for c in [(a, a + 2), (a + 2, a + 4), (a + 2, b),
|
|
(a + 4, a + 6), (a + 4, b), (a + 6, b)]:
|
|
chords24.append(tuple(0 if v == 24 else v for v in c))
|
|
run_v_c_algorithm(faces24, chords24, outer24, n24)
|