# Univerzitet u Novom Sadu, Fakultet tehničkih nauka, Novi Sad, Srbija
# Studijski program OAS Informacioni inženjering
# Predmet Metode i tehnike nauke o podacima

# Pomoćni sadržaj


# %% Pomoćne klase

class Graf:
    def __init__(self, nazivi_čvorova):
        self.mreža = {naziv: {} for naziv in nazivi_čvorova}

    def formiranje_grane(self, naziv_polaznog_čvora, naziv_odredišnog_čvora, 
                         težina=1):
        self.mreža[naziv_polaznog_čvora][naziv_odredišnog_čvora] = težina
        self.mreža[naziv_odredišnog_čvora][naziv_polaznog_čvora] = težina
    
    def __str__(self):
        redovi = []
        for k, s in self.mreža.items():
            redovi.append("'{}' : {}".format(k, s))
        return "\n".join(redovi)

class ČvorPretrage:
    def __init__(self, naziv, nadređeni, vrednost):
        self.naziv = naziv
        self.nadređeni = nadređeni
        self.vrednost = vrednost

    def __str__(self):
        return ("Čvor ({} | {} | {})".format(
            self.naziv, 
            self.nadređeni if self.nadređeni is not None else "/", 
            self.vrednost))


# %% Implementacija pohlepne pretrage

class PretragaPohlepna:
    def __init__(self, graf, početak, cilj, heuristika):
        self.graf = graf
        self.početak = početak
        self.cilj = cilj
        self.heuristika = heuristika
        self.neobrađeno = []
        self.obrađeno = {}

    def pretraživanje(self, prikaz=True):
        korak = 0
        self.neobrađeno = []
        self.obrađeno = {}
        
        self.neobrađeno.append(ČvorPretrage(self.početak, None,
                                            self.heuristika(self.početak,
                                                            self.cilj)))
        while self.neobrađeno:
            korak += 1
            trenutni_čvor = self.neobrađeno.pop(0)

            if prikaz:
                print("\t", "{}. trenutni čvor: {}".format(
                    korak, trenutni_čvor))

            if trenutni_čvor.naziv == self.cilj:
                rešenje = []
                cena = 0
                while trenutni_čvor is not None:
                    rešenje.append(trenutni_čvor.naziv)
                    if trenutni_čvor.nadređeni is not None:
                        cena += (self.graf.mreža[trenutni_čvor.nadređeni.naziv]
                                 [trenutni_čvor.naziv])
                    trenutni_čvor = trenutni_čvor.nadređeni
                rešenje.reverse()
                return (rešenje, cena)

            for k, s in self.graf.mreža[trenutni_čvor.naziv].items():
                if (k not in self.obrađeno and 
                    not [a for a in self.neobrađeno if a.naziv == k]):
                    novi_čvor = ČvorPretrage(k, trenutni_čvor,
                                             self.heuristika(k, self.cilj))
                    
                    for a, b in enumerate(self.neobrađeno):
                        if novi_čvor.vrednost < b.vrednost:
                            self.neobrađeno.insert(a, novi_čvor)
                            break
                    else:
                        self.neobrađeno.append(novi_čvor)

            self.obrađeno[trenutni_čvor.naziv] = trenutni_čvor

        return None


# %% Formiranje grafa

graf = Graf(["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"])

graf.formiranje_grane("A", "B", 2)
graf.formiranje_grane("A", "C", 3)
graf.formiranje_grane("A", "D", 4)

graf.formiranje_grane("B", "E", 3)
graf.formiranje_grane("B", "F", 4)
graf.formiranje_grane("C", "F", 5)
graf.formiranje_grane("D", "F", 2)
graf.formiranje_grane("D", "G", 3)

graf.formiranje_grane("E", "H", 3)
graf.formiranje_grane("F", "H", 2)
graf.formiranje_grane("F", "I", 5)
graf.formiranje_grane("F", "J", 3)
graf.formiranje_grane("G", "J", 2)

graf.formiranje_grane("H", "K", 4)
graf.formiranje_grane("I", "K", 4)
graf.formiranje_grane("J", "K", 2)

print("Graf")
print(graf)
print("")


# %% Definisanje heuristike

koordinate = {
    "A": (3, 5),
    "B": (2, 4),
    "C": (3, 4),
    "D": (4, 4),
    "E": (1, 3),
    "F": (3, 3),
    "G": (5, 3),
    "H": (2, 2),
    "I": (3, 2),
    "J": (4, 2),
    "K": (3, 1)
}

def heuristika(a, b):
    ka = koordinate[a]
    kb = koordinate[b]
    return abs(ka[0] - kb[0]) + abs(ka[1] - kb[1])

print("Heuristika A -> K: {}".format(heuristika("A", "K")))
print("Heuristika A -> G: {}".format(heuristika("A", "G")))
print("Heuristika E -> C: {}".format(heuristika("E", "C")))
print("Heuristika H -> D: {}".format(heuristika("H", "D")))
print("")


# %% Izvođenje pohlepne pretrage

pretraga = PretragaPohlepna(graf, "A", "K", heuristika)

print("Pretraga")
rešenje = pretraga.pretraživanje()
print("")

print("Rešenje: {}".format(rešenje if rešenje is not None else "/"))