Implementación de Estructuras de Datos de Grafos en Python

Este documento detalla la implementación de una estructura de datos de grafo en Python, incluyendo la definición de nodos, la gestión de conexiones y la aplicación de algoritmos para encontrar caminos y optimizar costos.

Clase `NodoGrafo`

Representa un nodo individual dentro del grafo.

• `__init__(self, valor)`: Constructor de la clase `NodoGrafo`. Inicializa el nodo con un valor y una lista vacía para almacenar sus conexiones. Cada conexión es una tupla que contiene el nodo de destino y una etiqueta (que puede incluir información como el costo).
• `agregar_conexion(self, nodo_destino, etiqueta)`: Añade una conexión a este nodo. Verifica que no exista ya una conexión al mismo nodo de destino para evitar duplicados.

Clase `Grafo`

Representa la estructura completa del grafo, gestionando todos los nodos y sus interconexiones.

• `__init__(self)`: Constructor de la clase `Grafo`. Inicializa un diccionario vacío self.nodos para almacenar los nodos, donde la clave es el valor del nodo y el valor es la instancia del objeto `NodoGrafo`.
• `agregar_nodo(self, valor)`: Añade un nuevo nodo al grafo si este no existe previamente.
• `agregar_arista(self, origen, destino, etiqueta)`: Crea una conexión (arista) entre dos nodos existentes. Añade la conexión en ambas direcciones para representar un grafo no dirigido.

Funcionalidades de Búsqueda y Optimización

• `nodo_con_mas_conexiones(self)`: Itera sobre todos los nodos del grafo y devuelve el valor del nodo que posee la mayor cantidad de conexiones salientes.
• `conexion_mas_costosa(self)`: Calcula el costo total de las conexiones entre nodos adyacentes (considerando el costo de la conexión de ida y la de vuelta, asumiendo que la etiqueta contiene un diccionario con la clave 'cost'). Devuelve la tupla de nodos que forman la conexión más costosa y su costo total.
• `camino_minimo_costo(self, inicio, fin)`: Implementa el algoritmo de Dijkstra para encontrar el camino de menor costo entre dos nodos especificados (inicio y fin). Utiliza una cola de prioridad (`heapq`) para gestionar eficientemente los nodos a visitar. Devuelve el camino como una lista de nodos y el costo acumulado.

Ejemplo de Uso

A continuación, se muestra un ejemplo práctico de cómo utilizar la clase `Grafo`:

import heapq

class NodoGrafo:
    def __init__(self, valor):
        self.valor = valor
        self.conexiones = []  # Lista de tuplas (nodo_destino, etiqueta)

    def agregar_conexion(self, nodo_destino, etiqueta):
        if all(conn[0] != nodo_destino for conn in self.conexiones):
            self.conexiones.append((nodo_destino, etiqueta))

class Grafo:
    def __init__(self):
        self.nodos = {}

    def agregar_nodo(self, valor):
        if valor not in self.nodos:
            self.nodos[valor] = NodoGrafo(valor)

    def agregar_arista(self, origen, destino, etiqueta):
        if origen in self.nodos and destino in self.nodos:
            self.nodos[origen].agregar_conexion(destino, etiqueta)
            self.nodos[destino].agregar_conexion(origen, etiqueta)

    def nodo_con_mas_conexiones(self):
        max_conexiones = 0
        nodo_max = None
        for nodo in self.nodos.values():
            if len(nodo.conexiones) > max_conexiones:
                max_conexiones = len(nodo.conexiones)
                nodo_max = nodo.valor
        return nodo_max

    def conexion_mas_costosa(self):
        max_costo = 0
        conexion_max = None
        for nodo in self.nodos.values():
            for conexion in nodo.conexiones:
                # Asumiendo que la etiqueta es un diccionario con 'cost'
                # y que la conexión de destino también tiene una conexión con 'cost'
                # Nota: Esta lógica puede necesitar ajuste dependiendo de la estructura exacta de la etiqueta
                try:
                    costo_origen = conexion[1]['cost']
                    # Intentar acceder al costo de la conexión de vuelta para el cálculo
                    # Esto asume que el nodo de destino tiene al menos una conexión y la primera es la relevante
                    if self.nodos[conexion[0]].conexiones:
                        costo_destino = self.nodos[conexion[0]].conexiones[0][1]['cost']
                        costo_total = costo_origen + costo_destino
                        if costo_total > max_costo:
                            max_costo = costo_total
                            conexion_max = (nodo.valor, conexion[0])
                    else:
                        # Si el nodo de destino no tiene conexiones, solo consideramos el costo de ida
                        if costo_origen > max_costo:
                            max_costo = costo_origen
                            conexion_max = (nodo.valor, conexion[0])
                except (KeyError, IndexError):
                    # Manejar casos donde 'cost' no está presente o la lista de conexiones está vacía
                    pass
        return conexion_max, max_costo

    def camino_minimo_costo(self, inicio, fin):
        import heapq
        cola_prioridad = [(0, inicio, [])]
        visitados = set()

        while cola_prioridad:
            acumulado, actual, camino = heapq.heappop(cola_prioridad)

            if actual in visitados:
                continue

            visitados.add(actual)
            camino = camino + [actual]

            if actual == fin:
                return camino, acumulado

            if actual not in self.nodos: # Asegurarse de que el nodo actual existe
                continue

            for vecino, etiqueta in self.nodos[actual].conexiones:
                if vecino not in visitados:
                    try:
                        costo = etiqueta['cost']
                        heapq.heappush(cola_prioridad, (acumulado + costo, vecino, camino))
                    except KeyError:
                        # Manejar el caso donde la etiqueta no tiene 'cost'
                        pass
        return None, None

# Creación del grafo y adición de nodos y aristas
grafo = Grafo()
camaras = [1, 2, 3, 4, 5]
for camara in camaras:
    grafo.agregar_nodo(camara)

# Crear conexiones ficticias y costos
conexiones = [(1, 2, 10), (1, 3, 15), (2, 4, 20), (2, 5, 10), (3, 4, 5), (3, 5, 10), (4, 5, 5)]
for origen, destino, costo in conexiones:
    grafo.agregar_arista(origen, destino, {'cost': costo})

# Obtener respuestas
nodo_max = grafo.nodo_con_mas_conexiones()
conexion_max, costo_max = grafo.conexion_mas_costosa()
camino, costo = grafo.camino_minimo_costo(1, 4)

# Imprimir resultados
print(f"La cámara con más conexiones es: Cámara {nodo_max}")
print(f"La conexión más costosa es entre la Cámara {conexion_max[0]} y la Cámara {conexion_max[1]} con un costo de {costo_max}")
print(f"El camino de menor costo desde la Cámara 1 a la Cámara 4 es: {camino} con un costo de {costo}")

Resultados del Ejemplo

La ejecución del código anterior producirá las siguientes salidas:

La cámara con más conexiones es: Cámara 2
La conexión más costosa es entre la Cámara 2 y la Cámara 4 con un costo de 30
El camino de menor costo desde la Cámara 1 a la Cámara 4 es: [1, 3, 4] con un costo de 20

Nota: El cálculo de la conexion_mas_costosa en el ejemplo original podría tener una lógica simplificada. La implementación proporcionada intenta considerar el costo de ida y vuelta, pero la interpretación exacta de 'costo total' puede variar según los requisitos específicos del problema.