Componentes fuertemente conexos

Lo que cubre este capítulo

El bloque de grafos arrancó con depth-first search y con la promesa de que su orden de finalización revela estructura profunda. Este capítulo de cierre cobra esa promesa completa. Un componente fuertemente conexo de un grafo dirigido es un grupo maximal de nodos donde cada nodo puede llegar a todos los demás y regresar: un nudo bien apretado de alcanzabilidad mutua. Encuentra todos, colapsa cada uno a un solo punto, y cualquier grafo dirigido, por enredado que esté, se convierte en un grafo dirigido acíclico: todos los ciclos quedan escondidos dentro de los componentes, y lo que queda entre ellos va en un solo sentido y sin ciclos. Esa descomposición es el primer movimiento estándar para analizar grafos dirigidos cíclicos, desde detección de deadlocks hasta optimización de compiladores y análisis de la estructura de la web. Aquí construimos el algoritmo de Kosaraju —dos pasadas de depth-first search y un truco precioso, invertir cada arista—, lo verificamos contra su rival de una sola pasada, el de Tarjan, y vemos emerger un fenómeno real: conforme se acumulan aristas dirigidas al azar, un componente gigante cristaliza de golpe cuando el grado promedio cruza el uno.

Un poco de historia

Los dos algoritmos estándar enmarcan una época muy productiva de la teoría de grafos. Robert Tarjan publicó su algoritmo de una sola pasada con low-link en 1972, parte de la misma explosión de trabajo sobre depth-first search (junto con John Hopcroft) que también produjo la prueba de planaridad en tiempo lineal y la biconectividad: los papers que convirtieron DFS de un simple recorrido en un instrumento analítico. El algoritmo de dos pasadas de Kosaraju tiene una procedencia curiosa: S. Rao Kosaraju lo describió en unas notas de clase sin publicar de 1978, y Micha Sharir publicó esencialmente el mismo método en 1981, así que a veces se le llama algoritmo de Kosaraju-Sharir. El de Tarjan es más rápido en constantes (una pasada, no dos) y es el que usan librerías como networkx, pero el de Kosaraju es el que todo mundo aprende, porque su correctitud es transparentísima: corre DFS, invierte las aristas, corre DFS otra vez en orden inverso de finalización. Que existan dos algoritmos tan distintos para el mismo problema se debe a que la conectividad fuerte es lo bastante fundamental como para haberse resuelto de forma independiente más de una vez: la firma recurrente, a lo largo de todo este bloque, de un problema verdaderamente fundacional.

La intuición

El algoritmo de Kosaraju descansa en una sola observación: invertir cada arista del grafo deja los componentes fuertemente conexos intactos, pero voltea las calles de un solo sentido que hay entre ellos. Si los nodos $a$ y $b$ pueden alcanzarse mutuamente, lo siguen pudiendo después de invertir (un viaje redondo al revés sigue siendo un viaje redondo). Pero si el componente $X$ podía llegar al componente $Y$ en un solo sentido en el grafo original, entonces en el grafo invertido es $Y$ el que llega a $X$. Así que los componentes son invariantes, pero su "aguas abajo" y "aguas arriba" se intercambian. Esa es la palanca que jala el algoritmo.

Así la usa. Pasada uno: corre depth-first search sobre el grafo original y registra el orden en que los nodos terminan (ya explorados todos sus descendientes). El hecho clave —el mismo que está detrás del ordenamiento topológico— es que el componente que termina al último es un componente "fuente" en la condensación: no queda nada aguas arriba de él. Pasada dos: procesa los nodos en orden inverso de finalización (el que terminó al último, primero) y corre depth-first search sobre el grafo invertido. Empezando desde ese componente fuente y siguiendo las aristas invertidas, alcanzas exactamente los nodos de ese componente y nada más, porque las aristas invertidas hacia otros componentes apuntan en el sentido equivocado para escaparse. Entonces el primer árbol de DFS de la pasada dos es justamente un SCC. Márcalo como listo, pasa al siguiente nodo sin terminar en orden inverso de finalización, y su árbol de DFS es el siguiente SCC. Cada árbol de la segunda búsqueda es exactamente un componente fuertemente conexo. Dos pasadas lineales, y toda la astucia está en la inversión.

Complejidad: cómo escala

El de Kosaraju es $O(V + E)$: dos recorridos depth-first más construir la transpuesta, cada uno lineal, así que todo el asunto es lineal en el tamaño del grafo. El de Tarjan también es $O(V+E)$ pero lo logra en una sola pasada, ahorrándose un factor constante. El espacio es $O(V)$ para las marcas de visitado, la pila de finalización y la asignación de componentes (más $O(V+E)$ para guardar la transpuesta). Lineal es lo mejor que puede ser: tienes que leer cada arista. Así que en vez de echar a correr a los dos algoritmos por velocidad, el enfrentamiento usa la descomposición en SCC para revelar algo sobre los grafos dirigidos mismos: cómo se comporta el tamaño del componente fuertemente conexo más grande conforme le vas espolvoreando aristas dirigidas al azar.

La forma es una transición de fase, uno de los fenómenos más impresionantes en grafos aleatorios. Por debajo de un grado de salida promedio de más o menos uno, el componente fuertemente conexo más grande es despreciable: con grado 0.5 traía cerca del 0.2% de los nodos, o sea que el grafo es esencialmente puros componentes diminutos y nada de alcanzabilidad mutua a escala. Justo alrededor del grado uno, nuclea un componente gigante: para el grado 3, un solo componente fuertemente conexo se tragó casi el 89% del grafo entero. La transición es abrupta y no es una maña del algoritmo: es una propiedad real de los grafos dirigidos, la prima dirigida de la clásica emergencia del componente gigante en la teoría de grafos aleatorios, y es la razón de que la web tenga un "núcleo" enorme de páginas que se alcanzan todas entre sí, rodeado de tentáculos que no. La descomposición en SCC es cómo mides esa estructura, y el algoritmo que la calcula es lineal.

En qué es bueno y en qué no

La descomposición en SCC es el primer paso correcto siempre que tengas un grafo dirigido que pueda contener ciclos y quieras entender o simplificar su estructura. Detecta ciclos (cualquier componente con más de un nodo, o con un self-loop, es un ciclo): la base de la detección de deadlocks en sistemas operativos y bases de datos, donde un ciclo en el grafo de espera significa que hay procesos atorados esperándose entre sí. Condensa un grafo enredado a un DAG, tras lo cual puedes correr los algoritmos acíclicos —ordenamiento topológico, caminos más cortos en DAG, programación dinámica— que asumen que no hay ciclos. Los compiladores lo usan para encontrar loops en el control-flow y para agrupar funciones mutuamente recursivas; identifica comunidades en grafos sociales y de la web; resuelve 2-SAT en tiempo lineal (una aplicación clásica y sorprendente). Cuando lo que importa es "quién alcanza a quién, en ambos sentidos", los SCC son la herramienta.

Donde no aplica es en grafos no dirigidos, donde los "componentes conexos" (una inundación simple con BFS/DFS, del capítulo de representación de grafos) son la noción más sencilla y correcta: la conectividad fuerte es un concepto dirigido, nacido de que las aristas tengan dirección. También responde una pregunta estructural, no métrica: te dice cuáles nodos se alcanzan mutuamente, no qué tan lejos están ni por qué camino. Y como todo análisis de grafo completo, necesita el grafo en la mano; no es un algoritmo online para aristas que van llegando con el tiempo (mantener los SCC bajo inserción de aristas es un problema aparte y más difícil).

Los datos, o las entradas

El enfrentamiento barre grafos dirigidos aleatorios de 500 nodos a lo largo de grados de salida promedio crecientes y mide la fracción de nodos en el componente fuertemente conexo más grande, revelando la transición de fase del SCC gigante alrededor del grado uno. La correctitud se verifica cruzándola con el algoritmo independiente de una sola pasada de Tarjan: sobre cientos de digrafos aleatorios, los componentes de Kosaraju deben coincidir exactamente con los de Tarjan, cada nodo debe caer en exactamente un componente, y la condensación debe ser acíclica (verificado ordenando topológicamente el supergrafo). La animación corre sobre un grafo dirigido chiquito con tres componentes bien claros y los va revelando uno por uno, coloreando cada uno conforme lo encuentra.

Constrúyelo, una función a la vez

La inversión de aristas, el truco sobre el que gira todo el algoritmo:

def transpose(adj, n):
    """The reverse graph: every edge u → v becomes v → u. Kosaraju's second pass runs on this.
    Reversing edges keeps each SCC intact (if a↔b in the original, still a↔b reversed) but
    flips the one-way links BETWEEN components, which is what isolates them."""
    radj = [[] for _ in range(n)]
    for u in range(n):
        for v in adj[u]:
            radj[v].append(u)
    return radj

Las dos pasadas de Kosaraju: pila de orden de finalización, luego DFS sobre la transpuesta en orden inverso:

def strongly_connected_components(adj, n):
    """Kosaraju's algorithm. Pass 1: DFS the graph, pushing each node onto a stack when it
    FINISHES (all its descendants done). Pass 2: DFS the transpose, popping nodes off that
    stack (i.e. in reverse finish order); every tree reached in the second search is one SCC.
    O(V+E). Returns a list of components, each a list of node ids. (Iterative DFS so deep
    graphs don't overflow the call stack.)"""
    # --- pass 1: finish-order stack on the original graph ---
    visited = [False] * n
    order = []                                   # nodes in order of finishing
    for s in range(n):
        if visited[s]:
            continue
        stack = [(s, iter(adj[s]))]
        visited[s] = True
        while stack:
            node, it = stack[-1]
            advanced = False
            for w in it:
                if not visited[w]:
                    visited[w] = True
                    stack.append((w, iter(adj[w])))
                    advanced = True
                    break
            if not advanced:
                order.append(node)               # node is finished
                stack.pop()

    # --- pass 2: DFS the transpose in reverse finish order ---
    radj = transpose(adj, n)
    assigned = [False] * n
    components = []
    for s in reversed(order):
        if assigned[s]:
            continue
        comp = []                                # everything reachable here (in the transpose) is one SCC
        stack = [s]
        assigned[s] = True
        while stack:
            u = stack.pop()
            comp.append(u)
            for w in radj[u]:
                if not assigned[w]:
                    assigned[w] = True
                    stack.append(w)
        components.append(sorted(comp))
    return components

Y colapsar los componentes a su condensación acíclica:

def condensation(adj, n, components):
    """Collapse each SCC to a single super-node; the result is always a DAG. Returns the number
    of super-nodes and the edges between them — the acyclic skeleton of the directed graph."""
    comp_id = [0] * n
    for cid, comp in enumerate(components):
        for node in comp:
            comp_id[node] = cid
    dag_edges = set()
    for u in range(n):
        for v in adj[u]:
            if comp_id[u] != comp_id[v]:
                dag_edges.add((comp_id[u], comp_id[v]))
    return len(components), dag_edges

Míralo funcionar

Aquí hay un grafo dirigido con tres componentes fuertemente conexos, revelados uno por uno. Al inicio cada nodo está gris: la pregunta es cuáles de ellos pueden alcanzarse mutuamente. Luego, componente por componente, el algoritmo colorea un grupo: los nodos 0, 1, 2 forman un componente verde (ciclan 0→1→2→0, así que cada uno alcanza a los otros y de regreso); los nodos 3, 4 uno azul (3↔4); los nodos 5, 6, 7 uno morado (5→6→7→5). Las aristas grises entre grupos de color van en un solo sentido —puedes ir del componente verde a los otros pero nunca regresar—, que es justamente por lo que son componentes separados. Colapsa cada mancha de color a un solo supernodo y esas aristas de un solo sentido forman un DAG: el grafo dirigido enredado, vuelto acíclico:

El código completo

La pestaña "desde cero" es el algoritmo de dos pasadas de Kosaraju con la transpuesta y la condensación; la pestaña de librería es el algoritmo de una sola pasada de Tarjan: la referencia independiente contra la que se verifica Kosaraju, y lo que networkx usa de verdad. Cámbiate entre ambas para comparar dos soluciones en tiempo lineal al mismo problema.

"""Strongly connected components — the maximal groups of nodes in a DIRECTED graph that can
all reach each other. Within one component you can get from any node to any other and back;
between components, reachability only goes one way. Collapse each component to a single point
and the whole graph becomes a DAG (the "condensation"), which is why SCCs are the standard
first step in analyzing any cyclic directed graph: they find the cycles-of-cycles and reduce
the rest to the acyclic case you already know how to handle.

This is a fitting close to the graph tier because it comes right back to depth-first search,
where the tier began. Kosaraju's algorithm — built here — finds every SCC with just TWO DFS
passes and one strikingly simple trick: run DFS, record the order in which nodes finish, then
run DFS again on the graph with every edge REVERSED, taking nodes in reverse finish order.
Each tree of that second search is exactly one strongly connected component. Two passes over
the graph, O(V+E), and the reversal is the whole idea.
"""


# region: transpose
def transpose(adj, n):
    """The reverse graph: every edge u → v becomes v → u. Kosaraju's second pass runs on this.
    Reversing edges keeps each SCC intact (if a↔b in the original, still a↔b reversed) but
    flips the one-way links BETWEEN components, which is what isolates them."""
    radj = [[] for _ in range(n)]
    for u in range(n):
        for v in adj[u]:
            radj[v].append(u)
    return radj
# endregion


# region: kosaraju
def strongly_connected_components(adj, n):
    """Kosaraju's algorithm. Pass 1: DFS the graph, pushing each node onto a stack when it
    FINISHES (all its descendants done). Pass 2: DFS the transpose, popping nodes off that
    stack (i.e. in reverse finish order); every tree reached in the second search is one SCC.
    O(V+E). Returns a list of components, each a list of node ids. (Iterative DFS so deep
    graphs don't overflow the call stack.)"""
    # --- pass 1: finish-order stack on the original graph ---
    visited = [False] * n
    order = []                                   # nodes in order of finishing
    for s in range(n):
        if visited[s]:
            continue
        stack = [(s, iter(adj[s]))]
        visited[s] = True
        while stack:
            node, it = stack[-1]
            advanced = False
            for w in it:
                if not visited[w]:
                    visited[w] = True
                    stack.append((w, iter(adj[w])))
                    advanced = True
                    break
            if not advanced:
                order.append(node)               # node is finished
                stack.pop()

    # --- pass 2: DFS the transpose in reverse finish order ---
    radj = transpose(adj, n)
    assigned = [False] * n
    components = []
    for s in reversed(order):
        if assigned[s]:
            continue
        comp = []                                # everything reachable here (in the transpose) is one SCC
        stack = [s]
        assigned[s] = True
        while stack:
            u = stack.pop()
            comp.append(u)
            for w in radj[u]:
                if not assigned[w]:
                    assigned[w] = True
                    stack.append(w)
        components.append(sorted(comp))
    return components
# endregion


# region: condensation
def condensation(adj, n, components):
    """Collapse each SCC to a single super-node; the result is always a DAG. Returns the number
    of super-nodes and the edges between them — the acyclic skeleton of the directed graph."""
    comp_id = [0] * n
    for cid, comp in enumerate(components):
        for node in comp:
            comp_id[node] = cid
    dag_edges = set()
    for u in range(n):
        for v in adj[u]:
            if comp_id[u] != comp_id[v]:
                dag_edges.add((comp_id[u], comp_id[v]))
    return len(components), dag_edges
# endregion

"""The library counterpart and the independent reference. In production, strongly connected
components come from networkx:

    import networkx as nx
    list(nx.strongly_connected_components(G))   # a list of node-sets, uses Tarjan's algorithm

networkx uses TARJAN's algorithm — the other classic SCC method, which finds every component
in a SINGLE depth-first pass (Kosaraju needs two) by tracking a "low-link" number per node:
the oldest node reachable from it. When a node's low-link equals its own index, it's the root
of an SCC and the component is popped off a stack. It's cleverer and one pass, but subtler to
get right; Kosaraju's two passes are easier to see. `tarjan_scc` below is that independent
algorithm, the reference the trace generator checks Kosaraju against.
"""
import sys


# region: tarjan
def tarjan_scc(adj, n):
    """Tarjan's single-pass SCC algorithm. Each node gets an index (DFS discovery time) and a
    low-link (the smallest index reachable via its subtree and back-edges). Nodes are pushed on
    a stack as they're visited; when a node's low-link equals its index, it's an SCC root and
    everything above it on the stack forms the component. Independent of Kosaraju's two-pass
    reversal trick, so it's a real cross-check."""
    sys.setrecursionlimit(max(10000, n * 4))
    index_of = [None] * n
    low = [0] * n
    on_stack = [False] * n
    stack = []
    counter = [0]
    components = []

    def dfs(u):
        index_of[u] = low[u] = counter[0]
        counter[0] += 1
        stack.append(u)
        on_stack[u] = True
        for v in adj[u]:
            if index_of[v] is None:
                dfs(v)
                low[u] = min(low[u], low[v])
            elif on_stack[v]:
                low[u] = min(low[u], index_of[v])   # back-edge to a node still on the stack
        if low[u] == index_of[u]:                   # u is the root of an SCC
            comp = []
            while True:
                w = stack.pop()
                on_stack[w] = False
                comp.append(w)
                if w == u:
                    break
            components.append(sorted(comp))

    for s in range(n):
        if index_of[s] is None:
            dfs(s)
    return components
# endregion

Desde cero vs librería

Que dos algoritmos tan distintos —las dos pasadas con inversión de Kosaraju, la pasada única con números low-link de Tarjan— calculen la misma descomposición es la lección de cierre del bloque de grafos, y hace eco de los capítulos de árboles de expansión mínima: una estructura bien definida admite varios algoritmos correctos, y verificarlos uno contra otro es la prueba de correctitud más fuerte que hay. El de Kosaraju gana en claridad —su correctitud es un argumento cortito de orden de finalización que te cabe en la cabeza—, mientras que el de Tarjan gana en factores constantes, una sola pasada en lugar de dos, que es por lo que las librerías lo eligen. Ese intercambio entre el algoritmo más fácil de entender y el más rápido de correr ha aparecido a lo largo de todo el bloque (Kosaraju vs Tarjan, Prim vs Kruskal, Bellman-Ford vs Dijkstra), y la habilidad práctica está en saber cuál eje importa en tu situación. En producción llamarías networkx.strongly_connected_components; construir Kosaraju tú mismo es lo que convierte "invierte las aristas y vuelve a hacer DFS" en un truco que viste funcionar en vez de una receta que memorizaste.

Dónde te lo vas a topar de verdad

La descomposición en SCC aparece por todo el software de sistemas y el análisis de datos. Los sistemas operativos y las bases de datos detectan deadlocks encontrando ciclos (SCC no triviales) en el grafo de espera de procesos y locks. Los compiladores usan SCC para identificar loops en los grafos de flujo de control, para agrupar funciones mutuamente recursivas de cara a la optimización, y en análisis de punteros y de flujo de datos. El problema 2-SAT —¿es satisfacible una fórmula de cláusulas de dos literales?— se resuelve en tiempo lineal construyendo un grafo de implicaciones y revisando sus SCC, una aplicación célebre por lo elegante. Los estudios de estructura de la web usan SCC para encontrar el "núcleo" gigante de páginas mutuamente enlazadas (el modelo de moño de la web). El análisis de redes sociales los usa para encontrar grupos muy cerrados, y los model checkers los usan para encontrar ciclos que representan violaciones de liveness. Donde sea que un grafo dirigido tenga ciclos que haya que encontrar o colapsar, los componentes fuertemente conexos son la herramienta.

Puntos clave

Los componentes fuertemente conexos son los grupos maximales de nodos de un grafo dirigido que pueden alcanzarse todos mutuamente, y encontrarlos descompone cualquier grafo dirigido enredado en una condensación acíclica de componentes. El algoritmo de Kosaraju los encuentra en dos pasadas lineales de depth-first —registra el orden de finalización, luego haz DFS sobre el grafo con las aristas invertidas en orden inverso de finalización—, con la inversión de aristas como toda su idea; es razonamiento de orden de finalización (ordenamiento topológico) aplicado a un grafo cíclico. La descomposición es lineal, se verifica aquí contra el método independiente de una sola pasada de Tarjan, y expone estructura real, como el componente fuertemente conexo gigante que emerge de golpe cuando el grado promedio de un grafo dirigido aleatorio cruza el uno.

Con esto cierra el bloque de grafos, habiendo construido desde la representación y el recorrido (BFS, DFS), pasando por el ordenamiento (ordenamiento topológico), la familia de caminos más cortos (Dijkstra, Bellman-Ford, Floyd-Warshall, A*), los árboles de expansión mínima (Prim, Kruskal) y finalmente la descomposición estructural. El siguiente bloque cambia de grafos a strings: búsqueda de patrones y algoritmos de texto, empezando por la elegante forma en que KMP busca un patrón en un texto sin retroceder nunca, que, como tanto de lo que hay aquí, saca su velocidad de precalcular estructura antes de que arranque el loop principal.