#!/usr/bin/env python3 """Enumerate all vertex-labelled, oriented, reduced planar four-vertex maps. Only Python's standard library is used. A map is represented by a prescribed vertex permutation alpha and a fixed-point-free involution beta. We retain maps that are connected, loopless, planar, and have no face of degree < 3. Independent cyclic rotations of the four vertex slots are quotiented exactly. The output includes every orbit representative and all aggregate counts. Run: python enumerate_four_point.py --output four_point_skeletons.json """ import argparse import itertools import json import math from collections import Counter, defaultdict def compositions(total, parts): if parts == 1: if total >= 1: yield (total,) return for first in range(1, total - parts + 2): for tail in compositions(total - first, parts - 1): yield (first,) + tail def cycles(perm): seen = set() answer = [] for root in range(len(perm)): if root in seen: continue orbit = [] h = root while h not in seen: seen.add(h) orbit.append(h) h = perm[h] answer.append(orbit) return answer def make_vertices(degrees): alpha, owner, starts = [], [], [] for i, d in enumerate(degrees): start = len(alpha) starts.append(start) alpha.extend(start + (k + 1) % d for k in range(d)) owner.extend([i] * d) return tuple(alpha), tuple(owner), tuple(starts) def connected(alpha, beta): seen = {0} stack = [0] while stack: h = stack.pop() for k in (alpha[h], beta[h]): if k not in seen: seen.add(k) stack.append(k) return len(seen) == len(alpha) def cyclic_relabellings(degrees, starts): for shifts in itertools.product(*(range(d) for d in degrees)): rho = [] for start, d, shift in zip(starts, degrees, shifts): rho.extend(start + (k + shift) % d for k in range(d)) yield tuple(rho) def conjugate(beta, rho): answer = [None] * len(beta) for h in range(len(beta)): answer[rho[h]] = rho[beta[h]] return tuple(answer) def edge_multiplicities(beta, owner): counts = Counter() for h, k in enumerate(beta): if h < k: counts[tuple(sorted((owner[h], owner[k])))] += 1 return tuple((i, j, m) for (i, j), m in sorted(counts.items())) def abstract_key(edges): """Canonical adjacency data under all vertex permutations.""" return min( tuple(sorted((min(p[i], p[j]), max(p[i], p[j]), m) for i, j, m in edges)) for p in itertools.permutations(range(4)) ) def bipartition(edges): adjacency = [set() for _ in range(4)] for i, j, _ in edges: adjacency[i].add(j) adjacency[j].add(i) colour = {0: 0} stack = [0] while stack: i = stack.pop() for j in adjacency[i]: if j in colour: if colour[j] == colour[i]: return None else: colour[j] = 1 - colour[i] stack.append(j) return [[i + 1 for i in range(4) if colour[i] == c] for c in (0, 1)] def enumerate_degree(degrees): alpha, owner, starts = make_vertices(degrees) size = len(alpha) edge_count = size // 2 beta = [-1] * size raw = Counter() representatives = {} relabellings = list(cyclic_relabellings(degrees, starts)) canonical_cache = {} def visit(remaining): if not remaining: if not connected(alpha, beta): return face_cycles = cycles(tuple(alpha[beta[h]] for h in range(size))) if len(face_cycles) != edge_count - 2: return if min(map(len, face_cycles)) < 3: return pairing = tuple(beta) canonical = canonical_cache.get(pairing) if canonical is None: orbit = {conjugate(pairing, rho) for rho in relabellings} canonical = min(orbit) for element in orbit: canonical_cache[element] = canonical raw[canonical] += 1 representatives[canonical] = face_cycles return h = remaining[0] for pos, k in enumerate(remaining[1:]): if owner[h] == owner[k]: continue beta[h], beta[k] = k, h visit(remaining[1:pos + 1] + remaining[pos + 2:]) visit(tuple(range(size))) result = [] for pairing in sorted(raw): face_cycles = cycles(tuple(alpha[pairing[h]] for h in range(size))) edges = edge_multiplicities(pairing, owner) stabilizer = sum(conjugate(pairing, rho) == pairing for rho in relabellings) expected_orbit_size = math.prod(degrees) // stabilizer assert raw[pairing] == expected_orbit_size result.append({ "degrees": list(degrees), "edge_count": edge_count, "alpha_cycles": [[h + 1 for h in c] for c in cycles(alpha)], "beta_cycles": [[h + 1 for h in c] for c in cycles(pairing)], "face_cycles": [[h + 1 for h in c] for c in face_cycles], "face_degrees": sorted(map(len, face_cycles)), "zero_orders": sorted(len(c) - 2 for c in face_cycles), "adjacency": [[i + 1, j + 1, m] for i, j, m in edges], "abstract_key": [[i + 1, j + 1, m] for i, j, m in abstract_key(edges)], "bipartition": bipartition(edges), "labelled_pairing_count": raw[pairing], "automorphism_order": stabilizer, }) return result def main(): parser = argparse.ArgumentParser() parser.add_argument("--output", default="four_point_skeletons.json") args = parser.parse_args() maps = [] for edges in range(3, 7): for degrees in compositions(2 * edges, 4): if max(degrees) > edges: continue maps.extend(enumerate_degree(degrees)) type_names = { (3, (3, 1, 1, 1)): "S", (3, (2, 2, 1, 1)): "P", (4, (3, 2, 2, 1)): "T", (4, (4, 2, 1, 1)): "D_s", (4, (2, 2, 2, 2)): "C", (4, (3, 3, 1, 1)): "D_o", (5, (3, 3, 2, 2)): "H", (5, (4, 3, 2, 1)): "L", (6, (3, 3, 3, 3)): "K", (6, (4, 4, 2, 2)): "M", } for number, item in enumerate(maps, start=1): item["cell_id"] = "cell_{:03d}".format(number) item["type"] = type_names[(item["edge_count"], tuple(sorted(item["degrees"], reverse=True)))] grouped = defaultdict(list) for item in maps: key = (item["edge_count"], tuple(tuple(e) for e in item["abstract_key"])) grouped[key].append(item) summary = [] for (edges, key), items in sorted(grouped.items()): face_types = sorted({tuple(item["face_degrees"]) for item in items}) assert len(face_types) == 1 summary.append({ "type": items[0]["type"], "edge_count": edges, "abstract_key": key, "degree_multiset": sorted(items[0]["degrees"], reverse=True), "face_degrees": face_types[0], "zero_orders": [degree - 2 for degree in face_types[0]], "vertex_labelled_oriented_cells": len(items), "bipartite": items[0]["bipartition"] is not None, "automorphism_orders": sorted({item["automorphism_order"] for item in items}), }) totals = dict(sorted(Counter(item["edge_count"] for item in maps).items())) output = { "conventions": { "vertices": "Four individually labelled external vertices, labels 1 to 4.", "orientation": "Cyclic orders are preserved; orientation reversal is not quotiented.", "reduced": "Connected, genus zero, no loops, and every face degree at least three.", "isomorphism": "Independent cyclic rotations of fixed vertex slots.", }, "totals_by_edge_count": totals, "total_cells": len(maps), "abstract_types": summary, "cells": maps, } with open(args.output, "w", encoding="utf-8") as stream: json.dump(output, stream, ensure_ascii=False, indent=2) stream.write("\n") print(json.dumps({"totals": totals, "total": len(maps), "types": summary}, indent=2)) if __name__ == "__main__": main()