Определение бинарных отношений в графе (транзитивность, симметричность и рефлексивность)

graphs_jit.py

# Графы
import time
import warnings

from numba import jit
from numba.core.errors import NumbaDeprecationWarning, NumbaWarning

warnings.simplefilter('ignore', category=NumbaDeprecationWarning)
warnings.simplefilter('ignore', category=NumbaWarning)


@jit
def reflex(n, m, edges):
    if n < m:
        return [False] + [edge[0] == edge[1] for edge in edges]
    return [(i, i) in edges for i in range(1, m + 1)]


@jit
def symmetric(edges):
    return [tuple(reversed(edge)) in edges for edge in edges]


@jit
def transitive(edges):
    return [(edge[0], f_edge[1]) in edges
            for edge in edges
            if edge[0] != edge[1]
            for f_edge in edges
            if edge[1] == f_edge[0] and edge[0] != f_edge[1] and f_edge[0] != f_edge[1]]


with open('input{}.txt'.format(input()), 'r') as f:
    n, m = map(int, f.readline().split())
    edges = [tuple(map(int, f.readline().split())) for _ in range(n)]
# n, m = map(int, input().split())
# edges = [tuple(map(int, input().split())) for _ in range(n)]

if n == 0:
    print('Антирефлексивное' if m != 0 else 'Любое по рефлексивности')
else:
    reflex_list = reflex(n, m, edges)
    if all(reflex_list):
        print('Рефлексивное')
    elif any(reflex_list):
        print('Не рефлексивное')
    else:
        print('Антирефлексивное')

if n == 0:
    print('Любое по симметричности')
else:
    symm_list = symmetric(edges)
    if all(symm_list):
        print('Симметричное')
    elif any(symm_list):
        print('Не симметричное')
    else:
        print('Антисимметричное')

if n <= 2:
    print('Любое по транзитивности')
else:
    transit_list = transitive(edges)
    if not transit_list:
        print('Любое по транзитивности')
    elif all(transit_list):
        print('Транзитивное')
    elif any(transit_list):
        print('Не транзитивное')
    else:
        print('Антитранзитивное')

graphs_vanila.py

# -*- coding: utf-8 -*-
# Графы

def calculate(n: int, m: int, edges: list[tuple[int, int]]) -> tuple[set[bool], set[bool], set[bool]]:
    reflex, symm, transit = set(), set(), set()
    if n == 0:
        pass
    elif n < m:  # рефлексивности не достичь, не хватает рёбер для всех вершин
        reflex.add(False)
        for edge in edges:
            if edge[0] == edge[1]:
                reflex.add(True)
                symm.add(True)
            else:
                if n > 2:
                    for f_edge in edges:
                        if edge[1] == f_edge[0] and edge[0] != f_edge[1] and f_edge[0] != f_edge[1]:
                            transit.add((edge[0], f_edge[1]) in edges)
                        if transit == {True, False}:
                            break
                symm.add((edge[1], edge[0]) in edges)

            if reflex == symm == transit == {True, False} or n <= 2 and reflex == symm == {True, False}:
                break
    elif n == m:
        for i in range(n):
            reflex.add((i + 1, i + 1) in edges)
            symm.add((edges[i][1], edges[i][0]) in edges)
            if n > 2 and edges[i][0] != edges[i][1]:
                for f_edge in edges:
                    if edges[i][1] == f_edge[0] and edges[i][0] != f_edge[1] and f_edge[0] != f_edge[1]:
                        transit.add((edges[i][0], f_edge[1]) in edges)
                    if transit == {True, False}:
                        break
            if reflex == symm == transit == {True, False} or n <= 2 and reflex == symm == {True, False}:
                break
    else:
        for i in range(1, m + 1):
            reflex.add((i, i) in edges)
            if reflex == {True, False}:
                break
        for edge in edges:
            symm.add((edge[1], edge[0]) in edges)
            if n > 2 and edge[0] != edge[1]:
                for f_edge in edges:
                    if edge[1] == f_edge[0] and edge[0] != f_edge[1] and f_edge[0] != f_edge[1]:
                        transit.add((edge[0], f_edge[1]) in edges)
                    if transit == {True, False}:
                        break
            if symm == transit == {True, False} or n <= 2 and symm == {True, False}:
                break
    return reflex, symm, transit


n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(n)]

reflex_list, symm_list, transit_list = calculate(n, m, edges)

if n == 0:
    print('Антирефлексивное' if m != 0 else 'Любое по рефлексивности')
else:
    if all(reflex_list):
        print('Рефлексивное')
    elif any(reflex_list):
        print('Не рефлексивное')
    else:
        print('Антирефлексивное')

if n == 0:
    print('Любое по симметричности')
else:
    if all(symm_list):
        print('Симметричное')
    elif any(symm_list):
        print('Не симметричное')
    else:
        print('Антисимметричное')

if n <= 2:
    print('Любое по транзитивности')
else:
    if not transit_list:
        print('Любое по транзитивности')
    elif all(transit_list):
        print('Транзитивное')
    elif any(transit_list):
        print('Не транзитивное')
    else:
        print('Антитранзитивное')