import numpy as np
import cascade_creation
import itertools
from scipy import sparse
from scipy.sparse import linalg

def find_kth_rip_constants(M, k):
    """
    Returns max(A_1, A_2) where:
    1 + A_1 = arg max |Mx|_2^2 s.t. |x|_2 = 1 and |x|_0 = k
    1 - A_2 = arg min |Mx|_2^2 s.t. |x|_2 = 1 and |x|_0 = kx
    """
    delta = 0
    print(M.shape)
    for col_set in itertools.combinations(xrange(M.shape[1]), k):
        M_kcol = M[:,list(col_set)]
        delta_upper, delta_lower = upperlower_bound_rip(M_kcol)
        delta = max(delta, max(delta_upper, delta_lower))
    return delta


def upperlower_bound_rip(M):
    """
    returns arg max/min |Mx|_2^2 s.t. |x|_2 = 1
    which is the greatest eigenvalue value of M^T*M
    or the square of the greatest singular value of M
    """
    M = sparse.csc_matrix(M)
    s_upper = linalg.svds(M, 1, tol=.01, which ='LM', maxiter = 2000,
                                return_singular_vectors=False)
    s_lower = linalg.svds(M, 1, tol=.01, which = 'SM', maxiter= 2000,
                                return_singular_vectors=False)
    return s_upper ** 2 - 1, 1 -s_lower ** 2


def test():
    """
    unit test
    """
    G = cascade_creation.InfluenceGraph(max_proba=.3)
    G.erdos_init(n=10, p =1)
    cascades = cascade_creation.generate_cascades(G, p_init=.3, n_cascades=10)
    M, __ = cascade_creation.icc_matrixvector_for_node(cascades, None)
    M = cascade_creation.normalize_matrix(M)
    print(find_kth_rip_constants(M, 5))


if __name__=="__main__":
    test()