#!/usr/bin/env python3
# Source: t3-probability-information.html
import numpy as np


def pagerank(adj: np.ndarray, d: float = 0.85, tol: float = 1e-10, max_iter: int = 10000) -> np.ndarray:
    """Power iteration for PageRank. adj[i, j] = 1 if page i links to page j."""
    adj = np.asarray(adj, dtype=float)
    if adj.ndim != 2 or adj.shape[0] != adj.shape[1] or len(adj) == 0:
        raise ValueError("Use a nonempty square adjacency matrix")
    if not np.isfinite(adj).all() or (adj < 0).any() or not 0 <= d < 1:
        raise ValueError("Use finite nonnegative weights and 0 <= damping < 1")
    if tol <= 0 or not np.isfinite(tol) or not isinstance(max_iter, int) or max_iter <= 0:
        raise ValueError("Use positive tolerance and iteration bound")
    n = adj.shape[0]
    out = adj.sum(axis=1, keepdims=True)
    # Dangling pages (no out-links) jump uniformly.
    P = np.where(out > 0, adj / np.where(out > 0, out, 1), 1.0 / n)
    G = d * P + (1 - d) / n          # row-stochastic "Google matrix"
    pi = np.full(n, 1.0 / n)
    for _ in range(max_iter):  # Remaining iterations bound this loop.
        new = pi @ G                 # one step of the chain
        if np.abs(new - pi).sum() < tol:
            return new
        pi = new
    raise RuntimeError("PageRank did not reach tolerance within max_iter")


adj = np.array([[0, 1, 1, 0],
                [0, 0, 1, 0],
                [1, 0, 0, 0],
                [0, 0, 1, 0]], dtype=float)
pi = pagerank(adj)
print(np.round(pi, 4), round(pi.sum(), 6))
# [0.3725 0.1958 0.3941 0.0375] 1.0
