Zadanie skúšky z 14.1.2019

Naprogramujte metódy triedy Graph (neorientovaný ohodnotený graf) pre reprezentáciu pomocou zoznamu hrán (z úlohového servera L.I.S.T. si stiahnite kompletnú verziu skuska.py):

class Vertex:
    def __init__(self, name):
        self.name = name
        self.d = None

class Edge:
    def __init__(self, start, end, weight):    # start a end sú typu Vertex
        self.start = start
        self.end = end
        self.weight = weight

class Graph:
    def __init__(self, filename):
        self.vertices = []
        self.edges = []
        ...

    def get_vertex(self, name):
        return ...

    def insert_edge(self, name1, name2, weight):
        ...

    def incident_edges(self, vertex):
        ...

Dátová štruktúra Graph bude využívať triedy Vertex (pre vrcholy) a Edge (pre hrany). Atribút vertices bude obsahovať zoznam všetkých vrcholov grafu (inštancie Vertex), atribút edges bude obsahovať všetky hrany grafu (inštancie Edge), keďže graf je neorientovaný, každá hrana bude v tomto zozname dvakrát (pre oba smery). Nepoužívajte žiadne ďalšie atribúty.

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)
  • get_vertex vráti inštanciu Vertex: ak už existuje vrchol s týmto menom v zozname vertices vráti tento objekt, inak vyrobí nový a pridá ho do zoznamu vertices
  • insert_edge vloží do edges novú hranu - vloží oba smery (parametrami sú dva reťazce a celé číslo)
  • incident_edges vráti generátor so všetkými hranami (inštancie Edge), ktoré vychádzajú z daného vrcholu (typu Vertex)

Teraz doprogramujte dijkstrov algoritmus z prednášky (metódu dijkstra(vertex) s parametrom typu Vertex), 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 atribút d v každom vrchole
  • prioritný front vrcholov nemusíte programovať ako optimálnu dátovú štruktúru - stačí použiť obyčajný zoznam dvojíc (d[vrchol], vrchol), ktorý budeš treba udržiavať utriedený
  • metóda nebude vracať žiadnu hodnotu

Ďalej doprogramujte metódu get_path(vertex1, vertex2), ktorá pre vypočítané vzdialeností (atribút d vo vrcholoch) z dijkstrovho algoritmu dokáže zrekonštruovať cestu od štartu vertex1 do cieľa vertex2:

  • 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 (inštancií Vertex), 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')
    v1 = g.get_vertex('0')
    g.dijkstra(v1)
    path = g.get_path(v1, g.get_vertex('8'))
    print(*(v.name for v in path))
    path = g.get_path(v1, g.get_vertex('5'))
    print(*(v.name for v in path))

Výpis potom bude:

0 3 6 7 4 5 8
0 3 6 7 4 5

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.



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