Zadanie skúšky z 1.2.2019¶

Naprogramujte metódy triedy Graph (neorientovaný ohodnotený graf) pre reprezentáciu asociatívne pole susedov (z úlohového servera L.I.S.T. si stiahnite kompletnú verziu skuska.py):

class Graph:
    def __init__(self, filename):
        self.vertices = {}
        self.d = {}
        ...

    def incident_edges(self, name1):   # generátor, vracia dvojice meno a vahu
        ...

    def dijkstra(self, name1):
        ...

    def get_path(self, name1, name2):
        ...
        return None

Atribút vertices popisuje všetky vrcholy spolu aj s príslušnými hranami a ich váhami. Realizujte ho asociatívnym poľom, v ktorom pre každé meno vrcholu priradíme asociatívne pole susediacich vrcholov. Keďže graf je neorientovaný, každá hrana bude v tejto štruktúre zaznačená dvakrát (pre oba smery). Atribút d bude asociatívne pole, ktoré sa využije pri dijkstrovom algoritme.

Metóda

• __init__ prečíta textový súbor a vytvorí z neho neorientovaný graf. Každý riadok súboru popisuje jednu hranu: mená dvoch vrcholov a celočíselnú váhu (hodnotu na hrane)
• incident_edges vráti generátor so všetkými susediacimi vrcholmi aj s príslušnými váhami (dvojice meno vrcholu a váha), ktoré vychádzajú z daného vrcholu

Teraz doprogramujte dijkstrov algoritmus z prednášky (metódu dijkstra(meno1) s parametrom meno štartového vrcholu), pseudokód:

def dijkstra(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
    visited = set()
    while queue:
        vrchol1 = queue.remove_min()
        visited.add(vrchol1)
        for vrchol2 in susediace_vrcholy(vrchol1):
            if vrchol2 nie je v visited:
                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

Pritom

• namiesto poľa D použite asociatívne pole v atribúte d (kľúčom je meno vrcholu)
• prioritný front vrcholov nemusíte programovať ako optimálnu dátovú štruktúru - stačí použiť obyčajný zoznam mien vrcholov, ktorý bude utriedený podľa príslušných hodnôt v poli d
• metóda nebude vracať žiadnu hodnotu

Ďalej doprogramujte metódu get_path(meno1, meno2), ktorá pre vypočítané vzdialeností (v atribúte d) z dijkstrovho algoritmu dokáže zrekonštruovať cestu od štartového vrcholu s meno1 do cieľového s meno2:

• začnite od konca: pre cieľový vrchol nájdete 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 vrátiť ako postupnosť (list) vrcholov (mien), alebo vráti None, ak cesta neexistuje

Napr. pre subor1.txt:

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

program môžete testovať napr. takto:

if __name__ == '__main__':
    g = Graph('subor1.txt')
    g.dijkstra('0')
    print('d = ', *(g.d[name] for name in sorted(g.vertices)))
    path = g.get_path('0', '8')
    print(*path)
    path = g.get_path('0', '5')
    print(*path)
    path = g.get_path('0', '0')
    print(*path)

Výpis potom bude:

d =  0 5 11 3 7 8 5 6 9
0 3 6 7 4 5 8
0 3 6 7 4 5
0

Aby ste mohli spúšťať skúškové testy, program uložte do súboru skuska.py. Pozrite si testovacie dáta v súboroch 'subor1.txt', 'subor2.txt', 'subor3.txt', …, ktoré bude používať testovač.

Riešenie odovzdajte na úlohový server L.I.S.T..

Praktická časť končí o 11:00 a skúška ďalej pokračuje od 12:00 vyhodnotením v kancelárii m162.