Relacije u SAGE-u ⇨ implementacija funkcija

verzija: SageMath 9.4

Ovdje su implementriane neke dodatne funkcije za lakši i brži rad s relacijama u SAGE-u.

Sve implementirane funkcije možete koristiti u svojem notebooku tako da učitate datoteku relacije.sage.

Binarna relacija zadana pomoću neke formule

Funkcija relacija_formula definira binarnu relaciju na skupu skup (koji je zadan preko liste) formulom fun. Parametar izlaz može imati tri vrijednosti: "matrica", "elementi", "graf" ovisno o tome želimo li dobiti matricu incidencije, elemente ili graf relacije zadane formulom. Po defaultu parametar izlaz ima vrijednost "matrica".  Parametar velicinaVrha utječe samo na veličinu vrha u grafičkom prikazu grafa.

In [1]:
def relacija_formula(skup,fun,izlaz="matrica",velicinaVrha=700, oznakaVrha=True):
    if izlaz=="matrica":
        bul=lambda x: 1 if x==True else 0
        matrica=matrix([[bul(fun(x,y)) for y in skup] for x in skup])
        return matrica
    elif izlaz=="elementi":
        elementi=[]
        for x in skup:
            for y in skup:
                if fun(x,y): elementi.append((x,y))
        return elementi
    elif izlaz=="graf":
        graf=DiGraph({},loops=True)
        graf.add_vertices(skup)
        for x in skup:
            for y in skup:
                if fun(x,y): graf.add_edge(x,y)
        slika=graf.plot(vertex_size=velicinaVrha,graph_border=True,layout="circular",vertex_labels=oznakaVrha)
        return slika
    else:
        return "opcija 'izlaz' mora imati neku od tri vrijednosti: matrica, elementi, graf"

Binarna relacija zadana pomoću matrice incidencije

Funkcija relacija_matrica definira binarnu relaciju pomoću kvadratne matrice matrica koja ima samo nule i jedinice. Parametar izlaz može imati dvije vrijednosti: "elementi" ili "graf" ovisno o tome želimo li dobiti elemente ili graf relacije zadane matricom incidencije. Po defaultu parametar izlaz ima vrijednost "elementi". Parametrom oznakeElemenata (kojeg zadajemo preko liste) određujemo imena elemenata skupa na kojemu je relacija zadana (ta lista mora imati onoliko elemenata koliki je red matrice incidencije kojom je relacija zadana). Po defaultu je vrijednost parametra oznakeElemenata postavljena na None, što znači da će elementi biti prvih n prirodnih brojeva (ukoliko je matrica incidencije reda n).  Parametar velicinaVrha utječe samo na veličinu vrha u grafičkom prikazu grafa.

In [2]:
def relacija_matrica(matrica,oznakeElemenata=None,izlaz="elementi",velicinaVrha=700, oznakaVrha=True):
    if matrica.nrows()!=matrica.ncols(): return "Error: Na ulazu mora biti kvadratna matrica"
    for i in range(matrica.nrows()):
        for j in range(matrica.ncols()):
            if matrica[i,j]!=0 and matrica[i,j]!=1: return "Error: Elementi matrice moraju biti nule ili jedinice"
    if oznakeElemenata==None: oznakeElemenata=range(1,matrica.nrows()+1)
    if len(oznakeElemenata)!=matrica.nrows(): return "lista 'oznakeElemenata' mora imati broj elemenata jednak broju redaka ulazne matrice"
    if izlaz=="elementi":
        elementi=[]
        for i in range(matrica.nrows()):
            for j in range(matrica.ncols()):
                if matrica[i,j]==1: elementi.append((oznakeElemenata[i],oznakeElemenata[j]))
        return elementi
    elif izlaz=="graf":
        graf=DiGraph({},loops=True)
        graf.add_vertices(oznakeElemenata)
        for i in range(matrica.nrows()):
            for j in range(matrica.ncols()):
                if matrica[i,j]==1: graf.add_edge(oznakeElemenata[i],oznakeElemenata[j])
        slika=graf.plot(vertex_size=velicinaVrha,graph_border=True,layout="circular",vertex_labels=oznakaVrha)
        return slika
    else:
        return "opcija 'izlaz' mora imati neku od dvije vrijednosti: elementi, graf"

Binarna relacija zadana pomoću svojih elemenata

Funkcija relacija_elementi definira binarnu relaciju nabrajanjem njezinih elemenata. Parametar elementi sadrži elemente binarne relacije, a zadaje se kao lista uređenih parova pri čemu treba paziti da elementi uređenih parova pripadaju skupu skup na kojemu je relacija definirana (parametar skup se također zadaje preko liste). Parametar izlaz može imati dvije vrijednosti: "matrica" ili "graf" ovisno o tome želimo li dobiti matricu incidencije ili graf relacije zadane svojim elementima. Po defaultu parametar izlaz ima vrijednost "matrica". Parametar velicinaVrha utječe samo na veličinu vrha u grafičkom prikazu grafa.

In [3]:
def relacija_elementi(skup,elementi,izlaz="matrica",velicinaVrha=700,oznakaVrha=True):
    if not(set(elementi).issubset(set(map(lambda x:tuple(x),list(cartesian_product([skup,skup])))))): 
        return "Error: Nije dobro definirana relacija na zadanom skupu"
    if izlaz=="matrica":
        matrica=matrix(len(skup))
        for i in range(len(skup)):
            for j in range(len(skup)):
                if (skup[i],skup[j]) in elementi: matrica[i,j]=1
        return matrica
    elif izlaz=="graf":
        graf=DiGraph({},loops=True)
        graf.add_vertices(skup)
        for x in skup:
            for y in skup:
                if (x,y) in elementi: graf.add_edge(x,y)
        slika=graf.plot(vertex_size=velicinaVrha,graph_border=True,layout="circular",vertex_labels=oznakaVrha)
        return slika
    else:
        return "opcija 'izlaz' mora imati neku od dvije vrijednosti: matrica, graf"

Binarna relacija zadana pomoću grafa

Funkcija relacija_graf definira binarnu relaciju pomoću grafa. Parametar vrhovi sadrži imena vrhova grafa (tj. skup na kojemu je definirana binarna relacija), a zadaje se kao lista. Parametar digraf sadrži definiciju grafa binarne relacije, a zadaje se kao rječnik čiji ključevi su vrhovi grafa, a vrijednosti ključeva su liste koje sadrže one vrhove grafa u koje ulaze lukovi iz promatranog vrha (ključa). Parametar izlaz može imati tri vrijednosti: "graf", "matrica" ili "elementi" ovisno o tome želimo li dobiti grafički prikaz grafa relacije, matricu incidencije ili elemente relacije koja je zadana grafom. Po defaultu parametar izlaz ima vrijednost "graf". Parametar velicinaVrha  utječe samo na veličinu vrha u grafičkom prikazu grafa.

In [4]:
def relacija_graf(vrhovi,digraf,izlaz="graf",velicinaVrha=700,oznakaVrha=True):
    if izlaz=="graf":
        graf=DiGraph(digraf,loops=True)
        slika=graf.plot(vertex_size=velicinaVrha,graph_border=True,layout="circular",vertex_labels=oznakaVrha)
        return slika
    elif izlaz=="matrica":
        matrica=matrix(len(vrhovi))
        for i in range(len(vrhovi)):
            for j in range(len(vrhovi)):
                if vrhovi[j] in digraf[vrhovi[i]]: matrica[i,j]=1
        return matrica
    elif izlaz=="elementi":
        elementi=[]
        for x in vrhovi:
            for y in vrhovi:
                if y in digraf[x]: elementi.append((x,y))
        return elementi
    else:
      return "opcija 'izlaz' mora imati neku od tri vrijednosti: matrica, elementi, graf"

Ispisivanje matrice incidencije u obliku tablice

Funkcije matrica_table i matrica_html ispisuju matricu incidencije relacije u obliku tablice s označenim imenima redaka i stupaca. Općenito, ove funkcije mogu bilo koju dvodimenzionalnu python listu ispisati u obliku tablice s označenim recima i stupcima. Varijabla lista je dvodimenzionalna python lista koja će se ispisati u obliku tablice. Varijable redak i stupac su jednodimenzionalne python liste sa željenim imenima redaka i stupaca u tablici. Funkcija matrica_table daje ispis tablice u tekstualnom obliku, a funkcija matrica_html daje ispis tablice u html obliku.

In [5]:
def matrica_table(lista,redak,stupac):
    redak=list(redak)
    stupac=list(stupac)
    lista=list(map(list,list(lista)))
    lista2=list(map(list, zip(*lista)))
    ds=list(map(lambda x: len(str(max(x))),lista2))
    ds2=list(map(lambda x: len(str(x)),stupac))
    duljine_stupaca=list(map(max,zip(ds,ds2)))
    redak=list(map(lambda x: str(x)+'|', redak))
    dsnula=max(map(lambda x:len(x),redak))
    duljine_stupaca=[dsnula]+duljine_stupaca
    stupac=[' '*(dsnula-1)+'|']+stupac
    broj_crtica='-'*(sum(duljine_stupaca)+len(duljine_stupaca)-1)
    for k in range(len(lista)):
        lista[k]=[redak[k]]+lista[k]
    for k in range(len(stupac)):
        print(str(stupac[k]).rjust(duljine_stupaca[k]), end=' ')
    print()
    print(broj_crtica)
    for element in lista:
        for k in range(len(element)):
            print(str(element[k]).rjust(duljine_stupaca[k]), end=' ')
        if element!=lista[-1]: print()
In [6]:
def matrica_html(lista,redak,stupac):
    redak=list(redak)
    stupac=list(stupac)
    lista=list(map(list,list(lista)))
    stupac=[' ']+stupac
    for k in range(len(lista)):
        lista[k]=[redak[k]]+lista[k]
    lista=[stupac]+lista
    return table(lista)

Svojstva binarnih relacija

Donje implementacije podrazumijevaju da je relacija zadana preko matrice incidencije. Ime same funkcije govori koje svojstvo relacije ona ispituje. Ako relacija zadovoljava određeno svojstvo, funkcija vraća vrijednost True, a ukoliko ga ne zadovoljava, vraća se vrijednost False.

In [7]:
def refleksivna(matrica):
    if matrica.nrows()!=matrica.ncols(): return "Error: Na ulazu mora biti kvadratna matrica"
    for i in range(matrica.nrows()):
        for j in range(matrica.ncols()):
            if matrica[i,j]!=0 and matrica[i,j]!=1: return "Error: Elementi matrice moraju biti nule ili jedinice"
    for a in range(matrica.nrows()):
        if matrica[a,a]==0: return False
    return True
In [8]:
def irefleksivna(matrica):
    if matrica.nrows()!=matrica.ncols(): return "Error: Na ulazu mora biti kvadratna matrica"
    for i in range(matrica.nrows()):
        for j in range(matrica.ncols()):
            if matrica[i,j]!=0 and matrica[i,j]!=1: return "Error: Elementi matrice moraju biti nule ili jedinice"
    for a in range(matrica.nrows()):
        if matrica[a,a]==1: return False
    return True
In [9]:
def simetricna(matrica):
    if matrica.nrows()!=matrica.ncols(): return "Error: Na ulazu mora biti kvadratna matrica"
    for i in range(matrica.nrows()):
        for j in range(matrica.ncols()):
            if matrica[i,j]!=0 and matrica[i,j]!=1: return "Error: Elementi matrice moraju biti nule ili jedinice"
    for a in range(matrica.nrows()):
        for b in range(matrica.nrows()):
            if matrica[a,b]!=matrica[b,a]: return False
    return True
In [10]:
def antisimetricna(matrica):
    if matrica.nrows()!=matrica.ncols(): return "Error: Na ulazu mora biti kvadratna matrica"
    for i in range(matrica.nrows()):
        for j in range(matrica.ncols()):
            if matrica[i,j]!=0 and matrica[i,j]!=1: return "Error: Elementi matrice moraju biti nule ili jedinice"
    for a in range(matrica.nrows()):
        for b in range(matrica.nrows()):
            if a!=b and matrica[a,b]+matrica[b,a]>1: return False
    return True
In [11]:
def asimetricna(matrica):
    if matrica.nrows()!=matrica.ncols(): return "Error: Na ulazu mora biti kvadratna matrica"
    for i in range(matrica.nrows()):
        for j in range(matrica.ncols()):
            if matrica[i,j]!=0 and matrica[i,j]!=1: return "Error: Elementi matrice moraju biti nule ili jedinice"
    for a in range(matrica.nrows()):
        for b in range(matrica.nrows()):
            if matrica[a,b]+matrica[b,a]>1: return False
    return True
In [12]:
def kompletna(matrica):
    if matrica.nrows()!=matrica.ncols(): return "Error: Na ulazu mora biti kvadratna matrica"
    for i in range(matrica.nrows()):
        for j in range(matrica.ncols()):
            if matrica[i,j]!=0 and matrica[i,j]!=1: return "Error: Elementi matrice moraju biti nule ili jedinice"
    for a in range(matrica.nrows()):
        for b in range(matrica.nrows()):
            if a!=b and matrica[a,b]+matrica[b,a]<1: return False
    return True
In [13]:
def strogo_kompletna(matrica):
    if matrica.nrows()!=matrica.ncols(): return "Error: Na ulazu mora biti kvadratna matrica"
    for i in range(matrica.nrows()):
        for j in range(matrica.ncols()):
            if matrica[i,j]!=0 and matrica[i,j]!=1: return "Error: Elementi matrice moraju biti nule ili jedinice"
    for a in range(matrica.nrows()):
        for b in range(matrica.nrows()):
            if matrica[a,b]+matrica[b,a]<1: return False
    return True
In [14]:
def tranzitivna(matrica):
    if matrica.nrows()!=matrica.ncols(): return "Error: Na ulazu mora biti kvadratna matrica"
    for i in range(matrica.nrows()):
        for j in range(matrica.ncols()):
            if matrica[i,j]!=0 and matrica[i,j]!=1: return "Error: Elementi matrice moraju biti nule ili jedinice"
    for a in range(matrica.nrows()):
        for b in range(matrica.nrows()):
            for c in range(matrica.nrows()):
                if matrica[a,c]<matrica[a,b]+matrica[b,c]-1: return False
    return True
In [15]:
def relacija_ekvivalencije(matrica):
    return refleksivna(matrica) and simetricna(matrica) and tranzitivna(matrica)
In [16]:
def parcijalni_uredjaj(matrica):
    return refleksivna(matrica) and antisimetricna(matrica) and tranzitivna(matrica)
In [17]:
def linearni_uredjaj(matrica):
    return refleksivna(matrica) and antisimetricna(matrica) and tranzitivna(matrica) and strogo_kompletna(matrica)

Dvije dodatne funkcije za parcijalni uređaj

Funkcija matrica_incidencije_PUS omogućuje brzo kreiranje matrice incidencije parcijalnog uređaja koji je definiran na jedan od sljedeća dva načina:

  • varijabla uredjaj je uređeni par kojemu je prva komponenta skup na kojemu je definirani parcijalni uređaj (skup je zadan preko liste). Druga komponenta je lista uređenih parova koji predstavljaju elemente relacije. Međutim, nisu navedeni svi parovi relacije, nego samo oni koji su u Hasseovom dijagramu direktno spojeni bridom (uvažavamo da se radi o parcijalnom uređaju pa navodimo samo elemente koji su u relaciji i između njih nema drugih elemenata).
  • varijabla uredjaj je rječnik. Ključevi u rječniku su elementi skupa na kojemu je relacija definirana, a vrijednost pojedinog ključa je lista svih elemenata koji natkrivaju promatrani ključ, tj. prema kojima od ključa postoji direktni uzlazni brid u Hasseovom dijagramu. Također, u tom slučaju se koristi i varijabla redoslijed_elemenata koja je po defaultu stavljena na None. U tom slučaju se elementi skupa u matricu incidencije smještaju redoslijedom kakvim se nalaze u listi uredjaj.keys(). Ukoliko želimo sami određeni redoslijed elemenata, tada u varijablu redoslijed_elemenata spremimo listu elemenata u  željenom redoslijedu.
In [18]:
def matrica_incidencije_PUS(uredjaj,redoslijed_elemenata=None):
    bul=lambda x: 1 if x==True else 0
    pus=Poset(uredjaj)
    if type(uredjaj)==tuple:
        matrica=matrix([[bul(pus.is_lequal(x,y)) for y in uredjaj[0]] for x in uredjaj[0]])
        return matrica
    elif type(uredjaj)==dict:
        if redoslijed_elemenata==None: redoslijed_elemenata=uredjaj.keys()
        matrica=matrix([[bul(pus.is_lequal(x,y)) for y in redoslijed_elemenata] for x in redoslijed_elemenata])
        return matrica
    else:
        return "Error: nepravilno definirani parcijalni uredjaj"

Funkcija elementi_PUS omogućuje brže ispisivanje svih elemenata relacije parcijalnog uređaja. Za varijable uredjaj i redoslijed_elemenata vrijede ista objašnjenja kao i kod funkcije matrica_incidencije_PUS.

In [19]:
def elementi_PUS(uredjaj,redoslijed_elemenata=None):
    if type(uredjaj)==tuple:
        redoslijed_elemenata=uredjaj[0]
        matrica=matrica_incidencije_PUS(uredjaj,redoslijed_elemenata)
        elementi=[]
        for i in range(matrica.nrows()):
            for j in range(matrica.nrows()):
                if matrica[i,j]==1: elementi.append((redoslijed_elemenata[i],redoslijed_elemenata[j]))
        return elementi
    elif type(uredjaj)==dict:
        matrica=matrica_incidencije_PUS(uredjaj,redoslijed_elemenata)
        elementi=[]
        for i in range(matrica.nrows()):
            for j in range(matrica.nrows()):
                if matrica[i,j]==1: elementi.append((redoslijed_elemenata[i],redoslijed_elemenata[j]))
        return elementi
    else:
        return "Error: nepravilno definirani parcijalni uredjaj"

Zatvorenja binarnih relacija

Funkcija refleksivno_zatvorenje određuje refleksivno zatvorenje binarne relacije koja je zadana matricom incidencije matrica. Funkcija na izlazu vraća matricu incidencije refleksivnog zatvorenja.

In [20]:
def refleksivno_zatvorenje(matrica):
    if matrica.nrows()!=matrica.ncols(): return "Error: Na ulazu mora biti kvadratna matrica"
    for i in range(matrica.nrows()):
        for j in range(matrica.ncols()):
            if matrica[i,j]!=0 and matrica[i,j]!=1: return "Error: Elementi matrice moraju biti nule ili jedinice"
    matrica1=copy(matrica)
    for j in range(matrica1.nrows()):
        if matrica1[j,j]!=1: matrica1[j,j]=1
    return matrica1

Funkcija simetricno_zatvorenje određuje simetrično zatvorenje binarne relacije koja je zadana matricom incidencije matrica. Funkcija na izlazu vraća matricu incidencije simetričnog zatvorenja.

In [21]:
def simetricno_zatvorenje(matrica):
    if matrica.nrows()!=matrica.ncols(): return "Error: Na ulazu mora biti kvadratna matrica"
    for i in range(matrica.nrows()):
        for j in range(matrica.ncols()):
            if matrica[i,j]!=0 and matrica[i,j]!=1: return "Error: Elementi matrice moraju biti nule ili jedinice"
    matrica1=copy(matrica)
    for i in range(matrica1.nrows()):
        for j in range(matrica1.nrows()):
            if matrica1[i,j]!=matrica1[j,i]:
                matrica1[i,j]=1
                matrica1[j,i]=1
    return matrica1

Funkcija tranzitivno_zatvorenje određuje tranzitivno zatvorenje binarne relacije koja je zadana matricom incidencije matrica. Funkcija na izlazu vraća matricu incidencije tranzitivnog zatvorenja. Implementacija se temelji na Warshallovom algoritmu. Složenost tog algoritma je $O(n^3)$, gdje je $n$ red matrice incidencije zadane relacije.

In [22]:
def tranzitivno_zatvorenje(matrica):
    if matrica.nrows()!=matrica.ncols(): return "Error: Na ulazu mora biti kvadratna matrica"
    for i in range(matrica.nrows()):
        for j in range(matrica.ncols()):
            if matrica[i,j]!=0 and matrica[i,j]!=1: return "Error: Elementi matrice moraju biti nule ili jedinice"
    W=copy(matrica)
    for k in range(matrica.nrows()):
        for i in range(matrica.nrows()):
            for j in range(matrica.nrows()):
                W[i,j]=W[i,j] or (W[i,k] and W[k,j])
    return W

Funkcija ekvivalencija_zatvorenje vraća najmanju relaciju ekvivalencije koja sadrži relaciju zadanu matricom incidencije matrica. Funkcija na izlazu vraća matricu incidencije tražene relacije ekvivalencije.

In [23]:
def ekvivalencija_zatvorenje(matrica):
    if matrica.nrows()!=matrica.ncols(): return "Error: Na ulazu mora biti kvadratna matrica"
    for i in range(matrica.nrows()):
        for j in range(matrica.ncols()):
            if matrica[i,j]!=0 and matrica[i,j]!=1: return "Error: Elementi matrice moraju biti nule ili jedinice"
    mat=tranzitivno_zatvorenje(simetricno_zatvorenje(refleksivno_zatvorenje(matrica)))
    return mat

Klase ekvivalencije

Funkcija klase_ekvivalencije određuje klasu ekvivalencije svakog elementa ukoliko je na ulazu zadana relacija ekvivalencije svojom matricom incidencije. Parametrom skup (kojeg zadajemo preko liste) određujemo imena elemenata skupa na kojemu je relacija zadana (ta lista mora imati onoliko elemenata koliki je red matrice incidencije kojom je relacija zadana). Po defaultu je vrijednost parametra skup postavljena na None, što znači da će elementi biti prvih n prirodnih brojeva (ukoliko je matrica incidencije reda n). Parametar element daje klase svih elemenata ili samo jednog elementa. Po defaultu je vrijednost parametra element jednaka "svi", što znači da će na izlazu biti klase svih elemenata u obliku rječnika. Ukoliko želimo samo klasu jednog određenog elementa, tada vrijednost parametra element postavimo na željeni element.

In [24]:
def klase_ekvivalencije(matrica,skup=None,element="svi"):
    if matrica.nrows()!=matrica.ncols(): return "Error: Na ulazu mora biti kvadratna matrica"
    for i in range(matrica.nrows()):
        for j in range(matrica.ncols()):
            if matrica[i,j]!=0 and matrica[i,j]!=1: return "Error: Elementi matrice moraju biti nule ili jedinice"
    if not(relacija_ekvivalencije(matrica)): return "Error: Zadana relacija nije relacija ekvivalencije"
    if skup==None: skup=range(1,matrica.nrows()+1)
    if len(set(skup))!=matrica.nrows(): return "Error: broj elemenata skupa nije jednak redu matrice"
    if element=="svi":
        klase_elemenata=dict(zip(skup,[[] for k in range(matrica.nrows())]))
        for i in range(matrica.nrows()):
            for j in range(matrica.nrows()):
                if matrica[i,j]==1: klase_elemenata[skup[i]].append(skup[j])
        return klase_elemenata
    else:
        klasa=[]
        indeks=skup.index(element)
        for j in range(matrica.nrows()):
            if matrica[indeks,j]==1: klasa.append(skup[j])
        return klasa
In [ ]: