path: root/lab2/lab2.py

import numpy as np
import math
import matplotlib.pyplot as plt


def check_reflexivity(matrix):
    diag_values = np.diagonal(matrix)
    diag_values = np.unique(diag_values)
    return int(diag_values.size == 1 and diag_values == [1])


def check_antisymmetry(matrix):
    new_matrix = np.multiply(matrix, matrix.T)
    for i in range(len(new_matrix)):
        for j in range(len(new_matrix[i])):
            if i != j and new_matrix[i][j] != 0:
                return 0
    return 1


def check_transitivity(matrix):
    mlp_mx = np.matmul(matrix, matrix)
    for i in range(len(mlp_mx)):
        for j in range(len(mlp_mx[i])):
            if mlp_mx[i][j] > 1:
                mlp_mx[i][j] = 1
    return int((mlp_mx <= matrix).all())


def order_check(relation):
    return check_antisymmetry(relation) and \
            check_reflexivity(relation) and \
            check_transitivity(relation)

############################

def reflexive_closure(matrix):
    n = len(matrix)
    for i in range(n):
        matrix[i][i] = 1


def symmetry_closure(matrix):
    n = len(matrix)
    for i in range(n):
        for j in range(n):
            if matrix[i][j]:
                matrix[j][i] = 1


def transitive_closure(matrix):
    n = len(matrix)
    for _ in range(n):
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    if matrix[i][k] and matrix[k][j]:
                        matrix[i][j] = 1


def create_equivalent_closure(bin_relation):
    relation = bin_relation.copy()
    reflexive_closure(relation)
    symmetry_closure(relation)
    transitive_closure(relation)
    return relation

###################################

def get_slices_list(relation_matrix, for_factor_set=1, attributes=None):
    n = len(relation_matrix)
    slices = []
    for i in range(n):
        slice = []
        for j in range(n):
            if relation_matrix[i][j]:
                if attributes is None:
                    slice.append(j + for_factor_set)
                else:
                    slice.append(attributes[j])
        slices.append(slice)
    return slices


def create_factor_set(bin_relation):
    slices = get_slices_list(bin_relation, 1, None)
    print("Фактор-множество данной эквивалентности:")
    print(set(map(tuple, slices)))
    return slices


def create_representative_system(factor_set):
    factor_set = sorted(factor_set, key=len)
    d = {}
    representative_system = []
    for eq_class in factor_set:
        for representative in eq_class:
            if representative not in representative_system:
                d[representative] = eq_class
                representative_system.append(representative)
                break

    print("Система представителей данного фактор-множества:")
    print(representative_system)
    for representative, eq_class in d.items():
        print(representative, "принадлежит множеству", eq_class)


####################################################

def get_dividers(l):
    d = {}
    for elem in l:
        dividers = []
        for divider in l:
            if elem % divider == 0:
                dividers.append(divider)
        d[elem] = dividers

    return d


def get_min_elem(objects, elements, k=0):
    min_elements = []
    for i in range(k, len(objects)):
        is_min = True
        for j in range(k, len(objects)):
            if objects[j][i] != 0 and i != j:
                is_min = False
        if is_min:
            min_elements.append(elements[i])
    return min_elements


def get_max_elem(some_set, objs, k=0):
    max_elements = []
    for i in range(k, len(some_set)):
        is_max = True
        for j in range(k, len(some_set)):
            if some_set[i][j] != 0 and i != j:
                is_max = False
        if is_max:
            max_elements.append(objs[i])

    return max_elements


def get_least_elem(some_set, objs):
    min_elem_list = get_min_elem(some_set, objs)
    if len(min_elem_list) != 1:
        return None
    else:
        return min_elem_list[0]


def get_greatest_elem(some_set, objs):
    max_elem_list = get_max_elem(some_set, objs)
    if len(max_elem_list) != 1:
        return None
    else:
        return max_elem_list[0]


def get_order_set_elem():
    objs = []
    print('Введите элементы множества:')
    objs = input().split()
    print("Введите значения матрицы бинарного отношения:")
    n = len(objs)
    entries = [list(map(int, input().split())) for i in range(n)]
    some_set = np.array(entries).reshape(n, n)
    if not order_check(some_set):
        print("Введённое отношение не является отношением порядка")
        return 0

    print("Минимальные элементы в множестве:", get_min_elem(some_set, objs))
    print("Максимальные элементы в множестве:", get_max_elem(some_set, objs))
    print("Наименьший элемент в множестве:", get_least_elem(some_set, objs))
    print("Наибольший элемент в множестве:", get_greatest_elem(some_set, objs))

###########################################

def get_dividers_list(n):
    dividers_list = [1]
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            dividers_list.append(i)
            dividers_list.append(n // i)
    dividers_list.append(n)
    return sorted(dividers_list)


def make_hasse():
    print('Введите элементы множества:')
    objs = input().split()
    n = len(objs)
    print("Введите значения матрицы бинарного отношения:")
    entries = [list(map(int, input().split())) for _ in range(n)]
    some_set = np.array(entries).reshape(n, n)
    if not order_check(some_set):
        print("Введенное отношение не является отношением порядка")
        return []

    hasse_levels = {key: 1 for key in objs}
    i = 0
    some_k = 0
    while True:
        min_elems = get_min_elem(some_set, objs, some_k)
        i += 1

        if not min_elems:
            break

        for elem in min_elems:
            hasse_levels[elem] = i

        some_k += len(min_elems)

    connected_values_dict = {}
    for key, value in hasse_levels.items():
        lvl_diff = 1
        connected_values = []
        relation_list = get_slices_list(some_set, 0, objs)[objs.index(key)]
        for i in relation_list:
            if hasse_levels[i] == value + lvl_diff:
                connected_values.append(i)

        connected_values = list(set(connected_values))
        connected_values.sort()
        connected_values_dict[key] = connected_values

    hasse_data = []
    for i in hasse_levels:
        hasse_data.append([i, hasse_levels[i], connected_values_dict[i]])

    # связи здесь построены снизу-вверх
    return hasse_data


def visualize_hasse(hasse_data):
    plt.xlim(-1.0, len(hasse_data) * 2)
    plt.ylim(0, len(hasse_data) * 3 + 1.5)

    lvl_to_elems = {key[1]: 0 for key in hasse_data}
    for hasse_elem in hasse_data:
        for level in lvl_to_elems:
            if hasse_elem[1] == level:
                lvl_to_elems[level] += 1

    max_lvl_elem_amount = lvl_to_elems[max(lvl_to_elems, key=lvl_to_elems.get)]

    lvl = 4
    elem_address = {}
    for hasse_elem in hasse_data:
        elem_lvl = hasse_elem[1]
        elem = hasse_elem[0]
        hasse_elem_y = elem_lvl * lvl
        hasse_elem_x = 1.5 * (max_lvl_elem_amount - lvl_to_elems[elem_lvl])
        lvl_to_elems[elem_lvl] += -1
        plt.text(hasse_elem_x - 0.1, hasse_elem_y - 0.1, f'{elem}')
        plt.scatter(hasse_elem_x + 0.1, hasse_elem_y + 0.1, s=350, facecolors='none', edgecolors='black')
        elem_address[elem] = [hasse_elem_x + 0.1, hasse_elem_y + 0.1]

    for hasse_elem in hasse_data:
        x1, y1 = elem_address[hasse_elem[0]][0], elem_address[hasse_elem[0]][1]
        for connected_elem in hasse_elem[2]:
            plt.plot([x1, elem_address[connected_elem][0]],
                     [y1 + 1, elem_address[connected_elem][1] - 1],
                     color="black")

    plt.show()

#########################################################

def get_closure_system(rel_matrix, objs, attrs):
    closure_system = [objs]
    row_slices = get_slices_list(rel_matrix.copy().T, 1, objs)
    is_empty_included = False
    for attr_i in range(len(attrs)):
        after_intersection = [list(row_slices[attr_i])]
        for closure_i in range(len(closure_system)):
            cs_set = set(closure_system[closure_i])
            intersection = set(row_slices[attr_i]) & cs_set
            intersection = sorted(intersection)
            if intersection not in after_intersection \
                    and intersection or not is_empty_included:
                after_intersection.append(intersection)

            if not intersection:
                is_empty_included = True

        if after_intersection not in closure_system:
            closure_system += after_intersection

    new_closure_system = []
    for closure in closure_system:
        if closure not in new_closure_system:
            new_closure_system.append(closure)

    print("Система замыканий:", new_closure_system)
    return closure_system


def get_context(closure, rel_matrix, objs, attrs):
    if not closure:
        context = attrs
    else:
        column_slices = get_slices_list(rel_matrix, 1, attrs)
        list_of_sets = []
        for elem in closure:
            obj_i = objs.index(elem)
            list_of_sets.append(set(column_slices[obj_i]))

        context = list_of_sets[0]
        for cur_set in list_of_sets:
            context = context.intersection(cur_set)

    return sorted(context)


def make_lattice_concept():
    print("Введите элементы множества:")
    objects = input().split()
    print("Введите множество атрибутов:")
    attributes = input().split()
    print('Введите матрицу отношения на декартовом произведении множеств объектов и атрибутов:')
    entries = []
    for _ in range(len(objects)):
        entries.extend(map(int, input().split()))
    relation_matrix = np.array(entries).reshape(len(objects), len(attributes))
    closure_system = get_closure_system(relation_matrix, objects, attributes)

    lattice_concept = []
    for closure in closure_system:
        context = get_context(closure, relation_matrix, objects, attributes)
        concept = closure, context
        lattice_concept.append(concept)

    new_lattice_concept = []
    for concept in lattice_concept:
        if concept not in new_lattice_concept:
            new_lattice_concept.append(concept)

    print("Решетка концептов:", new_lattice_concept)

##################################################

def main():
    print("1. Эквивалентное замыкание, система представителей")
    print("2. минимальные и максимальные элементы")
    print("3. Построение диаграммы Хассе")
    print("4. Построение решётки концептов")
    task = int(input("Выберите задачу: "))

    if task == 1:
        n = int(input("Введите размер матрицы: "))
        l = []

        print(f"На следующих {n} строках введите матрицу:")
        for _ in range(n):
            l.extend(map(int, input().split()))
        matrix = np.array(l, dtype=bool).reshape(n, n)

        # 1 - эквивалентное замыкание
        eq = create_equivalent_closure(matrix)
        print("Матрица эквивалентного замыкания:")
        print(eq.astype(int))

        # 2 - система представителей
        factor_set = create_factor_set(matrix)
        create_representative_system(factor_set)

    elif task == 2:

        # 3 - минимальные (максимальные) и наименьший (наибольший) элементы множества
        get_order_set_elem()
    
    elif task == 3:
        # 4 - Диаграмма Хассе
        hasse_data = make_hasse()
        if hasse_data:
            print(hasse_data)
            visualize_hasse(hasse_data)

    elif task == 4:
        # 5 - Решётка концептов
        make_lattice_concept()


if __name__ == "__main__":
    main()