#!/usr/bin/env python3
"""Vector de caminos en miniatura: ¿llega a un estado estable, o gira para siempre?

Cada AS guarda un solo camino hacia un destino. Cuando le toca, mira lo que sus
vecinos le pueden ofrecer, descarta los caminos que ya lo contienen (así BGP evita
ciclos) y se queda con el que más le gusta. Si en una vuelta completa nadie cambia,
la red es estable. Si vuelve a un estado ya visto, en ese orden nunca se detendrá.

Uso:  python3 spvp.py         muestra los tres ejemplos del capítulo
"""
import random

# Las relaciones de los seis AS de ases/ases.clab.yml.
ASES_PROVIDERS = {          # cliente: sus proveedores
    64601: [64602, 64604],
    64602: [64605],
    64603: [64606],
    64604: [64606],
    64605: [],
    64606: [],
}
ASES_PEERS = [(64605, 64606)]


class Graph:
    """Relaciones entre AS: quién es proveedor de quién y quién es peer de quién."""

    def __init__(self, providers, peers=()):
        self.providers = {node: list(ups) for node, ups in providers.items()}
        self.peers = {frozenset(pair) for pair in peers}
        self.nodes = sorted(self.providers)

    def relation(self, node, other):
        """Qué es other para node: customer, peer, provider o None si no son vecinos."""
        if other in self.providers[node]:
            return "provider"
        if node in self.providers[other]:
            return "customer"
        if frozenset((node, other)) in self.peers:
            return "peer"
        return None

    def neighbors(self, node):
        return [other for other in self.nodes
                if other != node and self.relation(node, other) is not None]


def is_valley_free(graph, path):
    """Dice si un camino, leído del que lo usa al que lo originó, es valle-libre.

    El anuncio viaja del origen al primero de la lista. Subiendo de cliente a
    proveedor cualquier número de veces, a lo sumo un enlace de peers, y después
    solo bajando de proveedor a cliente.
    """
    climbing = True
    for sender, receiver in zip(reversed(path), list(reversed(path))[1:]):
        step = graph.relation(receiver, sender)     # qué es el que anuncia para el que recibe
        if step == "customer":                      # sube: el cliente le anuncia al proveedor
            if not climbing:
                return False
        elif step == "peer":
            if not climbing:
                return False
            climbing = False
        elif step == "provider":                    # baja: el proveedor le anuncia al cliente
            climbing = False
        else:
            return False
    return True


def gao_rexford_export(graph, node, path, receiver):
    """Rutas propias y de clientes, a todos. Las demás, solo a clientes."""
    if len(path) == 1 or graph.relation(node, path[1]) == "customer":
        return True
    return graph.relation(node, receiver) == "customer"


def gao_rexford_rank(graph, node, path):
    """Primero clientes, luego peers, luego proveedores. Después, el camino más corto."""
    order = {"customer": 2, "peer": 1, "provider": 0}
    return (order[graph.relation(node, path[1])], -len(path), -path[1])


def simulate(graph, destination, rank, export, order=None, rounds=200):
    """Activa los AS por turnos. Devuelve (estable, caminos, historia de estados)."""
    best = {node: None for node in graph.nodes}
    best[destination] = (destination,)
    order = order or [node for node in graph.nodes if node != destination]
    history = []
    seen = set()
    for _ in range(rounds):
        changed = False
        for node in order:
            candidates = []
            for other in graph.neighbors(node):
                offered = best[other]
                if offered is None or node in offered:
                    continue
                if not export(graph, other, offered, node):
                    continue
                candidates.append((node,) + offered)
            new = max(candidates, key=lambda path: rank(graph, node, path), default=None)
            if new != best[node]:
                best[node] = new
                changed = True
        state = tuple(sorted(best.items()))
        history.append(dict(best))
        if not changed:
            return True, best, history
        if state in seen:
            return False, best, history
        seen.add(state)
    return False, best, history


def ring_graph(cycle=True):
    """Tres AS y un destino 0, que es cliente de los tres.

    Con cycle=True, 1 es proveedor de 2, 2 de 3, y 3 de 1: un ciclo de proveedores.
    Con cycle=False, el último enlace se invierte: 1 es proveedor de 3 y no hay ciclo.
    """
    providers = {0: [1, 2, 3], 1: [], 2: [1], 3: [2]}
    if cycle:
        providers[1] = [3]
    else:
        providers[3] = [2, 1]
    return Graph(providers)


def ring_rank(graph, node, path):
    """Todos son clientes, así que cada AS es libre de ordenarlos: prefiere al del anillo."""
    return (gao_rexford_rank(graph, node, path)[0], path[1] != 0, -len(path))


def ases_graph():
    return Graph(ASES_PROVIDERS, ASES_PEERS)


def predicted_paths(destination):
    """Camino de cada AS hacia destination, si los seis cumplen las reglas de Gao y Rexford."""
    graph = ases_graph()
    stable, best, _ = simulate(graph, destination, gao_rexford_rank, gao_rexford_export)
    assert stable
    return best


def show_ring(cycle):
    graph = ring_graph(cycle)
    title = "con un ciclo de proveedores" if cycle else "sin ciclo de proveedores"
    print(f"Anillo {title}:")
    stable, _, history = simulate(graph, 0, ring_rank, gao_rexford_export, [1, 2, 3])
    for number, state in enumerate(history, start=1):
        paths = "   ".join(" ".join(map(str, state[node])) for node in (1, 2, 3))
        print(f"  vuelta {number}:  {paths}")
    print("  estable" if stable else "  repite un estado ya visto: en este orden no termina nunca")
    print()


def show_ases():
    graph = ases_graph()
    print("Seis AS con las reglas de Gao y Rexford (camino de cada uno hacia 64603):")
    best = predicted_paths(64603)
    for node in graph.nodes:
        print(f"  {node}: {' '.join(map(str, best[node][1:])) or '(origen)'}")
    others = [node for node in graph.nodes if node != 64603]
    results = set()
    for seed in range(50):
        order = others[:]
        random.Random(seed).shuffle(order)
        _, paths, _ = simulate(graph, 64603, gao_rexford_rank, gao_rexford_export, order)
        results.add(tuple(sorted(paths.items())))
    print(f"  con 50 órdenes de activación al azar: {len(results)} resultado distinto")


if __name__ == "__main__":
    show_ring(True)
    show_ring(False)
    show_ases()