Dijkstra directo sobre grafos algebraicos: sin mapa de adyacencia y en O(s log s)
Un post esboza cómo ejecutar el algoritmo de caminos mínimos sobre las expresiones que usa la librería alga, con un coste declarado de O(s log s) y sin materializar aristas.
Trabajar con la representación algebraica de un grafo sin expandirlo antes a un mapa de adyacencia no solo es posible: ya hay un esbozo de cómo hacerlo con Dijkstra encima. Un post describe un método para ejecutar el algoritmo de caminos mínimos sobre las expresiones que maneja alga, la librería de grafos algebraicos de Andrey Mokhov, con un coste declarado de O(s log s), donde s es el tamaño de la expresión del grafo.
El punto de partida es el tipo de datos de alga: Empty, Vertex, Overlay y Connect con peso. Hasta ahora, las operaciones sobre estos grafos pasaban por convertirlos primero en un mapa de adyacencia y trabajar sobre él. El problema es que expandir la expresión obliga a materializar todas las aristas, lo que cuesta O(n²), y eso deja fuera a los algoritmos subcuadráticos en el número de vértices.
Connect guarda una biclique
La pieza clave es Connect. En un grafo dirigido describe una biclique: un subgrafo bipartito completo dirigido desde cada vértice del hijo izquierdo hasta cada vértice del hijo derecho, siempre que los conjuntos sean disjuntos. Ocupa O(1) de espacio para sí mismo y O(n) para sus hijos, no en proporción al número de aristas, que sería O(n²). La representación de alga es, de hecho, una forma de compresión de grafos.
La compresión de grafos es un campo activo. El post se apoya en el paper Faster Graph Algorithms Through DAG Compression, de Max Bannach, Florian Andreas Marwitz y Till Tantau, publicado en STACS 2024, donde describen algoritmos sobre una estructura que bautizan como switching graph. Antes de llegar ahí definen un DAG de clústeres: un DAG cuyos sumideros son exactamente el conjunto de vértices V del grafo G que describe, y en el que cada nodo representa el subconjunto de sumideros alcanzables desde él. Añadiendo una relación de aristas extra E' se obtiene una compresión DAG: si (u', v') está en E', entonces el producto C(u') × C(v') está en G.
El paralelismo con alga es directo: Connect w x y añade el producto V(x) × V(y) al grafo padre. Para pasar de una expresión de alga a una compresión DAG hay que resolver tres detalles: consolidar en un único nodo todos los constructores Vertex que denotan el mismo vértice lógico, descartar las subexpresiones sin vértices como Empty, y quedarse con la arista de peso mínimo cuando aparezcan multiedges, algo que no rompe el cálculo de caminos mínimos porque siempre interesa la arista más barata.
El grafo de conmutación
La estructura que permite buscar de verdad es el switching graph, una ampliación de la compresión DAG. BMT duplican todos los vértices salvo los que representan V: el original se queda como vértice superior, el que representa un vértice real es intermedio, y la copia es inferior. Añaden además una arista invertida por cada relación padre-hijo, que sirve para subir hacia los ancestros y establecer alcanzabilidad y distancias.
El resultado es un Dijkstra que corre sobre la descripción del grafo y no sobre el grafo, en O(s log s).
Todo esto es un esbozo del método. La cifra de O(s log s) es la que da el propio autor sobre el papel, no una medición independiente. Para quien trabaje con alga o con grafos comprimidos, la propuesta apunta a un sitio concreto donde rascar: evitar la expansión que convierte una estructura pequeña en un problema cuadrático.
