Rastreando el tipo de dato desaparecido

En busca del tipo de dato faltante

• Un grafo es un conjunto de nodos conectados por flechas (aristas).
• Los nodos y las aristas pueden contener datos.
• En ingeniería de software, los grafos existen de muchas formas, como dependencias entre paquetes, enlaces de internet, el espacio de estados del software, bases de datos relacionales, listas enlazadas, árboles binarios y tablas hash.
• En la lógica de negocio, los grafos también se usan en referencias de citas, redes de transporte y redes sociales.
• Si trabajas mucho tiempo en desarrollo de software, es muy probable que te topes con grafos en todas partes.

Dudas sobre el uso de grafos

• Los grafos son útiles, pero usarlos en código real resulta pesado.
• La mayoría de los lenguajes principales no ofrecen soporte para grafos como tipo integrado, rara vez aparecen en las bibliotecas estándar y tampoco hay tantas bibliotecas de terceros realmente sólidas.
• Muchas veces hay que implementar el grafo por cuenta propia.
• Existe una brecha entre la frecuencia con la que los ingenieros de software podrían usar grafos y el soporte disponible en el ecosistema de programación.

Por qué no existe un tipo grafo

Hay demasiadas decisiones de diseño

• Existen muchos tipos de grafos: dirigidos y no dirigidos, simples y multigrafos, hipergrafos, ubergraphs, etc.
• Para cada tipo, hay que decidir si los nodos y las aristas tendrán ID, y qué datos se van a almacenar.
• Una biblioteca de grafos perfecta que cubra todas las posibilidades requeriría muchísimo tiempo.
• El rendimiento de los algoritmos de grafos es importante, y los casos especiales importan.
• Los algoritmos de grafos son difíciles de implementar correctamente.

Hay demasiadas decisiones de implementación

• Incluso si asumimos que solo se soporta un grafo dirigido simple, hay muchas maneras de representarlo internamente.
• Existen distintas formas de almacenamiento, como listas de aristas, listas de adyacencia, matrices de adyacencia y conjuntos de estructuras.
• Distintas operaciones sobre grafos tienen características de rendimiento diferentes según la representación elegida.
• La mejor representación interna cambia según qué tan disperso o denso sea el grafo.
• Implementar datos en nodos, datos en aristas y distintos tipos de nodos y aristas vuelve todo más complejo.

El rendimiento importa demasiado

• Muchos algoritmos de grafos resuelven problemas NP-completos o incluso más difíciles.
• Los grafos pueden convertirse en problemas muy grandes, y el rendimiento cambia mucho según la representación y los detalles de implementación del algoritmo.
• Se necesita mucho control sobre la representación de los datos y sobre los algoritmos.

Consenso general

• La variedad de tipos de grafos, representaciones, algoritmos, la sensibilidad al rendimiento y la ejecución de algoritmos costosos sobre grafos grandes explican por qué el soporte para grafos no está tan extendido.
• Esto explica por qué los lenguajes no suelen ofrecer soporte para grafos en la biblioteca estándar.
• También explica por qué los programadores evitan las bibliotecas de grafos de terceros.
• Como usar grafos es difícil, salvo en situaciones extremas no queremos pensar en términos de grafos.

Opinión de GN⁺

• Este artículo ofrece una visión sobre por qué los grafos no han logrado establecerse como un tipo de dato básico en los lenguajes de programación y sus bibliotecas.
• La teoría de grafos es un campo importante de la informática y tiene aplicaciones en algoritmos, análisis de redes, bases de datos y muchas otras áreas.
• Para usar grafos de manera efectiva, son clave la optimización del rendimiento y la elección de la estructura de datos adecuada.
• Algunas bibliotecas de terceros son NetworkX, Boost Graph Library y Graph-tool, y pueden usarse para resolver distintos problemas relacionados con grafos.
• Al usar grafos, es importante elegir el tipo de grafo y el algoritmo adecuados para las características del problema, ya que eso se relaciona directamente con el rendimiento del sistema.

[GN⁺]

Opinión de Hacker News

• Graphviz tiene su propia biblioteca de grafos, y esta no se usa en otros proyectos. Esta biblioteca tiene ventajas y desventajas.

  • Con base en esta experiencia, terminaron sufriendo su propio "síndrome del segundo sistema".
  • Decidieron que una biblioteca de grafos debía ser modular, segura en tipos y eficiente. Esto podría ser una variación de "bueno, rápido y barato: elige dos".
  • Modular significa que querían escribir un conjunto de bibliotecas de algoritmos de grafos que pudieran desarrollarse y compilarse de forma independiente.
  • Seguridad de tipos significa que querían detectar errores de programación en tiempo de compilación o, como muy tarde, en el enlazado. No querían errores en tiempo de ejecución.
  • Eficiencia significa que acceder a las propiedades de un grafo debía ser tan barato como acceder a un campo de una estructura en C.
  • Se puede debatir si estos objetivos valían la pena, pero era lo que ellos querían. Como en su laboratorio estaban algunos de los famosos creadores de C++, esperaban poder recibir ayuda y decidieron darle otra oportunidad a C++.
  • Gordon Woodhull, un exinterno y programador brillante, implementó este tipo de biblioteca de grafos en C++ con plantillas. Se publicó mediante sourceforge en https://www.dynagraph.org/.
  • Como no estaban seguros de que otras personas pudieran entender cómo funcionaba el código, hicieron una revisión con los famosos inventores de C++. Se dieron cuenta de que quizá ya habían pasado el borde del abismo de la complejidad.
  • No fue culpa de Gordon, y él siguió avanzando y también hizo con éxito trabajo de diseño dinámico de grafos en Microsoft OLE. Viéndolo en retrospectiva, quizá este fue su propio proyecto Xanadu.
  • Mientras estaban absortos en eso, aparecieron muchas otras cosas, como Gephi (Java) y NetworkX y NetworKit (Python).
  • John Ellson es un ingeniero de software muy talentoso que escribió partes de Graphviz y revivió el esfuerzo principal.

• Si programas en .NET, te recomiendo probar Arborescence, una biblioteca de grafos pequeña y no muy rica en funciones.

  • Creo que esta biblioteca ofrece una buena separación entre abstracciones, algoritmos y estructuras de datos.
  • El usuario puede usar aristas con sus propios ID o grafos implícitos que se despliegan sobre la marcha.
  • Se pueden usar tanto interfaces de adyacencia (vecinos salientes) como de incidencia (aristas salientes + cabeza).
  • La biblioteca no impone un tipo de arista, pero ofrece como utilidad una estructura básica de pares cola-cabeza.

• Los grafos no son una estructura de datos ni un tipo de dato, sino una abstracción.

  • En esencia, lo único necesario para definir un grafo es un conjunto de vértices y una función de vecindad.
  • Todo lo demás son restricciones caso por caso.
  • Si consideras los hipergrafos, un grafo no es más que un caso especial.
  • Si lo piensas desde la perspectiva de bases de datos, un grafo es un problema de optimización de consultas e indexación.

• Me han preguntado mucho por qué no existe un tipo de dato grafo integrado en los lenguajes de programación.

  • Ahora me da gusto poder señalar análisis más profundos como este.

• El obstáculo central es el siguiente:

  • Para problemas de grafos simples y pequeños, es bastante fácil programar una lista de adyacencia como vector de vectores.
  • Para problemas de grafos complejos y enormes, no hay manera de obtener rendimiento salvo personalizando una implementación de grafo adecuada para el problema.
  • No está claro qué tipo de soporte del lenguaje sería útil.

• Este texto responde en gran medida a la pregunta de por qué los algoritmos de grafos no tienen mejor soporte en los lenguajes de programación.

  • Si observas el soporte para grafos en general, aparecen preguntas más amplias, como por qué OGM no es tan popular como ORM, o por qué JSON se usa más que RDF.
  • Al final, por razones históricas y por la complejidad de los grafos, esto no escala bien entre desarrolladores.

• Las herramientas para dibujar grafos también son muy decepcionantes.

  • En grafos con más de 500 nodos, la salida se vuelve difícil de entender o demasiado compleja.
  • Faltan funciones que organicen automáticamente el grafo en una estructura jerárquica y ofrezcan una buena interfaz para explorarlo.

• Este texto es realmente genial.

  • Respecto a la observación clave de que "hay demasiadas opciones de implementación", en realidad no es así.
  • En la práctica, una biblioteca puede implementar todas las representaciones de grafos adecuadas.
  • Se pueden adaptar los algoritmos a la representación y convertir de una representación a otra.

• Electric Clojure usa Clojure mismo (s-expresiones) como sintaxis de autoría de grafos.

  • Un DSL de autoría de grafos debe expresar alcance, flujo de control y abstracción, lo cual en esencia es lo mismo que un lenguaje de programación.

• Hay otro tipo de dato útil, como una tabla (por ejemplo, una tabla dentro de una base de datos).

  • Habría avances en los lenguajes de programación si el compilador eligiera la implementación de la estructura de datos.
  • Usar estructuras abstractas (secuencias, mapas, conjuntos, tablas, grafos, etc.) y dejar que el compilador elija la implementación concreta con base en el perfil del programa.