from random import randint
from copy import copy, deepcopy
from pprint import pprint

matrix = [
    [0, 1, 0, 0, 1],
    [1, 0, 1, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 1, 0, 1],
    [1, 0, 0, 1, 0]
]

cycle = [[1, 2], [2, 3], [3, 4], [4, 5], [5, 1]]


def random_graph():
    """
    Составлем новую зашифрованную матрицу на основе изначальной
    :return:
    """
    _list = []
    _dict_no = dict()
    _dict_on = dict()
    # случайным образом выбираем обозначения вершин
    for i in range(1, len(matrix)+1):
        value = randint(1, len(matrix))
        while value in _list:
            value = randint(1, len(matrix))
        _list.append(value)
        _dict_no[value] = i
        _dict_on[i] = value
    rand_matrix = []
    # создаем новую матрицу в соответствии с новыми номерами вершин
    for i in range(len(matrix)):
        _list_m = []
        for j in range(len(matrix)):
            value = 0 if i+1 == j+1 else matrix[_dict_no[i+1]-1][_dict_no[j+1]-1]
            # добавляем случайные числа
            _list_m.append(str(value) + str(randint(1, 5)))
        rand_matrix.append(_list_m)
    # вовзращаем матрицу H и словари соответствия с изначальной матрицей
    return rand_matrix, _dict_no, _dict_on


def chiper(rand_matrix, N):
    """
    Шифруем матрицу
    :param rand_matrix:
    :param N:
    :return:
    """
    F = deepcopy(rand_matrix)
    for i in range(len(F)):
        for j in range(len(F)):
            F[i][j] = (int(F[i][j]) ** 3) % N
    return F


def check_morf(H1, F, N, d):
    """
    Доказательство изоморфизма
    :param H1:
    :param F:
    :param N:
    :param d:
    :return:
    """
    test = deepcopy(H1)
    for i in range(len(test)):
        for j in range(len(test)):
            test[i][j] = (int(test[i][j]) ** d) % N
    return True if test == F else False


def get_H(H1):
    test = deepcopy(H1)
    for i in range(len(test)):
        for j in range(len(test)):
            test[i][j] = int(test[i][j]) // 10
    return test


def check2(H1, dict_no):
    """
    Убеждаемся что H и G это один и тот же граф
    :param H1:
    :param dict_no:
    :return:
    """
    test = get_H(H1)
    test_matrix = []
    for i in range(len(test)):
        _list_m = []
        for j in range(len(test)):
            value = 0 if i + 1 == j + 1 else test[dict_no[i + 1] - 1][dict_no[j + 1] - 1]
            _list_m.append(value)
        test_matrix.append(_list_m)
    return True if test_matrix == matrix else False


def new_cycle(dict_on):
    """
    В соответствии со словарем соответстия изначальной матрицы
    и зашифрованной составляем новый гамльтонов цикл
    :param dict_on:
    :return:
    """
    new_cycle = []
    for c in cycle:
        new_cycle.append([dict_on[c[0]], dict_on[c[1]]])
    return new_cycle


def check_cycle(new_cycle, F, H1, N, d):
    """
    Проверка гамильтонова цикла
    :param new_cycle:
    :param F:
    :param H1:
    :param N:
    :param d:
    :return:
    """
    for i in range(len(new_cycle)):
        new_cycle[i].append(int(H1[new_cycle[i][0]-1][new_cycle[i][1]-1]))

    for i in range(len(new_cycle)):
        t = (new_cycle[i][2] ** d) % N
        if F[new_cycle[i][0]-1][new_cycle[i][1]-1] != t:
            return False
    return True


def check_cycle_2(new_cycle):
    """
    Проверка что гамильтонов цикл проходит через каждую вершину только один раз
    :param new_cycle:
    :return:
    """
    test = []
    for c in new_cycle:
        if c[1] not in test:
            test.append(c[1])
        else:
            return False
    return True


if __name__ == '__main__':
    H1, dict_no, dict_on = random_graph()
    new_cycle = new_cycle(dict_on)
    N = 55
    d = 3
    F = chiper(H1, N)
    check = check_morf(H1, F, N, d)
    check_2 = check2(H1, dict_on)
    check_3 = check_cycle(new_cycle, F, H1, N, d)
    check_4 = check_cycle_2(new_cycle)
    print('Исходная матрица')
    pprint(matrix)
    print()
    print('Гамильтонов цикл')
    print(cycle)
    print()
    print('Матрица H')
    pprint(H1)
    print()
    print('Гамильтонов цикл')
    print(new_cycle)
    print()
    print('Матрица F')
    pprint(F)
    print('Проверка на изоморфность:', check)
    print('H и G один и тот же граф:', check_2)
    print('Проверка наличия цикла:', check_3)
    print('Проверка, что цикл гамильтонов:', check_4)