32. Grafy


Terminológia

Graf je dátová štruktúra na reprezentovanie vzťahov medzi dvojicami objektov. Preto sa skladá

  • z množiny takýchto objektov - hovoríme im vrcholy: V = {V1, V2, …}

  • z množiny takýchto spojení (vzťahov medzi dvojicami), ktorým hovoríme hrany; množinu budeme označovať H, pričom každá hrana je dvojica (v, w), kde v, w in V

    • ak sú to neusporiadané dvojice, hovoríme tomu neorientovaný graf

    • ak sú to usporiadané dvojica, hovoríme tomu orientovaný graf

Graf budeme znázorňovať takto:

  • vrcholy sú krúžky (podobne ako pri dátovej štruktúre strom)

  • hrany sú spojovníky medzi vrcholmi, pričom, ak je graf orientovaný, tak spojovníkmi sú šípky

Graf najčastejšie používame, keď potrebujeme vyjadriť takéto situácie:

  • mestá spojené cestami (najčastejšie je to neorientovaný graf: mestá sú vrcholy, hrany označujú cesty medzi mestami)

  • križovatky a ulice v meste (križovatky sú vrcholy, hrany sú ulice medzi križovatkami)

  • susediace štáty alebo nejaké oblasti (štáty sú vrcholy, hrany označujú, že nejaké štáty susedia)

  • mestská verejná doprava (zastávky sú vrcholy, hrany označujú, že existuje linka, ktorá má tieto dve susediace zastávky)

  • skupina ľudí, ktorí sa navzájom poznajú (ľudia sú vrcholy, hrany označujú, že nejaké konkrétne dve osoby sa poznajú)

Rôzne príklady využitia typu graf:

_images/32_0.png

Problém siedmich mostov: medzi jednotlivými brehmi a ostrovmi mesta vedie sedem mostov. Otázkou je, či sa dá prejsť cez všetky mosty takým spôsobom, že sa dostaneme opäť do pôvodného miesta, bez toho aby sme nejaký most prešli viackrát. Leonhard Euler vyriešil tento problém v roku 1736.

_images/32_1.png

Cestná sieť SR (graf) obsahuje väčšie mestá (vrcholy grafu) a cesty rôznych farieb medzi nimi (hrany). Na hranách grafu sú zapísané vzdialenosti v kilometroch (váhy hrán).

_images/32_2.png

Mapa (graf) liniek MHD Bratislavy. V tejto mape sú vrcholmi grafu zastávky a farby hrán vyjadrujú rôzne dopravné prostriedky. Na hranách sú zapísané čísla liniek (sú to váhy hrán).

_images/32_3.png

Mapa (graf) zobrazuje letecké trasy (hrany) medzi niektorými dôležitými mestami sveta (vrcholy).

_images/32_4.png

Obrázok (graf) zobrazuje vzťahy (hrany) medzi členmi (vrcholmi) nejakej skupiny.

_images/32_5.png

Toto je tzv. pojmová mapa. V tomto obrázku (grafe) sú v krúžkoch (vrcholoch) nejaké informatické pojmy. Niektoré z nich sú spojené šípkami (orientované hrany), ktoré vyjadrujú nejaký vzťah (váha hrany).

_images/32_6.png

V tejto schéme sú mená najznámejších programovacích jazykov aj s rokmi, kedy vznikli (vrcholy grafu). Spojené sú šípkami (hrany grafu), ktoré vyjadrujú vzťah, ako ktorý jazyk ovplyvnil nejaký iný.

Dôležité pojmy

  • ak existuje hrana (v, w) - tak hovoríme, že v a w sú susediace vrcholy

  • v grafe môžeme mať uchované rôzne informácie:

    • v každom vrchole (podobne ako v strome), napríklad meno, súradnice v ploche (na mape), …

    • každá hrana môže mať nejakú hodnotu (tzv. váha), vtedy tomu hovoríme ohodnotený graf, napríklad vzdialenosť dvoch miest, cena cestovného lístka, linky, ktoré spájajú dve zastávky, vzťahy medzi pojmami, …

  • cesta je postupnosť vrcholov, ktoré sú spojené hranami

    • dĺžka cesty pre neohodnotený graf počet hrán na ceste, t.j. počet vrcholov cesty - 1

    • dĺžka cesty v ohodnotenom grafe je súčet váh na hranách cesty

  • cyklus je taká cesta, pre ktorú prvý a posledný vrchol sú rovnaké

    • ak graf neobsahuje ani jeden cyklus, hovoríme že je acyklický

  • hovoríme, že graf je súvislý (spojitý), ak pre každé dva vrcholy v, w in V, existuje cesta z v do w, inak je graf nesúvislý

    • niekedy bude pre nás dôležité, keď nejaký graf bude súvislý/nesúvislý bez cyklov, ale aj súvislý/nesúvislý s cyklom

  • hrane (v, v) hovoríme slučka (toto bude veľmi zriedkavé, ak sa to niekedy objaví, upozorníme na to)

  • pojem komponent označuje súvislý podgraf, ktorý je disjunktný so zvyškom grafu (neexistuje hrana ku vrcholom vo zvyšku grafu)

Ďalej ukážeme najčastejšie spôsoby reprezentácie grafov. Konkrétna reprezentácia sa potom zvolí väčšinou podľa problémovej oblasti a rôznych obmedzení v zadaní.


Reprezentácie

Tento konkrétny graf postupne ukážeme v rôznych reprezentáciách

_images/32_7.png

Na rozdiel od dátových štruktúr spájaný zoznam a binárny strom, pri ktorých sme si ukázali jedinú reprezentáciu pomocou smerníkov, pri dátovej štruktúre graf si väčšinou zvolíte tú reprezentáciu, s ktorou sa vám pri tej ktorej konkrétnej úlohe najlepšie pracuje. Nižšie uvedieme niekoľko bežných reprezentácií, v ktorých sa využívajú pythonovské typy list, set a dict. Neskôr uvidíte aj iné spôsoby reprezentácie grafov.

Zoznam množín susedností

Aby sme nemuseli pracovať s jednoznakovými reťazcami 'a', 'b', …, očíslujeme vrcholy číslami 0, 1, 2, …

Pre čitateľnosť zápisu najprv vytvoríme 8 konštánt a=0, b=1, c=2, … a pomocou nich zadefinujeme celý graf ako zoznam množín, kde i-ta množina reprezentuje všetkých susedov i-teho vrcholu:

a,b,c,d,e,f,g,h = range(8)
graf = [{b,c,d,e,f},  #a
        {c,e},        #b
        {d},          #c
        {e},          #d
        {f},          #e
        {c,g,h},      #f
        {f,h},        #g
        {f,g},        #h
        ]

Pre túto štruktúru vieme zistiť, počet vrcholov, počet všetkých hrán, stupeň konkrétneho vrcholu a či medzi dvoma konkrétnymi vrcholmi je hrana:

>>> print('pocet vrcholov:', len(graf))
pocet vrcholov: 8
>>> print('pocet hran:', sum(map(len, graf)))
pocet hran: 17
>>> print('stupen vrcholu f:', len(graf[f]))
stupen vrcholu f: 3
>>> print('hrana medzi b, e:', e in graf[b])
hrana medzi b, e: True
>>> print('hrana medzi c, a:', a in graf[c])
hrana medzi c, a: False

Túto reprezentáciu môžeme „zabaliť“ do triedy napríklad takto:

class Graf:
    def __init__(self, zoz=None):
        if zoz is None:
            self.zoz = []
        else:
            self.zoz = zoz

    def pridaj_hranu(self, v1, v2):
        while len(self.zoz)-1 < max(v1, v2):
            self.zoz.append(set())
        self.zoz[v1].add(v2)

    def je_hrana(self, v1, v2):
        return v2 in self.zoz[v1]

    def daj_vrcholy(self):
        return list(range(len(self.zoz)))

    def daj_hrany(self):
        return [(v1, v2) for v1 in range(len(self.zoz)) for v2 in self.zoz[v1]]

    def stupen(self, v=None):
        if v is not None:
            return len(self.zoz[v])
        return max(map(len, self.zoz))

    def __str__(self):
        return f'vrcholy: {self.daj_vrcholy()}\nhrany: {self.daj_hrany()}'

    def __repr__(self):
        return f'Graf({self.zoz})'

a graf môžeme teraz vytvoriť napríklad takto:

>>> a,b,c,d,e,f,g,h = range(8)
>>> graf = Graf()
>>> graf.pridaj_hranu(a,b)
>>> graf.pridaj_hranu(b,e)
>>> graf.pridaj_hranu(f,h)
>>> graf.pridaj_hranu(g,f)
>>> graf
Graf([{1}, {4}, set(), set(), set(), {7}, {5}, set()])
>>> print(graf)
vrcholy: [0, 1, 2, 3, 4, 5, 6, 7]
hrany: [(0, 1), (1, 4), (5, 7), (6, 5)]

Všimnite si, že sme vyrobili dve rôzne metódy __repr__() a __str__(). Metóda __repr__() sa zavolá, napríklad keď v dialógovom režime zapíšeme >>> graf. Metóda __str__() sa zavolá, napríklad keď budeme graf vypisovať príkazom print(). Metóda daj_hrany() využíva generátorovú notáciu:

return [(v1, v2) for v1 in range(len(self.zoz)) for v2 in self.zoz[v1]]

Metóda generuje všetky dvojice vrcholov, ktoré tvoria hrany. To isté môžeme zapísať aj takto:

return [(v1, v2) for v1, sus in enumerate(self.zoz) for v2 in sus]

Tak ako sme túto triedu Graf definovali, je trochu komplikované vytvoriť izolovaný vrchol, t.j. taký, z ktorého nevychádza žiadna hrana (asi by pomohla metóda pridaj_vrchol()).

Ak máme vyrobenú štruktúru grafu (ako zoznam množín susedov), vieme z nej priamo vytvoriť triedu graf:

>>> a,b,c,d,e,f,g,h = range(8)
>>> gg = [{b,c,d,e,f},{c,e},{d},{e},{f},{c,g,h},{f,h},{f,g}]
>>> graf = Graf(gg)
>>> print(graf)
vrcholy: [0, 1, 2, 3, 4, 5, 6, 7]
hrany: [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 2), (1, 4), (2, 3),
(3, 4), (4, 5), (5, 2), (5, 6), (5, 7), (6, 5), (6, 7), (7, 5), (7, 6)]
>>> graf.je_hrana(b, e)
True
>>> graf.je_hrana(c, a)
False
>>> print('stupen vrcholu f:', graf.stupen(f))
stupen vrcholu f: 3

V tejto reprezentácii grafu triedou Graf o samotnom vrchole nemáme žiadnu špeciálnu informáciu okrem jeho poradového čísla a prislúchajúcej množiny susedov.

Zadefinujeme novú triedu Graf, ktorá bude uchovávať zoznam vrcholov, t.j. zoznam objektov typu Vrchol:

class Graf:

    class Vrchol:
        def __init__(self, meno):
            self.meno = meno
            self.sus = set()

    #-------

    def __init__(self):
        self.zoz = []

    def pridaj_vrchol(self, meno):      # vráti inštanciu Vrchol
        for v in self.zoz:
            if v.meno == meno:
                return v                # už existuje
        novy = self.Vrchol(meno)
        self.zoz.append(novy)
        return novy

    def hladaj_vrchol(self, meno):      # vráti inštanciu Vrchol
        for v in self.zoz:
            if v.meno == meno:
                return v
        return None

    def pridaj_hranu(self, v1, v2):
        self.pridaj_vrchol(v1).sus.add(v2)

    def je_hrana(self, v1, v2):
        return v2 in self.hladaj_vrchol(v1).sus

    def daj_vrcholy(self):
        return [v.meno for v in self.zoz]

    def daj_hrany(self):
        return [(v1.meno, v2) for v1 in self.zoz for v2 in v1.sus]

    def stupen(self, v=None):
        if v is not None:
            return len(self.hladaj_vrchol(v).sus)
        return max(len(v.sus) for v in self.zoz)

    def __str__(self):
        return f'vrcholy: {self.daj_vrcholy()}\nhrany: {self.daj_hrany()}'

S vrcholmi teraz musíme pracovať prostredníctvom ich mien, t.j. jednoznakových reťazcov, napríklad

>>> graf = Graf()
>>> for v1, v2 in 'ab ac ad ae af bc be cd de ef fc fg fh gf gh hf hg'.split():
        graf.pridaj_hranu(v1, v2)
>>> print(graf)
vrcholy: ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
hrany: [('a', 'c'), ('a', 'b'), ('a', 'e'), ('a', 'd'), ('a', 'f'), ('b', 'c'),
('b', 'e'), ('c', 'd'), ('d', 'e'), ('e', 'f'), ('f', 'g'), ('f', 'c'), ('f', 'h'),
('g', 'h'), ('g', 'f'), ('h', 'g'), ('h', 'f')]
>>> print('stupen vrcholu f:', graf.stupen('f'))
stupen vrcholu f: 3
>>> print('stupen grafu:', graf.stupen())
stupen grafu: 5
>>> print('hrana medzi b, e:', graf.je_hrana('b', 'e'))    # alebo graf.je_hrana(*'be')
hrana medzi b, e: True
>>> print('hrana medzi c, a:', graf.je_hrana('c', 'a'))
hrana medzi c, a: False
>>> print('pocet hran:', len(graf.daj_hrany()))
pocet hran: 17

Zrejme efektívnejšie by sa táto definícia realizovala nie zoznamom vrcholov (typ list), ale asociatívnym poľom (typ dict) vrcholov, v ktorom kľúčom by bol identifikátor vrcholu.

Asociatívne pole množín susedností

Pri realizácii reprezentácie množiny susedností pomocou tried Graf a Vrchol sa ukázalo nešikovné, keď sme mali všetky vrcholy (inštancie triedy Vrchol) uložené v zozname. Pri práci s takýmito vrcholmi sme museli veľakrát preliezať celý zoznam a hľadať vrchol s daným identifikátorom. Ak by sme namiesto toho použili asociatívne pole, výrazne by sa to zjednodušilo, napríklad

graf = {'a': set('bcdef'),   # {'b','c','d','e','f'}
        'b': set('ce'),
        'c': set('d'),
        'd': set('e'),
        'e': set('f'),
        'f': set('cgh'),
        'g': set('fh'),
        'h': set('fg'),
       }

Zapíšeme to pomocou tried Graf a Vrchol:

class Graf:

    class Vrchol:
        def __init__(self, meno):
            self.meno = meno
            self.sus = set()

        def pridaj_hranu(self, v2):
            self.sus.add(v2)

        def __contains__(self, v2):
            return v2 in self.sus

    #-------

    def __init__(self):
        self.zoz = {}

    def pridaj_vrchol(self, meno):
        if meno not in self.zoz:
            self.zoz[meno] = self.Vrchol(meno)

    def pridaj_hranu(self, v1, v2):
        self.pridaj_vrchol(v1)
        self.pridaj_vrchol(v2)
        self.zoz[v1].pridaj_hranu(v2)

    def je_hrana(self, v1, v2):
        return v2 in self.zoz[v1]

    def daj_vrcholy(self):
        return list(self.zoz.keys())

    def daj_hrany(self):
        return [(v1, v2) for v1, v in self.zoz.items() for v2 in v.sus]

    def stupen(self, v=None):
        if v  is not None:
            return len(self.zoz[v].sus)
        return max(len(v.sus) for v in self.zoz.values())

    def __str__(self):
        return f'vrcholy: {self.daj_vrcholy()}\nhrany: {self.daj_hrany()}'

Otestovať to môžeme rovnako ako sme testovali zoznam množín susedností:

graf = Graf()
for v1, v2 in 'ab ac ad ae af bc be cd de ef fc fg fh gf gh hf hg'.split():
    graf.pridaj_hranu(v1, v2)
print(graf)
print('stupen vrcholu f:', graf.stupen('f'))
print('stupen grafu:', graf.stupen())
print('hrana medzi b, e:', graf.je_hrana('b', 'e'))
print('hrana medzi c, a:', graf.je_hrana('c', 'a'))
print('pocet hran:', len(graf.daj_hrany()))

a dostávame úplne rovnaké výsledky:

vrcholy: ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
hrany: [('a', 'e'), ('a', 'f'), ('a', 'c'), ('a', 'd'), ('a', 'b'),
 ('b', 'c'), ('b', 'e'), ('c', 'd'), ('d', 'e'), ('e', 'f'), ('f', 'g'),
 ('f', 'c'), ('f', 'h'), ('g', 'f'), ('g', 'h'), ('h', 'g'), ('h', 'f')]
stupen vrcholu f: 3
stupen grafu: 5
hrana medzi b, e: True
hrana medzi c, a: False
pocet hran: 17

Zoznam asociatívnych polí susedností

Ak máme, napríklad takýto ohodnotený graf:

_images/32_8.png

tak namiesto množiny susedností (prvá reprezentácia grafu) použijeme asociatívne pole (typ dict), v ktorom si pri každom susedovi budeme pamätať aj číslo na hrane, t.j. váhu:

a,b,c,d,e,f,g,h = range(8)

graf = [{b:2,c:1,d:3,e:9,f:4},     #a
        {c:4,e:3},                 #b
        {d:8},                     #c
        {e:7},                     #d
        {f:5},                     #e
        {c:2,g:2,h:9},             #f
        {f:2,h:6},                 #g
        {f:9,g:6},                 #h
        ]

Mohli by sme tu využiť aj reprezentáciu asociatívne pole množín susedností, v ktorej by sme množiny opäť nahradili asociatívnymi poľami, napríklad

a,b,c,d,e,f,g,h = range(8)

graf = {a: {b:2,c:1,d:3,e:9,f:4},
        b: {c:4,e:3},
        c: {d:8},
        d: {e:7},
        e: {f:5},
        f: {c:2,g:2,h:9},
        g: {f:2,h:6},
        h: {f:9,g:6},
        }

Zrejme túto reprezentáciu by sme mali volať asociatívne pole asociatívnych polí susedností. Aj tu môžeme čísla vrcholov nahradiť reťazcami:

graf = {'a': {'b':2,'c':1,'d':3,'e':9,'f':4},
        'b': {'c':4,'e':3},
        'c': {'d':8},
        'd': {'e':7},
        'e': {'f':5},
        'f': {'c':2,'g':2,'h':9},
        'g': {'f':2,'h':6},
        'h': {'f':9,'g':6},
        }

Matica susedností

Graf zapíšeme do dvojrozmernej tabuľky (zoznam zoznamov) veľkosti n x n, kde n je počet vrcholov:

graf = [[0,1,1,1,1,1,0,0],
        [0,0,1,0,1,0,0,0],
        [0,0,0,1,0,0,0,0],
        [0,0,0,0,1,0,0,0],
        [0,0,0,0,0,1,0,0],
        [0,0,1,0,0,0,1,1],
        [0,0,0,0,0,1,0,1],
        [0,0,0,0,0,1,1,0],
        ]

Často sa namiesto 0 a 1 píšu False a True.

Ukážme, ako sa zapisuje práca s takouto reprezentáciou:

>>> a,b,c,d,e,f,g,h = range(8)
>>> print('pocet vrcholov:', len(graf))
pocet vrcholov: 8
>>> print('pocet hran:', sum(map(sum,graf)))
pocet hran: 17
>>> print('stupen vrcholu f:', sum(graf[f]))
stupen vrcholu f: 3
>>> print('hrana medzi b, e:', graf[b][e]==1)
hrana medzi b, e: True
>>> print('hrana medzi c, a:', graf[c][a]==1)
hrana medzi c, a: False

Matica susedností s váhami

Namiesto 0 a 1 v dvojrozmernej tabuľke zapisujeme priamo váhy na príslušných hranách, pričom treba nejako označiť hodnotu, ktorá reprezentuje, že tu nie je hrana, napríklad

a,b,c,d,e,f,g,h = range(8)
_ = -1       # označuje, že tu nie je hrana, mohla tu byť aj hocijaká iná hodnota, napríklad None

graf = [[_,2,1,3,9,4,_,_],
        [_,_,4,_,3,_,_,_],
        [_,_,_,8,_,_,_,_],
        [_,_,_,_,7,_,_,_],
        [_,_,_,_,_,5,_,_],
        [_,_,2,_,_,_,2,9],
        [_,_,_,_,_,2,_,6],
        [_,_,_,_,_,9,6,_],
        ]

Ukážme, ako sa zapisuje práca s takouto reprezentáciou:

>>> print('pocet vrcholov:', len(graf))
pocet vrcholov: 8
>>> print('pocet hran:', sum(1 for r in graf for x in r if x!=_))
pocet hran: 17
>>> print('stupen vrcholu f:', sum(1 for x in graf[f] if x!=_))
stupen vrcholu f: 3
>>> print('hrana medzi b,e:', graf[b][e]!=_)
hrana medzi b,e: True
>>> print('hrana medzi c,a:', graf[c][a]!=_)
hrana medzi c,a: False
>>> print('vaha na hrane medzi b,e:', graf[b][e])
vaha na hrane medzi b,e: 3

Cvičenia

L.I.S.T.


  1. Pre tento daný graf (ručne) zapíš množinu vrcholov a množinu hrán:

    _images/32_9.png

    Odpovedz áno/nie:

    • je tento graf orientovaný?

    • je tento graf súvislý?

    • je tento graf ohodnotený?

    • je tento graf acyklický?

    Potom

    • zapíš nejakú cestu (postupnosť vrcholov) z vrcholu 0 do vrcholu 3

    • nájdi čo najviac rôznych cyklov, ktoré majú dĺžku aspoň 3 a v ktorých sú všetky vrcholy rôzne (okrem prvého a posledného)


  1. Zapíš graf z úlohy (1) v reprezentácii zoznam množín susedností:

    graf = [...]
    

    Potom aj v reprezentácii asociatívne pole množín susedností:

    graf = {...}
    

  1. Nakresli graf (na papieri), ktorý zodpovedá reprezentácii tabuľka susedností:

    A

    B

    C

    D

    E

    F

    A

    7

    5

    1

    B

    2

    7

    3

    C

    2

    8

    D

    1

    2

    4

    E

    6

    5

    F

    1

    8

    Koľko vrcholov a koľko hrán má tento graf?


  1. Zapíš graf z úlohy (3) v reprezentácii asociatívne pole asociatívnych polí susedností:

    graf = {...}
    

  1. Zapíš hodnoty do vrcholov grafu na obrázku, ak poznáš jeho reprezentáciu

    _images/32_10.png

    Toto je reprezentácia grafu:

    graf = [{2, 3, 4}, {3, 4}, {0, 3, 4}, {0, 1, 2}, {0, 1, 2, 5}, {4}]
    

    Potom odpovedz áno/nie:

    • je tento graf orientovaný?

    • je tento graf súvislý?

    • je tento graf ohodnotený?

    • je tento graf acyklický?


  1. Prepíš graf z úlohy (5) do reprezentácie matica susedností:

    graf = [[...], ...]
    

  1. Podľa vzoru triedy Graf pre jednu z reprezentácií (napríklad zoznam množín susedností) zapíš metódy pre reprezentáciu matica susedností:

    class Graf:
    
        def __init__(self, n):              # n je počet vrcholov, t.j. veľkosť matice
            self.matica = [...]             # zadefinuje prázdny graf (v matici sú samé 0)
    
        def pridaj_hranu(self, v1, v2):
            ...
    
        def je_hrana(self, v1, v2):
            return ...
    
        def daj_vrcholy(self):              # vráti množinu čísel vrcholov
            return ...
    
        def daj_hrany(self):                # vráti množinu usporiadaných dvojíc
            return ...
    
        def stupen(self, v1=None):          # zistí stupeň vrcholu alebo celého grafu
            if v1 is not None:
                return ...
            return ...
    
        def __str__(self):
            return f'vrcholy: {self.daj_vrcholy()}\nhrany: {self.daj_hrany()}'
    

  1. Zadefinuj inštanciu triedy z úlohy (7) tak, aby zodpovedala grafu z úloh (5) a (6). Napríklad:

    graf = Graf(...)
    graf.pridaj_hranu(...)
    ...
    for i in graf.daj_vrcholy():
        print('stupen vrcholu', i, 'je', graf.stupen(i))
    

  1. Do triedy Graf z úlohy (7) dopíš tieto dve metódy a otestuj ich na grafe z úlohy (8):

    • je_neorientovany() zistí, či je graf orientovaný (vtedy vráti True)

    • trojuholniky() vypíše všetky také trojice vrcholov, ktoré sú navzájom spojené hranami oboma smermi každý s každým

    class Graf:
        ...
    
        def je_neorientovany(self):
            return ...
    
        def trojuholniky(self):
            print(...)
    

  1. Do triedy Graf z prednášky, ktorá definuje reprezentáciu asociatívne pole množín susedností dodefinuj metódy na vykreslenie grafu:

    class Graf:
        canvas = None
    
        class Vrchol:
            def __init__(self, meno, x, y):
                self.meno = meno
                self.sus = set()
                self.x, self.y = x, y
    
            ...
    
            def kresli(self):           # vykreslí vrchol ako kruh s textom self.meno
                ...
    
            def kresli_hranu(self, vrchol2):           # vykreslí hranu k vrchol2
                ...                                    # netreba kresliť šípky
    
        #-------
    
        def __init__(self):             # inicializácia triedy Graf
            self.graf = {}
    
        def pridaj_vrchol(self, meno, x, y):
            ...
    
        ...
    
        def kresli(self):               # vykreslí celý graf
            ...
    

    Kreslenie otestuj na grafe z úlohy (5).


  1. Do triedy z úlohy (10) doprogramuj inicializáciu __init__() tak, aby sa popis grafu mohol prečítať z textového súboru:

    class Graf:
        ...
    
        #-------
    
        def __init__(self, meno_suboru=None):
            self.graf = {...}
    

    Textový súbor by mohol mať napríklad takýto formát - každý riadok popisuje jeden vrchol:

    meno x y zoznam_mien_susedov
    

    Zadefinuj 2 súbory pre grafy z úloh (1) a (5) tak, aby sa výsledné obrázky čo najviac podobali, napríklad súbor pre graf z úlohy (5) môže začínať týmito dvoma riadkami:

    0 130 130 2 3 4
    1 50 50 3 4
    

9. Domáce zadanie

L.I.S.T.


Vytvor dátovú štruktúru Graf, ktorá bude implementovať graf reprezentovaný ako množina hrán:

class Graf:
    def __init__(self, meno_suboru):
        self.graf = set()
        ...

    def pridaj_hranu(self, v1, v2):
        ...

    def je_hrana(self, v1, v2):
        return False

    def daj_vrcholy(self):
        return set()              # vráti množinu mien vrcholov

    def daj_hrany(self):
        return set()              # vráti množinu dvojíc mien vrcholov

    def uloz1(self, meno_suboru):
        ...

    def uloz2(self, meno_suboru):
        ...

    def uloz3(self, meno_suboru):
        ...

V triede môžeš dodefinovať ďalšie pomocné metódy ale nie ďalšie atribúty s hodnotami. Trieda dokáže pracovať s týmito tromi typmi súborov:

  • typ=1 označuje takýto tvar súboru:

    • súbor začína riadkom: #1

    • každý ďalší riadok popisuje jeden vrchol: meno vrcholu a zoznam mien jeho susedov

    • riadky môžu nasledovať v ľubovoľnom poradí a aj zoznam mien susedov môže byť v ľubovoľnom poradí

    • meno vrcholu je ľubovoľný reťazec, ktorý neobsahuje medzeru

    • napríklad:

      #1
      a b c d e f
      b c e
      c d
      d e
      e f
      f c g h
      g f h
      h f g
      
  • typ=2 označuje takýto tvar súboru:

    • súbor začína riadkom: #2

    • každý ďalší riadok popisuje jednu hranu ako dvojicu mien vrcholov oddelených medzerou

    • riadky môžu nasledovať v ľubovoľnom poradí

    • meno vrcholu je ľubovoľný reťazec, ktorý neobsahuje medzeru

    • napríklad:

      #2
      a c
      a b
      a e
      a d
      a f
      b c
      b e
      c d
      d e
      e f
      f g
      f c
      f h
      g h
      g f
      h g
      h f
      
  • typ=3 označuje takýto tvar súboru:

    • súbor začína riadkom: #3

    • ďalší riadok obsahuje zoznam mien všetkých vrcholov v nejakom poradí

    • všetky ďalšie riadky popisujú maticu susedností, pričom poradie vrcholov je dané prvým riadkom súboru

    • meno vrcholu je ľubovoľný reťazec, ktorý neobsahuje medzeru

    • napríklad:

      #3
      a b c d e f g h
      0 1 1 1 1 1 0 0
      0 0 1 0 1 0 0 0
      0 0 0 1 0 0 0 0
      0 0 0 0 1 0 0 0
      0 0 0 0 0 1 0 0
      0 0 1 0 0 0 1 1
      0 0 0 0 0 1 0 1
      0 0 0 0 0 1 1 0
      

Graf sa inicializuje ľubovoľným z týchto formátov (rozpozná sa z prvého riadku súboru). Graf sa dokáže zapísať do súboru ľubovoľným z týchto formátov (metódami uloz1(), uloz2() a uloz3() podľa typu formátu).

Všetky 3 ukážkové súbory vytvoria rovnaký graf.

Obmedzenia

  • svoje riešenie odovzdaj v súbore riesenie.py najneskôr do 31. mája, pričom sa v ňom bude nachádzať len jedna definícia triedy Graf.

  • prvé tri riadky tohto súboru budú obsahovať:

    # 9. zadanie: gaf
    # autor: Janko Hrasko
    # datum: 31.4.2020
    
  • zrejme ako autora uvedieš svoje meno

  • atribút graf v triede Graf musí obsahovať reprezentáciu grafu množinou hrán (typu set, pričom hrany sú dvojice mien vrcholov, t.j. tuple); v triede nedefinuj ďalšie atribúty

  • program by nemal počas testovania testovačom nič vypisovať (žiadne testovacie print())

  • testovač bude spúšťať definíciu triedy s rôznymi textovými súbormi, ktoré si môžeš stiahnuť z L.I.S.T.u