#!/usr/bin/env python3
"""
pagerank_eigenvalue_survey.py

Surveys the eigenvalue sorts produced by PageRank, HITS, Fiedler, and PPR
on a synthetic social graph, then maps each sort onto the 8-bin Sidon spectral
basis from Semantics.Spectrum / Semantics.GraphRank.

Goal: show that each classical ranking algorithm "observes" a different subset
of the 8 spectral bins, and that the bad-link gate (verifySpectralGap) is the
Sidon-filter analog of the cut identified by the Fiedler eigenvector.

Requires: networkx, scipy, numpy
  uv pip install networkx scipy numpy
"""

import numpy as np
import networkx as nx
from scipy.sparse.linalg import eigsh
from typing import List, Dict, Tuple

# ── Sidon spectral primitives (mirror Semantics.Spectrum) ────────────────────

BIN_COUNT = 8

def verify_spectral_gap(active: List[int]) -> bool:
    """No two active bin indices may be adjacent. Mirrors verifySpectralGap."""
    return all(abs(i - j) > 1 for i in active for j in active if i != j)

def piecewise_merge(a: List[float], b: List[float]) -> List[float]:
    """Saturating superposition. Mirrors SpectralSignature.piecewiseMerge."""
    return [min(1.0, x + y) for x, y in zip(a, b)]

def spectral_overlap(a: List[float], b: List[float]) -> float:
    """Inner product. Mirrors SpectralSignature.spectralOverlap."""
    return sum(x * y for x, y in zip(a, b))

def bad_link(src_sig: List[float], edge_sig: List[float],
             dst_sig: List[float], threshold: float = 0.05) -> bool:
    merged = piecewise_merge(piecewise_merge(src_sig, edge_sig), dst_sig)
    active = [i for i, v in enumerate(merged) if v > threshold]
    return not verify_spectral_gap(active)

# ── Rank mode → bin mapping (mirrors Semantics.GraphRank.RankMode) ────────────

def pagerank_sig(score: float, max_score: float) -> List[float]:
    """PageRank mass pools into bin 0 (DC / stationary distribution)."""
    sig = [0.0] * BIN_COUNT
    sig[0] = score / max_score if max_score > 0 else 0.0
    return sig

def hits_sig(auth: float, hub: float) -> List[float]:
    """HITS: authority → bin 0, hub → bin 2. Gap of 2 satisfies Sidon."""
    sig = [0.0] * BIN_COUNT
    sig[0] = auth
    sig[2] = hub  # bin 1 is skipped — maintains verifySpectralGap
    return sig

def fiedler_sig(fiedler_val: float) -> List[float]:
    """Fiedler component → bin 1 (community boundary = second eigenvector)."""
    sig = [0.0] * BIN_COUNT
    sig[1] = min(1.0, abs(fiedler_val))
    return sig

def ppr_sig(score: float, seed_bin: int) -> List[float]:
    """PPR seeded at bin k: propagates energy near that bin."""
    sig = [0.0] * BIN_COUNT
    sig[seed_bin] = score
    return sig

# ── Build test graph ──────────────────────────────────────────────────────────

def build_test_graph() -> nx.DiGraph:
    """
    Two communities with a bridge and a spam link farm.

    Community A (0-3): densely linked, should have high PageRank
    Community B (4-7): densely linked, should have high PageRank
    Bridge 3→4:        the "bad link" candidate — crosses Sidon bin boundary
    Spam farm (8-10):  link farm → node 0 (artificial authority injection)
    """
    g = nx.DiGraph()
    for i in range(3):
        for j in range(i + 1, 4):
            g.add_edge(i, j)
            g.add_edge(j, i)
    for i in range(4, 7):
        for j in range(i + 1, 8):
            g.add_edge(i, j)
            g.add_edge(j, i)
    g.add_edge(3, 4)  # inter-community bridge
    for i in [8, 9, 10]:
        g.add_edge(i, 0)  # spam → target
        g.add_edge(i, 8 if i != 8 else 10)  # farm cross-links
    return g

# ── Run classical algorithms ──────────────────────────────────────────────────

def run_pagerank(g: nx.DiGraph, alpha: float = 0.85) -> Dict[int, float]:
    return nx.pagerank(g, alpha=alpha, max_iter=300)

def run_hits(g: nx.DiGraph) -> Tuple[Dict[int, float], Dict[int, float]]:
    try:
        hubs, auths = nx.hits(g, max_iter=300, normalized=True)
    except nx.PowerIterationFailedConvergence:
        default = {n: 1.0 / len(g) for n in g}
        hubs, auths = default, default
    return hubs, auths

def run_fiedler(g: nx.DiGraph) -> np.ndarray:
    ug = g.to_undirected()
    nodes = sorted(ug.nodes())
    L = nx.laplacian_matrix(ug, nodelist=nodes).astype(float)
    try:
        vals, vecs = eigsh(L, k=2, which='SM', tol=1e-8, maxiter=1000)
        # Second column = Fiedler vector (index 1 after sorting by eigenvalue)
        order = np.argsort(vals)
        return vecs[:, order[1]], nodes
    except Exception as exc:
        print(f"  [fiedler] eigsh failed: {exc}")
        return np.zeros(len(nodes)), nodes

# ── Survey ────────────────────────────────────────────────────────────────────

def run_survey(g: nx.DiGraph):
    nodes = sorted(g.nodes())
    pr    = run_pagerank(g)
    hubs, auths = run_hits(g)
    fiedler_vec, fiedler_nodes = run_fiedler(g)
    fiedler_map  = {fiedler_nodes[i]: fiedler_vec[i]
                    for i in range(len(fiedler_nodes))}

    max_pr   = max(pr.values()) or 1.0
    max_auth = max(auths.values()) or 1.0
    max_hub  = max(hubs.values()) or 1.0

    print("=" * 72)
    print("EIGENVALUE SORT SURVEY — mapped to 8-bin Sidon spectral basis")
    print("=" * 72)

    # ── PageRank (bin-0 dominant) ──────────────────────────────────────────
    pr_sorted = sorted(pr.items(), key=lambda x: -x[1])
    print("\n[PageRank]  bin 0 ← DC / stationary distribution")
    print(f"  {'node':>5}  {'PR':>8}  {'bin0':>6}  {'gap':>5}  community")
    for node, score in pr_sorted:
        sig    = pagerank_sig(score, max_pr)
        active = [i for i, v in enumerate(sig) if v > 0.05]
        gap_ok = verify_spectral_gap(active)
        comm   = 'A' if node <= 3 else ('B' if node <= 7 else 'spam')
        print(f"  {node:>5}  {score:>8.5f}  {sig[0]:>6.3f}  {'OK' if gap_ok else 'BAD':>5}  {comm}")

    # ── HITS (bins 0 + 2) ─────────────────────────────────────────────────
    auth_sorted = sorted(auths.items(), key=lambda x: -x[1])
    print("\n[HITS Authority]  bin 0 (auth) + bin 2 (hub); gap=2 satisfies Sidon")
    print(f"  {'node':>5}  {'auth':>8}  {'hub':>8}  {'gap':>5}  community")
    for node, auth in auth_sorted:
        hub    = hubs.get(node, 0.0)
        sig    = hits_sig(auth / max_auth, hub / max_hub)
        active = [i for i, v in enumerate(sig) if v > 0.05]
        gap_ok = verify_spectral_gap(active)
        comm   = 'A' if node <= 3 else ('B' if node <= 7 else 'spam')
        print(f"  {node:>5}  {auth:>8.5f}  {hub:>8.5f}  {'OK' if gap_ok else 'BAD':>5}  {comm}")

    # ── Fiedler (bin 1) ───────────────────────────────────────────────────
    print("\n[Fiedler]  bin 1 ← community boundary (second Laplacian eigenvector)")
    fiedler_sorted = sorted(fiedler_map.items(), key=lambda x: x[1])
    neg_side = [n for n, v in fiedler_sorted if v < 0]
    pos_side = [n for n, v in fiedler_sorted if v >= 0]
    print(f"  Community A (Fiedler < 0): {neg_side}")
    print(f"  Community B (Fiedler ≥ 0): {pos_side}")
    print(f"  {'node':>5}  {'F_val':>9}  {'bin1':>6}  community")
    for node, val in fiedler_sorted:
        sig  = fiedler_sig(val)
        comm = 'A' if val < 0 else 'B'
        print(f"  {node:>5}  {val:>+9.5f}  {sig[1]:>6.3f}  {comm}")

    # ── Bad-link gate on bridge and spam ──────────────────────────────────
    print("\n[Bad-link gate]")

    # Bridge 3→4
    src_sig  = pagerank_sig(pr[3], max_pr)
    dst_sig  = pagerank_sig(pr[4], max_pr)
    edge_sig = [0.5] + [0.0] * 7   # bridge carries half bin-0 authority
    merged   = piecewise_merge(piecewise_merge(src_sig, edge_sig), dst_sig)
    active_m = [i for i, v in enumerate(merged) if v > 0.05]
    is_bad   = not verify_spectral_gap(active_m)
    print(f"  Bridge 3→4:  merged active bins={active_m}  "
          f"gap={'FAIL (bad link)' if is_bad else 'OK'}")

    for spam_node in [8, 9, 10]:
        s_sig  = pagerank_sig(pr[spam_node], max_pr)
        t_sig  = pagerank_sig(pr[0], max_pr)
        e_sig  = [0.5] + [0.0] * 7
        merged = piecewise_merge(piecewise_merge(s_sig, e_sig), t_sig)
        active_m = [i for i, v in enumerate(merged) if v > 0.05]
        is_bad = not verify_spectral_gap(active_m)
        print(f"  Spam {spam_node}→0:   merged active bins={active_m}  "
              f"gap={'FAIL (bad link)' if is_bad else 'OK'}")

    # ── Spectral overlap as PPR dot product ───────────────────────────────
    print("\n[Spectral overlap — PPR dot product with seed = community A sig]")
    seed_sig = pagerank_sig(1.0, 1.0)  # pure bin-0 seed
    scores   = []
    for node in nodes:
        sig   = pagerank_sig(pr[node], max_pr)
        score = spectral_overlap(sig, seed_sig)
        scores.append((node, score))
    scores.sort(key=lambda x: -x[1])
    print(f"  {'node':>5}  {'overlap':>9}  community")
    for node, sc in scores:
        comm = 'A' if node <= 3 else ('B' if node <= 7 else 'spam')
        print(f"  {node:>5}  {sc:>9.5f}  {comm}")

    # ── Summary ───────────────────────────────────────────────────────────
    print("\n[Summary — eigenvalue sort → spectral bin mapping]")
    print("  PageRank     → bin 0   (DC authority; bad link = bin-0 bleed)")
    print("  HITS auth    → bin 0   (top singular vector = pure authority)")
    print("  HITS hub     → bin 2   (gap=2 from authority; Sidon-safe)")
    print("  Fiedler      → bin 1   (community cut = spectral gap)")
    print("  PPR seed     → bin k   (propagates along matching-bin paths)")
    print("  CheiRank     → 1-bin0  (givers have LOW bin-0; receivers HIGH)")
    print("  verifySpectralGap ← detects ALL of the above failures at once")
    print("  erdosHooleyDelta  ← density threshold for Sidon property in 8-bin space")


if __name__ == "__main__":
    g = build_test_graph()
    print(f"Graph: {len(g.nodes())} nodes, {len(g.edges())} edges\n")
    run_survey(g)