# How Epidemics Spread 7, Exercise 1
# Exercise 1: how clustering changes an outbreak when the number of contacts stays the same (T = 0.25 assumed).
import random

def random_network(n, mean_degree):
    """Random network: pick random pairs until there are n * mean_degree / 2 links."""
    nbrs = [set() for _ in range(n)]
    links = 0
    while links < n * mean_degree // 2:
        a, b = random.randrange(n), random.randrange(n)
        if a != b and b not in nbrs[a]:
            nbrs[a].add(b)
            nbrs[b].add(a)
            links += 1
    return nbrs

def clustered_network(n, mean_degree, rewire):
    """Ring of neighbours (everyone knows the people nearby); each link is rewired at random with chance `rewire`."""
    nbrs = [set() for _ in range(n)]
    for i in range(n):
        for step in range(1, mean_degree // 2 + 1):
            j = (i + step) % n
            if random.random() < rewire:
                j = random.randrange(n)
                while j == i or j in nbrs[i]:
                    j = random.randrange(n)
            nbrs[i].add(j)
            nbrs[j].add(i)
    return nbrs

def hub_network(n, m):
    """Growth with preferential attachment: each newcomer links to m people, favouring the already well connected."""
    nbrs = [set() for _ in range(n)]
    pool = []                      # a person appears here once per link they have
    targets = list(range(m))
    for new in range(m, n):
        for t in set(targets):
            nbrs[new].add(t)
            nbrs[t].add(new)
        pool.extend(targets)
        pool.extend([new] * m)
        targets = [random.choice(pool) for _ in range(m)]
    return nbrs

def describe(nbrs):
    n = len(nbrs)
    degrees = [len(x) for x in nbrs]
    mean = sum(degrees) / n
    excess = (sum(d * d for d in degrees) / n - mean) / mean   # average number of *other* contacts a contact has
    tri, trip = 0, 0
    for i in range(n):
        d = degrees[i]
        if d >= 2:
            trip += d * (d - 1) / 2
            tri += sum(len(nbrs[i] & nbrs[j]) for j in nbrs[i]) / 2
    return mean, max(degrees), excess, tri / trip


def outbreak(nbrs, T, blocked=frozenset()):
    """One outbreak from a random unblocked person; returns how many people were ever infected."""
    start = random.randrange(len(nbrs))
    while start in blocked:
        start = random.randrange(len(nbrs))
    reached, frontier = {start}, [start]
    while frontier:
        following = []
        for u in frontier:
            for v in nbrs[u]:
                if v not in reached and v not in blocked and random.random() < T:
                    reached.add(v)
                    following.append(v)
        frontier = following
    return len(reached)

def summarise(nbrs, T, runs, blocked=frozenset()):
    sizes = [outbreak(nbrs, T, blocked) for _ in range(runs)]
    big = [s for s in sizes if s > 20]
    fizzled = 1 - len(big) / runs
    share = sum(big) / len(big) / len(nbrs) if big else 0.0   # 0 if none took off
    return fizzled, share, sum(sizes) / runs / len(nbrs)


random.seed(21)
n, T, runs = 2000, 0.25, 300
print("rewire   clustering   excess degree   fizzled   size if it takes off (0 = none)   average size")
for rewire in [0.0, 0.01, 0.05, 0.2, 1.0]:
    g = clustered_network(n, 6, rewire)
    mean, biggest, excess, clustering = describe(g)
    fizzled, share, average = summarise(g, T, runs)
    print(f"{rewire:6.2f} {clustering:12.3f} {excess:15.2f} {fizzled:9.1%} {share:32.1%} {average:14.1%}")

# Output when run:
# rewire   clustering   excess degree   fizzled   size if it takes off (0 = none)   average size
#   0.00        0.600            5.00     94.7%                             1.4%           0.4%
#   0.01        0.579            5.01     88.7%                             1.5%           0.5%
#   0.05        0.511            5.05     80.0%                             2.2%           0.7%
#   0.20        0.298            5.17     60.0%                            19.3%           7.9%
#   1.00        0.002            5.51     44.3%                            54.6%          30.5%

# Reading the output: as rewiring rises, clustering falls from 0.600 to 0.002 while the excess degree barely moves (5.00 to 5.51). The average share infected, though, climbs from 0.4% to 30.5%, and the fizzle rate falls from 94.7% to 44.3%. So the excess degree alone does not explain the differences: clustering matters, and the rule T * excess overpredicts spread on highly clustered networks (it gives 1.25 at rewire 0 although nearly every outbreak fizzles). The reasons (many transmissions land on people already infected, and the infection must creep around the ring) are my inference and were not tested here. All numbers are for assumed T and sizes.