import igraph as ig
import matplotlib.pyplot as plt
import timeit
from memory_profiler import profile

N = 30

MM = [[0,1,0,0,0,0],
      [0,0,1,0,0,0],
      [0,0,0,1,0,0],
      [0,0,0,0,0,0],
      [0,0,0,0,0,1],
      [0,0,0,0,0,0]]

M = [[0, 1, 1, 1, 1, 1, 1, 0, 0, 0],
     [1, 0, 1, 0, 0, 0, 1, 1, 1, 1],
     [1, 1, 0, 1, 0, 0, 0, 0, 0, 1],
     [1, 0, 1, 0, 1, 0, 0, 0, 0, 0],
     [1, 0, 0, 1, 0, 1, 0, 0, 0, 0],
     [1, 0, 0, 0, 1, 0, 1, 0, 0, 0],
     [1, 1, 0, 0, 0, 1, 0, 1, 0, 0],
     [0, 1, 0, 0, 0, 0, 1, 0, 1, 0],
     [0, 1, 0, 0, 0, 0, 0, 1, 0, 1],
     [0, 1, 1, 0, 0, 0, 0, 0, 1, 0]]

def smeh(ms):
    ss = []
    for i in range(len(ms[0])):
        for j in range(len(ms[0])):
            if ms[i][j] != 0:
                ss.append([i, j, ms[i][j]])
    return ss

#@profile
def tre(n,M):
    m = M
    tre = [[0 for j in range(n)] for i in range(n)]
    if n < 10:
        for i in range(n):
            for j in range(n):
                tre[i][j] = m[i][j]
    else:
        for i in range(len(m)):
            for j in range(len(m)):
                tre[i][j] = m[i][j]
        for i in range(9, len(tre) - 1):
            tre[i + 1][i] = 1
            tre[i][i + 1] = 1
        k = 2
        for i in range(10, len(tre)):
            if i % 2 == 0:
                tre[k][i] = 1
                tre[i][k] = 1
            if i % 2 == 1:
                tre[k][i] = 1
                tre[i][k] = 1
                k = k + 1
                tre[k][i] = 1
                tre[i][k] = 1
    for i in range(len(tre)):
        for j in range(len(tre)):
            if tre[i][j] == 1:
                tre[j][i] = 0
    ss = smeh(tre)
    kk = []

    for i in range(len(ss)):
        kk.append((ss[i][0], ss[i][1]))
    return kk,tre

def poisk_cmp_sv(M):
    result = []
    n = len(M)
    for i in range(n):
        a = []
        a.append(i)
        for j in range(n):
            if M[i][j] > 0:
                a.append(j)
        f = 0
        for k in a:
            for g in result:
                if k in g:
                    f += 1
                    result[result.index(g)] = add(a, g)
        if f == 0:
            result.append(a)
    return check(result)

def add(a, g):
    for i in a:
        if i not in g:
            g.append(i)
    return g

def check(result):
    n = len(result)
    for i in range(n):
        for j in range(len(result[i])):
            f = 0
            for k in range(i+1, n):
                if result[i][j] in result[k]:
                    result[k] = add(result[i], result[k])
                    result[i] = 'err'
                    f = 1
                    break
            if f == 1:
                break
    while 'err' in result:
        result.remove('err')
    return result


def gpr(kk,N):
    G = ig.Graph(directed=False)
    G.add_vertices(N)
    G.vs['label'] = range(N)
    G.add_edges(kk)
    G.es['weight'] = [1 for i in range(N)]
    ig.plot(G, bbox=(300, 300), vertex_label_color='black',
            vertex_label_size=10, vertex_size=20, vertex_color='white',
            edge_width=[edge for edge in G.es['weight']])
    return 0


if __name__ == "__main__":
    print(poisk_cmp_sv(MM))
    gpr(tre(N, M)[0],N)
    ss = smeh(MM)
    kk = []
    for i in range(len(ss)):
        kk.append((ss[i][0], ss[i][1]))
    gpr(kk,6)