Dijkstrav1

# -*- coding: utf-8 -*-
"""
Created on Thu Dec  2 14:30:30 2021

@author: HRodriguez
"""
import sys

class Grafica:
    
    def __init__(self, vertices, aristas):
        self.vertices = vertices
        self.aristas= aristas
        
    def get_aristas(self):
        return self.aristas
    
    def get_vertices(self):
        return self.vertices
    
    def getVecinos(self, vertice_name):
        vecinos = []
        for arista in self.aristas:
            if arista.von == vertice_name:
                vecinos.append(arista.vdn)
    
        return vecinos

    def existeVertice(self, name):
        for v in self.vertices:
            if v.nombre == name:
                return v
        return None
    
    def existeArista(self, nvo, nvd):
        for a in self.aristas:
            if a.von == nvo and a.vdn == nvd:
                return a
        return None
        
        
class Vertice:
    
    def __init__(self, nombre, valor):
        self.nombre  = nombre
        self.valor = valor
        
    def setValor(self, valor):
        self.valor = valor
        
        
    def __str__(self):
        return "Vertice N: "+self.nombre+" V:"+str(self.valor)
    
    
class VerticeDijkstra(Vertice):
    
    def __init__(self, nombre, valor):
        self.nombre  = nombre
        self.valor = valor 
        self.vanterior = None
        
    def setVerAnt(self, nombre_vertice_anterior):
        self.vanterior = nombre_vertice_anterior
        
    def __str__(self):
        return "Vertice N: "+self.nombre+" V:"+str(self.valor)+" VA:"+str(self.vanterior)
    
class Arista:
    
    def __init__(self, v_origen_nombre, v_destino_nombre, valor):
       self.von = v_origen_nombre
       self.vdn = v_destino_nombre
       self.valor = valor
    
    def __str__(self):
        return "Arista VO: "+self.von+" VD: " +self.vdn+ " V: " + str(self.valor)
    
    
    
class Dijkstra():
    
    def __init__(self, grafica, nombre_nodo_soruce):
        self.g = grafica
        self.nns = nombre_nodo_soruce
        self.s = []
        self.q = []
        
    
    def inicializa(self):
        for vertice in self.g.get_vertices():
            if vertice.nombre == self.nns:
                vertice.valor = 0
            else:
                vertice.valor = sys.maxsize
    
    def inicializa_q(self):
        for vertice in self.g.get_vertices():
            self.q.append(vertice.nombre)
            
    def extrae_minimo(self):
        vertice_minimo = None
        vertice_valor_minimo = sys.maxsize
        for vertice_name in self.q:
            vertice_obj = self.g.existeVertice(vertice_name)
            if vertice_obj.valor <= vertice_valor_minimo:
                vertice_valor_minimo = vertice_obj.valor
                vertice_minimo = vertice_name
                
        return vertice_minimo
    
    
    def getCamino(self, nombre_vertice_destino):
        vertice_destino = self.g.existeVertice(nombre_vertice_destino)
        strCamino = "->"+(nombre_vertice_destino)
        nombreVerticeAnterior = vertice_destino.vanterior
        while nombreVerticeAnterior:
            vertice_anterior = self.g.existeVertice(nombreVerticeAnterior)
            strCamino = "->"+(nombreVerticeAnterior) + strCamino
            nombreVerticeAnterior = vertice_anterior.vanterior
            
        return strCamino[2:]            
            
    def corre_alg(self):
        while self.q :
            nv_minimo = self.extrae_minimo()
            vertice_origen = self.g.existeVertice(nv_minimo)
            vecinos = self.g.getVecinos(nv_minimo)
            for vecino in vecinos:
                vertice_destino = self.g.existeVertice(vecino)
                arista = self.g.existeArista(nv_minimo, vecino)
                peso_vertice_origen = vertice_origen.valor
                peso_vertice_destino = vertice_destino.valor
                peso_arista = arista.valor
                pvo_mas_pa = peso_vertice_origen + peso_arista
                if pvo_mas_pa < peso_vertice_destino:
                    vertice_destino.valor = pvo_mas_pa
                    vertice_destino.vanterior = nv_minimo
            
            self.s.append(nv_minimo)
            self.q.remove(nv_minimo)
                
    def __str__(self):
        valores_de_s = "Los elementos en S: "
        for vertice in self.s:
            valores_de_s += vertice + " "
            
        valorer_de_q = "Los elementos de Q:"
        for vertice in self.q:
            valorer_de_q += vertice + " "
            
        valores_de_los_vertices = "Y los valores de los pesos actuales son: "
        for vertice in self.g.get_vertices():
            valores_de_los_vertices += vertice.nombre + ":"+str(vertice.valor)+" "
    
        return valores_de_s + "\n"+ valorer_de_q+ "\n"+valores_de_los_vertices
vertices = []
aristas = []
vertices.append(VerticeDijkstra("S", 0))
vertices.append(VerticeDijkstra("T", 0))
vertices.append(VerticeDijkstra("Y", 0))
vertices.append(VerticeDijkstra("X", 0))
vertices.append(VerticeDijkstra("Z", 0))
aristas.append(Arista("S", "T", 10))
aristas.append(Arista("S", "Y", 5))
aristas.append(Arista("T", "X", 1))
aristas.append(Arista("T", "Y", 2))
aristas.append(Arista("Y", "T", 3))
aristas.append(Arista("Y", "X", 9))
aristas.append(Arista("Y", "Z", 2))
aristas.append(Arista("Z", "X", 6))
aristas.append(Arista("Z", "S", 7))
aristas.append(Arista("X", "Z", 4))

g1 = Grafica(vertices, aristas)

dijs = Dijkstra(g1, "S")
dijs.inicializa()
dijs.inicializa_q()
dijs.corre_alg()
print(dijs)
print (dijs.getCamino("X"))
import pdb; pdb.set_trace()