import igraph
from pprint import pprint
import sys
import time
names = ['Pete', 'Stuart', 'John', 'George',
         'Paul', 'Ringo', 'Tommy', 'Chas', 'Norman']
     #1  2  3  4  5  6  7  8  9
M = [[0, 6, 0, 0, 0, 0, 0, 0, 0], # 1 Pete
     [0, 0, 0, 3, 0, 0, 0, 0, 0], # 2 Stuart
     [0, 1, 0, 0, 1, 0, 4, 0, 0], # 3 John
     [0, 0, 4, 0, 0, 0, 0, 0, 0], # 4 George
     [0, 0, 0, 6, 0, 0, 3, 0, 0], # 5 Paul
     [0, 0, 1, 3, 0, 0, 0, 0, 0], # 6 Ringo
     [0, 0, 0, 0, 0, 1, 0, 0, 2], # 7 Tommy
	 [0, 0, 0, 0, 0, 2, 0, 0, 0], # 8 Chas
 	 [0, 0, 0, 0, 0, 0, 0, 4, 0]] # 9 Norman


def toFixed(numObj, digits=0):
    return f"{numObj:.{digits}f}"


def sp_sm(M, k=1):
    n = len(M)
    spisok_smej = []
    rebra = []
    ves = []
    for i in range(n):
        for j in range(n):
            if M[i][j] != 0:
                spisok_smej.append([i+1, j+1, M[i][j]])
                rebra.append((i, j))
                ves.append(M[i][j])
    if k == 1:
        return rebra, ves
    if k == 2:
        return spisok_smej


def graph(M, names):
    G = igraph.Graph(directed=True)
    G.add_vertices(9)
    G.vs["label"] = names
    mas = sp_sm(M)
    G.add_edges(mas[0])
    G.es['label'] = mas[1]
    igraph.plot(G, bbox=(1000, 1000), vertex_label_color='black',
                vertex_label_size=20, vertex_size=100, vertex_color='white')


def massiv_zapisey(M, names):
    result = []
    for i in range(len(M)):
        result.append(['№ вершины: ', 'Имя: ', 'Ко-во детей: ', 'Их номера: ', 'Кол-во родителей: ', 'Их номера: ', 'Кол-во соседей: ', 'Их номера: ', 'Сумма инцедентныз ребер: '])
        result[i][0] += str(i+1)
        result[i][1] += names[i]
        kd, nd = 0, ''
        kr, nr = 0, ''
        sir = 0
        for j in range(len(M)):
            if M[i][j] > 0:
                sir += M[i][j]
                kd += 1
                nd += str(j+1) + ' '
            if M[j][i] > 0:
                sir += M[j][i]
                kr += 1
                nr += str(j+1) + ' '
        result[i][2] += str(kd)
        result[i][3] += nd
        result[i][4] += str(kr)
        result[i][5] += nr
        result[i][6] += str(kd + kr)
        result[i][7] += nd + nr
        result[i][8] += str(sir)
        nd = ''; nr = ''
    return result
ss = sp_sm(M,k=2)
mz = massiv_zapisey(M, names)

# Матрица смежности
def sosedi_ms(M, names):
    num = int(input('Введите номер вершины: '))-1
    if num == -1:
        print('Вершины с таким номером не существует')
    else:
        result = 'Соседи: '
        for i in range(len(M)):
            if M[num][i] > 0:
                result += names[i] + ', '
            if M[i][num] > 0:
                result += names[i] + ', '
        print(result)
def chains_ms(M):
    num = input('Номера вершин для цепи: ')
    p = 0
    for i in range(len(num)-1):
        v = int(num[i]) - 1
        vv = int(num[i+1]) - 1
        if M[v][vv] > 0:
            p = 1
            continue
        else:
            break
    if p != 0:
        print('Заданная последовательность образует цепь')
    else:
        print('Не образует')
def versh_ms(M):
    num = int(input('Введите вес: '))
    result = 'Номера вершин, сумма весов инц ребер которых больше '+ str(num) + ': '
    for i in range(len(M)):
        sum = 0
        for j in range(len(M)):
            if M[i][j] > 0:
                sum += M[i][j]
            if M[j][i] > 0:
                sum += M[j][i]
        if sum > num:
            result += str(i+1) + ' '
    print(result)
def kolreb_ms(M):
    nums = 0
    for i in range(len(M)):
        for j in range(len(M)):
            if M[i][j] > 0:
                nums += 1
    print('Ребер = ' + str(nums))
# Список смежности
def sosedi_ss(ss):
    M = ss
    num = int(input('Введите номер вершины: '))
    result = 'Номера соседей заданной вершины: '
    for i in M:
        if i[0] == num:
            result += str(i[1]) + ' '
        if i[1] == num:
            result += str(i[0]) + ' '
    print(result)
def chain_ss(ss):
    nums = input('Введите последовательность: ')
    p = 0
    M = ss
    flag = False
    for i in range(len(nums)-1):
        for j in M:
            if int(nums[i]) == j[0] and int(nums[i+1]) == j[1]:
                p = 1
                break
            else:
                p = 0
                flag = True
        if flag:
            break
    if p == 1:
        print('Заданная последовательность цикл образует!')
    else:
        print('Не образует!')
def versh_ss(ss, name):
    M = ss
    num = int(input('Введите величиу веса: '))
    result = "Вершины, сумма весов которых больше " + str(num) + ": "
    for i in range(len(name)):
        max = 0
        for k in M:
            if k[0] == i+1 or k[1] == i+1:
                max += k[2]
        if max > num:
            result += str(i+1) + ' '
    print(result)
def kolreb_ss(ss):
    M = ss
    print('Ребер = ' + str(len(M)))
# Массив записей
def sosedi_mz(mz):
    M = mz
    num = input('Введите номер вершины: ')
    for i in M:
        if num in i[0]:
            print(i[7])
def chains_mz(mz):
    M = mz
    nums = input('Введте последовательность: ')
    p = 0
    for i in range(len(nums)-1):
        for j in M:
           if nums[i] in j[0] and nums[i+1] in j[3]:
               p = 1
               break
           else:
               p = 0
               continue
        if p == 0:
            break
    if p == 1:
        print('Образует последовательность')
    else:
        print('Не образует')
def versh_mz(mz):
    M = mz
    num = int(input('Введите вес:'))
    result = 'Номера вершин: '
    for i in M:
        if int(i[8][len(i[8])-2:len(i[8])]) > num:
            result += i[0][len(i[0])-2:len(i[0])]
    print(result)
def kolreb_mz(mz):
    M = mz
    res = 0
    for i in M:
        res += int(i[6][len(i[6])-2:len(i[6])])
    print('Ребер = ' + str(int(res/2)))

# Задание 3:
print(ss)

# Задание 4
graph(M, names)

# Задание 5
pprint(mz)

# Задание 6
print('Для матрицы смежности')
sosedi_ms(M, names)
chains_ms(M)
versh_ms(M)
kolreb_ms(M)
print('Для списка смежности')
sosedi_ss(ss)
chain_ss(ss)
versh_ss(ss, names)
kolreb_ss(ss)
print('Для массива записей')
sosedi_mz(mz)
chains_mz(mz)
versh_mz(mz)
kolreb_mz(mz)
# Задание 7
print('Размер массива записей: ' + str(sys.getsizeof(mz)) + ' байт')
print('Размер матрицы смежности: ' + str(sys.getsizeof(M)) + ' байт')
print('Размер списка смежности: ' + str(sys.getsizeof(ss)) + ' байт')


def sosedi_ms8(M, names):
    num = 6
    result = 'Соседи: '
    for i in range(len(M)):
        if M[num][i] > 0:
            result += names[i] + ', '
        if M[i][num] > 0:
            result += names[i] + ', '
def chains_ms8(M):
    num = '1234'
    p = 0
    for i in range(len(num)-1):
        v = int(num[i]) - 1
        vv = int(num[i+1]) - 1
        if M[v][vv] > 0:
            p = 1
            continue
        else:
            break
def versh_ms8(M):
    num = 10
    result = 'Номера вершин, сумма весов инц ребер которых больше '+ str(num) + ': '
    for i in range(len(M)):
        sum = 0
        for j in range(len(M)):
            if M[i][j] > 0:
                sum += M[i][j]
            if M[j][i] > 0:
                sum += M[j][i]
        if sum > num:
            result += str(i+1) + ' '
def kolreb_ms8(M):
    nums = 0
    for i in range(len(M)):
        for j in range(len(M)):
            if M[i][j] > 0:
                nums += 1

def sosedi_ss8(ss):
    M = ss
    num = 4
    result = 'Номера соседей заданной вершины: '
    for i in M:
        if i[0] == num:
            result += str(i[1]) + ' '
        if i[1] == num:
            result += str(i[0]) + ' '
def chain_ss8(ss):
    nums = '1461'
    p = 0
    M = ss
    flag = False
    for i in range(len(nums)-1):
        for j in M:
            if int(nums[i]) == j[0] and int(nums[i+1]) == j[1]:
                p = 1
                break
            else:
                p = 0
                flag = True
        if flag:
            break
def versh_ss8(ss, name):
    M = ss
    num = 7
    result = "Вершины, сумма весов которых больше " + str(num) + ": "
    for i in range(len(name)):
        max = 0
        for k in M:
            if k[0] == i+1 or k[1] == i+1:
                max += k[2]
        if max > num:
            result += str(i+1) + ' '
def kolreb_ss8(ss):
    M = ss
    len(M)

def sosedi_mz8(mz):
    M = mz
    num = '5'
    for i in M:
        if num in i[0]:
            break
def chains_mz8(mz):
    M = mz
    nums = '1234'
    p = 0
    for i in range(len(nums)-1):
        for j in M:
           if nums[i] in j[0] and nums[i+1] in j[3]:
               p = 1
               break
           else:
               p = 0
               continue
        if p == 0:
            break
def versh_mz8(mz):
    M = mz
    num = 8
    result = 'Номера вершин: '
    for i in M:
        if int(i[8][len(i[8])-2:len(i[8])]) > num:
            result += i[0][len(i[0])-2:len(i[0])]
def kolreb_mz8(mz):
    M = mz
    res = 0
    for i in M:
        res += int(i[6][len(i[6])-2:len(i[6])])
# Задание 8
t, t1, t2, t3, t4, t5, t6, t7, t8, t9, t10, t11 = 0, 0, 0 ,0, 0, 0, 0, 0, 0, 0, 0, 0
for i in range(pow(10,6)):
    a = time.time()
    sosedi_ms8(M, names)
    b = time.time()
    t += b - a

    a1 = time.time()
    chains_ms8(M)
    b1 = time.time()
    t1 += b1 - a1

    a2 = time.time()
    versh_ms8(M)
    b2 = time.time()
    t2 += b2 - a2

    a3 = time.time()
    kolreb_ms8(M)
    b3 = time.time()
    t3 += b3 - a3

    a4 = time.time()
    sosedi_ss8(ss)
    b4 = time.time()
    t4 += b4 - a4

    a5 = time.time()
    chain_ss8(ss)
    b5 = time.time()
    t5 += b5 - a5

    a6 = time.time()
    versh_ss8(ss, names)
    b6 = time.time()
    t6 += b6 - a6

    a7 = time.time()
    kolreb_ss8(ss)
    b7 = time.time()
    t7 += b7 - a7

    a8 = time.time()
    sosedi_mz8(mz)
    b8 = time.time()
    t8 += b8 - a8

    a9 = time.time()
    chains_mz8(mz)
    b9 = time.time()
    t9 += b9 - a9

    a10 = time.time()
    versh_mz8(mz)
    b10 = time.time()
    t10 += b10 - a10

    a11 = time.time()
    kolreb_mz8(mz)
    b11 = time.time()
    t11 += b11 - a11

print('Время выполнения поиска всех соседей через матрицу смежности: '+ str(t/(pow(10,6))))
print('Время выполнения поиска цепи в матрице смежности: '+ str(t1/(pow(10,6))))
print('Время выполнения поиска всех вершин вес которых больше 10 через матрицу смежности: '+ str(t2/(pow(10,6))))
print('Время выполнения поиска количества ребер через матрицу смежности: '+ str(t3/(pow(10,6))))

print('Время выполнения поиска всех соседей через список смежности: '+ str(t4/(pow(10,6))))
print('Время выполнения поиска цепи в список смежности: '+ str(t5/(pow(10,6))))
print('Время выполнения поиска всех вершин вес которых больше 10 через список смежности: '+ str(t6/(pow(10,6))))
print('Время выполнения поиска количества ребер через список смежности: '+ str(t7/(pow(10,6))))

print('Время выполнения поиска всех соседей через массив записей: '+ str(t8/(pow(10,6))))
print('Время выполнения поиска цепи в массив записей: '+ str(t9/(pow(10,6))))
print('Время выполнения поиска всех вершин вес которых больше 10 через массив записей: '+ str(t10/(pow(10,6))))
print('Время выполнения поиска количества ребер через массив записей: '+ str(t11/(pow(10,6))))