diff options
Diffstat (limited to 'lab2/lab2.py')
| -rw-r--r-- | lab2/lab2.py | 391 |
1 files changed, 391 insertions, 0 deletions
diff --git a/lab2/lab2.py b/lab2/lab2.py new file mode 100644 index 0000000..e1616a9 --- /dev/null +++ b/lab2/lab2.py @@ -0,0 +1,391 @@ +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()
\ No newline at end of file |