Converts affinity matrix into normalised graph Laplacian,
    for spectral clustering.
    (At least) two forms exist:

    L = (D^-0.5).A.(D^-0.5) - default

    L = (D^-1).A - `Shi-Malik` type, from Shi Malik paper

def laplace(affinity_matrix, shi_malik_type=False):
    """ Converts affinity matrix into normalised graph Laplacian,
    for spectral clustering.
    (At least) two forms exist:

    L = (D^-0.5).A.(D^-0.5) - default

    L = (D^-1).A - `Shi-Malik` type, from Shi Malik paper"""

    diagonal = affinity_matrix.sum(axis=1) - affinity_matrix.diagonal()
    zeros = diagonal <= 1e-10
    diagonal[zeros] = 1
    if (diagonal <= 1e-10).any():  # arbitrarily small value
        raise ZeroDivisionError
    if shi_malik_type:
        inv_d = np.diag(1 / diagonal)
        return inv_d.dot(affinity_matrix)
    diagonal = np.sqrt(diagonal)
    return affinity_matrix / diagonal / diagonal[:, np.newaxis]