Spaces:
Running
on
CPU Upgrade
Running
on
CPU Upgrade
File size: 2,314 Bytes
c89947b |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
"""
Utilities for working with planar graphs and embeddings.
"""
from typing import List, Tuple, Dict
def extract_faces_from_planar_embedding(n_vertices: int, adj_cyclic: Dict[int, List[int]]) -> List[Tuple[int, int, int]]:
"""
Extract triangular faces from a planar embedding.
In plantri's ASCII output format, the adjacency lists are given in CYCLIC ORDER
around each vertex, representing the planar embedding. This function extracts
the faces (triangles) from this embedding.
Args:
n_vertices: Number of vertices
adj_cyclic: Adjacency dictionary where neighbors are in cyclic order
Returns:
List of triangular faces as (v0, v1, v2) tuples, sorted
"""
faces_set = set()
# For each directed edge (u, v), find the face to its right
for u in range(n_vertices):
neighbors = adj_cyclic[u]
for i, v in enumerate(neighbors):
# Start at edge u -> v
# Find the face by following edges clockwise around the face boundary
face = [u, v]
current = v
prev = u
# Follow the face boundary
while True:
# At vertex 'current', we came from 'prev'
# Find 'prev' in current's neighbor list
current_neighbors = adj_cyclic[current]
try:
prev_idx = current_neighbors.index(prev)
except ValueError:
# Edge not found - broken embedding
break
# Next vertex in face is the one BEFORE prev in cyclic order
# (going clockwise around the face)
next_v = current_neighbors[(prev_idx - 1) % len(current_neighbors)]
if next_v == u:
# Completed the face
break
face.append(next_v)
prev = current
current = next_v
if len(face) > n_vertices:
# Sanity check - shouldn't happen for valid embeddings
break
# Store face as sorted tuple for deduplication
if len(face) == 3:
face_tuple = tuple(sorted(face))
faces_set.add(face_tuple)
return sorted(list(faces_set))
|