- Donald Knuth abordó los strong components y weak components de los grafos dirigidos en la conferencia de Navidad 2024 de Stanford, y señaló el algoritmo de strong components de Tarjan como su algoritmo favorito
- Si se contrae cada strong component en un solo vértice, el resultado es un DAG sin ciclos, y el algoritmo funciona encontrando y eliminando el sink strong component
- Aquí, weak component no se refiere a un componente conexo ignorando la dirección, sino a una partición más general que vuelve a agrupar los strong components para formar un linear order
- El algoritmo de Tarjan distingue entre tree arc, back arc, loop, forward arc y cross arc durante el DFS, y obtiene al mismo tiempo los strong components y su orden topológico
- Lo que Knuth destaca como atractivo no es solo el procedimiento, sino la profunda estructura de datos organizada para que la información necesaria para decidir esté disponible exactamente en el momento correcto
El punto de partida de la conferencia y el nuevo libro de Knuth
- Al inicio de la conferencia, Knuth habló de su nuevo libro Constraint Satisfaction
- El manuscrito interno fue enviado a la editorial el día anterior, y ya puede reservarse
- Es posible que no llegue a imprimirse antes de Navidad, y la fecha oficial de publicación parece ser el 3 de febrero
- Dentro del libro aparece indicado como impresión de enero, y ha sido el principal proyecto de Knuth durante los últimos 5 años
- Los detalles del tema de esta vez, Strong Components and Weak Components, están en el pre-fascículo 12A
- Actualmente el libro va en el volume 4 Fascicle 7, y los fascículos anteriores se publicaron en tapa dura como volume 4A y 4B
- Este contenido formará en el futuro el primer tercio del volume 4C
- El subtítulo de la charla se acerca a “Which algorithm do you love the most?”
- Knuth dijo que normalmente no le gusta elegir un “algoritmo favorito”, pero que en este caso la respuesta es claramente el algoritmo de strong components de Tarjan
- Cuando aprendió este procedimiento en 1973, entendió por primera vez que una estructura de datos también podía ser “profunda”, igual que un teorema o un algoritmo
Diferencia entre strong component y weak component
- Un grafo dirigido está formado por vértices y flechas con dirección
- Si dos vértices u y v son mutuamente alcanzables, pertenecen al mismo strong component
- Todos los vértices de un ciclo quedan incluidos en el mismo strong component
- Incluso si hay caminos que entran desde varios lugares, un vértice del que no se puede salir puede constituir por sí solo un strong component
- El weak component que usa Knuth no es lo mismo que un componente no dirigido al ignorar las direcciones
- Su postura es que, si se ignora la dirección y se obtiene una componente conexa, eso debería llamarse “undirected component”
- Weak component es el concepto de volver a particionar el DAG obtenido al contraer los strong components, de modo que el conjunto completo quede en un orden lineal
- Si cada strong component se contrae en un “super vertex”, se obtiene un grafo sin ciclos
- Esto puede verse como un orden parcial
- Si además se contrae hasta weak components, se obtiene un orden total o linear order
- También está directamente relacionado con el ordenamiento topológico
- Si un x siempre aparece antes que y en todo ordenamiento topológico, entonces están en weak components distintos
- Si en un orden x puede aparecer antes que y y en otro y puede aparecer antes que x, entonces pertenecen al mismo weak component
- Knuth conecta esto con la incomparabilidad mutua
Historia del concepto y del algoritmo
- El concepto de weak component surgió en un intercambio de cartas entre Knuth, Ron Graham y un profesor citado como Mazkin sobre otro problema
- En una carta que Mazkin envió a Graham el 28 de febrero de 1970 ya aparecía la idea de obtener un orden total mediante una partición
- En diciembre de 1970, Knuth escribió a Graham que los tres habían demostrado un resultado más general, cada uno con un enfoque distinto
- Knuth decidió incluir a Mazkin como coautor, pero justo después recibió la noticia de que Mazkin había muerto repentinamente de un infarto
- El artículo relacionado apareció en 1972 en Discrete Mathematics volume 2 number 1
- En ese momento Discrete Mathematics era una revista recién nacida, y nadie imaginaba cuántos artículos excelentes publicaría después
- El algoritmo de strong components de Tarjan apareció en 1972 en SIAM Journal on Computing volume 1 number 2
- Tarjan era entonces estudiante de posgrado, y ese artículo fue el sexto en su lista de publicaciones
- Knuth leyó ese trabajo en enero de 1973 y desde entonces le encantó el algoritmo
- El libro de algoritmos de Aho, Hopcroft y Ullman también explica bien el algoritmo de Tarjan
- Hopcroft compartió oficina con Tarjan durante un sabático en Stanford, donde idearon varios algoritmos
- Hopcroft tenía la idea de un algoritmo para biconnected components en grafos no dirigidos, y Tarjan aplicó una idea similar a los strong components de grafos dirigidos
- El libro de Shimon Even trata el low point del algoritmo de Tarjan
- Tarjan resolvió la aparente circularidad de que para encontrar un component parece hacer falta el low point, pero para calcular el low point parece necesario conocer antes el component
Cómo encontrar strong components con DFS
- Knuth compara la exploración del grafo con explorar una cueva
- Cada room es un vertex, y la lista de otras rooms a las que se puede ir desde allí corresponde a los outgoing arcs
- La computadora no ve el dibujo, solo explora a partir de la lista de vértices y la lista de arcs
- El método básico de exploración es depth-first search
- Se avanza en profundidad por un outgoing arc que aún no se haya visto
- Cuando ya no hay adónde ir, se retrocede a la posición anterior
- Si se llega a un vertex ya visitado, se determina el tipo de ese arc
- En DFS, los arcs se dividen en cinco tipos
- tree arc: arc del árbol DFS que descubre por primera vez un nuevo vertex
- back arc: arc que regresa a un ancestro
- loop: arc que va hacia sí mismo y no afecta a los strong components
- forward arc: arc que apunta a un descendiente
- cross arc: arc que apunta a un vertex que no es ancestro ni descendiente
- Cada vez que el algoritmo descubre un strong component, en realidad encuentra un sink component del grafo que aún queda
- Todo DAG finito tiene siempre al menos un sink
- El método avanza eliminando ese sink strong component y repitiendo sobre el resto del grafo
- Así, al mismo tiempo que encuentra los strong components, también obtiene su ordenamiento topológico
- El rendimiento se presenta como muy rápido
- Para M arcs y N vértices, en el peor caso requiere alrededor de 5M + 17N accesos a memoria
- Esa cifra incluye operaciones como verificar el final de la lista de arcs o actualizar punteros
Weak components, versión mejorada e implementación
- El algoritmo de weak components también puede ejecutarse junto con el proceso de encontrar strong components
- Aprovecha que los strong components se descubren de derecha a izquierda, es decir, empezando por los sinks
- Cuando un nuevo strong component entra por la izquierda, se decide cómo debe combinarse con los weak components ya existentes
- Para decidir los weak components, son importantes los source y sink dentro de cada component
- Todos los sinks de un weak component deben tener arcs hacia todos los sources del siguiente weak component
- Esta condición es necesaria y suficiente para que existan weak components
- En programación, basta con seguir solo los sources para poder hacer las actualizaciones
- En 1974, Tarjan publicó un artículo de 3 páginas sobre un algoritmo para encontrar weak components en Information Processing Letters volume 3 number 1
- Knuth resume ese contenido en su pre-fascículo 12A
- Mantener una estructura de datos suficiente para garantizar tiempo lineal en el peor caso no es algo trivial
- Dijkstra también trató el problema de los strong components
- El capítulo 25 de su libro, “Finding the maximal strong components in a directed graph”, trata este tema
- Dijkstra usó una estructura basada en ir eliminando sink strong components, pero no llegó a la simplificación del low point de Tarjan
- Su solución introduce cuatro arreglos nuevos para seguir la estructura
- Knuth y Tarjan revisaron recientemente el algoritmo clásico y produjeron mejores definiciones y una versión mejorada
- Lo ajustaron a partir de una idea de Kurki-Suonio de los años 70, aunque el artículo original tenía una falacia
- Redujeron los accesos de alrededor de 7 por arc a unos 5 por arc
- Fusionaron algunos fields para lograr una forma más compleja pero más rápida, y Knuth bromeó diciendo que no era “premature optimization”, sino “post-mature optimization”
- La implementación se ofrece como un programa CWEB
- Se mencionan los nombres de programa Tarjan strong and weak y Tarjan strong
- La entrada es un grafo en formato Stanford GraphBase
- Knuth dijo que reorganizará los programas de su sitio web para que sea más fácil encontrarlos y corregirá el hecho de que no se actualizan desde 2022
- Stanford GraphBase incluye un ejemplo de grafo dirigido en el que unas 1,000 categorías del tesauro de Roget son los vértices, y las relaciones de synonym o antonym son los arcs
1 comentarios
Comentarios de Hacker News
En 2022, cuando visité San Francisco, estaba recorriendo el campus de Stanford y, justo cuando iba saliendo por un pasillo tranquilo y vacío de un edificio en verano, me encontré por casualidad con la oficina de Knuth
Me sorprendió lo pequeña que era para alguien de su fama, así que miré de nuevo, pero más bien me pareció un espacio que encajaba muy bien con su personalidad modesta
https://janvandenberg.blog/wp-content/img_1813-scaled.jpg
También tengo no uno, sino dos cheques de recompensa. Eran erratas pequeñas, pero tener esos dos documentos me parece realmente genial
Nadie la va a usar con mala intención, pero creo que me daría bastante escalofrío enterarme de que una foto de mi oficina está publicada sin que yo lo supiera
En mi tiempo libre estoy leyendo TAOCP 4A y 4B, y son realmente excelentes; los recomiendo muchísimo.
Para la mayoría de los programadores no son prácticos, pero la forma en que Knuth diseña y explica algoritmos es asombrosa y única.
En particular, la implementación de Dancing Links en 4B fue actualizada considerablemente desde el famoso paper, y es una estructura de datos refinada y hermosa, además de muy rápida. Incluso en sus 80 sigue siendo extraordinario.
Al calcular el costo necesario para nuestra escala, daba decenas de millones de dólares, pero todo el presupuesto de infraestructura de Route 53 estaba en el orden de decenas de miles de dólares. En el edge reutilizábamos como servidores de nombres servidores de CloudFront a los que se les había roto el disco duro, los servidores de API también eran modestos y el equipo era de unas seis personas. La forma AWS de “hacerlo a como dé lugar” consistía en gastar casi nada, reducir el riesgo a la baja y hacerlo rápido.
Así que no podíamos pedir decenas de millones de dólares para limpiadores de paquetes; además tardarían mucho en llegar y podían dejarnos demasiado atados a un proveedor específico.
Al principio decidimos operar los servidores de nombres de Route 53 en rangos de IP dedicados para lograr cierto aislamiento, y con enlaces de red dedicados podíamos evitar que otra infraestructura de Amazon se viera afectada. Pero eso no resolvía el problema de que los clientes de Route 53 compartieran el mismo destino, y el plan real era más o menos “si surge un problema, filtremos muy bien con las herramientas de red y de sistemas existentes”.
A comienzos del verano de ese año estaba metido en algoritmos combinatorios mientras leía el fascículo más reciente de Knuth relacionado con 4A, y una noche de pronto se me ocurrió que, si creábamos muchos servidores de nombres virtuales, podíamos asignar a cada cliente una combinación única de cuatro servidores de nombres virtuales. También podíamos controlar el grado de solapamiento, y calculé rápidamente que con unos 2,000 servidores de nombres podíamos garantizar que ningún par de clientes compartiera más de dos. En los experimentos, un dominio se resolvía bien aunque no se pudiera llegar a dos servidores de nombres, pero a partir de más que eso empezaba a haber problemas, así que ese número era importante.
El algoritmo de búsqueda recursiva para asignar IPs estuvo directamente inspirado en algoritmos de 4A, y proporcionó dos dimensiones adicionales de aislamiento independientes del dominio del cliente. El cliente recibe cuatro servidores de nombres de cuatro “stripes” independientes, que corresponden a distintos dominios de nivel superior usados en los nombres de los servidores (co.uk, com, net, org). Así, aunque uno de esos dominios de nivel superior tuviera un problema como un error de DNSSEC, solo se vería afectado un servidor de nombres.
Además, los hicimos salir de cuatro “braids” independientes, con lo que podíamos garantizar que ningún par de servidores de nombres compartiera una ruta de red específica ni hardware físico. Aunque por mi formación en estadística y criptografía conocía la combinatoria, sin haber leído 4A no habría podido diseñar algo así.
Nunca me había entusiasmado tanto una solución. Porque ofrecía un aislamiento demostrable a nivel de IP de red entre dominios de clientes prácticamente sin costo adicional de infraestructura. Era matemática. No fue totalmente gratis: tuvimos que usar 2,000 direcciones IP anycast y, por la forma en que muchos dominios de nivel superior exigen el registro de servidores de nombres y registros glue, también tuvimos que registrar 512 dominios. El proceso con los registradores fue bastante entretenido, pero al final lo logramos.
A este método lo llamamos Shuffle Sharding, y fue más un descubrimiento que una invención. Muchos sistemas multitenant que usan asignación aleatoria terminan obteniendo alguna forma de shuffle sharding, y técnicas de filtrado de red como Stochastic Fair Blue logran un efecto parecido mediante hashing basado en el tiempo. Pero no había visto el mismo enfoque con el nivel de control que nosotros podíamos aplicar, y pudimos extenderlo hasta shuffle sharding recursivo y anidado para aislar más niveles: no solo al llamador, sino incluso al llamador del llamador en patrones de “llamar en nombre de”.
Años después, como muestra de gratitud, fui en persona a ver la conferencia navideña de Knuth y me senté en la primera fila. Como uno nunca sabe qué le va a inspirar, todavía leo todo el material que publica Knuth. Incluso sus piezas para órgano.
Por eso creo que los libros de Knuth son sorprendentemente prácticos para los programadores. Amplían la forma de pensar y profundizan la comprensión; ¿qué más se puede pedir?
El paper original de Dancing Links es uno de mis papers favoritos. En frases como “este proceso hace que las variables puntero dentro de la estructura de datos global ejecuten una danza cuidadosamente coreografiada” se ve tal cual el amor de Knuth por los algoritmos.
Lo estoy usando para generar crucigramas, haciendo que las palabras horizontales y verticales formen una cobertura exacta (exact cover) de la cuadrícula.
Me da curiosidad si el algoritmo actualizado usa menos memoria.
Para este problema grande estimo que hay alrededor de 100 millones de soluciones, y aunque encontrara 100 por segundo tardaría unos diez días en terminar.
El problema en el que estoy trabajando es contar la cantidad de casos en ‘Fancy Tetris Houten Puzzel’ en los que las piezas del mismo color están todas conectadas compartiendo al menos un lado.
También estoy pensando en otros algoritmos menos sensibles a la memoria para resolver este problema de cobertura exacta.
Lo pregunto como alguien que recién empezó hace poco a leer literatura relacionada con ciencias de la computación.
Hace unos años fui a San Francisco y me sorprendió enterarme de que Donald Knuth no solo seguía vivo, sino que además continuaba dando conferencias todos los años en Stanford.
Recuerdo mucho aquella noche en que fui a buscar el edificio en el campus y lo vi hablar en persona sobre un tema que casi no podía seguir. Donald Knuth es realmente una leyenda.
Un compañero de equipo encontró el mes pasado un error en Seminumerical Algorithms y recibió un cheque de recompensa por 1 hexadecimal dollar; llegó junto con una impresión del correo original con anotaciones manuscritas.
Lo que más me inspira de Donald Knuth es su dedicación y disciplina sostenidas durante décadas.
Como alguien que cambia constantemente de proyectos, lenguajes y distribuciones, tengo muchísimo que aprender de él.
La ropa es muy llamativa y viva; parece un traje tradicional o folclórico de los que se usaban en algún pueblo antiguo, pero no sé bien si es iraní, eslavo o algo intermedio.
¿Alguien tiene una mejor idea?
Mi recuerdo es borroso y quizá también tenía que ver con su esposa. Parece que la usa seguido en conferencias desde mediados de la década de 2010, y debe de haber alguna explicación en algún lado.
Una vez estuve junto a Knuth en 2012, en la plaza frente al Manchester Town Hall, cuando intentaba subirse al marco de una ventana para ver llegar la antorcha olímpica. Le hablé y, por un momento, extendí la mano por si se caía por la ventana, pero no pasó nada. Me pareció una persona muy curiosa, con preguntas e inteligencia brillantes, y más joven de lo que indicaba su edad.
Ambos estábamos asistiendo al evento por el centenario del nacimiento de Alan Turing, y fue asombroso estar en la misma sala con gigantes de la computación como Knuth, Gary Kasparov, Fred Brooks, Vint Cerf, entre otros. A la hora del almuerzo, la antorcha olímpica llegó a la plaza de afuera, y él no pudo resistirse a ir a verla. Parecía ser el único realmente emocionado por eso.
Esa noche dio una charla durante la cena y, más tarde, cuando volví a verlo en Manchester justo después de que se publicara 4B, le pedí que me firmara el libro y pareció reconocerme vagamente del evento anterior.
Cuento esto porque creo que su camisa sugiere una mente mucho más ecléctica y curiosa. También vi pruebas claras de eso en otros lugares.
Así que tal vez de ahí venga su cariño por la vestimenta tradicional Sami.
[0]: https://youtu.be/jB0aeePskBg
https://www.youtube.com/playlist?list=PLoROMvodv4rOAvKVR_dyC...
Revisé y tiene 87 años. Donald Knuth nació el 10 de enero de 1938.
Guau.
Knuth sigue siendo asombroso.
Dicho eso, es muy sorprendente y decepcionante que nadie en Stanford se haya ocupado bien de una grabación de audio a la altura de este material. Suena como si alguien lo hubiera grabado con una grabadora en el bolsillo.
No me refiero a la voz de Knuth en su vejez, sino a lo mala que es la calidad del audio cuando él hace una pausa y recibe preguntas del público.
Videos como este me recuerdan por qué me enamoré de las computadoras en primer lugar.
Es bastante sorprendente que siga tan lúcido. Lamentablemente, cuando yo era estudiante de licenciatura hace unos 20 años, él ya no daba clases.
Me gusta cómo maneja las preguntas: https://youtu.be/Hi8r_63LGyg?t=827
Se toma el tiempo para entender qué le están preguntando y responde con mucha claridad.