Operacijske raziskave - vaje 11.5.2020

class Graf:
    ...

    def DFS(G, previsit=None, postvisit=None, koreni=None):
        def nothing(u, v):
            pass
        if previsit is None:
            previsit = nothing
        if postvisit is None:
            postvisit = nothing
        if koreni is None:
            koreni = G.vozlisca()
        globina = {}
        stars = {}
        def obisci(u, v):
            if u in globina:
                return
            globina[u] = globina[v] + 1 if v is not None else 0
            stars[u] = v
            previsit(u, v)
            for w in G.sosedi(u):
                obisci(w, u)
            postvisit(u, v)
        for w in koreni:
            obisci(w, None)
        for u in G.vozlisca():
            if u not in globina:
                globina[u] = float('inf')
                stars[u] = None
        return (globina, stars)

graph TD

A --- B
B --- C
C --- F
F --- E
F --- I

D --- G
G --- H

class UtezenDigraf(Digraf):
    ...

    def bellmanFord(G, koren):
        razdalje = {v: 0 if v == koren else float('inf')
                    for v in G.vozlisca()}
        stars = {koren: None}
        naslednji = {koren}
        for i in range(len(G)):
            if len(naslednji) == 0:
                break
            trenutni, naslednji = naslednji, set()
            for v in trenutni:
                d = razdalje[v]
                for w, r in G.utezeniSosedi(v).items():
                    r += d
                    if r < razdalje[w]:
                        razdalje[w] = r
                        stars[w] = v
                        naslednji.add(w)
        else: # če se for zanka ne konča z break
            if len(naslednji) > 0:
                raise ValueError("graf ima negativen cikel")
        return (razdalje, stars)

graph TD

A -- 3 --> B
B -- 7 --> C
B -- 9 --> E
C -- -7 --> D
D -- 4 --> H
H -- -5 --> G
G -- -1 --> F

class Digraf(Graf):
    ...

    def topoloskoUrejanje(G):
        stopnje = {u: len(G.vhodniSosedi(u)) for u in G.vozlisca()}
        vrsta = {u for u, s in stopnje.items() if s == 0}
        urejanje = []
        while len(vrsta) != 0:
            u = vrsta.pop()
            urejanje.append(u)
            for v in G.izhodniSosedi(u):
                stopnje[v] -= 1
                if stopnje[v] == 0:
                    vrsta.append(v)
        return urejanje