Grafos creados con elementos SVG

Esta Herramienta de Web Tool Online sirve para crear grafos usando exclusivamente elementos SVG. Puede interactuar con el editor SVG traspasando el código SVG generado en la gráfica a ese editor y así poder realizar modificaciones en los elementos SVG de la gráfica. Otra posibilidad es traspasar el código al Parseador XML con objeto de verificar la corrección del SVG, pues en cualquier caso un SVG es un XML.

En la Figura puede ver un grafo generado con este editor. Realmente es un árbol, pues un grafo conexo sin ciclos es un árbol. En adelante hablaremos de grafos que incluye también a los árboles. Se observa que los nodos apuntan a sus padres. Para generarlo hemos utilizado la siguiente información para establecer los nodos:

[
  {"index": 0, "parent": -1},
  {"index": 1, "parent": 0},
  {"index": 2, "parent": 0},
  {"index": 3, "parent": 0},
  {"index": 4, "parent": 2},
  {"index": 5, "parent": 2},
  {"index": 6, "parent": 3},
  {"index": 7, "parent": 4}
]

Se trata de un Array donde cada objeto representa un nodo. Cada nodo tiene un indice (index) único. Serán cualesquiera números enteros no negativos, no necesariamente seguidos ni ordenados, pero en ningún caso repetidos. Cada nodo debe apuntar obligatoriamente a algún padre (parent). En esta cadena de enlaces tiene que haber uno o más nodos que sean los iniciales, llamado nodo raíz en caso de un árbol. Apuntarán al valor -1.

La disposición gráfica de los nodos y aristas se realiza de forma automática. Aunque es posible desplazar las líneas de las aristas usando alguna configuración para el nodo. Más abajo hablaremos de las configuraciones que particularizan la presentación.

Interfaz de la herramienta

La información de nodos del primer ejemplo del apartado anterior se inserta en el área de texto del inicio de la herramienta como puede ver en la Figura. Pero por defecto no se pintan las flechas. Para ello hay que seleccionar la configuración marcador final con el valor arrow.

Existe la posibilidad de exportar el grafo en un archivo de texto, generándose lo siguiente para el ejemplo visto antes. Se trata de una representación JSON de un objeto que contiene dos propiedades. Una de ellas es nodes que contiene la información de los nodos. La otra es config que contiene la configuración general del grafo. Se puede exportar sólo las configuraciones que difieren de los valores iniciales, ahorrándonos así tamaño de archivo:

{
  "nodes": [
    {"index": 0, "parent": -1},
    {"index": 1, "parent": 0},
    {"index": 2, "parent": 0},
    {"index": 3, "parent": 0},
    {"index": 4, "parent": 2},
    {"index": 5, "parent": 2},
    {"index": 6, "parent": 3},
    {"index": 7, "parent": 4}
  ],
  "config": {
    "markerEnd": "arrow"
  }
}

Posteriormente podemos cargar ese archivo de texto e importar el grafo guardado.

Configuración del grafo

La configuración general establece propiedades para todo el grafo. En la siguiente tabla se resumen las configuraciones posibles en este momento. Es posible que se modifique en el futuro. En la herramienta también hay una ayuda que mostrará esta tabla con los valores actuales.

El código SVG puede ser modificado traspasando su contenido al Editor SVG usando el botón . En el editor SVG podemos realizar modificaciones en la propia gráfica, como corregir ubicaciones de elementos, cambiar colores, etc.

También puede traspasarse el código al Parseador XML para verificar la corrección del mismo usando el botón .

A continuación se muestra una lista con las configuraciones de la gráfica:

Algunos detalles a tener en cuenta con la tabla anterior cuando pasemos la configuración en create({values, config}):

• Columna Valor inicial: No es necesario pasar los valores por defecto.
• Los valores como [1 .. 10] se refiere a un número entre esos dos valores. Con [Text] expresamos que puede incluirse cualquier texto, aunque se chequeará con una expresión regular.
• Columna Chequeo: Los valores se chequean con expresiones regulares o bien con los valores alternativos de la columna Valores.
• Si un valor no pasa el chequeo se utilizará el valor inicial.

Configuración del nodo

En la Figura puede observar un grafo. La información de nodos se expone en el código a continuación de este párrafo. Las propiedades index y parent son obligatorias. Otras propiedades como value son opcionales. También pueden aplicarse todas las propiedades de la configuración general que afecten a nodos, líneas y marcadores.

Los nodos se encierran en un círculo. Su valor es el del índice a no ser que se especifique la propiedad value. Observe que el nodo con índice 1 tiene establecido "value":"X".

[
  {"index":0, "parent":-1},
  {"index":1, "value":"X", "parent":[
          {"index":0, "value":"A"}
      ]
  },
  {"index":2, "parent":[
         {"index":0, "value":"B"},
         {"index":1, "value":"C"}
      ]
  },
  {"index":3, "parent":[
         {"index":1, "value":"D"},
         {"index":4, "value":"E"}
      ]
  },
  {"index":4, "parent":[
         {"index":1, "value":"F"},
         2
      ]
  }
]

La propiedad parent es un Array con una colección de nodos donde apunta el nodo. Puede simplificarse con un número entero, como por ejemplo {"index":0, "parent":-1}, de tal forma que apunta a un único nodo cuyo índice es ese número. Si hemos de apuntar a varios nodos usaremos un Array, pudiendo combinar objetos y números, como el parent del nodo 4 en el código anterior. Ese nodo 4 apunta al 1 con una arista cuyo texto es "F" y también apunta al 2 sin más especificaciones.

Supongamos ahora que el nodo 4 también debe apuntar al 0. Sólo basta agregar un cero a la definición del nodo 4 del código anterior:

"parent":[{"index":1, "value":"F"}, 2, 0]

El resultado se muestra en la Figura.

La arista que une el nodo 4 y el 0 cruza otros elementos. Existe la posibilidad de desplazar esa arista usando la propiedad lineOffset. Para ello sustituímos el 0 del código anterior por lo siguiente:

{"index":0, "lineOffset":1}

El resultado se muestra en la Figura.

La propiedad lineOffset es un String como H V donde H y V son números reales positivos o negativos para desplazar horizontal y verticalmente. Si sólo se pasa un número se aplicará al horizontal. Para sólo desplazar verticalmente pasaremos un cero en H. El desplazamiento es igual al radio de los círculos, valor que se calcula automáticamente.

Si seleccionamos la configuración para presentar marcadores finales en forma de flecha, vemos en la Figura que el nodo 4 apunta a los nodos 0, 1 y 2 (al nodo 1 le pusimos un valor "X"). Recuerde que esta configuración de flechas no es a nivel de nodo, sino a nivel general, aunque también puede configurarse cada flecha individualmente.

Podemos invertir el sentido de la flecha usando la propiedad markerReverse. Por defecto tiene el valor falso. Para invertir una flecha le daremos el valor verdadero:

{"index":0, "offset":"h1", "markerReverse":true}

El resultado se muestra en la Figura, donde se observa que la arista que une el 4 y el 0 tiene una flecha que apunta en la dirección inversa 0→4.

Por último veamos la propiedad lineTextOffset. Observamos que el texto "D", que es el valor de la arista que une el nodo 3 con el 1, quedó automáticamente ubicado en un lugar que lo hace poco legible. Podemos desplazarlo usando el String "-0.75 0.25". Con dos valores el primero es el desplazamiento vertical y el segundo el horizontal. Con sólo un valor se aplicará al horizontal. Por lo tanto desplazamos 0.75 a la izquierda y 0.25 abajo. En el nodo 3 agregamos esta propiedad:

{"index":3, "parent":[{"index":1, "value":"D", "lineTextOffset":"-0.75 0.25"}, {"index":4, "value":"E"}]}

El resultado se muestra en la Figura. El JSON final de este ejemplo está accesible como muestra en la herramienta. El código final para importar es el siguiente:

{"nodes":[{"index":0,"parent":-1},
{"index":1,"value":"X","parent":[{"index":0,"value":"A"}]},
{"index":2,"parent":[{"index":0,"value":"B"},{"index":1,"value":"C"}]},
{"index":3,"parent":[{"index":1,"value":"D","lineTextOffset":"-0.75 0.25"},
{"index":4,"value":"E"}]},{"index":4,"parent":[{"index":1,"value":"F"},2,{"index":0,"lineOffset":1,"markerReverse":true}]}],
"config":{"markerEnd":"arrow"}}

Grafos no conexos

Es posible representar un grafo no conexo compuesto de varios subgrafos. En la Figura se observan dos subgrafos no conectados. Para ello basta indicar los nodos raíces 0 y 3 que apuntan a un padre -1, como se observa en el código.

En cada nivel se ubican de forma automática los nodos, centrándolos en cada línea horizontal de nodos. En cualquier caso siempre existe la posibilidad de editar el grafo con el Editor SVG para modificar cualquier elemento.

[{"index":0, "parent":-1},
{"index":1, "parent":0},
{"index":2, "parent":0},
{"index":3, "parent":-1},
{"index":4, "parent":3},
{"index":5, "parent":3},
{"index":6, "parent":4},
{"index":7, "parent":4}]

Matriz de adyacencia para definir el grafo

G =
[[null,2,1,null,14],
[null,null,3,20,13],
[null,null,null,null,8],
[null,null,null,null,null],
[null,null,null,2,null]]

He realizado una mejora en los módulos de esta herramienta para que permita introducir la definición de un grafo con una matriz de adyacencia. Se trata de un array de dimensión n×n para un grafo de n nodos. Cuando G[i][j] === null entonces es que no hay arista en la dirección de los nodos i → j. Si es distinto de nulo ese será el valor de la arista. La Figura muestra un ejemplo de esa matriz como un array de dimensión 5 × 5 que define un grafo G.

El anterior es un grafo dirigido porque o no hay arista entre dos nodos o, si la hay va en una sola dirección, es decir G[i][j] === null y G[j][i] !== null o viceversa. En el ejemplo de la Figura puede ver que G[0][4]=14 mientras que G[4][0]=null, por lo que la dirección de la arista será 0→4. Si G[i][j] === G[j][i] para todos los nodos entonces el grafo es no dirigido. Esta forma de estructurar el grafo es más sencilla, pero no permite reubicar aristas. En la primera de las siguientes imágenes se presenta la obtenida con la matriz de adyacencia:

La Figura expone como se representa el grafo con la definición completa, mucho más clara, pues se han reubicado nodos y aristas para que no crucen por encima de otros elementos.

Ambos son el mismo grafo, pero en el primero la arista 1→4 (con valor 13) cruza por el nodo 2. Por lo tanto la matriz de adyacencia no siempre consigue una visualización óptima del grafo. Mientras que con la definición podemos manipular hasta cierto punto la representación gráfica. El grafo de la segunda imagen usa la siguiente definición, notándose el uso de propiedades como lineOffset o lineTextOffset para ese cometido:

[{"index":0,"parent":-1},
{"index":1,"parent":[{"index":0,"value":2,"markerStart":"arrow","lineTextOffset":-0.8}]},
{"index":2,"parent":[{"index":0,"value":1,"markerStart":"arrow","lineTextOffset":0.8},{"index":1,"value":3,"markerStart":"arrow","lineTextOffset":"0 0.8"}]},
{"index":3,"parent":[{"index":1,"value":20,"markerStart":"arrow","lineTextOffset":-0.8},{"index":4,"value":2,"markerStart":"arrow","lineTextOffset":"0 0.8"}]},
{"index":4,"parent":[{"index":1,"value":13,"markerStart":"arrow","lineTextOffset":"0 0.8"},{"index":2,"value":8,"markerStart":"arrow","lineTextOffset":0.8},{"index":0,"value":14,"markerStart":"arrow","lineOffset":"1","lineTextOffset":0.8}]}
]

En la Figura puede ver como introducimos la matriz de adyacencia del grafo anterior en la herramienta. Cuando ejecutemos para crear el grafo, el contenido de texto de la matriz de adyacencia se sustituirá por la definición generada del grafo. Hemos incorporado un par de mejoras que sólo se tienen en cuenta en el modo matriz de adyacencia: Enlaces arriba y Flechas.

La aplicación detecta si es un array válido para ser una matriz de adyacencia, en cuyo caso se aplicarán esas dos propiedades. La que dice "Flechas" sirve para agregar flechas al grafo, que siempre serán en la dirección i→j de la matriz. Esto se consigue agregando la propiedad "markerStart":"arrow" a cada enlace parent.

Veamos ahora la otra propiedad Enlaces arriba. La aplicación ubica automáticamente los nodos usando los niveles de cada rama partiendo del orden ascendente de los índices de los nodos. Así se espera que un nodo n tenga un enlace (parent) a alguno anterior, n-1 por ejemplo, de tal forma que esto nos permite estructurar los niveles.

Si activamos Enlaces arriba el enlace se ubicará en el nodo n-1 apuntando al nodo n, lo que produce una ubicación distinta de los nodos, como se observa en la Figura. Es el mismo grafo que vimos antes, pero esta vista no parece mejorar la presentación, aunque para algún caso particular podría ser necesario representarlo en esa forma.

Una mejora adicional es la que se observa en la Figura, agregando una nueva entrada para exportar la matriz de adyacencia con cualquier grafo generado.