#!/usr/bin/env python3
"""
Numerical validation for "Traversing Data in Symbolic Systems".

A typed knowledge graph G = (V, E): concepts V, typed directed edges
(subject, relation, object, confidence). Relations carry flags: transitive,
functional. Traversal follows typed edges; along a TRANSITIVE relation it
composes (a-r->b, b-r->c  =>  a-r->c); confidence decays x gamma per hop with
floor theta; endpoints must be in V.

We validate:
  T1 Conservativity : every derived fact is in the transitive closure of the
                      asserted edges (0 fabrications)
  T2 Termination    : every path length <= floor(log_gamma(theta/c0))
  T3 Path-as-proof  : 100% of returned facts re-verify by re-walking the path
  T4 Functional uniq: a functional relation yields <=1 successor, or a
                      contradiction is detected when two distinct values exist
"""
import random, math
from collections import defaultdict, deque

SEED = 20260915
random.seed(SEED)

N = 4000                    # concepts
M = 20000                   # asserted edges of the transitive relation
GAMMA = 0.75               # confidence decay per hop  (mirrors the deployed floor)
THETA = 0.40               # confidence floor
C0 = 1.0
DEPTH_BOUND = math.floor(math.log(THETA / C0, GAMMA))   # theoretical max hops

concepts = list(range(N))

# ---- asserted edges of a TRANSITIVE relation "part_of" (a DAG, to be sane) ----
# random DAG: edges only from lower id to higher id
asserted = set()
adj = defaultdict(list)
while len(asserted) < M:
    a = random.randint(0, N - 2)
    b = random.randint(a + 1, N - 1)
    if (a, b) not in asserted:
        asserted.add((a, b))
        adj[a].append(b)

# ---- ground-truth transitive closure (BFS reachability over asserted edges) ----
def full_closure_size_sample(sample_nodes):
    total = 0
    for s in sample_nodes:
        seen = set()
        dq = deque([s])
        while dq:
            x = dq.popleft()
            for y in adj[x]:
                if y not in seen:
                    seen.add(y); dq.append(y)
        total += len(seen)
    return total

# ---- bounded, confidence-decayed traversal (what the system actually does) ----
def traverse(seed):
    """Return derived facts (seed, obj, path) reachable within depth+confidence bound."""
    results = []
    # state: (node, path_of_edges, confidence)
    stack = [(seed, [], C0)]
    best_depth = 0
    while stack:
        node, path, conf = stack.pop()
        for nxt in adj[node]:
            c2 = conf * GAMMA
            if c2 < THETA:
                continue
            p2 = path + [(node, nxt)]
            best_depth = max(best_depth, len(p2))
            if node != seed or True:
                results.append((seed, nxt, tuple(p2)))
            stack.append((nxt, p2, c2))
    return results, best_depth

# reachable-set (unbounded) for soundness check per seed
def reachable(seed):
    seen = set(); dq = deque([seed])
    while dq:
        x = dq.popleft()
        for y in adj[x]:
            if y not in seen:
                seen.add(y); dq.append(y)
    return seen

seeds = random.sample(concepts, 300)
fabrications = 0
proof_ok = 0
proof_total = 0
max_path = 0
derived_total = 0
for s in seeds:
    derived, bd = traverse(s)
    max_path = max(max_path, bd)
    rs = reachable(s)
    for (a, b, path) in derived:
        derived_total += 1
        # T1: derived fact must be in the (unbounded) transitive closure
        if b not in rs:
            fabrications += 1
        # T3: re-verify the path — every hop must be an asserted edge, and
        #     consecutive hops must chain (compose) under the transitive relation
        proof_total += 1
        ok = all(e in asserted for e in path)
        ok = ok and all(path[i][1] == path[i + 1][0] for i in range(len(path) - 1))
        ok = ok and path[0][0] == a and path[-1][1] == b
        if ok:
            proof_ok += 1

# ---- T4: functional relation "class_of" (at most one object per subject) ----
class_of = defaultdict(set)         # asserted functional edges
# consistent assignments
for x in range(0, 1000):
    class_of[x].add(random.randint(10000, 10020))   # exactly one class each
# inject contradictions: 50 subjects given a second, distinct class
contradiction_subjects = random.sample(range(0, 1000), 50)
for x in contradiction_subjects:
    other = random.randint(10021, 10040)
    class_of[x].add(other)

def functional_step(subject):
    vals = class_of.get(subject, set())
    if len(vals) <= 1:
        return ("unique", next(iter(vals)) if vals else None)
    return ("contradiction", tuple(sorted(vals)))

detected = sum(1 for x in range(0, 1000) if functional_step(x)[0] == "contradiction")
unique_ok = sum(1 for x in range(0, 1000)
                if x not in contradiction_subjects and functional_step(x)[0] == "unique")

# ---------- report ----------
print("=" * 72)
print(" Traversing Data in Symbolic Systems — numerical validation")
print(f" seed={SEED}  concepts={N}  asserted transitive edges={M}")
print(f" gamma={GAMMA}  theta={THETA}  c0={C0}  ->  depth bound = {DEPTH_BOUND} hops")
print("=" * 72)
print(f" traversal seeds: {len(seeds)}   derived facts returned: {derived_total}")
print("-" * 72)
print(f"[T1] conservativity : fabrications (derived not in closure): {fabrications}"
      f"   {'PASS' if fabrications == 0 else 'FAIL'}")
print(f"[T2] termination    : max observed path length {max_path} <= bound {DEPTH_BOUND}"
      f"   {'PASS' if max_path <= DEPTH_BOUND else 'FAIL'}")
print(f"[T3] path-as-proof  : {proof_ok}/{proof_total} facts re-verified by re-walking path"
      f"   {'PASS' if proof_ok == proof_total else 'FAIL'}")
print(f"[T4] functional uniq: contradictions detected {detected}/50 ; "
      f"unique successors {unique_ok}/950"
      f"   {'PASS' if detected == 50 and unique_ok == 950 else 'FAIL'}")
print("=" * 72)