"""Authored PageRank matrix construction; not a reconstruction of Google Search."""
from fractions import Fraction as F
import json

G={'A':['B','C'],'B':['C'],'C':[]};N=list(G)
def matrix(v,alpha=F(1,2),fix_dangling=True):
    if len(v)!=3 or sum(v)!=1 or any(x<0 for x in v)or not 0<=alpha<1:raise ValueError('normalized nonnegative vector and 0<=alpha<1')
    P=[]
    for u in N:
        row=[F(int(w in G[u]),len(G[u]))for w in N]if G[u]else list(v)if fix_dangling else [F(0)]*3
        P.append(row)
    M=[[alpha*P[i][j]+(1-alpha)*v[j]for j in range(3)]for i in range(3)]
    return P,M
def step(p,M):return [sum(p[i]*M[i][j]for i in range(3))for j in range(3)]
def stationary(M):
    A=[[M[j][i]-int(i==j)for j in range(3)]+[F(0)]for i in range(2)]+[[F(1),F(1),F(1),F(1)]]
    for col in range(3):
        pivot=next(i for i in range(col,3)if A[i][col]);A[col],A[pivot]=A[pivot],A[col];s=A[col][col];A[col]=[x/s for x in A[col]]
        for i in range(3):
            if i!=col:
                s=A[i][col];A[i]=[x-s*y for x,y in zip(A[i],A[col])]
    p=[A[i][-1]for i in range(3)];assert sum(p)==1 and step(p,M)==p;return p
def power(M):
    p=[F(1,3)]*3;first=[]
    for t in range(1,201):
        p=step(p,M);assert sum(p)==1 and all(x>=0 for x in p)
        residual=sum(abs(x-y)for x,y in zip(step(p,M),p))
        if t<=3:first.append({'iteration':t,'distribution':p.copy()})
        if residual<F(1,10**10):return {'iterations':t,'first_three':first,'last_distribution':p,'l1_fixed_point_residual':residual}
    raise AssertionError('fixture failed to converge')
def demo():
    uniform=[F(1,3)]*3;P,M=matrix(uniform);exact=stationary(M);iterate=power(M)
    assert exact==[F(8,33),F(10,33),F(15,33)]
    assert max(abs(x-y)for x,y in zip(iterate['last_distribution'],exact))<F(1,10**9)
    badP,badM=matrix(uniform,fix_dangling=False);badnext=step(uniform,badM);assert sum(badM[2])==F(1,2)and sum(badnext)==F(5,6)
    biased=[F(4,5),F(1,10),F(1,10)];bP,bM=matrix(biased);bexact=stationary(bM);assert bexact[0]>bexact[1]and bexact[0]>bexact[2]
    invalid=[]
    for v,a in [([F(1),F(1),F(1)],F(1,2)),(uniform,F(1))]:
        try:matrix(v,a)
        except ValueError:invalid.append(True)
        else:raise AssertionError('invalid accepted')
    return {'authored_graph':G,'node_order':N,'alpha':F(1,2),'uniform':{'personalization':uniform,'dangling_replacement_same_vector':uniform,'row_transition_P':P,'teleport_M':M,'independent_exact_linear_solution':exact,'power_iteration':iterate},'incorrect_unfixed_dangling':{'P':badP,'M':badM,'next_distribution':badnext,'mass_after_one_step':sum(badnext)},'biased':{'personalization_and_dangling':biased,'P':bP,'M':bM,'exact_stationary':bexact},'two_invalid_inputs_rejected':invalid,'networkx_google_or_real_website_rank_executed':False}
if __name__=='__main__':print(json.dumps(demo(),default=str,indent=2))