Rastreando el tipo de dato desaparecido
(hillelwayne.com)- Los grafos están por todo el software, como en dependencias, enlaces web, espacios de estado de model checkers y claves foráneas de bases de datos relacionales, pero los lenguajes de programación convencionales casi no tienen tipos integrados ni soporte en la biblioteca estándar
- La primera razón por la que es difícil crear un tipo de grafo integrado es que hay muchos tipos de grafos, como dirigidos o no dirigidos, simples o multigrafos, e hipergrafos, y ciertas propiedades cambian mucho la elección del algoritmo y el rendimiento
- Según la forma de representación —lista de aristas, lista de adyacencia, matriz de adyacencia, structs con referencias, etc.— cambian la memoria y el rendimiento de consulta, así que es difícil que una sola representación genérica cubra todos los casos de uso
- Los algoritmos de grafos son difíciles de implementar y suelen ejecutarse sobre entradas grandes, por lo que, como muestran los casos de Nosey Parker y Gecode, la representación y el recorrido ajustados al problema pueden ser más importantes que una biblioteca genérica
- La razón por la que los grafos son raros en la biblioteca estándar es la gran carga de trade-offs de tipos, representación, algoritmos y rendimiento, además del costo de mantenimiento; incluso las bibliotecas de terceros pueden ser limitadas o lentas
Los grafos son comunes, pero el soporte del lenguaje es escaso
- Un grafo está compuesto por nodos y aristas, y tanto los nodos como las aristas pueden contener datos
- En la ingeniería de software, los grafos aparecen de muchas formas
- Las dependencias de paquetes y los
importde módulos forman un grafo dirigido - Internet es un grafo de enlaces entre páginas web
- Los model checkers exploran el espacio de estados de todas las configuraciones posibles; los nodos son estados y las aristas son transiciones válidas
- Las bases de datos relacionales pueden verse como nodos de registros y aristas de claves foráneas
- Un grafo puede verse como una generalización de listas enlazadas, árboles binarios y tablas hash
- Las dependencias de paquetes y los
- Incluso en la lógica de negocio aparecen seguido grafos como relaciones de citación académica, rutas de redes de transporte y conexiones de redes sociales
- Aunque los grafos se necesitan con frecuencia, la mayoría de los lenguajes convencionales no los ofrecen como tipo integrado y rara vez los incluyen en la biblioteca estándar
- En muchos ecosistemas también faltan bibliotecas de grafos de terceros realmente sólidas, así que a menudo toca implementarlos por cuenta propia
Diseñar un tipo de grafo implica demasiadas opciones
- Además de grafos dirigidos y no dirigidos, existen muchas variantes
- Grafos simples, donde hay como máximo una arista entre dos nodos, y multigrafos, que permiten varias aristas
- Hipergrafos, donde una arista conecta tres o más nodos
- Ubergrafos, donde una arista puede apuntar a otras aristas
- Cada variante trae decisiones de diseño adicionales
- Hay que decidir si las aristas también tendrán ID o solo los nodos
- También hay que decidir qué datos almacenarán nodos y aristas
- Podría ofrecerse un tipo genérico que cubra todo, algo como un “hiperubermultigrafo dirigido”, y dejar que el usuario imponga restricciones, pero de inmediato aparecen dos problemas
- La interfaz cambia, por ejemplo si el resultado de una operación es un solo valor o una lista
- Si no se aprovechan propiedades especiales del grafo, el rendimiento de los algoritmos empeora
- Por ejemplo, maximum weight matching puede usar un algoritmo rápido si se sabe que el grafo es bipartito, pero para grafos generales hace falta un algoritmo más lento y más genérico
- Cuando hay un problema P, un grafo G y algoritmos A, B y C, también aparece el problema del despacho de algoritmos: elegir cuál ejecutar
- Una biblioteca de grafos perfecta tendría que soportar muchos tipos de grafos, pero eso reduce el tiempo disponible para implementar los algoritmos que los usuarios realmente quieren
- Los algoritmos de grafos son difíciles de implementar
- El algoritmo
find_shortest_pathescrito por el creador de Python fue corregido cinco veces después - Nicole dice que todas las implementaciones de PageRank que comparó estaban mal
- NetworkX ofrece unos 500 algoritmos de grafos, y solo ese código suma casi 60,000 líneas
- Toda la biblioteca estándar de Python tiene alrededor de 300 paquetes y menos de 600,000 líneas
- El algoritmo
- Quienes mantienen la biblioteca estándar tendrían que decidir qué tipos de grafos, qué tratamientos topológicos especiales y qué algoritmos incluir, así que la carga de mantenimiento es alta
- Incluso Python, conocido por su enfoque de “batteries included”, avanza hacia quitar módulos de la biblioteca estándar, como muestra PEP 594, que elimina 20 módulos
También es difícil fijar una sola representación de grafos
- Incluso si solo pensamos en el grafo dirigido más simple, hay varias representaciones internas posibles
- Lista de aristas:
[[a, b], [b, c], [c, a], [c, b]] - Lista de adyacencia:
[[b], [c], [a, b]] - Matriz de adyacencia:
[0 1 0; 0 0 1; 1 1 0] - Conjunto de structs que se referencian entre sí
- Lista de aristas:
- El rendimiento de las operaciones cambia según la representación
- Si un grafo con 100 nodos y 200 aristas se representa con una matriz de adyacencia, en una matriz de 100×100 habrá 200 unos y 9,800 ceros
- Si el mismo grafo se representa como lista de aristas, solo hacen falta 200 pares de nodos
- Según el lenguaje y el nivel de optimización, la diferencia de memoria puede superar 20 veces
- En cambio, para un grafo con 100 nodos y 8,000 aristas, al buscar una arista entre el nodo 0 y el 93, el resultado cambia
- Una matriz de adyacencia permite consulta en O(1) con
graph[0][93] - Una lista de aristas requiere recorrer las 8,000 aristas, así que toma O(|edge|)
- Una matriz de adyacencia permite consulta en O(1) con
- Un grafo con pocas aristas es un grafo disperso, y uno con casi todas las aristas posibles es un grafo denso
- Un programa que construye grafos desde datos externos puede empezar con un grafo disperso y luego volverse denso, así que no existe una “siempre buena elección” de representación interna
- Si además se soportan datos en nodos, datos en aristas y múltiples tipos de nodos y aristas, la complejidad de implementación crece aún más
- Las bibliotecas de terceros suelen elegir una de dos direcciones
- Ofrecer un único tipo rico que cubra todos los casos de uso, sacrificando eficiencia
- Ofrecer tipos de grafo separados por representación y dejar al usuario el manejo de datos en nodos y aristas
Los trade-offs que muestran NetworkX y Petgraph
- NetworkX almacena los grafos como una estructura de dict de dict de dict para poder adjuntar datos arbitrarios a nodos y aristas
- Ofrece funciones para convertir a otras representaciones, pero no una forma de trabajar directamente con esas representaciones como tales
- Petgraph, una biblioteca de grafos representativa de Rust, ofrece tipos por caso de uso como
graph,graphmapymatrix_graph - Bradford usa Petgraph en Nosey Parker, una herramienta de seguridad que busca secretos en todo el historial de un repositorio git
- El grafo de benchmark es CPython, con 250,000 commits y 1,300,000 objetos
- Como cada nodo commit tiene solo unas pocas aristas, eligió una lista de adyacencia
- Soportar varias representaciones aumenta el costo de agregar algoritmos
- Si se escribe un algoritmo separado para cada representación, la carga de mantenimiento aumenta entre 3 y 4 veces
- Si se escribe sobre una abstracción genérica de tipos polimórficos, el rendimiento baja
- Una persona entrevistada estimó que un algoritmo de grafos escrito a medida puede ser más de 20 veces más rápido que uno genérico
Las restricciones de rendimiento son el problema central de las bibliotecas de grafos
- En algoritmos de grafos abundan los problemas NP-complete o incluso más difíciles
- De los 21 problemas canónicos NP-complete de Karp, 14 son problemas de grafos
- Los problemas de grafos pueden ejecutarse sobre entradas enormes, así que la representación y los detalles de implementación determinan si algo es viable o no
- En Nosey Parker, Bradford tenía que recorrer un grafo de objetos para reconstruir un snapshot del sistema de archivos en cada commit
- Los cuatro graph walkers de Petgraph no se adaptaban a ese caso de uso
- Diseñó sobre la marcha un algoritmo de recorrido de grafos “semi-novel” y redujo el uso de memoria a una milésima parte
- Zayenz menciona el 15 puzzle como ejemplo de un caso donde el grafo es tan grande que no se puede manejar completo
- La búsqueda de una solución consiste en ejecutar A* search sobre el espacio de estados
- Ese espacio de estados tiene más de 20 billones de estados
- Si se generan todos los nodos, ya se fracasó
- También en un proyecto de investigación para añadir grafos al solver de restricciones Gecode en el que participó Zayenz, un tipo de grafo genérico no podía competir con una representación elegida específicamente para el problema
- Las bases de datos de grafos también se diseñaron para ejecutar algoritmos complejos sobre grafos, pero siguen teniendo problemas de rendimiento
- Según Nicole, si no se limita la profundidad al recorrer, se termina visitando todo el grafo
- Incluso una búsqueda de profundidad como “sal tres pasos y encuentra si existe un camino” puede terminar tocando muchísimos datos
- Nicole dice que su trabajo de consultoría en rendimiento de consultas de grafos consiste principalmente en migraciones para salir de bases de datos de grafos
- En un proyecto, dejaron intacto solo un cálculo y reescribieron el resto como un procedimiento MapReduce
- Era más difícil de entender, pero sí podía terminarse durante la noche
Por qué los grafos son raros en la biblioteca estándar
- Que el soporte amplio para grafos sea raro se debe a la combinación de varios factores
- Hay muchos tipos de grafos
- Cada tipo de grafo admite muchas formas de representación
- Hay muchos tipos de algoritmos de grafos
- El rendimiento de los algoritmos es sensible a la representación y a los detalles de implementación
- La gente ejecuta algoritmos muy costosos sobre grafos muy grandes
- Las bibliotecas estándar de los lenguajes tendrían que absorber demasiadas decisiones de diseño, trade-offs y carga de mantenimiento
- También hay razones por las que los programadores evitan bibliotecas de grafos de terceros
- La biblioteca puede ser demasiado limitada
- Una biblioteca genérica puede no cumplir los requisitos de rendimiento
- Los grafos son útiles para analizar sistemas, pero en la etapa de implementación muchas veces hace falta controlar directamente la representación de los datos y la elección del algoritmo
Apéndice: lenguajes que ofrecen tipos de grafos y herramientas relacionadas
- Los lenguajes de consulta de grafos (GQL) cumplen en las bases de datos de grafos un papel equivalente al de SQL
- GraphQL no es un lenguaje de consulta de grafos; su nombre proviene de su conexión con Facebook Graph Search
- La principal diferencia entre GQL y SQL es que las relaciones, es decir, los “join”, son entidades de primera clase
- En un dataset de películas y personas, SQL implementa las relaciones de “actuó en”, “dirigió” y “produjo” como tablas many-to-many separadas
- En SPARQL, como las relaciones son aristas, es fácil consultar “qué personas participaron en la película Y y en qué rol”
- GQL también puede soportar manipulaciones de aristas como inversión, composición y clausura transitiva
- SPARQL no puede calcular cosas sobre rutas o sobre el interior de una ruta, por ejemplo recolectar la cadena de películas que conecta a dos actores
- Un GQL que sí lo soporte se vuelve mucho más complejo
- El lenguaje de especificación formal Alloy tiene primitivas útiles de recorrido sobre el tipo de dato relation, lo que facilita trabajar con representaciones de grafos más que en los lenguajes de programación generales
- Aun así, esas primitivas están basadas en aristas etiquetadas y pueden no encajar con otras representaciones de grafos
- Python añadió graphlib en 2020
- No tiene métodos aparte de
TopologicalSorter - Solo recibe el grafo como un dict de nodos
- Representa un grafo
a -> bcon un dict invertido, como{b: [a]}
- No tiene métodos aparte de
- En 2023,
graphlibno se usaba dentro de CPython- En GitHub hay menos de 900 archivos que hacen referencia a
graphlib zoneinfo, añadido el mismo año, aparece en más de 6,000 archivos- La expresión
def topological_sort(aparece en 4,000 archivos - Muchas implementaciones manuales de topological sort usan representaciones de grafo distintas de las de graphlib, así que es difícil convertirlas
- En GitHub hay menos de 900 archivos que hacen referencia a
- Otros ejemplos de bibliotecas estándar con tipos de grafos son Erlang y SWI-Prolog
- También existen lenguajes de programación donde “todo es un grafo”
- Los lenguajes de software matemático como Mathematica, MATLAB y Maple también tienen alguna forma de biblioteca de grafos
- Una actualización del 18 de marzo de 2024 reunió algunos comentarios sobre el artículo en una página separada
1 comentarios
Opiniones en Hacker News
Graphviz tiene su propia biblioteca gráfica básica, que no usan otros proyectos, y eso tiene tanto ventajas como desventajas.
Con base en esa experiencia, nosotros también sufrimos el típico síndrome del segundo sistema. Queríamos crear una biblioteca de grafos modular, type-safe y eficiente, pero al final probablemente era una variante de “bueno, rápido y barato: elige solo dos”.
Que fuera modular significaba que queríamos poder desarrollar y compilar de forma independiente un conjunto de bibliotecas de algoritmos de grafos; que fuera type-safe significaba que queríamos detectar errores de programación en tiempo de compilación o, a más tardar, durante el enlace, en vez de errores en runtime como “el nodo no tiene el atributo color”.
Que fuera eficiente significaba que el costo de acceder a las propiedades del grafo debía ser tan barato como acceder a un campo de una estructura en C, y no queríamos un enfoque que cargara tablas hash externas o hiciera muchas conversiones de cadenas.
Se puede debatir si esos objetivos tenían sentido o si valían el costo, pero eso era lo que queríamos en ese momento. En el laboratorio había famosos creadores de C++, y también consideramos darle otra oportunidad a C++.
Gordon Woodhull, que había sido pasante y siguió trabajando con nosotros, era un programador excelente y escribió una implementación de este tipo de biblioteca de grafos en C++ con templates. El código fuente también está publicado en https://www.dynagraph.org/.
Los demás no estábamos seguros de si algún día podríamos entender cómo funcionaba ese código, así que hicimos una revisión de código con famosos inventores de C++; después de muchísimas pantallas de código y silencio, la conclusión fue que “probablemente funcione”. En ese momento ya supimos que tal vez habíamos cruzado el precipicio de la complejidad.
Los errores de templates en tiempo de compilación llenaban toda la pantalla con un solo error y arrojaban detalles que solo un inventor de C++ podría amar. La culpa era nuestra, y Gordon siguió avanzando hasta hacer que el layout dinámico de grafos funcionara incluso en Microsoft OLE.
Viéndolo en retrospectiva, fue nuestro propio Project Xanadu, y mientras nosotros nos perdíamos ahí, aparecieron cosas como Gephi (Java), NetworkX y NetworKit (Python). John Ellson, un excelente ingeniero de software que escribió parte de Graphviz, reactivó el trabajo principal.
Como alguien que ha trabajado mucho con grafos, me preguntaron innumerables veces: “¿por qué los lenguajes de programación no tienen un tipo de dato grafo incorporado?”.
Ahora me alegra no tener que limitarme a pedir que me crean cuando digo “es realmente difícil hacerlo bien”, sino poder señalar un análisis más profundo como este artículo.
Lo que la mayoría de los lenguajes ofrece como tipos estructurales se reduce a arreglos estáticos, arreglos dinámicos y listas enlazadas. Cosas como árboles binarios de búsqueda o tablas hash son abstracciones semánticas que ocultan parte de las capacidades de la estructura subyacente, no representaciones estructurales puras.
La parte del artículo sobre que “hay demasiadas opciones de implementación” dice lo mismo. Luego vi Petgraph [0] y por primera vez revisé en serio una biblioteca de grafos de propósito general; fue bastante interesante, pero aun así he seguido implementando los grafos a nivel de dominio.
[0] https://github.com/petgraph/petgraph
https://core.tcl-lang.org/tcllib/doc/trunk/embedded/md/tclli...
Casi todos los lenguajes ofrecen hash maps, y aunque en ciertos casos uno puede implementar uno propio y hacerlo más rápido, la implementación por defecto suele funcionar bastante bien. Con los grafos es difícil hacer eso, y quizá, si se pudiera, habría que ofrecer varios tipos de grafos.
Además, HashMap de Java es un poco peculiar porque, a diferencia de la mayoría de los demás lenguajes, permite ajustar el factor de carga.
Lo que la gente quiere no es tanto el tipo grafo en sí, sino herramientas para recorrer grafos.
Pienso que un grafo es más una abstracción que una estructura de datos o un tipo de dato.
En lo fundamental, lo único que se necesita para definir un grafo es un conjunto de vértices v \in V y una función Neighbors(v), y para la mayoría de los algoritmos básicos de grafos eso realmente basta.
El resto son restricciones caso por caso: si A->B implica B->A, si el conjunto de nodos puede particionarse bajo ciertas restricciones, si tiene colores o etiquetas, etc.
Si se generaliza más, se llega hasta los hipergrafos; en ese caso basta con un conjunto de vértices y un conjunto de conjuntos de vértices. Pueden representarse de muchísimas maneras según el interés, y los grafos comunes son solo un caso especial.
Desde la perspectiva de bases de datos, también puede verse como un problema de optimización de consultas e indexación. Según qué preguntas quieras hacerle al grafo, cambia la representación que puede responderlas mejor. Así como no hay una sola forma de representar la abstracción “tabla”, tampoco hay una única forma de resolver “grafo”.
Están en el mismo nivel de abstracción que los números puros. Se puede decir que existen bibliotecas “numéricas” útiles, así como bibliotecas “gráficas” útiles, pero no hay muchas bibliotecas de “números” o de “grafos” como tal. Esos conceptos son demasiado abstractos para diseñar una API.
Los archivos serían vértices, y los directorios serían conjuntos de vértices que pueden anidarse.
Hay dos obstáculos principales
Para problemas de grafos simples y pequeños, es bastante fácil implementar directamente una lista de adyacencia hecha con vectores de vectores; y para problemas de grafos complejos y enormes, el rendimiento solo llega cuando se hace una implementación del grafo a la medida de los detalles del problema que se quiere resolver
Por eso no queda claro qué tipo de soporte del lenguaje ayudaría. Sería difícil salvo que existiera un compilador superinteligente capaz de analizar el código y decidir qué es óptimo: una lista de adyacencia, una matriz, un arreglo tridimensional, etc. Ese tipo de optimización difícilmente se verá en compiladores por un buen tiempo
Es otro ejemplo del fenómeno que observó Stroustrup. Somos buenos compartiendo código para cosas pequeñas como vectores y para cosas grandes como sistemas operativos, pero no compartimos bien los problemas de tamaño intermedio
Dentro del ecosistema de un lenguaje, la API de vectores es pequeña, y por eso parece fácil de compartir. En los sistemas operativos, la API es relativamente pequeña en comparación con su complejidad interna, y lo mismo pasa con las bibliotecas de cómputo numérico, así que se comparten bien
En cambio, mientras más se quiere personalizar algo, como una estructura de datos compleja, más se complica la API y más difícil es compartirlo. Al final, la posibilidad de compartir parece depender de la superficie de lo que se comparte, es decir, del tamaño relativo de su API
Electric Clojure usa las propias expresiones-s de Clojure como sintaxis para escribir grafos, y mediante macros concreta el flujo de datos de un sistema reactivo cliente/servidor
Aquí el caso de uso es una interfaz de usuario full-stack, pero la idea se puede generalizar. https://github.com/hyperfiddle/electric Soy fundador
Mi respuesta a “¿a dónde se fueron todos los tipos de grafo?” es que un DSL para escribir grafos tiene que expresar alcance, flujo de control y abstracciones; y cuando hace eso, en la práctica se vuelve isomorfo a un lenguaje de programación liberado del modelo de evaluación. En Python y TypeScript es bastante difícil insertar un lenguaje de programación completo
También vale la pena ver la entrada de blog “Four problems preventing visual flowchart programming from expressing web applications”
https://www.dustingetz.com/#/page/four%20problems%20preventi...
Este artículo responde principalmente a “por qué los lenguajes de programación no dan mejor soporte a los algoritmos de grafos”, y parece estar más enfocado en el procesamiento de grafos de “big data” que en el soporte general para grafos
Si vemos el soporte para grafos en general, también entran preguntas más amplias como “por qué los OGM (Object Graph Mapper) no son tan populares como los ORM” o “por qué JSON se usa tanto, pero RDF u otras serializaciones de grafos de bajo nivel no”
Al final, creo que las razones históricas pesan mucho. RDF salió un poco demasiado pronto, no logró evolucionar bien y terminó construyendo un ecosistema terrible de estándares académicos e implementaciones. Además, los grafos son intrínsecamente un poco más complejos en implementación y curva de aprendizaje, así que no escalan bien para muchos desarrolladores
No le daría demasiado peso a la sección “Graph Querying Language” del artículo. Hay partes que se leen como texto de marketing escrito por un usuario entusiasta de Neo4J o SPARQL que no ha construido productos reales
Dice que “la principal diferencia entre todos los GQL y SQL son los joins, es decir, que las relaciones son entidades de primera clase”, pero en SQL los joins también son entidades de primera clase. Incluso existe la palabra clave JOIN
Si se baja a una capa inferior de los lenguajes de consulta de grafos y se mira el plan de consulta, no hay muchas diferencias significativas con las consultas basadas en SQL. El hecho de que la estandarización de GQL[0] se esté llevando como una extensión de SQL es prueba de ello
SPARQL es fácil cuando se necesita un recorrido exacto de rutas, pero en cuanto uno intenta hacer algo un poco más complejo, como lo que haría en el backend de una webapp, se topa rápido con trampas que pueden destruir accidentalmente todo el conjunto de resultados, como hacer joins con valores no enlazados
[0]: https://en.wikipedia.org/wiki/Graph_Query_Language
Por ejemplo, las clases de tipos de Haskell no son de primera clase, y el flujo de control tampoco lo es en la mayoría de los lenguajes de programación
Solo que no tienen un atajo sintáctico; los lenguajes de consulta de grafos se enfocan, en esencia, en agregar ese atajo
Las herramientas para dibujar grafos también son bastante decepcionantes. Funcionan bien con grafos pequeños, pero cuando se superan unos 500 nodos, la salida se vuelve completamente incomprensible o muy difícil de ver.
Les falta la capacidad de organizar automáticamente el grafo en una estructura jerárquica y ofrecer una interfaz fácil de explorar. Si pensamos que estamos acostumbrados a ver, en cierta medida, casi todo lo que nos rodea como una estructura jerárquica, parece que al crear un tipo de datos de grafo de propósito general habría que resolver el mismo tipo de problema.
Tal vez esto deba implementarse a nivel de compilador, de modo que los algoritmos de grafos de propósito general se adapten a la jerarquía de estructuras generada. Si además se suma un demostrador de teoremas para verificar que ciertos subgrafos siempre tienen una estructura determinada, ese procedimiento podría generarse de forma estática, mientras que para el resto del grafo superior se generaría dinámicamente en tiempo de ejecución.
Por lo tanto, quien resuelva el problema del dibujo de grafos de propósito general probablemente también tendrá la capacidad o la intuición para implementar esto.
Una biblioteca de dibujo de grafos de propósito general al estilo Graphviz, que ofrece más opciones y control.
https://eclipse.dev/elk/
Experimentos realizados por el equipo de desarrollo de ELK en Kiel University.
https://github.com/kieler/KLighD
Wiki del proyecto Kieler.
https://rtsys.informatik.uni-kiel.de/confluence/display/KIEL...
Biblioteca de dibujo de grafos basada en restricciones.
https://www.adaptagrams.org/
Implementación en JavaScript.
https://ialab.it.monash.edu/webcola/
Como material interesante, HOLA: Human-like Orthogonal Network Layout.
https://ialab.it.monash.edu/~dwyer/papers/hola2015.pdf
La demo de Confluent Graphs hace que las aristas sean más legibles.
https://www.aviz.fr/~bbach/confluentgraphs/
Stress-Minimizing Orthogonal Layout of Data Flow Diagrams with Ports.
https://arxiv.org/pdf/1408.4626.pdf
Improved Optimal and Approximate Power Graph Compression for Clearer Visualisation of Dense Graphs.
https://arxiv.org/pdf/1311.6996v1.pdf
Incluso con grafos estructuralmente idénticos, dos personas podrían renderizarlos de formas totalmente distintas para destacar aspectos diferentes de los datos. Esto también se parece al problema de los “algoritmos de grafos de propósito general” y las “estructuras de datos de grafos de propósito general”.
Los grafos están en la frontera entre código y datos. Por ejemplo, todo programa tiene un grafo de llamadas, así que en cierto sentido un “algoritmo de grafos de propósito general” es el cómputo mismo.
Cuando se pasa de apenas unas decenas de nodos, normalmente es difícil hacerlos planos, o reducir los cruces y agrupar bien los nodos relacionados para que parezcan casi planos.
En realidad, el dibujo de grafos tiene que reconciliar cosas que casi nunca son jerárquicas, y es difícil trazar una línea matemáticamente rigurosa sobre hasta dónde considerar algo como una jerarquía. Cuantas menos suposiciones se hagan sobre la estructura del grafo subyacente —como conectividad, presencia o ausencia de ciclos, o dispersión—, peor se vuelve este problema.
En la práctica, al crear una UI para interactuar con grafos, normalmente se puede definir o imponer uno o dos niveles de metajerarquía para hacer clustering; así se reduce el impacto de los nodos tipo hairball que arruinan el layout y también se baja la cantidad de nodos, lo que mejora el rendimiento del renderizado. Para el layout se puede usar fCOSE, y también existe una implementación en Cytoscape.js.
Creo que la observación central de que “hay demasiadas opciones de implementación” no es del todo correcta.
En la práctica, una biblioteca podría implementar todas las representaciones de grafos adecuadas, ofrecer los algoritmos con mejor rendimiento para cada representación y proporcionar conversiones entre representaciones. Esas conversiones crecen en proporción al número de representaciones, y tanto su implementación como su uso son simples, así que la carga es bastante razonable tanto para mantenedores como para usuarios.
Además, también podría ofrecer conversiones de importación/exportación desde los tipos de datos y modismos de la biblioteca estándar. La memoria y el costo de conversión son baratos, y en el 99% de los casos de uso probablemente se pueda ignorar el overhead de transformar datos, tanto en RAM como en CPU.
También me viene a la mente la frase: “La dura verdad de trabajar en Google es que al final estás moviendo protobufs de un lugar a otro”.
https://news.ycombinator.com/item?id=20132880
Al final siempre termino reimplementando grafos. El rendimiento importa, y las bibliotecas de grafos ya hechas que he visto no aprovechaban la regularidad de nuestro dataset. Por ejemplo, usamos un DAG append-only en el que casi todos los nodos tienen una sola arista que apunta al elemento agregado más recientemente, así que internamente se puede usar codificación por longitud de corrida.
Tampoco he visto una biblioteca de grafos genérica que soporte las consultas que necesitamos. En particular, una importante es una función de diff de subgrafos.
Además, una implementación a medida no es tanto trabajo. Un grafo es mucho más fácil de reimplementar que un B-tree, y una implementación simple cabe en unas decenas de líneas. Incluso nuestra biblioteca muy optimizada, con algoritmos soportados incluidos, tiene apenas unos cientos de líneas.
Tener una forma de exportar los datos a un formato estándar sería cómodo, pero en nuestro caso de uso incorporar una biblioteca probablemente agregaría más problemas de los que resolvería.
Una aplicación faltante en la que he pensado a menudo es Excel para grafos.
Una herramienta para datos de un tamaño que quepa en RAM, como Excel para datos tabulares; es decir, una escala en la que necesitas una computadora, pero no un centro de datos. Implementaría muchos algoritmos y visualizaciones de forma “lo suficientemente buena” y se podría usar sin saber programar.
Como dice el texto, muchos problemas del mundo real son problemas de grafos; entonces, ¿por qué solo los programadores deberían tener herramientas para resolverlos?
Aun así, existen estructuras de datos y bibliotecas estándar que se ajustan suficientemente bien a la mayoría de los casos de uso, y si tienes requisitos especialmente difíciles, puedes crear una solución a medida.
El texto dice que los grafos suelen ser demasiado grandes, pero si se lo preguntas a personas que trabajan realmente con algoritmos de grafos, es fácil que hayan tenido esa experiencia. La mayoría de los programadores y usuarios probablemente solo lidian con grafos realmente pequeños.
No creo que un usuario común vea grafos en problemas aleatorios del mundo real. Lo que aprendí trabajando en una gran empresa es que, con suficiente esfuerzo, cualquier cosa puede convertirse en una hoja de cálculo de Excel.
https://strlen.com/treesheets/ se parece más a un Excel para datos en árbol.
Por ejemplo, dice que internet puede modelarse como un grafo; puede ser cierto, pero no queda claro qué se logra con eso. Internet puede representarse de muchas maneras, y no es evidente que representarla como grafo tenga implicaciones de ingeniería generalmente útiles.
Podría sonar igual de convincente decir que la representación ideal para obtener información útil es una función de codificación matricial de caja negra que mapea entradas arbitrarias a salidas consistentes, es decir, una red neuronal.
Para lugares como Google quizá sea una idea de miles de millones de dólares, pero internet en su conjunto no es un problema de grafos para mucha gente, y representarlo como grafo no resuelve gran cosa.
Es raro ver a alguien resolviendo problemas del mundo real en papel mediante grafos. Las tablas se usan todo el tiempo. Los grafos son comunes, pero los problemas de grafos no lo son.
En otros comentarios también se dijo que la visualización de grafos es difícil, pero una interfaz 3D te da mucho más espacio. Cuando empezó el boom de la VR pensé: “¿cuál será el Excel de la VR?”. La respuesta de Microsoft fue “una hoja de cálculo 2D flotando en un espacio 3D”. Me parece absurdo. Yo creo que son los grafos.
Si alguien quiere explorarlo conmigo, puede escribirme a mi nombre de usuario at gmail.com.
Los tipos de grafo existen desde hace bastante tiempo.
Erlang tiene https://www.erlang.org/doc/man/digraph.html y https://www.erlang.org/doc/man/digraph_utils, y si quieres hacer operaciones de teoría de conjuntos, también está https://www.erlang.org/doc/man/sofs.html.
Dice algo como: “Encontré otros dos lenguajes con tipos de grafo: Erlang y SWI-Prolog. No conozco bien ninguno de los dos, así que no puedo decir cuándo se agregaron, pero Erlang los tenía al menos antes de 2008. Contacté a alguien del comité del lenguaje central de Erlang, pero no recibí respuesta”.
La he usado para resolución de dependencias al ordenar tareas.