def prehodna_matrika_M(matrika):   #vrne matriko katere (i,j)-ti element prikazuje verjetnost, da se bomo iz i-tega vozlišča premaknili v j-to
    return Matrix([r/v for r, v in zip(matrika, sum(matrika))]) # vrstica / vsota vrstice

def brisanje(j, matrika):  #izbriše j-ti stolpec in j-to vrstico
    return matrika.delete_columns([j]).delete_rows([j])

def dodajanje(j, matrika):   #doda j-to vrstico in j-ti stolpec (ničle)
    return block_matrix([[matrika[:j, :j], 0, matrika[:j, j:]],
                         [0, Matrix(1, 1), 0],
                         [matrika[j:, :j], 0, matrika[j:, j:]]])

def element_H(i, j, matrika):    #izračuna (i,j)-ti element matrike H
    IM = dodajanje(j, (identity_matrix(matrika.nrows()-1) - brisanje(j, matrika))^-2)
    return sum(IM[i, k] * matrika[k, j] for k in range(matrika.nrows()) if k != j)

def matrika_H(matrika):  #vrne celotno matriko H
    return Matrix([next(zip(*dodajanje(j, (identity_matrix(matrika.nrows()-1) - brisanje(j, matrika))^-2) * matrika[:, j]))
                   for j in range(matrika.ncols())]).transpose()

def nakjucni_sprehod_blizine_centralnosti(i,matrika): #sprejme incidenčno matriko!
    vsota = 0
    n = matrika.nrows()
    rd = range(0,n)
    M = prehodna_matrika_M(matrika) #izračun matrike M
    H = matrika_H(M)
    for j in rd:
        vsota += H[j,i]
    return n/vsota   #vrne vrednost naključnega sprehoda iz vozlišča i

def centralno_po_nsbc(matrika):   #vrne centralno vozlišče in njegovo vrednost
    n = matrika.nrows()
    rd = range(0,n)
    najvecji = [0,0]
    for i in rd:
        if nakjucni_sprehod_blizine_centralnosti(i,matrika) > najvecji[1]:
            s, = nakjucni_sprehod_blizine_centralnosti(i,matrika)
            najvecji = [i,s]
    return najvecji

def oddaljenost_i(i,matrika):   #vrne oddaljenost (najkrajšo pot) i-tega vozlišča do vseh ostalih vozlišč
    n = matrika.nrows()
    rd = range(0,n)
    vektor = Matrix(n,1)
    for j in rd:  #j != i
        if j == i:  #spusti
            pass #vektor = vektor
        elif matrika[i,j] != 0:  #sosednja vozlišča
            vektor[j] = 1
        else:
            for l in range(1,n):
                if vektor[j] != 0:
                    pass #vektor = vektor
                elif (matrika^l)[i,j] != 0:
                    vektor[j] = l
    return vektor


def centralnost_i(i,matrika):  #centralno vozlišče
    s, = sum(oddaljenost_i(i,matrika))   #edini element se zapiše v spremenljivko s
    return 1/s

def centralnost(matrika):
    vek = [0,0]
    for i in range(0,matrika.nrows()):
        if centralnost_i(i,matrika) > vek[1]:
            vek = [i,centralnost_i(i,matrika)]
    return vek

def min_centralno(matrika):
    d = matrika.nrows()
    vek = [d,d]
    for i in range(0,d):
        if centralnost_i(i,matrika) < vek[1]:
            vek = [i,centralnost_i(i,matrika)]
    return vek