Zadanie skúšky z 10.6.2021


Galéria umenia má v rôznych sálach (miestnostiach) diela jednotlivých umelcov. Z niektorých sál sa vieme presunúť do iných (sú medzi nimi dvere, chodby, schodištia, …). Každá sála má priradené číslo, ktoré vyjadruje momentálnu návštevnícku popularitu daného umelca a jeho diel.

Vieme, ktorá sála je vstupná do galérie a ktorou sa z galérie odchádza. Navrhni takú trasu, ktorou získaš čo najväčší súčet čísel popularity navštívených sál.

Pravidlá galérie nedovoľujú návštíviť tú istú sálu (toho istého umelca) viackrát, to znamená, že keď z nejakej sály odídeme, nesmieme do nej znovu vojsť. Výnimkou je prípad, keď vstup aj výstup do galérie je v tej istej sále.

V reči grafov: je daný neorientovaný neohodnotený graf, pre ktorý je v každom vrchole zadané nejaké celé číslo (tzv. popularita). Úlohou je nájsť takú trasu medzi dvoma danými vrcholmi, pre ktorú je súčet číselných hodnôt vo vrcholoch maximálny. Ak je štartový a cieľový vrchol rovnaký, úlohou je nájsť cyklus.

Zadefinuj metódy triedy Galeria:

class Galeria:
    def __init__(self, meno_suboru):
        ...

    def umelci(self):
        return ...

    def prechody(self, meno):
        return ...

    def __getitem__(self, meno):
        return ...

    def __setitem__(self, meno, cislo):
        ...

    def zmen_prechod(self, meno1, meno2):
        ...

    def trasa(self, meno1, meno2):
        return ...

Metódy:

  • __init__ prečíta súbor a vytvorí z neho nejakú grafovú reprezentáciu

  • umelci() vráti množinu mien všetkých umelcov

  • prechody(meno) vráti množinu (set) mien všetkých umelcov, ku ktorým sa dá priamo prejsť zo sály umelca meno

  • __getitem__(meno) vráti číselnú popularitu daného umelca (alebo KeyError)

  • __setitem(meno, cislo) nastaví novú číselnú popularitu pre daného umelca (bude sa testovať len pre existujúceho umelca)

  • zmen_prechod(meno1, meno2) ak bol prechod medi meno1 a meno2, tak ho zruší, inak ho vytvorí

  • trasa(vstup, vystup) nájde najvýhodnejšiu trasu (ako postupnosť mien umelcov) - oba parametre sú mená umelcov, ak sa vstup == vystup, hľadá cyklus v grafe; ak trasa neexistuje vráti None, inak vráti dvojicu: samotnú trasu (list) a súčet popularity navštívených vrcholov

Pre cyklus musí platiť, že prvý a posledný vrchol v trase je rovnaký a trasa musí mať aspoň 4 vrcholy (teda minimálne 3 hrany).

V textovom súbore máme kompletné informácie o galérii:

  • v súbore sú riadky dvoch typov

  • buď je to meno umelca s jeho číselnou popularitou (teda dvojica reťazec číslo)

  • alebo prechod z jednej sály (jedného umelca) do druhej (k druhému umelcovi) (teda dvojica reťazec reťazec)

Ak pre niektorého umelca nemáme zadanú jeho číselnú popularitu, predpokladáme hodnotu 0.

Napríklad 'subor1.txt' popisuje graf s piatimi vrcholmi, ktoré sú spojené piatimi hranami:

Galanda 5
Fulla Alexy
Benka Galanda
Alexy 15
Benka Fulla
Cipar Galanda
Benka 10
Galanda Alexy

Napríklad tento test:

if __name__ == '__main__':
    g = Galeria('subor1.txt')
    for m in g.umelci():
        print(f'g[{m!r}] =', g[m], '  prechody =', g.prechody(m))
    for m1, m2 in ('Fulla', 'Galanda'), ('Benka', 'Benka'), ('Cipar', 'Cipar'):
        print(f'g.trasa({m1!r}, {m2!r}) =', g.trasa(m1, m2))

vypíše (možno v inom poradí):

g['Benka'] = 10   prechody = {'Fulla', 'Galanda'}
g['Cipar'] = 0   prechody = {'Galanda'}
g['Fulla'] = 0   prechody = {'Benka', 'Alexy'}
g['Alexy'] = 15   prechody = {'Fulla', 'Galanda'}
g['Galanda'] = 5   prechody = {'Benka', 'Cipar', 'Alexy'}
g.trasa('Fulla', 'Galanda') = (['Fulla', 'Alexy', 'Galanda'], 20)
g.trasa('Benka', 'Benka') = (['Benka', 'Galanda', 'Alexy', 'Fulla', 'Benka'], 30)
g.trasa('Cipar', 'Cipar') = None

Z úlohového servera L.I.S.T. si stiahni kostru programu skuska.py. Pozri si testovacie dáta v súboroch 'subor1.txt', 'subor2.txt', 'subor3.txt', …, ktoré bude používať testovač. Aby si mohol spúšťať skúškové testy, program ulož do súboru skuska.py. Riešenie (bez dátových súborov) odovzdaj na úlohový server https://list.fmph.uniba.sk/. Tvoj odovzdaný program musí začínať tromi riadkami komentárov:

# 1. skuska: galeria
# autor: Janko Hraško
# datum: 10.6.2021