JSTreeGraph. HTML4+Javascript Tree Graph

image 
Imagen: Árbol en modo Horizontal.

 

image 
Imagen: Árbol en modo Vertical.

 

Llevo tiempo buscando algún componente que me permita representar en un entorno web, información jerárquica en cajitas. Hasta hoy no he dado con ninguna opción que cubra mis requerimientos; esto es, que no necesite plug-ins adicionales (flash, silverlight, etc.), que no haya que pagar licencias, y que permita mostrar la jerarquía tanto en vertical como en horizontal.

Estudiando detenidamente esta solución existente, me he de dado cuenta de que la lógica que hay detrás de estos árboles no parece muy complicada. Básicamente se trata de pintar una cajita por cada nodo, y unas líneas que las unan.

image 
Imagen: Componente Silverlight de YWorks

 

Así que, ya se sabe, a reinventar la rueda; me puse a programarlo. Y he llegado a la conclusión de que es más difícil de lo que parece. Aunque tampoco es para tanto 🙂 Eso sí, se aprende un montón.

Las dificultades con las que me he encontrado son:

Dibujar líneas sobre una capa en HTML: Con HTML5 y los lienzos, es fácil. Pero con HTML4, hay que aplicar algún truquillo.

El Layout, o dónde va cada cajita: Dar con un algoritmo, medianamente eficiente que permita conocer la posición de cada cajita, me ha traído de cabeza, pero ha salido… y creo que no ha quedado mal.

 

Dibujar líneas sobre una Capa HTML.

Investigando un poco por ahí, he dado con un par de artículos que comentaban el problema. Básicamente hay tres posibilidades para resolverlo:

image

Dibujar una capa de un pixel por un pixel en cada punto de la línea. El inconveniente evidente de esta técnica es que es muy ineficiente.

Usar una imagen con una línea en diagonal, hacia arriba o hacia abajo, y redimensionarla hasta ajustarla a los puntos necesarios. El inconveniente de esta técnica es que las líneas quedan muy pixeladas. La ventaja es que es muy eficiente.

Usar un div que tenga la longitud total de la línea. Esto sólo funciona para líneas rectas. La ventaja es que no se requieren imágenes adicionales, y es muy óptimo. Es la técnica que he utilizado, ya que, al menos en esta primera versión, sólo permitiré unir las cajitas con líneas rectas.

 

image

Lo que hacemos en esta función es crear una capa de lineWidth píxeles de grosor, con una longitud o determinada por la diferencia de posición de los puntos X e Y de los parámetros.

Como podemos ver, es bastante sencillo. Quizá lo más destacable es la manera en que se conoce si la línea es vertical u horizontal: si la coordenada X del punto de inicio de la línea es la misma que la coordenada X del punto final, entonces se trata de una línea vertical.

 

image

 

El Layout, o la disposición de las cajitas.

Para este tema, que ha costado bastante, he usado varias funciones recursivas, que establecen la posición de cada nodo.

El posicionamiento es distinto si pintamos el árbol en modo horizontal o vertical. Explicaré el posicionamiento Horizontal, pues parece más fácil de ver. Comprendido éste, el posicionamiento Vertical es exactamente igual, pero jugando con la posición superior de las cajitas, en lugar de la posición izquierda.

Como es necesario pasearse por la estructura del árbol, y calcular constantemente el nivel, la referencia al nodo padre, y al nodo que está a la izquierda en el mismo nivel (LeftNode), he creado una función que realiza todo este cálculo una única vez, al principio. Esta función es la función PrepareNode.

image

El LeftNode de un nodo es el que está inmediatamente a la izquierda en el mismo nivel. De este modo puedo navegar por el árbol de arriba a abajo, entre niveles, mediante las propiedades ParentNode y Nodes, y horizontalmente dentro de un mismo nivel mediante la propiedad LeftNode.

El parámetro rightLimits, es un array que contiene para cada nivel, el último nodo hijo analizado. Es un atajo para conocer cuál es LeftNode que está en una rama distinta de la que estoy analizando.

 

image

Habiendo pues, analizado cada nodo, y realizado este cálculo previo, pasmos a calcular las posiciones de cada cajita.

La función PerformLayout(node)

Esta es una función también recursiva. Su función es establecer las coordenadas de posición y el tamaño de cada una de las cajitas.

El parámetro de entrada de esta función es un nodo.

(1) Para conocer la posición de un nodo, lo primero que hemos de saber es si tiene hijos; si no los tiene (6) la posición izquierda será la del nodo inmediatamente a la izquierda, más un margen predefinido.

(2) Si el nodo tiene hijos, entra en juego la recursividad, pues volvemos a llamar a la función para cada uno de los hijos. Esta característica hace que se analicen en primer lugar los nodos finales de cada rama. Y esto está bien, pues normalmente la posición de un nodo irá condicionada por la posición de los elementos que tiene por debajo. Si el nodo no tiene hijos en cambio, el se pinta al lado del que tenga a la izquierda.

 

image

 

Una vez analizados los hijos, (3) utilizamos los resultados del paso anterior, localizamos el centro, y posicionamos el nodo en ese punto.

image

Puede ocurrir que ese centro se superponga con el nodo de la izquierda(4), con lo que hay que mover a la derecha(5) el nodo en cuestión, y todos sus descendientes.

image 
Imagen: El centro de los nodos hijos se superpone con el de la izquierda.

A continuación, (7) queda calcular la posición superior, el ancho y alto de cada cajita. La posición superior va en función del nivel, y el ancho y alto son valores constantes.

Por último, debemos indicar las coordenadas de los puntos de anclaje de los conectores(8). ¿Y qué es esto? Son los puntos donde está el inicio de la línea en caso de un nodo padre, y el fin de la línea en caso de un nodo hijo. Conociendo la izquierda, derecha, ancho y alto de cada nodo, este valor es muy fácil de calcular.

image
Imagen: Puntos de Anclaje.

Una vez calculadas las posiciones, ya sólo es cuestión de recorrerlos y pintar en cada posición una cajita. Y por último las líneas que conectan padres e hijos.

image 
Imagen: Flujo Completo.

Este mismo algoritmo es el que se utiliza para calcular las posiciones de los nodos en el modo Vertical.

 

El código fuente y los ejemplos están publicados en Codeplex: http://jstreegraph.codeplex.com

 

Referencias:

http://www.p01.org/releases/Drawing_lines_in_JavaScript/

http://www.yworks.com/products/yfilessilverlight/Demo.yFiles.Graph.Collapse.html

http://jsdraw2d.jsfiction.com/

http://en.wikipedia.org/wiki/Graph_drawing