didericis
bd9c46d3e4
Migrate the paper content into the amsart template and include the supporting experiments scripts.
86 lines
2.6 KiB
Python
86 lines
2.6 KiB
Python
"""
|
|
Coverage analysis: for each pair (n, target-class restriction), check whether
|
|
every iso-class in the restriction is reachable as a level resolution of
|
|
some triangulation on n vertices.
|
|
"""
|
|
import networkx as nx
|
|
import time
|
|
from level_cycles import all_level_resolutions
|
|
from triangulation_gen import enumerate_all_triangulations
|
|
|
|
|
|
def iso_class(G, reps):
|
|
for i, r in enumerate(reps):
|
|
if nx.is_isomorphic(G, r):
|
|
return i
|
|
return -1
|
|
|
|
|
|
def resolution_classes(G, reps):
|
|
return {iso_class(Gp, reps) for Gp, _, _, _ in all_level_resolutions(G)}
|
|
|
|
|
|
def min_degree(G):
|
|
return min(d for _, d in G.degree())
|
|
|
|
|
|
def coverage_report(n, target_filter=None, source_filter=None):
|
|
"""
|
|
target_filter / source_filter: callables G -> bool, or None for "any".
|
|
"""
|
|
print(f"\n{'='*60}\nn = {n}\n{'='*60}")
|
|
t0 = time.time()
|
|
reps = enumerate_all_triangulations(n)
|
|
print(f"Total iso-classes: {len(reps)}")
|
|
|
|
if source_filter is None:
|
|
sources = list(range(len(reps)))
|
|
print(f"Sources: all {len(sources)}")
|
|
else:
|
|
sources = [i for i, G in enumerate(reps) if source_filter(G)]
|
|
print(f"Sources (filtered): {len(sources)}")
|
|
|
|
if target_filter is None:
|
|
targets = set(range(len(reps)))
|
|
else:
|
|
targets = {i for i, G in enumerate(reps) if target_filter(G)}
|
|
print(f"Targets: {len(targets)} iso-classes")
|
|
for i in sorted(targets):
|
|
deg = sorted((d for _, d in reps[i].degree()), reverse=True)
|
|
print(f" T{i}: degree {deg}")
|
|
|
|
reached, sources_per_target = set(), {i: [] for i in targets}
|
|
for src_i in sources:
|
|
prod = resolution_classes(reps[src_i], reps) & targets
|
|
for p in prod:
|
|
sources_per_target[p].append(src_i)
|
|
reached |= prod
|
|
|
|
print("\nCoverage:")
|
|
for i in sorted(targets):
|
|
sources_list = sources_per_target[i]
|
|
status = "REACHED" if sources_list else "UNREACHABLE"
|
|
s = ", ".join(f"T{j}" for j in sources_list[:6])
|
|
if len(sources_list) > 6:
|
|
s += f", ... ({len(sources_list)} total)"
|
|
elif not sources_list:
|
|
s = "(none)"
|
|
print(f" T{i}: {status} via {s}")
|
|
|
|
uncov = targets - reached
|
|
print(f"\nUncovered: {sorted(uncov)}")
|
|
print(f"Time: {time.time()-t0:.1f}s")
|
|
|
|
|
|
if __name__ == "__main__":
|
|
# General coverage (any source, any target)
|
|
for n in [6, 7]:
|
|
coverage_report(n)
|
|
|
|
# md3 sources -> md4 targets
|
|
print("\n\n" + "#"*60)
|
|
print("md3 sources -> md4 targets")
|
|
print("#"*60)
|
|
for n in [6, 7, 8]:
|
|
coverage_report(n, target_filter=lambda G: min_degree(G) >= 4)
|