Los grafos no son estructuras de datos

 Enlace al artículo original

En la vida de un programador, te toca lidiar con miles de estructuras. En otras palabras, siempre estás decidiendo cómo organizar tus datos. Hay muchas opciones, desde variables simples hasta matrices complejas de estructuras definidas a medida. Uno de esos enfoques comunes son los grafos.

Pero los grafos no son estructuras de datos: son estructuras matemáticas.

Por supuesto, puedes aplicarlos como estructuras de datos; muchísimas piezas de software dependen de ellos. Incluso si no te das cuenta, estás tratando con grafos todo el tiempo. Por ejemplo, una lista enlazada es solo un caso especial de un grafo dirigido.

Pero cuando consideramos a los grafos como construcciones matemáticas en lugar de meras estructuras de datos, se convierten en una herramienta mucho más poderosa. Aquí presento dos aplicaciones más de los grafos en el desarrollo de software: como diseño de procesamiento y como representación de la base de código.

Nota: Aunque este es un post de programación general, utilizaré Go para los ejemplos de código.

---

Procesamiento mediante grafos

Abordemos este problema: Tenemos que procesar la temperatura mínima diaria de una ciudad (X), calculando $x^3$ y luego la raíz cuadrada del resultado o su logaritmo natural opuesto. Después, almacenamos el resultado en un mapa, usando el resultado como clave y su certificado como valor.

Pero debemos tener cuidado con:

• Los números son enteros de 8 bits con signo (-128 a 127).

• Manejo de grupos de números reales.

• Si $x<0$, calcular $\sqrt{x^3}$ dará un error matemático. En tales casos, el programa usará $\ln (-x)$.

• Si $x^3$ desborda el valor máximo de un int8, se buscará $\ln (-x^3)$.

• Al buscar el logaritmo natural ($\ln$), pediremos a un servicio remoto una firma de error.

¿Es un problema realista? Por supuesto que no. Pero la idea abstracta está presente. Pensemos en un enfoque tradicional:

func process(input []int8, certs map[float64]string) {
  for i := 0; i < len(input); i++ {
    var result float64
    var needCert bool
    var cert = "no_need"

    x := input[i]
    switch {
      case x > 0 && x*x*x < 0: // probando escenarios de desbordamiento (overflow)
        x = x * x * x
        // queremos el mismo comportamiento que si x < 0
        fallthrough 
      case x < 0:
        needCert = true
        result = math.Log(float64(-x))
      default:
        x = x * x * x
        result = math.Sqrt(float64(x))
    }

    if needCert {
      cert = askCert(x)
    }

    certs[result] = cert
  }
}

Aquí tenemos problemas: estamos procesando las entradas una por una, intentando hacer todo en el mismo lugar, procesando en lote (batch) y esperando la respuesta de askCert(x) antes de procesar otra entrada. En resumen, no estamos siendo eficientes ni aplicando buenas prácticas de código limpio (clean code).

Para limpiar este desastre, podemos tomar un enfoque diferente: grafos. Asumamos que tratamos los procesos como vértices y las comunicaciones como aristas. Cada proceso realizará una de nuestras operaciones atómicas: $x^3$, $x<0$, $\sqrt{x}$ y $\ln (x)$, y la comunicación se hará a través de canales (channels).

Para implementar esto, creemos cada función asumiendo que se ejecutará indefinidamente (como nodos). Luego, les pasamos los canales de entrada y salida (aristas). El enfoque más claro para declarar aristas es definir primero una matriz de adyacencia, luego especificar los tipos de canales correspondientes y, finalmente, asignar pesos a las aristas (por ejemplo, usando tamaños de búfer en Go). Por supuesto, hacerlo así no es estrictamente necesario; en el ejemplo de la implementación completa de abajo declaro cada canal manualmente, esperando que sea más claro en sus intenciones:

Implementación de código en Playground

Pero, ¿por qué querríamos crear este lío? Por dos factores principales: control y rendimiento. Nuestro ejemplo es solo una base para empezar a pensar. Los procesos son tan flexibles como podamos imaginar. Uno de los escenarios más importantes para aplicar esto es cuando tienes muchas operaciones de E/S (I/O); puedes usar un proceso de vértice para iniciar llamadas en segundo plano a tu operación de E/S y enviar su respuesta a algún otro vértice donde sepas que se usará. Eso reduciría el tiempo de espera sin comprometer el recurso remoto, evitando una sobrecarga de llamadas (una abstracción de un sistema de inventario "justo a tiempo").

Este enfoque fue aplicado para mejorar el procesamiento de datos de diversos clientes, logrando una mejora de 16 veces en la eficiencia del tiempo combinado y la utilización de recursos.

 

---

El código como grafo

Otro beneficio es que ayuda en el estudio y mantenimiento del software. Puedes aplicar la teoría de grafos para entender tu base de código e incluso predecir su comportamiento antes de escribir una sola línea de código.

Estudiar el código por sí mismo es algo que, como programadores, no solemos hacer. Pero deberíamos. Este tema ha sido estudiado por Germán Cárdenas en su publicación "Evaluating the Graph-based Visualization Technique: A Controlled Experiment".

La aplicación de grafos para estudiar bases de código no es una idea nueva. Allá por el 2002, Eva Van Emden y Leon Moonen publicaron "Java Quality Assurance by Detecting Code Smells". En esa investigación, representaron "entidades" del software utilizando grafos: paquetes, clases, métodos, etc.

Tener grafos en una etapa de diseño es relativamente común, pero ¿cuánto tiempo invertimos realmente en estudiar y mantener estos grafos? En mi experiencia, casi nadie actualiza un grafo que se creó en las primeras etapas del proyecto. Además, el grafo suele servir meramente como una referencia visual más que como una herramienta de desarrollo activa.

Imagina un grafo totalmente actualizado que represente tu API REST, abarcando funciones, llamadas y modelos. Podríamos darnos cuenta rápidamente del esfuerzo que requiere un cambio. Puedes aplicar una Búsqueda en Profundidad (DFS) o una Búsqueda en Anchura (BFS) para descubrir cuántas partes de tu código se verán afectadas. Luego, toma tu Árbol de Dominadores para evaluar los riesgos de tu plan. Y, por supuesto, si el grafo se desconecta (tu conectividad es mayor a 1), notarás rápidamente que tienes código muerto con el que lidiar.

Asignemos también pesos a las aristas para representar el tiempo de ejecución esperado de las funciones. Esto nos permite estimar el tiempo de respuesta de un endpoint utilizando el algoritmo de Dijkstra. Seríamos capaces de calcular cuántos recursos necesitamos para atender el número esperado de usuarios concurrentes y qué partes de nuestro software requieren más optimizaciones.

Este tema es tan extenso como la propia teoría de grafos. Hay una gran cantidad de estudios y documentación disponible. Depende de ti, como desarrollador, adoptar este conocimiento y aplicarlo a tu trabajo diario.

---

Conclusión

Como desarrolladores de software, sabemos que hay demasiadas herramientas disponibles. Casi cada año se lanza al mercado una nueva tecnología o actualización con características asombrosas, y muchos esperan que nos mantengamos al día y las adoptemos lo más rápido posible para estar a la vanguardia de la industria tecnológica. Como consecuencia, nos estamos alejando cada vez más de los principios fundamentales.

Discutir periódicamente los fundamentos de las ciencias de la computación nos ayuda a redescubrir herramientas valiosas, trucos y mejores prácticas. Nos recuerda que debemos reflexionar continuamente sobre nuestras implementaciones y estudiar su comportamiento en lugar de simplemente reaplicar la misma fórmula una y otra vez.

Esta vez, se han puesto los grafos a debate. Sus ventajas son enormes. Deberíamos aprovechar todo su potencial en lugar de usarlos simplemente para estructurar datos. Recuerda:

Los grafos no son estructuras de datos.