10. Grafy a union-find

Reprezentácie grafov

Už z programovania v 1. ročníku poznáme väčšie množstvo rôznych reprezentácií. Tu sa pozrieme na konkrétne štyri:

  1. zoznam hrán (edge list)
    • všetky hrany sú sústredené do jedného zoznamu (pole alebo spájaný zoznam) pričom nie sú usporiadané v žiadnom poradí
    • v tomto zozname sú buď priamo dvojice (usporiadané alebo neusporiadané) vrcholov alebo hrán, ktoré sú objektmi s atribútmi začiatok a koniec hrany
    • ak je graf ohodnotený, tento zoznam pri každej hrane obsahuje aj jej váhu
    • reprezentácia si ešte pamätá aj zoznam všetkých vrcholov
  2. zoznam susedov (adjacency list)
    • pre každý vrchol sa udržuje zoznam (pole alebo spájaný zoznam) všetkých susediacich vrcholov
    • v neorientovanom grafe sa každá hrana musí nachádzať v oboch zoznamoch pre oba vrcholy
    • aby boli všetky operácie čo najefektívnejšie, zvykne sa zoznam realizovať dvojsmerným spájaným zoznamom: vyhodenie konkrétnej hrany (remove_edge()) má potom časovú zložitosť O(1), inak bude mať táto operácia zložitosť O(d)
  3. asociatívne pole susedov (adjacency map)
    • veľmi podobná realizácia zoznamu susedov: namiesto zoznamu použijeme asociatívne pole
    • vďaka tomu má operácia vyhľadania hrany (get_edge()) zložitosť len O(1)
    • zrejme kľúčom v týchto asociatívnych poliach susedov bude druhý vrchol, tento by ale mal byť hashovateľný
  4. matica susedností (adjacency matrix)
    • každý riadok matice (i-ty) obsahuje informácie o susedoch i-teho vrcholu, teda j-ty stĺpec označuje hranu medzi i-tym a j-tym vrcholom, napr. hodnoty False/True alebo 0/1 označujú: neexistuje hrana/hrana existuje, resp. pre ohodnotené grafy priamo táto matica označuje váhu konkrétnej hrany (resp. nejaká hodnota označuje neexistenciu hrany, napr. None)
    • pre riedke grafy, v ktorých má každý vrchol malý počet hrán (susedov) je toto veľmi neefektívna reprezentácia, lebo väčšina matice (možno 90%) obsahuje informáciu o neexistencii príslušnej hrany
    • zrejme matica pre neorientovaný graf je symetrická

Ak by sme definovali abstraktnú triedu graf pravdepodobne by obsahovala tieto metódy:

Tabuľka zložitostí metód
metóda graf1 graf2 graf3 graf4  
vertex_count() O(1) O(1) O(1) O(1) počet vrcholov
edge_count() O(1) O(1) O(1) O(1) počet hrán
vertices() O(n) O(n) O(n) O(n) všetky vrcholy
edges() O(m) O(m) O(m) O(n**2) všetky hrany
get_edge(u, v) O(m) O(d) O(1) O(1) či je konkrétna hrana
degree(v) O(m) O(1) O(1) O(n) stupeň vrcholu
incident_edges(v) O(m) O(d) O(d) O(n) všetky susediace vrcholy
insert_vertex(x) O(1) O(1) O(1) O(n**2) vlož vrchol
remove_vertex(v) O(m) O(d) O(d) O(n**2) odstráň vrchol
insert_edge(u, v, x) O(1) O(1) O(1) O(1) vlož hranu
remove_edge(e) O(1) O(1) O(1) O(1) odstráň hranu
pamäť O(n+m) O(n+m) O(n+m) O(n**2)  

V tejto tabuľke je okrem zložitostí operácií pre tieto 4 reprezentácie aj ich pamäťová zložitosť. Jednotlivé premenné tu majú tento význam:

  • n počet vrcholov
  • m počet hrán
  • d stupeň vrcholu (pre riedke grafy sa blíži k O(1), pre husté k O(n))

Algoritmy prehľadávania grafu

V 1. ročníku sme sa zoznámili s týmito troma základnými algoritmami:

  1. prehľadávanie do hĺbky (depth-first search - DFS)
  2. prehľadávanie do šírky (breadth-first search - BFS)
  3. prehľadávanie do hĺbky s návratom (backtracking)

Prehľadávanie do hĺbky

pseudokód:

def prehladavanie(vrchol1):
    označ ako navštívený(vrchol1)
    for vrchol2 in susediace_vrcholy(vrchol1):
        if vrchol2 je ešte nenavštívený:
            rekurzívne volaj prehladavanie(vrchol2)

alebo:

def prehladavanie(vrchol1):
    for vrchol2 in susediace_vrcholy(vrchol1):
        if vrchol2 je ešte nenavštívený:
            označ ako navštívená hrana z vrchol1 do vrchol2
            rekurzívne volaj prehladavanie(vrchol2)

Zložitosť algoritmu lineárne závisí od počtu vrcholov a počtu hrán, t.j. O(m + n)

Algoritmus sa využije hlavne na zisťovanie:

  • počtu komponentov, všetkých komponentov, maximálneho komponentu
  • či je graf súvislý
  • či sú dva vrcholy v tom istom komponente
  • nájdenie ľubovoľnej cesty medzi dvoma vrcholmi

Prehľadávanie do šírky

pseudokód:

def prehladavanie(vrchol1):
    queue = [vrchol1]
    while queue:
        vrchol1 = queue.pop(0)
        if vrchol1 je ešte nenavštívený:
            označ ako navštívený(vrchol1)
            for vrchol2 in susediace_vrcholy(vrchol1):
                if vrchol2 je ešte nenavštívený:
                    queue.append(vrchol2)

alebo:

def prehladavanie(vrchol1):
    uroven = [vrchol1]
    while uroven:
        dalsia_uroven = []
        for vrchol1 in uroven:
            if vrchol1 je ešte nenavštívený:
                označ ako navštívený(vrchol1)
                for vrchol2 in susediace_vrcholy(vrchol1):
                    if vrchol2 je ešte nenavštívený:
                        dalsia_uroven.append(vrchol2)
        uroven = dalsia_uroven

Zložitosť algoritmu lineárne závisí od počtu vrcholov a počtu hrán, t.j. O(m + n)

Algoritmus sa využije hlavne na zisťovanie:

  • to isté ako prehľadávanie do hĺbky
  • vzdialenosť dvoch vrcholov, nájdenie najkratšej cesty medzi dvoma vrcholmi - len pre neohodnotené grafy

Backtracking

Je to hrubá sila - väčšinou O(2**n). Dajú sa riešiť ľubovoľné problémy aj na ohodnoených grafoch.

pseudokód:

def prehladavanie(vrchol1):
    označ ako navštívený(vrchol1)
    if nájdené riešenie:
        spracuj()
    else:
        for vrchol2 in susediace_vrcholy(vrchol1):
            if vrchol2 je ešte nenavštívený:
                rekurzívne volaj prehladavanie(vrchol2)
    odznač ako navštívený(vrchol1)

Dijkstrov algoritmus

pseudokód:

def prehladavanie(vrchol1):
    # pole D sú momentálne vzdialenosti od vrchol1
    D[všetky vrcholy] = inf      # nekonečno
    D[vrchol1] = 0
    queue = prioritný front všetkých vrcholov podľa kľúčov D
    while queue:
        vrchol1 = queue.remove_min()
        for vrchol2 in susediace_vrcholy(vrchol1):
            if vrchol2 je v queue:           # ešte nebol spracovaný
                if D[vrchol1] + vaha(vrchol1, vrchol2) < D[vrchol2]:
                    D[vrchol2] = D[vrchol1] + vaha(vrchol1, vrchol2)
                    zmeň kľúč D[vrchol2] v queue pre vrchol2

    return D     # pole vzdialeností všetkých vrcholov od vrchol1

Union-Find problém

motivácia:

  • tajná služba sa snaží odhaliť identitu agentov
  • každý agent má niekoľko svojich mien (zrejme pre každé má aj svoj pas)
  • tajná služba by chcela mať systém, pomocou ktorého by vedela rýchlo zistiť, či dve rôzne mená patria jednému agentovi (napr. ‚James Bond‘ a ‚007‘)
  • zrejme takýto systém sa dá reprezentovať ako graf, v ktorom vrcholmi sú rôzne mená agentov a hranami vyjadrujeme, že dve mená patria jednému agentovi

V takomto systéme práve komponenty grafu vyjadrujú vzťah medzi agentom a jeho rôznymi menami. Takže tajná služba chce rýchlo vedieť zistiť, či sa dve mená nachádzajú v tom istom komponente.

Už vieme zostaviť jednoduché algoritmy, ktoré pomocou prehľadávania do_hĺbky alebo do_šírky zostroja množiny vrcholov pre jednotlivé komponenty. Najväčší problém ale nastáva, keď sa tajná služba dozvie nový vzťah medzi dvoma menami (novú hranu grafu) a bude treba znovu prepočítať všetky komponenty, pritom by možno stačilo s existujúcimi komponentmi niečo urobiť. (Hoci, ak to potrebujeme zistiť len raz na začiatku bez ďalších pridávaní hrán, algoritmus do_hĺbky je dostatočne efektívny.)

Tento problém sa nazýva union-find, resp. sústava disjunktných množín (disjoint set):

  • máme niekoľko disjunktných množín
  • chceme vedieť rýchlo nájsť, v ktorej množine sa nachádza nejaký prvok (v ktorom komponente sa nachádza nejaký vrchol): operácia find
  • a tiež chceme raz začas dve množiny spojiť do jednej (pridali sme novú hranu, musíme spojiť dva komponenty do jedného): operácia union

Ako reprezentovať takúto dátovú štruktúru (zrejme ju bude využívať napr. náš graf mien agentov), aby tieto operácie boli čo najefektívnejšie. Tieto disjunktné množiny by ste nemali pliesť so štandardným pythonovským typom set, preto sa niekedy používa aj terminológia disjunktné skupiny (group).

Aby sme vedeli manipulovať s takýmito množinami, každá bude mať svojho reprezentanta (jeden konkrétny prvok zo skupiny) - niekedy sa mu hovorí aj líder (leader).

Základné operácie tejto dátovej štruktúry:

  • make_set(x) - vytvorí novú jednoprvkovú množinu
    • zrejme samotný prvok je aj reprezentantom tejto množiny
  • union(p, q) - spojí dve množiny, ktoré obsahujú dané dva prvky, do jednej
    • väčšinou sa reprezentant jednej z týchto množín stáva reprezentantom aj ich zjednotenia
  • find(p) - vráti reprezentanta množiny, v ktorej sa daný prvok nachádza

Triviálne riešenie

Predpokladajme, že každý prvok má informáciu o reprezentantovi množiny, do ktorej patrí. Napr. ak sme mali graf definovaný ako pole vrcholov:

class Vertex:
    def __init__(self, data):
        self.data = data
        self.rep = self               # reprezentant

class Graph:
    def __init__(self):
        self.vertex = []
    ...

Pri vytvorení vrcholu sme mu automaticky pridelili reprezentanta (samého seba). Operácia FIND(p) potom vráti túto hodnotu. Zložitosť tejto operácie je O(1). Operácia UNION(p, q) najprv zistí reprezentantov oboch prvkov (pomocou FIND()) a ak sú rôzni, bude treba všetky výskyty druhého reprezentanta v poli všetkých prvkov (self.vertex) zmeniť na hodnoty prvého reprezentanta, teda schematicky:

def UNION(p, q):
    r1 = FIND(p)
    r2 = FIND(q)
    if r1 != r2:
        for v in vsetky_prvky:     # napr. self.vertex
            if v.rep == r2:
                v.rep = r1

Zrejme zložitosť tejto operácie je O(n) pre n počet prvkov (napr. vrcholov grafu).

Vo všeobecnosti toto riešenie znamená pomocnú tabuľku veľkosti n, v ktorej i-ty prvok tabuľky zodpovedá reprezentantovi i-teho prvku. Operácia FIND() iba siahne do tabuľky na príslušné miesto (teda O(1)) a operácia UNION() bude možno musieť prejsť celú tabuľku a niektorým prvkom zmeniť hodnotu (teda O(n)).

Nech r je jednorozmerné pole, ktoré pre každý prvok obsahuje jeho reprezentanta skupiny (napr. číslo komponentu). Operácia find(p) má zložitosť O(1), lebo len vyberie hodnotu z tabuľky. Operácia union(p, q) zistí reprezentantov pre oba prvky (r[p] a r[q]) a ak sú rôzne, prejde celú tabuľku a reprezentantov r[p] nahradí hodnotou r[q]. Zložitosť tejto operácie je O(n).

Ak by sme zapísali túto reprezentáciu do tabuľky (do poľa), v ktorej i-ty prvok označuje reprezentanta, tak pre izolované vrcholy tabuľka vyzerá takto:

0 1 2 3 4 5 6 7 8 9  
0 1 2 3 4 5 6 7 8 9  

Každý prvok je sám pre seba reprezentantom. Ak budeme teraz zjednocovať niektoré množiny, začnú sa prerábať reprezentanti pre jednotlivé prvky, napr. po operácii UNION(1,3) všetky prvky s reprezentantom 3 sa prerobia na 1:

0 1 2 3 4 5 6 7 8 9  
0 1 2 1 4 5 6 7 8 9  

Momentálne máme už len 9 disjunktných množín, pričom jedna z nich má 2 prvky.

Po ďalších niekoľkých volaniach: UNION(2,4), UNION(7,6), UNION(8,9):

0 1 2 3 4 5 6 7 8 9  
0 1 2 1 2 5 7 7 8 8  

Teraz máme už len 6 množín: dve sú 1 prvkové a štyri dvojprvkové.

Ďalšie dve volania UNION(3,4), UNION(7,8) zlúčia ďalšie množiny:

0 1 2 3 4 5 6 7 8 9  
0 1 1 1 1 5 7 7 7 7  

Prvé volanie UNION(3,4) najprv zistilo reprezentantov prvkov 3 a 4, to sú hodnoty 1 a 2 a preto prvky s hodnotami 2 sa nahradili 1.

Ďalšie volanie UNION(6,4) zlúči množiny s reprezentantmi 7 (pre prvok 6) a 1 (pre prvok 4), teda nahradia 1 hodnotami 7, vznikne tým jedna 8 prvková množina. Ak by sme ešte zavolali UNION(1,9), neudeje sa nič, lebo oba prvky majú teraz rovnakého reprezentanta:

0 1 2 3 4 5 6 7 8 9  
0 7 7 7 7 5 7 7 7 7  

Vidíme, že tu teraz máme 3 disjunktné množiny a vieme veľmi rýchlo zistiť, či sa ľubovoľné dva prvky x a y nachádzajú v tej istej množine: stačí otestovať

tab[x] == tab[y]

Zrejme operácia UNION() tu má časovú zložitosť O(n), keďže kvôli prečíslovaniu reprezentantov, musíme prejsť celú tabuľku. Ak by sme volali UNION() len pre prvky, ktoré sú v rôznych množinách, tak po n-1 volaniach by sme dostali jedinú množinu, ktorá by obsahovala všetky prvky.

Riešenie so zoznamami

Aby sme v predchádzajúcom tabuľkovom riešení nemuseli pri UNION() zakaždým prechádzať celé pole, pre každý komponent si vytvoríme „spájaný zoznam“ tých prvkov, ktoré do neho patria. Okrem toho si uložíme aj veľkosť tohto komponentu. Operácia UNION() bude teraz prechádzať a modifikovať len prvky menšieho komponentu. Potom ešte tieto dva spájané zoznamy zreťazí a nastaví si novú veľkosť komponentu.

V najhoršom prípade je operácia UNION() opäť O(n), ale pre každý prvok platí, že jeho hodnota reprezentanta sa zmení iba vtedy, keď sa nachádza v menšom (alebo rovnako veľkom) komponente. Lenže toto sa môže stať maximálne log n krát, preto n operácií UNION() bude trvať O(n log n) a preto amortizovaná zložitosť jednej operácie UNION() je O(log n).

V našom príklade s komponentmi grafu, by sme to mohli zapísať:

class Vertex:
    def __init__(self, data):
        self.data = data
        self.rep = self               # reprezentant
        self.next = None              # nasledovník v komponente
        self.size = 1                 # počet prvkov v komponente

class Graph:
    def __init__(self):
        self.vertex = []
    ...

Asi bude najvhodnejšie, keď reprezentantom bude prvý prvok komponentu, teda spájaného zoznamu. Potom schematicky:

def UNION(p, q):
    r1 = FIND(p)
    r2 = FIND(q)
    if r1 != r2:
        if r1.size < r2.size:
            # všetkým prvkom v zozname r1 zmen reprezentanta na r2
            p = last = r1
            while p is not None:
                p.rep = r2
                last, p = p, p.next
            # zreťaz oba zoznamy
            last.next = r2.next
            r2.next = r1
            # zvýš počet
            r2.size += r1.size
        else:
            # všetkým prvkom v zozname r2 zmen reprezentanta na r1
            ...
            # zreťaz oba zoznamy
            ...
            # zvýš počet
            ...

Riešenie stromami

Predchádzajúce riešenie pomocou spájaných zoznamov ešte trochu vylepšíme. Aby sme nemuseli pri operácii UNION() prechádzať veľkú časť prvkov (všetky v nejakom komponente), nebudeme z nich vytvárať spájané zoznamy, ale orientované stromy: každý prvok si bude namiesto nasledovníka (next) pamätať svojho rodiča v strome (teda parent), pričom koreň bude obsahovať referenciu na samého seba. Každý prvok sa teda nachádza v nejakom strome (komponent, teda disjunktná množina), pričom do koreňa (to bude reprezentantom množiny) sa vieme dostať veľmi jednoducho sledovaním smerníka parent.

Aby sa nám čo najlepšie robila operácia UNION() (budeme zlučovať dva stromy do jedného), pre každý komponent si budeme uchovávať (atribút rank) aj jeho výšku (najdlhšia cesta smerom k listom). Pri inicializácii nastavíme parent na seba samého (self) a rank na 0:

class Vertex:
    def __init__(self, data):
        self.data = data
        self.parent = self            # predchodca v strome
        self.rank = 0                 # výška stromu

class Graph:
    def __init__(self):
        self.vertex = []
    ...

Operácia FIND() schematicky:

def FIND(p):
    while p != p.parent:
        p = p.parent
    return p

Takto sa dostane do koreňa stromu, čo je reprezentantom celej množiny (komponentu). Operácia UNION() zistí, ktorý z komponentov má menší rank (výšku stromu) a ten potom pripojí ako ďalšieho syna ku koreňu väčšieho stromu. Keďže výška nového stromu sa pritom nezmení, netreba meniť ani hodnotu rank. Ak mali oba stromy rovnaký rank, tak pripojením jedného stromu ako syna k druhému sa o 1 zväčší jeho rank. Schematicky zapíšeme:

def UNION(p, q):
    r1 = FIND(p)
    r2 = FIND(q)
    if r1 != r2:
        if r1.rank > r2.rank:
            r2.parent = r1
        else:
            r1.parent = r2
            if r1.rank == r2.rank:
                r2.rank += 1

Časová zložitosť operácie FIND(p) závisí od výšky stromu, ktorý sa takto prechádza, čo je rank reprezentanta, teda koreňa stromu. Operácia UNION() urobí najprv 2 volania FIND() a potom len príkazy O(1). Teda obe operácia UNION() aj FIND() majú rovnakú zložitosť. Keďže strom výšky k mohol vzniknúť len spojením (UNION()) dvoch stromov výšky k-1, každý strom s koreňom rank rovný k má aspoň 2**k prvkov a preto takýto strom s n vrcholmi má výšku (rank) maximálne log n. Teda zložitosť oboch operácií je O(log n).

Existujú ešte ďalšie verzie a vylepšenia tejto dátovej štruktúry, my sa nimi v tomto predmete zaoberať nebudeme.

Príklad, ktorý sme robili pri tabuľkovej reprezentácii disjunktných množín, môžeme zopakovať aj pre stromčeky. Začnime s 10 jednoprvkovými množinami:

_images/10_1.png

Najprv spojíme UNION(1,3):

_images/10_2.png

Teraz postupne UNION(2,4), UNION(7,6), UNION(8,9):

_images/10_3.png

Potom UNION(3,4), UNION(7,8):

_images/10_4.png

Na záver UNION(6,4), UNION(1,9):

_images/10_5.png

Iné využitie union-find

Dátová štruktúra disjoint set sa používa nielen na udržiavanie množín vrcholov jednotlivých komponentov grafu, ale má využitie, napr. pre

  • zisťovanie, či je v grafe cyklus: postupne konštruujeme najprv z jednoprvkových množín (pre každý vrchol jedna) skladáme väčšie (prechádzame všetky hrany a pre každú spojíme dve zodpovedajúce množiny), ak zistíme, že oba vrcholy danej hrany sa už nachádzajú v jednom komponente, znamená to, že v grafe je cyklus
  • vytváranie minimálnej kostry grafu pomocou Kruskalovho algoritmu (budeme vytvárať takú množinu hrán, ktorých súčet ohodnotení je minimálny):
    1. každý vrchol grafu vytvoríme ako samostatnú množinu (make_set(v))
    2. vytvoríme prioritný front všetkých hrán, pričom kľúčmi budú ohodnotenia hrán
    3. kým vo výslednej množine nie je n-1 hrán, opakuje:
      • vyberie z prioritného frontu hranu s najmenšou váhou (remove_min()) -> (v1, v2)
      • ak tieto vrcholy ešte nie sú v tej istej disjunktnej množine (teda find(v1)!=find(v2)), tak ich zjednoť pomocou union(v1, v2) a pridaj do výslednej množiny hrán
    4. výsledná množina hrán je hľadaná minimálna kostra grafu


Cvičenia

L.I.S.T.

Trieda Graph

Toto je verzia triedy Graph postavená na kóde z poslednej prednášky prvého ročníka. Využijeme tento kód pri prvých úlohách cvičenia:

import tkinter
import random

class Graph:

    class Vertex:
        canvas = None

        def __init__(self, data, x, y):
            self.data = data
            self.xy = x, y
            self.incident_edges = set()

        def draw(self):
            x, y = self.xy
            self.canvas.create_oval(x-10, y-10, x+10, y+10, fill='lightgray')
            self.canvas.create_text(x, y, text=self.data)

    #----------------------------------------------

    def __init__(self, n):
        self.vertices = []
        self.weight = {}
        for i in range(n):
            for j in range(n):
                self.insert_vertex(j*80+20, i*80+20)
                num = len(self.vertices) - 1
                if j > 0 and 1+random.randrange(4):
                    self.insert_edge(num, num-1)
                if i > 0 and 1+random.randrange(4):
                    self.insert_edge(num, num-n)
        self.canvas = tkinter.Canvas(bg='white', width=600, height=600)
        self.canvas.pack()
        self.Vertex.canvas = self.canvas
        self.draw()

    def insert_vertex(self, x, y):
        num = len(self.vertices)
        self.vertices.append(self.Vertex(num, x, y))

    def insert_edge(self, v1, v2):
        self.weight[v1, v2] = self.weight[v2, v1] = random.randrange(1, 10)
        self.vertices[v1].incident_edges.add(v2)
        self.vertices[v2].incident_edges.add(v1)

    def get_edge(self, v1, v2):
        return v2 in self.vertices[v1].incident_edges

    def draw_edge(self, v1, v2):
        x1, y1 = self.vertices[v1].xy
        x2, y2 = self.vertices[v2].xy
        self.edge_id[v1, v2] = self.edge_id[v2, v1] = \
            self.canvas.create_line(x1, y1, x2, y2, width=3, fill='gray')
        x, y = (x1+x2) // 2, (y1+y2) // 2
        self.canvas.create_oval(x-10, y-10, x+10, y+10, fill='white', width=0)
        self.canvas.create_text(x, y, text=self.weight[v1, v2])

    def color_edge(self, v1, v2, color='black'):
        self.canvas.itemconfig(self.edge_id[v1, v2], fill=color)

    def draw(self):
        self.edge_id = {}
        for v1 in range(len(self.vertices)):
            for v2 in range(v1+1, len(self.vertices)):
                if self.get_edge(v1, v2):
                    self.draw_edge(v1, v2)
        for vrch in self.vertices:
            vrch.draw()

    def dijkstra(self, v1):
        inf = float('inf')
        d = [inf] * len(self.vertices)
        d[v1] = 0
        ...
        return d

    def draw_path(self, d, v1, v2):
        for i in range(len(self.vertices)):
            for j in range(i+1, len(self.vertices)):
                if self.get_edge(i, j):
                    self.color_edge(i, j)
        ...

Dijkstrov algoritmus

  1. Vygeneruj náhodný ohodnotený graf veľkosti 4x4 vrcholov a ručne na papieri zostav pre tento graf pole d vzdialeností od vrcholu 0 ku všetkým ostatným. Zapisuj pritom tieto zistené čísla z poľa d k jednotlivým vrcholom grafu.

    • spusti:

      g = Graph(4)
      d = g.dijkstra(0)
      
    • môžeš vyskúšať aj väčší graf 5x5 so štartom vo vrchole 6:

      g = Graph(5)
      d = g.dijkstra(6)
      

  1. Do triedy Graph doprogramuj dijkstrov algoritmus z prednášky (metódu dijkstra()).
    • môžeš použiť premennú inf (s hodnotou float('inf')), ktorá v Pythone reprezentuje nekonečno - vyskúšaj jednoduchú aritmetiku s touto hodnotou (porovnanie čísla s inf, pripočítanie/odpočítanie od inf, …)
    • prioritný front vrcholov nemusíš programovať ako optimálnu dátovú štruktúru - stačí použiť obyčajný zoznam dvojíc (d[vrchol], vrchol), ktorý buď budeš udržiavať utriedený, alebo v ňom zakaždým budeš hľadať minimálny prvok
    • metóda dijkstra() môže na záver ku každému vrcholu vypísať príslušné číslo (vzdialenosť) z poľa d
    • vyskúšaj potom spustiť túto metódu s rôznymi štartovými vrcholmi a výsledky skontroluj

  1. Do triedy Graph doprogramuj metódu draw_path(), ktorá pre pole vzdialeností z dijkstrovho algoritmu dokáže zrekonštruovať cestu od štartu v1 do cieľa v2.
    • ak máš dané aktuálne pole d, môžeš začať odkonca: pre cieľový vrchol nájdeš jeho predchodcu na trase (je to vrchol, ktorého vzdialenosť od štartu sa líši od cieľového presne o hodnotu na hrane)
    • metóda by mala túto cestu vykresliť (metóda draw_edge() prefarbí konkrétnu hranu grafu)

Union-find

  1. Postupne ručne odtrasuj všetky 3 reprezentácie operácií UNION() a FIND() (podobne, ako je to ukázané v prednáške) na 12 prvkovom poli celočíselných hodnôt range(12) a volaním UNION() pre dvojice
    • (0, 11), (1, 10), (2, 9), (3, 8), (4, 7)
    • (0, 7), (8, 1), (5, 9), (2, 6)
    • (11, 3), (2, 4)

  1. Operácie UNION() a FIND() realizuj stromčekovou reprezentáciou z prednášky, v ktorej si každý vrchol pamätá svoj rank. Skontroluj na údajoch z úlohy (4).

    • definuj:

      def FIND(p):
          ...
      def UNION(p, q):
          ...
      

  1. Uprav reprezentáciu stromčekmi z úlohy (5) tak, že sa pritom nepoužije rank (t.j. bez rank: rozhoduje sa náhodne s pravdepodobnosťou 1/2). Otestuj podobne ako v úlohe (5).

    • definuj:

      def FIND(p):
          ...
      def UNION(p, q):
          ...
      

  1. Zapíš funkciu, ktorá pomocou realizácie z (5) zistí počet disjunktných množín (komponentov grafu) len na základe informácií v tejto reprezentácií.
    • pravdepodobne budeš prechádzať pole prvkov a nejako si pri tom budeš evidovať rôzne množiny

Reprezentácie grafov

  1. Naprogramuj metódy triedy Graph (neorientovaný neohodnotený graf) pre reprezentáciu pomocou zoznamu hrán

    • využite triedy:

      class Vertex:
          def __init__(self, data):
              self.data = data
      
      class Edge:
          def __init__(self, start, end):     # start aj end sú typu Vertex
              self.start = start
              self.end = end
      
          def __eq__(self, other):
              return isinstance(other, Edge) and
                     (self.start == other.start and self.end == other.end or
                      self.start == other.end and self.end == other.start)
      
    • naprogramuj tieto metódy (abstraktný dátový typ) podľa možnosti čo najefektívnejšie:

      class Graph:
          def __init__(self):
              self.vertex = []
              self.edge = []
          def vertices(self):            # generátor, vracia objekty typu Vertex
              ...
          def vertex_count(self):
              ...
          def edges(self):               # generátor, vracia objekty typu Edge
              ...
          def edge_count(self):
              ...
          def get_edge(self, v1, v2):    # vráti objekt typu Edge alebo None
              ...
          def incident_edges(self, v):   # generátor, vracia objekty typu Edge
              ...
          def insert_vertex(self, x):    # x je dátová časť vrcholu, funkcia vráti objekt typu Vertex
              ...
          def remove_vertex(self, v):    # v je objekt typu Vertex
              ...
          def insert_edge(self, v1, v2): # vráti objekt typu Edge
              ...
          def remove_edge(self, e):      # e je objekt typu Edge
              ...
      

  1. Pomocou algoritmu do hĺbky zisti, či sa dva vrcholy nachádzajú v tom istom komponente:

    • rekurzívnu funkciu zapíš tak, aby používala len metódy z úlohy (2), teda aby táto funkcia fungovala pre ľubovoľnú reprezentáciu grafu:

      class Graph:
          ...
          def depth_first(self, v1, v2):
              ...
      
    • odhadni zložitosť tohto algoritmu

    • otestuj na náhodne vygenerovanom grafe, ktorý obsahuje niekoľko rôzne veľkých komponentov


  1. Pomocou algoritmu do hĺbky zisti, či je hrana medzi dvoma susednými vrcholmi most, t.j. po jej odstránení z grafu by sa zvýšil počet komponentov

    • rekurzívnu funkciu zapíš tak, aby používala len metódy z úlohy (1), teda aby táto funkcia fungovala pre ľubovoľnú reprezentáciu grafu:

      class Graph:
          ...
          def is_bridge(self, v1, v2):
              ...
      
    • odhadni zložitosť tohto algoritmu


  1. Pomocou algoritmu do hĺbky zisti počet komponentov grafu.

    • zapíšte:

      class Graph:
          ...
          def component_count(self):
              ...
      
    • odhadni zložitosť tohto algoritmu



8. Domáce zadanie

L.I.S.T.

Minimálna sieť

V Kocúrkove dostali európsky grant, aby si zaviedli internet do všetkých domov v obci. Financie ale dostanú len vtedy, keď to zabezpečia najmenšou možnou dĺžkou použitých optických káblov. Ďalšou podmienkou komisie bolo to, aby káble ťahali len priamo medzi domami, teda tak, že rozvetvovať sa budú len v domoch a nie mimo nich. Pre fungovanie internetu bude stačiť, keď bude existovať aspoň nepriame spojenie medzi každými dvoma domami (jeden z nich je obecný úrad, ktorý má prepojenie na internetového poskytovateľa).

Úlohu budete riešiť takto:

  • uložíte si polohy (x, y) všetkých domov v obci (dve celé čísla) - prečítate ich zo zadaného súboru
  • všetky dvojice domov potom uložíte do prioritného frontu, pričom kľúčom bude ich vzdialenosť
    • uvedomte si, že ak je v obci n domov, tak tento front musí obsahovať presne n*(n-1)/2 takýchto dvojíc (graf je neorientovaný, každá hrana bude vo fronte len raz)
  • postupne budete z tohto frontu vyberať dvojicu s najmenšou vzdialenosťou a ak pre tieto dva domy ešte neexistuje ani nepriame prepojenie, tak ich zaradíte do výsledného zoznamu internetovej siete
    • na zisťovanie, či sú dva domy už zosieťované, použijete ideu UNION-FIND (teda zistíte, či sú oba domy v rovnakom komponente)
  • ak bolo v obci n domov, tak zrejme stačí n-1 prepojení dvojíc domov, aby bola celá obec zosieťovaná (uvedomte si, že toto je Kruskalov algoritmus pre nájdenie kostry grafu).

Na prioritný front môžete (nemusíte) využiť modul heapq.

Trieda Kocurkovo bude obsahovať tri podtriedy a ich metódy:

  • trieda Dom popisuje vrcholy grafu
    • Dom.__init__(...) inicializuje vrchol a jeho union-find informáciu: vytvorí strom len s koreňom, parent odkazuje na samého seba, rank je 1
    • Dom.find() vráti koreň union-find stromu (postupuje po smerníkoch parent)
    • funkcia union pre tieto union-find stromy sa nachádza v triede Kocurkovo
  • trieda Spoj popisuje hrany grafu
    • Spoj.__init__(...) vytvorí hranu grafu, t.j. dvojicu dvoch vrcholov (domov), pričom v atribúte key bude dĺžka hrany, teda vzdialenosť dvoch domov
  • trieda Kocurkovo popisuje samotný graf (zoznam vrcholov), z ktorých sa vytvoria hrany - tie sa uložia do frontu
    • Kocurkovo.__init__(...) prečíta súbor a vytvorí z neho atribút pole (typu list), ktorý bude obsahovať všetky domy (objekty typu Dom)
    • Kocurkovo.union(...) spojí dva union-find stromy tak, že menšiemu z nich (s menším rank) koreňovému vrcholu zmení parent na koreň väčšieho stromu, ak majú rovnaký rank, tak ich spojí tiež, ale vtedy aj zvýši rank o 1
    • Kocurkovo.prioritny_front() vytvorí prioritný front (ako haldu) zo všetkých hrán grafu - prvkami budú objekty typu Spoj
      • uvedomte si, že v prioritnom fronte sa porovnávajú len kľúče
  • min_siet() vytvorí kostru grafu - vráti dvojicu hodnôt: dĺžku kostry (súčet dĺžok hrán kostry) a zoznam hrán (list) dvojíc súradníc domov
    • parametrom je prioritný front, ktorý sa vytvoril metódou prioritny_front()
  • do triedy Spoj môžete dodefinovať metódu Spoj.__lt__(self, iny), ktorá zabezpečí, že prioritný front pre porovnávanie prvkov použije len kľúče, teda táto metóda vráti True, keď self.key je menší ako iny.key

Ak by sme triedu otestovali týmito volaniami metód:

if __name__ == '__main__':
    k = Kocurkovo('subor1.txt')
    print('pocet domov =', len(k.pole))
    pq = k.prioritny_front()
    print('dlzka frontu =', len(pq.pole))
    d, r = k.min_siet(pq)
    print('dlzka kostry =', d)
    for d1, d2 in r:
        print(d1, '-', d2)

dostaneme tento výstup:

pocet domov = 8
dlzka frontu = 28
dlzka kostry = 654.1493569838469
(127, 66) - (158, 23)
(318, 178) - (278, 232)
(156, 135) - (127, 66)
(266, 309) - (278, 232)
(151, 317) - (43, 338)
(266, 309) - (151, 317)
(156, 135) - (278, 232)

Z úlohového servera L.I.S.T. si stiahnite kostru programu riesenie8.py aj testovacie súbory ‚subor01.txt‘`, 'subor02.txt', 'subor03.txt', …. Mali by ste dodržať tieto vlastnosti programu:

  • Nemeňte mená už zadaných atribútov (metód a premenných).
  • Do existujúcich tried môžete pridávať vlastné atribúty a metódy (môžete si vytvoriť aj vlastnú triedu).

Na začiatok súboru riesenie8.py pridajte tieto tri komentárové riadky (s vašim menom a dátumom):

# 8. zadanie: kostra grafu
# autor: Alan Turing
# datum: 20.12.2018

Riešenie odovzdajte na úlohový server L.I.S.T. najneskôr do 23:00 23. decembra. Môžete zaň získať 10 bodov. Testovač postupne preveruje vlastnosti vašich algoritmov, pri prvej chybe sa testovanie preruší a ďalšie časti sa netestujú:

  • 10% bodov za prečítanie súboru
  • 30% bodov za vytvorenie prioritného frontu
  • 60% bodov za algoritmus hľadania kostry grafu pre rôzne veľké grafy


© Copyright 2018-2019, Andrej Blaho.
Naposledy aktualizované 14. feb. 2019.
Vytvorené pomocou Sphinx 1.8.4.

Creative Commons License This work is licensed under a Creative Commons Attribution 4.0 International License.