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ú kolieska

  • 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 _images/32_1.png _images/32_2.png _images/32_3.png _images/32_4.png _images/32_5.png _images/32_6.png

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. 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. vzdialenosť dvoch miest, cena cestovného lístka, linky, ktoré spájajú dve zastávky, …

  • 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

  • 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. 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. 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. keď v dialógovom režime zapíšeme >>> graf. Metóda __str__() sa zavolá, napr. 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.

>>> 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.

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. 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.

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.

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. 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

    • graf

      _images/32_9.png
    • odpovedz áno/nie:

      • je tento graf orientovaný?

      • je tento graf súvislý?

      • je tento graf ohodnotený?

      • je tento graf acyklický?

    • 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 zadanej reprezentácii

    • zoznam množín susedností

      graf = [...]
      
    • asociatívne pole množín susedností

      graf = {...}
      

  1. Nakresli graf (na papieri), ktorý zodpovedá tejto 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. Označ vrcholy grafu na obrázku, ak poznáš jeho reprezentáciu

    • graf

      _images/32_10.png
    • reprezentácia

      graf = [{2, 3, 4}, {3, 4}, {0, 3, 4}, {0, 1, 2}, {0, 1, 2, 5}, {4}]
      
    • 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. „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.

      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íš zadané metódy a otestuj ich na grafe z úlohy (8)

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

      class Graf:
          ...
      
          def je_neorientovany(self):
              return ...
      
    • 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 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

    • napr.

      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):
              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

    • inicializácia grafu

      class Graf:
          ...
      
          #-------
      
          def __init__(self, meno_suboru=None):
              self.graf = {...}
      
    • textový súbor by mohol mať napr. 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. 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.

Vytvoriť 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 uloz(self, meno_suboru, typ=1):
        ...

V triede môžete 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.

      #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.

      #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.

      #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 (metódou uloz()) ľubovoľným z týchto formátov.

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

Obmedzenia

  • vaše riešenie odovzdajte v súbore riesenie9.py, 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: 22.4.2019
    
  • zrejme ako autora uvediete 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áš program by nemal počas testovania testovačom nič vypisovať (žiadne vaše testovacie print())

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