class GrafoPonderado:
    """Grafo ponderado usando lista de adyacencia"""
    def __init__(self, dirigido=False):
        self.dirigido = dirigido
        self.adyacencia = {}
    
    def agregar_vertice(self, v):
        """Agregar un vértice"""
        if v not in self.adyacencia:
            self.adyacencia[v] = []
    
    def agregar_arista(self, u, v, peso):
        """Agregar arista ponderada de u a v"""
        self.agregar_vertice(u)
        self.agregar_vertice(v)
        
        # Agregar arista u -> v con peso
        self.adyacencia[u].append((v, peso))
        
        # Si no dirigido, agregar v -> u
        if not self.dirigido:
            self.adyacencia[v].append((u, peso))
    
    def obtener_vecinos(self, v):
        """Obtener vecinos con sus pesos"""
        return self.adyacencia.get(v, [])
    
    def __repr__(self):
        lineas = [f"Grafo Ponderado ({'Dirigido' if self.dirigido else 'No Dirigido'}):"]
        for vertice, vecinos in self.adyacencia.items():
            vecinos_str = ', '.join([f"{v}({p})" for v, p in vecinos])
            lineas.append(f"  {vertice} -> [{vecinos_str}]")
        return '\n'.join(lineas)

# Ejemplo: Red de ciudades con distancias

red_ciudades = GrafoPonderado(dirigido=False)

# Agregar conexiones con distancias en km

red_ciudades.agregar_arista('Madrid', 'Barcelona', 620)
red_ciudades.agregar_arista('Madrid', 'Valencia', 355)
red_ciudades.agregar_arista('Madrid', 'Sevilla', 530)
red_ciudades.agregar_arista('Barcelona', 'Valencia', 350)
red_ciudades.agregar_arista('Valencia', 'Sevilla', 650)

print(red_ciudades)

print("\n" + "="\*60)
print("Vecinos de Madrid:")
for ciudad, distancia in red_ciudades.obtener_vecinos('Madrid'):
print(f" → {ciudad}: {distancia} km")

Grafo original:
              5
         A -------- B
         |   \   /  |
         |    \ /   |
       1 |     X    | 6
         |    / \   |
         |   /   \  |
         C -------- D
              3

MST (conexión mínima):
  - Aristas seleccionadas: A-C(1), C-D(3), C-B(2)
  - Costo total: 1 + 3 + 2 = 6
  - Conecta todos los vértices con costo mínimo

Camino más corto (A → D):
  - Ruta: A → C → D
  - Costo: 1 + 3 = 4
  - Es el camino de menor costo de A a D

import heapq

def prim_mst(grafo, inicio):
    """
    Algoritmo de Prim para MST

    Args:
        grafo: GrafoPonderado
        inicio: vértice inicial

    Returns:
        mst_aristas: lista de aristas en el MST
        costo_total: suma de pesos del MST
    """
    visitados = set()
    mst_aristas = []
    costo_total = 0

    # Min-heap: (peso, vertice_origen, vertice_destino)
    heap = []

    # Iniciar con el vértice inicial
    visitados.add(inicio)
    for vecino, peso in grafo.obtener_vecinos(inicio):
        heapq.heappush(heap, (peso, inicio, vecino))

    print(f"Iniciando Prim desde {inicio}\n")

    while heap and len(visitados) < len(grafo.adyacencia):
        peso, u, v = heapq.heappop(heap)

        # Si v ya está en el árbol, saltar
        if v in visitados:
            continue

        # Agregar arista al MST
        visitados.add(v)
        mst_aristas.append((u, v, peso))
        costo_total += peso

        print(f"Agregando arista: {u} -- {v} (peso: {peso})")
        print(f"  Costo acumulado: {costo_total}")

        # Agregar aristas desde v a vértices no visitados
        for vecino, peso_vecino in grafo.obtener_vecinos(v):
            if vecino not in visitados:
                heapq.heappush(heap, (peso_vecino, v, vecino))

    return mst_aristas, costo_total

# Ejemplo: Red de distribución eléctrica
print("="*60)
print("ALGORITMO DE PRIM: Red de Distribución Eléctrica")
print("="*60 + "\n")

red_electrica = GrafoPonderado(dirigido=False)

# Casas a conectar con costos de cableado
conexiones = [
    ('Casa A', 'Casa B', 4),
    ('Casa A', 'Casa C', 2),
    ('Casa B', 'Casa C', 1),
    ('Casa B', 'Casa D', 5),
    ('Casa C', 'Casa D', 8),
    ('Casa C', 'Casa E', 10),
    ('Casa D', 'Casa E', 2),
    ('Casa D', 'Casa F', 6),
    ('Casa E', 'Casa F', 3),
]

for u, v, costo in conexiones:
    red_electrica.agregar_arista(u, v, costo)

print("Red original:")
print(red_electrica)

print("\n" + "="*60)
print("Ejecutando Algoritmo de Prim:")
print("="*60 + "\n")

mst_aristas, costo_total = prim_mst(red_electrica, 'Casa A')

print("\n" + "="*60)
print("RESULTADO:")
print("="*60)
print(f"\nÁrbol de Expansión Mínima (MST):")
for u, v, peso in mst_aristas:
    print(f"  {u} -- {v}: {peso} unidades")

print(f"\nCosto total mínimo: {costo_total} unidades")
print(f"Aristas en MST: {len(mst_aristas)}")
print(f"Ahorro respecto a todas las conexiones: "
      f"{sum(c for _, _, c in conexiones) - costo_total} unidades")

class UnionFind:
    """
    Estructura Union-Find (Disjoint Set)
    con compresión de caminos y unión por rango
    """
    def __init__(self, elementos):
        self.padre = {e: e for e in elementos}
        self.rango = {e: 0 for e in elementos}
    
    def find(self, x):
        """Encontrar el representante con compresión de caminos"""
        if self.padre[x] != x:
            self.padre[x] = self.find(self.padre[x])  # Compresión
        return self.padre[x]
    
    def union(self, x, y):
        """Unir dos conjuntos por rango"""
        raiz_x = self.find(x)
        raiz_y = self.find(y)
        
        if raiz_x == raiz_y:
            return False  # Ya están en el mismo conjunto
        
        # Unión por rango
        if self.rango[raiz_x] < self.rango[raiz_y]:
            self.padre[raiz_x] = raiz_y
        elif self.rango[raiz_x] > self.rango[raiz_y]:
            self.padre[raiz_y] = raiz_x
        else:
            self.padre[raiz_y] = raiz_x
            self.rango[raiz_x] += 1
        
        return True

def kruskal_mst(grafo):
"""
Algoritmo de Kruskal para MST

    Args:
        grafo: GrafoPonderado

    Returns:
        mst_aristas: lista de aristas en el MST
        costo_total: suma de pesos del MST
    """
    # Obtener todas las aristas
    aristas = []
    for u in grafo.adyacencia:
        for v, peso in grafo.obtener_vecinos(u):
            # Evitar duplicados en grafos no dirigidos
            if u < v:
                aristas.append((peso, u, v))

    # Ordenar aristas por peso
    aristas.sort()

    # Inicializar Union-Find
    vertices = list(grafo.adyacencia.keys())
    uf = UnionFind(vertices)

    mst_aristas = []
    costo_total = 0

    print("Procesando aristas en orden de peso:\n")

    for peso, u, v in aristas:
        # Verificar si u y v están en diferentes componentes
        if uf.union(u, v):
            mst_aristas.append((u, v, peso))
            costo_total += peso
            print(f"✓ Agregar: {u} -- {v} (peso: {peso})")
            print(f"  Costo acumulado: {costo_total}")
        else:
            print(f"✗ Saltar: {u} -- {v} (peso: {peso}) - crearía ciclo")

        # Terminar si ya tenemos n-1 aristas
        if len(mst_aristas) == len(vertices) - 1:
            break

    return mst_aristas, costo_total

# Ejemplo: Red de fibra óptica

print("="*60)
print("ALGORITMO DE KRUSKAL: Red de Fibra Óptica")
print("="*60 + "\n")

red_fibra = GrafoPonderado(dirigido=False)

# Oficinas a conectar con costos de instalación

conexiones_fibra = [
('Oficina A', 'Oficina B', 7),
('Oficina A', 'Oficina D', 5),
('Oficina B', 'Oficina C', 8),
('Oficina B', 'Oficina D', 9),
('Oficina B', 'Oficina E', 7),
('Oficina C', 'Oficina E', 5),
('Oficina D', 'Oficina E', 15),
('Oficina D', 'Oficina F', 6),
('Oficina E', 'Oficina F', 8),
('Oficina E', 'Oficina G', 9),
('Oficina F', 'Oficina G', 11),
]

for u, v, costo in conexiones_fibra:
red_fibra.agregar_arista(u, v, costo)

print("Red original:")
for u, v, costo in conexiones_fibra:
print(f" {u} -- {v}: {costo}")

print("\n" + "="*60)
print("Ejecutando Algoritmo de Kruskal:")
print("="*60 + "\n")

mst_aristas_k, costo_total_k = kruskal_mst(red_fibra)

print("\n" + "="*60)
print("RESULTADO:")
print("="*60)
print(f"\nÁrbol de Expansión Mínima (MST):")
for u, v, peso in mst_aristas_k:
print(f" {u} -- {v}: {peso} unidades")

print(f"\nCosto total mínimo: {costo_total_k} unidades")
print(f"Aristas en MST: {len(mst_aristas_k)}")

import heapq

def dijkstra(grafo, inicio):
    """
    Algoritmo de Dijkstra para caminos más cortos

    Args:
        grafo: GrafoPonderado
        inicio: vértice inicial

    Returns:
        distancias: dict con distancias mínimas desde inicio
        padres: dict para reconstruir caminos
    """
    # Inicializar distancias y padres
    distancias = {v: float('inf') for v in grafo.adyacencia}
    distancias[inicio] = 0
    padres = {inicio: None}
    visitados = set()

    # Min-heap: (distancia, vértice)
    heap = [(0, inicio)]

    print(f"Iniciando Dijkstra desde {inicio}\n")

    while heap:
        dist_actual, u = heapq.heappop(heap)

        # Si ya visitado, saltar
        if u in visitados:
            continue

        visitados.add(u)
        print(f"Procesando {u} (distancia: {dist_actual})")

        # Relajar aristas
        for v, peso in grafo.obtener_vecinos(u):
            if v in visitados:
                continue

            nueva_dist = distancias[u] + peso

            # Si encontramos un camino mejor, actualizar
            if nueva_dist < distancias[v]:
                distancias[v] = nueva_dist
                padres[v] = u
                heapq.heappush(heap, (nueva_dist, v))
                print(f"  Relajar {u} -> {v}: distancia = {nueva_dist}")

    return distancias, padres

def reconstruir_camino(padres, inicio, fin):
    """Reconstruir camino desde inicio a fin"""
    if fin not in padres:
        return None

    camino = []
    actual = fin
    while actual is not None:
        camino.append(actual)
        actual = padres.get(actual)

    camino.reverse()
    return camino

# Ejemplo: Red de transporte
print("="*60)
print("ALGORITMO DE DIJKSTRA: Red de Transporte")
print("="*60 + "\n")

red_transporte = GrafoPonderado(dirigido=True)

# Ciudades con tiempos de viaje (minutos)
rutas = [
    ('A', 'B', 10),
    ('A', 'C', 3),
    ('B', 'C', 1),
    ('B', 'D', 2),
    ('C', 'B', 4),
    ('C', 'D', 8),
    ('C', 'E', 2),
    ('D', 'E', 7),
    ('E', 'D', 9),
]

for origen, destino, tiempo in rutas:
    red_transporte.agregar_arista(origen, destino, tiempo)

print("Red de transporte:")
for origen, destino, tiempo in rutas:
    print(f"  {origen} → {destino}: {tiempo} min")

print("\n" + "="*60)
print("Ejecutando Dijkstra desde A:")
print("="*60 + "\n")

distancias, padres = dijkstra(red_transporte, 'A')

print("\n" + "="*60)
print("RESULTADOS:")
print("="*60 + "\n")

print("Distancias mínimas desde A:")
for destino in sorted(distancias.keys()):
    dist = distancias[destino]
    if dist == float('inf'):
        print(f"  A → {destino}: INALCANZABLE")
    else:
        camino = reconstruir_camino(padres, 'A', destino)
        camino_str = ' → '.join(camino)
        print(f"  A → {destino}: {dist} min")
        print(f"    Ruta: {camino_str}")

def floyd_warshall(grafo):
    """
    Algoritmo de Floyd-Warshall para todos los pares
    
    Args:
        grafo: GrafoPonderado
    
    Returns:
        dist: matriz de distancias
        next: matriz para reconstruir caminos
    """
    vertices = list(grafo.adyacencia.keys())
    n = len(vertices)
    
    # Mapeo de vértices a índices
    v_to_idx = {v: i for i, v in enumerate(vertices)}
    idx_to_v = {i: v for v, i in v_to_idx.items()}
    
    # Inicializar matrices
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
    next_vertex = [[None] * n for _ in range(n)]
    
    # Distancia de un vértice a sí mismo es 0
    for i in range(n):
        dist[i][i] = 0
    
    # Inicializar con aristas directas
    for u in grafo.adyacencia:
        i = v_to_idx[u]
        for v, peso in grafo.obtener_vecinos(u):
            j = v_to_idx[v]
            dist[i][j] = peso
            next_vertex[i][j] = j
    
    print(f"Ejecutando Floyd-Warshall ({n} vértices)...\n")
    
    # Algoritmo principal: considerar cada vértice como intermedio
    for k in range(n):
        print(f"Iteración {k+1}/{n}: Usando {idx_to_v[k]} como intermedio")
        for i in range(n):
            for j in range(n):
                # ¿Es mejor pasar por k?
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    next_vertex[i][j] = next_vertex[i][k]
    
    # Detectar ciclos negativos
    tiene_ciclo_negativo = False
    for i in range(n):
        if dist[i][i] < 0:
            tiene_ciclo_negativo = True
            break
    
    return dist, next_vertex, v_to_idx, idx_to_v, tiene_ciclo_negativo

def reconstruir_camino_floyd(next_vertex, i, j, idx_to_v):
"""Reconstruir camino de i a j usando matriz next"""
if next_vertex[i][j] is None:
return None

    camino = [idx_to_v[i]]
    while i != j:
        i = next_vertex[i][j]
        camino.append(idx_to_v[i])

    return camino

# Ejemplo: Red de vuelos

print("="*60)
print("ALGORITMO DE FLOYD-WARSHALL: Red de Vuelos")
print("="*60 + "\n")

red_vuelos = GrafoPonderado(dirigido=True)

# Vuelos con precios

vuelos = [
('Madrid', 'Barcelona', 50),
('Madrid', 'Valencia', 40),
('Barcelona', 'París', 80),
('Valencia', 'Barcelona', 30),
('Valencia', 'París', 120),
('París', 'Londres', 60),
('Barcelona', 'Londres', 100),
]

for origen, destino, precio in vuelos:
red_vuelos.agregar_arista(origen, destino, precio)

print("Vuelos disponibles:")
for origen, destino, precio in vuelos:
print(f" {origen} → {destino}: ${precio}")

print("\n" + "="*60)
dist, next_v, v_to_idx, idx_to_v, ciclo_neg = floyd_warshall(red_vuelos)
print("="*60 + "\n")

if ciclo_neg:
print("⚠️ ERROR: Ciclo de costo negativo detectado")
else:
print("MATRIZ DE DISTANCIAS (Todos los pares):\n")

    # Encabezado
    vertices = list(v_to_idx.keys())
    print(f"{'Desde/A':<12}", end="")
    for v in vertices:
        print(f"{v:<12}", end="")
    print()
    print("-" * (12 * (len(vertices) + 1)))

    # Matriz
    for v1 in vertices:
        i = v_to_idx[v1]
        print(f"{v1:<12}", end="")
        for v2 in vertices:
            j = v_to_idx[v2]
            d = dist[i][j]
            if d == float('inf'):
                print(f"{'∞':<12}", end="")
            else:
                print(f"${d:<11}", end="")
        print()

    print("\n" + "="*60)
    print("EJEMPLOS DE RUTAS ÓPTIMAS:")
    print("="*60 + "\n")

    ejemplos = [('Madrid', 'Londres'), ('Valencia', 'Londres'), ('Madrid', 'París')]

    for origen, destino in ejemplos:
        i = v_to_idx[origen]
        j = v_to_idx[destino]
        d = dist[i][j]

        if d == float('inf'):
            print(f"{origen} → {destino}: INALCANZABLE")
        else:
            camino = reconstruir_camino_floyd(next_v, i, j, idx_to_v)
            camino_str = ' → '.join(camino)
            print(f"{origen} → {destino}: ${d}")
            print(f"  Ruta: {camino_str}\n")

def distancia_robot(p1, p2):
    """
    Distancia L-infinito (Chebyshev)
    El robot se mueve en X e Y simultáneamente
    Tiempo = max(|dx|, |dy|)
    """
    dx = abs(p1[0] - p2[0])
    dy = abs(p1[1] - p2[1])
    return max(dx, dy)

# Ejemplo: Puntos de contacto en PCB
puntos_contacto = {
    'P1': (0, 0),
    'P2': (3, 4),
    'P3': (6, 1),
    'P4': (2, 5),
    'P5': (8, 3),
}

# Crear grafo completo ponderado
grafo_pcb = GrafoPonderado(dirigido=False)

for p1, coord1 in puntos_contacto.items():
    for p2, coord2 in puntos_contacto.items():
        if p1 < p2:
            peso = distancia_robot(coord1, coord2)
            grafo_pcb.agregar_arista(p1, p2, peso)

print("="*60)
print("OPTIMIZACIÓN DE TESTING ROBÓTICO")
print("="*60 + "\n")

print("Puntos de contacto:")
for punto, (x, y) in puntos_contacto.items():
    print(f"  {punto}: ({x}, {y})")

print("\nDistancias de movimiento (L∞):")
for p1, coord1 in puntos_contacto.items():
    for p2, coord2 in puntos_contacto.items():
        if p1 < p2:
            d = distancia_robot(coord1, coord2)
            print(f"  {p1} ↔ {p2}: {d} unidades")

# Aplicar Prim para MST
print("\n" + "="*60)
print("Aplicando Prim para optimizar ruta:")
print("="*60 + "\n")

mst_robot, tiempo_total = prim_mst(grafo_pcb, 'P1')

print("\n" + "="*60)
print("SOLUCIÓN:")
print("="*60)
print(f"\nSecuencia óptima de movimientos:")
for u, v, tiempo in mst_robot:
    print(f"  {u} → {v}: {tiempo} unidades")

print(f"\nTiempo total minimizado: {tiempo_total} unidades")

# Para clustering: romper MST en k grupos
print("\n" + "="*60)
print("CLUSTERING (romper MST en 2 grupos):")
print("="*60)

# Encontrar la arista más pesada en el MST
arista_mas_pesada = max(mst_robot, key=lambda x: x[2])
print(f"\nRemover arista más pesada: {arista_mas_pesada[0]} -- {arista_mas_pesada[1]} ({arista_mas_pesada[2]})")

# Los dos clusters resultantes
cluster1 = {arista_mas_pesada[0]}
cluster2 = {arista_mas_pesada[1]}

for u, v, _ in mst_robot:
    if (u, v) == (arista_mas_pesada[0], arista_mas_pesada[1]):
        continue
    if u in cluster1 or v in cluster1:
        cluster1.add(u)
        cluster1.add(v)
    else:
        cluster2.add(u)
        cluster2.add(v)

print(f"\nCluster 1: {cluster1}")
print(f"Cluster 2: {cluster2}")

import math

# Mapeo T9

T9_MAP = {
'2': 'ABC', '3': 'DEF', '4': 'GHI',
'5': 'JKL', '6': 'MNO', '7': 'PQRS',
'8': 'TUV', '9': 'WXYZ'
}

# Probabilidades de bigramas (simplificado)

BIGRAM_PROB = {
('THE', 'CAT'): 0.01,
('THE', 'DOG'): 0.02,
('A', 'CAT'): 0.005,
('A', 'DOG'): 0.008,
}

def decodificar_t9(codigo):
"""Obtener posibles letras para un código T9"""
return T9_MAP.get(codigo, '')

def palabras_posibles(secuencia_t9, diccionario):
"""Obtener palabras del diccionario que coinciden con secuencia T9"""
posibles = []
for palabra in diccionario:
if len(palabra) != len(secuencia_t9):
continue

        coincide = True
        for i, codigo in enumerate(secuencia_t9):
            if palabra[i] not in decodificar_t9(codigo):
                coincide = False
                break

        if coincide:
            posibles.append(palabra)

    return posibles

def peso_transicion(palabra1, palabra2):
"""
Peso de transición entre dos palabras
Menor peso = más probable
""" # Obtener probabilidad del bigrama
prob = BIGRAM_PROB.get((palabra1, palabra2), 0.0001)

    # Convertir a peso (negativo del log)
    # Menor probabilidad = mayor peso
    return -math.log(prob)

# Ejemplo

print("="*60)
print("DESAMBIGUACIÓN DE TEXTO T9")
print("="*60 + "\n")

# Diccionario simplificado

diccionario = ['THE', 'A', 'CAT', 'DOG', 'SAT', 'RAT']

# Secuencia T9: "843 228" = "THE CAT" o "THE BAT" o...

secuencias = [
('843', ['THE']), # Solo una opción
('228', ['CAT']) # Podría ser CAT, BAT, AAT, etc.
]

print("Secuencia T9: 843 228")
print("\nDecodificación:")

grafo_t9 = GrafoPonderado(dirigido=True)

# Agregar vértice inicial

grafo_t9.agregar_vertice('START')

# Construir grafo de posibilidades

nivel_anterior = ['START']
for i, (seq, candidatos) in enumerate(secuencias):
print(f"\nPosición {i+1} ({seq}):")
posibles = palabras_posibles(seq, diccionario)
print(f" Posibles: {posibles}")

    for palabra_ant in nivel_anterior:
        for palabra_nueva in posibles:
            if palabra_ant == 'START':
                peso = 0
            else:
                peso = peso_transicion(palabra_ant, palabra_nueva)

            grafo_t9.agregar_arista(palabra_ant, palabra_nueva, peso)

    nivel_anterior = posibles

# Agregar vértice final

grafo_t9.agregar_vertice('END')
for palabra in nivel_anterior:
grafo_t9.agregar_arista(palabra, 'END', 0)

print("\n" + "="*60)
print("Aplicando Dijkstra para encontrar mejor interpretación:")
print("="*60 + "\n")

distancias, padres = dijkstra(grafo_t9, 'START')

print("\n" + "="*60)
print("RESULTADO:")
print("="*60)

# Reconstruir mejor camino

camino = reconstruir_camino(padres, 'START', 'END')
mejor_interpretacion = [p for p in camino if p not in ['START', 'END']]

print(f"\nMejor interpretación: {' '.join(mejor_interpretacion)}")
print(f"Costo total: {distancias['END']:.4f}")

"""
METODOLOGÍA PARA RESOLVER PROBLEMAS CON GRAFOS PONDERADOS

1. IDENTIFICAR EL PROBLEMA
  - ¿Necesito conectar todos los vértices con costo mínimo? → MST
  - ¿Necesito la ruta más corta entre dos puntos? → Shortest Path
  - ¿Necesito rutas entre todos los pares? → All-pairs Shortest Path

2. MODELAR COMO GRAFO
  - Vértices: ¿Qué entidades del problema?
  - Aristas: ¿Qué conexiones existen?
  - Pesos: ¿Qué costo representa? (distancia, tiempo, $)

3. VERIFICAR PROPIEDADES
  - ¿Dirigido o no dirigido?
  - ¿Hay pesos negativos?
  - ¿Es denso o esparso?

4. SELECCIONAR ALGORITMO
  - MST denso → Prim
  - MST esparso → Kruskal
  - SP sin negativos → Dijkstra
  - SP con negativos → Bellman-Ford
  - All-pairs → Floyd-Warshall

5. IMPLEMENTAR Y VALIDAR
  - Usar estructuras de datos adecuadas
  - Verificar casos borde
  - Validar resultado
"""