Grafos

import numpy as gr # Usamos gr como alias para numpy
import sys

class Grafo:

    def __init__(self):
        #constriumos el objeto grafo, inicializamos en una matriz de 8 x 8 con ceros.
        #definimos los nodos desde la A hasta la H
        fila = 8
        columna = 8
        self.Matriz = gr.zeros((fila,columna), dtype=int)
        self.nodos = ['A','B','C','D','E','F','G','H']

    def agregar_peso (self, nodo1, nodo2, peso):
        #Convierto las letras a indice
        index1 = self.nodos.index(nodo1)
        index2 = self.nodos.index(nodo2)
        #Agrego el peso a la matriz
        self.Matriz[index1][index2]= peso

    def mostrar_matriz___(self):
        print("Matriz de adyacencia:")
        print(" " + " ".join(self.nodos)) # con .join uno los elementos en una sola cadena
        for i, fila in enumerate(self.Matriz): #enumerate se utiliza para obtener tanto el índice (i) como el contenido de cada fila (fila)
            print(self.nodos[i], " ".join(map(str, fila)))
    
    def agregar_nodo(self, nuevo_nodo):
        if nuevo_nodo not in self.nodos: # verifico que el nodo no este
            self.nodos.append(nuevo_nodo)
            # Ampliar la matriz para incluir el nuevo nodo
            nueva_matriz = gr.zeros((len(self.nodos), len(self.nodos)), dtype=int) # genero una nueva matriz con los tamaños que tengo
            nueva_matriz[:self.Matriz.shape[0], :self.Matriz.shape[1]] = self.Matriz # copio los valores de filas y columna de la matriz
            self.Matriz = nueva_matriz
            print(f"Nodo {nuevo_nodo} agregado.")
        else:
            print("El nodo ya existe.")

    def agregar_arista(self, nodo1, nodo2, peso):
        if nodo1 in self.nodos and nodo2 in self.nodos: # busco los nodos y condiciono para que existan
            self.agregar_peso(nodo1, nodo2, peso)
            print(f"Arista agregada de {nodo1} a {nodo2} con peso {peso}.")
        else:
            print("Uno o ambos nodos no existen.")

    def ingresar_valores(self):
        print("Por favor, ingresa 8 valores para la matriz:")
        #solicito los valores de los tramos
        while True:
                #capturo errores de ingreso
                try:
                    peso_AB = int(input ("Ingrese el recorrido A-B: "))
                    peso_AC = int(input ("Ingrese el recorrido A-C: "))
                    peso_BD = int(input ("Ingrese el recorrido B-D: "))
                    peso_BG = int(input ("Ingrese el recorrido B-G: "))
                    peso_CD = int(input ("Ingrese el recorrido C-D: "))
                    peso_CF = int(input ("Ingrese el recorrido C-F: "))
                    peso_DE = int(input ("Ingrese el recorrido D-E: "))
                    peso_DF = int(input ("Ingrese el recorrido D-F: "))
                    peso_EG = int(input ("Ingrese el recorrido E-G: "))
                    peso_EH = int(input ("Ingrese el recorrido E-H: "))
                    peso_FH = int(input ("Ingrese el recorrido F-H: "))
                    # condiciono para que los valores ingresados sean positivos
                    if peso_AB <= 0 or peso_AC <= 0 or peso_BD <= 0 or peso_BG <= 0 or peso_CD <= 0 or peso_CF <= 0 or peso_DE <= 0 or peso_DF <= 0 or peso_EG <= 0 or peso_FH <= 0 or peso_EH <= 0:
                        print("Los núemros de los recorridos deben ser positivos , ((((()))))")
                        print("--------- Intente otra vez ------" )
                        break
                    else:
                        self.agregar_peso('A', 'B', peso_AB)
                        self.agregar_peso('A', 'C', peso_AC)
                        self.agregar_peso('B', 'D', peso_BD)
                        self.agregar_peso('B', 'G', peso_BG)
                        self.agregar_peso('C', 'D', peso_CD)
                        self.agregar_peso('C', 'F', peso_CF)
                        self.agregar_peso('D', 'F', peso_DF)
                        self.agregar_peso('D', 'E', peso_DE)
                        self.agregar_peso('E', 'G', peso_EG)
                        self.agregar_peso('E', 'H', peso_EH)
                        self.agregar_peso('F', 'H', peso_FH)
                        break
                except ValueError:
                    print("Por favor, ingresa un número entero válido.")

    def dijkstra (self, inicio, fin):
            num_nodos = len(self.nodos)
            distancias = [float('inf')] * num_nodos
            distancias[self.nodos.index(inicio)] = 0
            visitados = [False] * num_nodos
            predecesores = [None] * num_nodos

            for _ in range(num_nodos): # el _ significa que no es necesario un valor sino que se usa para recorrer el bucle
                nodo_actual = min((i for i in range(num_nodos) if not visitados[i]), #Este es un generador que itera sobre todos los índices de los nodos (de 0 a num_nodos - 1).
                                   key=lambda i: distancias[i], default=None)       #if not visitados[i] filtra solo los nodos que no han sido visitados. 
                                                                                 #Así, solo se consideran aquellos nodos que aún no han sido procesados por el algoritmo.
                if nodo_actual is None or distancias[nodo_actual] == float('inf'):
                    break
                visitados[nodo_actual] = True
                for vecino in range(num_nodos):
                    peso_arista = self.Matriz[nodo_actual][vecino]
                    if peso_arista > 0:
                        nueva_distancia = distancias[nodo_actual] + peso_arista
                        if nueva_distancia < distancias[vecino]:
                            distancias[vecino] = nueva_distancia
                            predecesores[vecino] = nodo_actual

            camino = []
            nodo = self.nodos.index(fin)
            while nodo is not None:
                camino.append(self.nodos[nodo])
                nodo = predecesores[nodo]
            camino.reverse()
            return camino, distancias[self.nodos.index(fin)]
       


grafo = Grafo() # creo una instancia del objeto
print(grafo.mostrar_matriz___())
grafo.ingresar_valores()
print(grafo.mostrar_matriz___())

# Agregar un nuevo nodo
#grafo.agregar_nodo('I')

# Agregar una nueva arista
#grafo.agregar_arista('A', 'I', 5)

# Mostrar la matriz actualizada
#print(grafo.mostrar_matriz___())

 # Solicitar al usuario el nodo de inicio
inicio = input("Ingresa el nodo de inicio (A-H): ").strip().upper()

if inicio in grafo.nodos: 
        camino, distancia = grafo.dijkstra(inicio, 'H')
        print(f"El camino más corto de {inicio} a H es: {' -> '.join(camino)} con una distancia de {distancia}.")
else:
    print("Nodo de inicio inválido. Debe ser entre A y H.")