Introducción mejoras en la aplicación

En 2020 implementé la aplicación Web Tools online: Grafos con SVG para crear grafos en SVG. Ese tema contiene la descripción general de la aplicación y su contenido sigue siendo vigente, por lo que sería recomendable una lectura antes para ver como se fundamenta la aplicación.

El motivo de crear esa aplicación en 2020 fue a raíz de estudiar el algoritmo de Dijkstra sobre caminos mínimos y los algoritmos de Kruskal y Prim sobre árboles de recubrimiento mínimo, necesitando una aplicación para representar visualmente esos grafos.

Quería seguir con este apasionante y complejo tema de los grafos, estudiando problemas como el de los caminos y ciclos Hamiltonianos, búsquedas en profundidad o anchura, coloreado de grafos, tipos de subgrafos, cliques, operaciones en grafos, isomorfirmos de grafos y subgrafos, entre otros problemas. Para implementar algoritmos para resolverlos y otros futuros en esa aplicación necesitaba llevar a cabo algunas mejoras que explicaremos en este tema:

• Botones de edición para agregar, eliminar y contraer nodos y aristas, permitiendo selección visual de elementos para su modificación, pudiendo moverlos con el ratón para reubicarlos. Se incluyen también acciones para deshacer y rehacer cambios.
• Agregar aristas con curvas Bezier cuadráticas o cúbicas, pues antes sólo podíamos incorporar líneas rectas. Exponemos como construir la flecha de una arista recta y de una arista curva.
• Ajustes visuales para modificar la presentación gráfica, que son modificaciones en el grafo que no afectan a su estructura, es decir, que no modifican la matriz de adyacencia, afectando sólo a su presentación gráfica en el SVG. Podemos actuar con las siguientes:
  • Ajustes con estilo CSS
  • Cambiar tamaño del SVG
  • Mover elementos
  • Aplicar zoom
  • Aplicar relleno
  • Esparcir elementos
  • Ajustar a rejilla
  • Ajustar a círculo

Otras mejoras implementadas que, previsiblemente, detallaré en temas posteriores, son las siguientes:

• Mejora de la exportación de grafos, pues antes sólo teníamos JSON, SVG y matriz de adyacencia y ahora incorporamos matriz incidencia, lista de adyacencia, lista de aristas, matriz de distancias, código para ejecutar en Wolfram Cloud y también código Wolfram Alpha. Y también importar grafos desde lista de aristas, matriz de incidencia o lista de adyacencia.
• Colección de muestras de grafos para importar en la aplicación.
• Asistente de generación de nuevos grafos y operaciones sobre grafos, con generación de código a ejecutar en Wolfram Cloud.
• Sección para ejecutar algoritmos sobre grafos, teniendo 47 de ellos implementados, algunos de los cuales ya expusimos más arriba. También se genera el código para Wolfram Cloud si estuviera disponible.

Edición de vértices y aristas

Hemos de indicar que los términos nodos y vértices son equivalentes, así como líneas y aristas. En lo que sigue podríamos usarlos indistintamente. La barra de botones superior afecta al área de texto donde introducimos un grafo en texto JSON o con una matriz de adyacencia, similar a la que teníamos en la aplicación antes de estas mejoras y que explicaremos en otro apartado. Por ahora vamos a centrarnos en la otra barra de botones que está junto al grafo en SVG.

Tal y como se observa en la Figura, ahora podemos seleccionar un nodo o una arista, bien picándolo con el ratón o usando el desplegable Seleccionar elemento. El color de selección, naranja por defecto, puede ser modificado con el botón con icono .

Antes de estas mejoras sólo podíamos modificar nodos y aristas modificándolo en el texto del JSON de la parte superior, lo cuál era muy engorroso y proclive a errores.

Ahora, una vez seleccionado el nodo con valor "X", que se corresponde con el índice 1 del array de nodos, podemos ver en el panel "Nodos" de la parte izquierda los valores de configuración para ese nodo concreto, valores que podemos cambiar y se actualizará el grafo. Si no hay ningún elemento seleccionado, los valores de configuración se aplican a todos los elementos.

En la Figura podemos ver los botones para agregar nodo , para agregar o editar una arista , para eliminar un nodo o una arista y para contraer nodos o aristas .

En la Figura puede ver que hemos creado dos nodos con el botón en un grafo nuevo, los hemos reubicado en alguna posición, seleccionamos el nodo 1 y vamos a editar la arista con el botón .

Elegimos el tipo de línea recta (rect) y finalmente obtenemos el grafo no dirigido de la Figura.

Por defecto un nuevo grafo se configura como no dirigido. Si lo necesitamos dirigido hemos de establecer la configuración por defecto para nuevas aristas, tal como se observa en la Figura. Una línea o arista tiene un marcador a cada lado, que usualmente es una flecha (arrow), aunque también puede ser un círculo pequeño (circle).

Ponemos como marcador final flecha y el grafo se convierte en dirigido, como se ve en la Figura.

Si agregamos otro nodo, ahora podemos seleccionar que tipo de marcador poner y en que lado de la línea, como vemos en la Figura.

La operación contraer nodos se refiere a seleccionar dos nodos, como se observa en la Figura donde se van a contraer los nodos 4 y 6. Entre esos nodos puede o no haber una arista. Se trata de fusionar ambos nodos en un único nodo.

Si hay una arista entre los dos nodos a contraer, esa arista pasa a convertirse en un auto-bucle (o self-loop), como se observa en la Figura. Se mantiene el índice 4 del primer nodo, aunque esto también es configurable.

Construyendo arista recta y posicionando su flecha

La Figura es un ejemplo que puede encontrar en las muestras de la aplicación, aplicando zoom 150%. Le ponemos fondo transparente a los círculos para observar que todas las líneas arrancan y terminan en el centro de cada círculo.Tiene dos aristas rectas (rect), una con curva cuadrática (quadratic) y dos con curva cúbica (cubic). Empecemos por ver como construimos una arista recta y como posicionamos el triángulo en forma de flecha, algo que se contemplaba ya en la versión anterior de la aplicación pero no había explicado.

Desde el nodo 2 etiquetado con "c" se originan tres aristas, una recta al nodo "d" (índice 3) y dos cúbicas, que son un auto-bucle a sí mismo y otra al nodo "b" (índice 1). Esto lo podemos ver en el JSON, omitiendo con puntos suspensivos el resto de propieades que no vienen al caso:

{"index":2,
    "value":"c",
    "parent":[
        {"index":3, "lineType":"rect", ...},
        {"index":1, "lineType":"cubic", ...},
        {"index":2, "lineType":"cubic", ...}
    ],
    ...
},

Veamos ahora como se configura la línea recta y su flecha. El código de los elementos SVG relacionados con los dos nodos etiquetados "c" y "d", que tienen índices de nodo 2 y 3 respectivamente, con la etiqueta "rect" que uno esos nodos, con la flecha apuntando al nodo "d". Observe los atributos data-node y data-line que indican a que parte del grafo pertenecen los elementos, algo que podemos activar al exportar el SVG marcando la opción identificar elementos SVG.

<!-- nodo "c" índice 2 --->
<circle cx="44.2" cy="43.8" r="9.38"
    stroke-width="0.4"
    stroke="currentcolor"
    fill="transparent"
    data-node="2"></circle>
<!-- nodo "d" índice 3 -->
<circle cx="27.43" cy="107.7" r="9.38"
    stroke-width="0.4"
    stroke="currentcolor"
    fill="transparent"
    data-node="3"></circle>
<!-- línea que une "c" y "d" -->
<path d="M44.2 43.8 L27.43 107.7"
    stroke-width="0.4"
    stroke="currentcolor"
    fill="none"
    data-line="2,3"></path>
<!-- polígono en forma de flecha en "d" -->
<polygon points="29.81 98.63 33.78 92.62 29.3 91.45"
    fill="currentcolor"
    data-line="2,3"></polygon>

Usamos un elemento SVG de tipo PATH para la línea y otro POLYGON para la flecha, con un CIRCLE para los círculos de los nodos. El nodo "c" tiene un círculo con centro en (x₁, y₁) = (44.2, 43.8) y tiene un radio r = 9.38. El nodo "d" está en (x₂, y₂) = (27.43, 107.7) con el mismo radio. El elemento PATH tien el atributo d="M44.2 43.8 L27.43 107.7" que viene a recopilar esos puntos y que podemos representar con d = Mx₂ y₂ Lx₁ y₁, de tal forma que SVG mueve ("M") el cursor al punto (x₁, y₁) nodo "c" y traza una línea recta ("L") hasta el punto final (x₂, y₂) nodo "d". De forma abreviada el código JavaScript para configurar esto es el siguiente:

// Construir elemento PATH
// (x1, y1), (x2, y2) son los centros de dos círculos
// El atributo "d" de la recta PATH es el siguiente
d = `M${x1} ${y1} L${x2} ${y2}`

El siguiente paso es construir la flecha con el elemento POLYGON:

// Construir elemento POLYGON con flecha en círculo centrado en (x2, y2)
// El ángulo de inclinación de la recta es el siguiente
angle = Math.atan2(y2-y1, x2-x1);

// Obtenemos el punto (xf, yf) de intersección entre la recta
// y la circunferencia centrada en (x2, y2)
xf = x2 - r * Math.cos(angle))
yf = y2 - r * Math.sin(angle))

// Obtenemos los otros dos puntos (xu, yu), (xv, yv) para configurar
// el POLYGON, un triángulo que forma la flecha que se ubican en el punto
// de intersección (xf, yf) con la inclinación de la recta PATH
a = 6 * ratio * markerSize * factorZoom;
b = 2 * a / factorZoom;
angle1 = angle + Math.PI * 1/b;
angle2 = angle +  Math.PI * (b-1)/b;
signMarker = posMarker==="end" ? -1 : 1;
xu = xf + signMarker * a * Math.cos(angle1);
yu = yf + signMarker * a * Math.sin(angle1);
xv = xf - signMarker * a * Math.cos(angle2);
yv = yf - signMarker * a * Math.sin(angle2);

// El atributo points del elemento POLYGON es entonces
points = `${xf} ${yf} ${xu} ${yu} ${xv} ${yv}`

Realizamos manualmente los cálculos anteriores:

Se observa en lo resaltado en amarillo que obtenemos los valores para el atributo points="29.81 98.63 33.78 92.62 29.3 91.45" del POLYGON que conforma la flecha. En la Figura puede ver esa flecha insertada en un SVG incluyendo los elementos del grafo relacionados, cuyo código puede obtener en formato texto y visualizar en la aplicación Editor SVG.

El punto inferior de ese triángulo es (x_f, y_f) = (29.81, 98.63), el de la derecha (x_u, y_u) = (33.78, 92.62) y el de la izquierda (x_v, y_v) = (29.30, 91.45), recordando que estos son valores de ViewBox.

Teniendo el ángulo φ y el punto (x₂, y₂) obtenemos el punto de intersección (x_f, y_f) entre la recta y el círculo, siendo x_f = x₂ - r cos(φ), y_f = y₂ - r sin(φ).

Puede parecer obvio a partir de las razones trigonométricas básicas, donde el eje cartesiano es con los valores positivos de X a la derecha desde el centro de ejes y los positivos de Y hacia arriba desde el centro, y con los ángulos positivos en sentido antihorario del reloj, es decir con el sentido que gira hacia el eje Y positivo, con lo que las ecuaciones deberían ser x_f = x₂ + r cos(φ), y_f = y₂ + r sin(φ) con operaciones "+" en lugar de "-". Pero hemos de recordar que las coordenadas en el SVG (así como en el elemento canvas y en general en HTML y CSS) son con el eje Y invertido y con los ángulos positivos en sentido horario, precisamente por eso, porque el eje Y está invertido. Esto se hace así para corresponder con el flujo de presentación de los contenidos visuales que siempre es a la derecha y hacia abajo.

Así que podemos usar esas fórmulas pero haciendo corresponder el ángulo con sentido horario a sentido antihorario, para lo cual hemos de sumar φ+π. Y sabiendo que cos(φ+π) = -cos(φ) y que sin(φ+π) = -sin(φ), llegamos entonces a las primeras ecuaciones con los signos negativos.

En a = 6 * ratio * markerSize * factorZoom la variable ratio es la relación entre el ancho del ViewBox y el ancho del SVG, que denominamos y calculamos en las fórmulas como r_w = w_v / w = 152.26 / 380.65 = 0.4 La variable markerSize es el tamaño del marcador o flecha, que por defecto tiene valor 2, aunque es configurable en la aplicación. El factor zoom es 1.5 pues ya hemos dicho que le habíamos aplicado un zoom de 150%. Obtenemos las variables a, b que nos servirán para configurar el tamaño del triángulo.

Los ángulos φ₁ y φ₂ nos sirven para obtener los otros dos puntos (x_u, y_u) y (x_v, y_v) respectivamente. El signo del marcador signMarker es en este caso -1, pues la flecha está al final de la relación nodo 2 a nodo 3. En las fórmulas ponemos s = -1.

Construyendo arista con curva Bezier y posicionando su flecha

Para incorporar las aristas curvas a un grafo he tenido que resolver la forma de posicionar la flecha, pues la técnica que vimos antes para las rectas ya no nos sirve. Ahora tenemos que buscar el punto de intersección entre el círculo y una curva de Bezier. En el tema Curvas Bezier en SVG hablamos sobre ellas en relación con los polígonos regulares o para aproximar arcos de circunferencia.

En la Figura hay un SVG con código en formato de texto que puede visualizar en Editor SVG. El código se muestra también a continuación, donde puede ver el detalle de los nodos "b" y "d" del mismo grafo muestra que comentamos en el apartado anterior. El nodo "b" tiene índice 1 y el "d" tiene índice 3. La arista es un elemento PATH con una curva Bezier cuadrática. La flecha es un POLYGON apuntando al nodo "b", siendo nuestro objetivo posicionarla en ese punto con la pendiente que tiene la curva en ese punto.

<svg viewBox="10 90 105 50" width="300" height="150" xmlns="http://www.w3.org/2000/svg">
    <!-- Línea que une "d" con "b" -->
    <path d="M27.43 107.7 Q61.8 153.93 96.17 105.98"
        stroke-width="0.4"
        stroke="currentcolor"
        fill="none"
        data-line="3,1"></path>
    <!-- Nodo "b" índice 1 -->
    <circle cx="96.17" cy="105.98" r="9.38"
        stroke-width="0.4"
        stroke="currentcolor"
        fill="transparent"
        data-node="1"></circle>
    <!-- Nodo "d" índice 3 -->
    <circle cx="27.43" cy="107.7" r="9.38"
        stroke-width="0.4"
        stroke="currentcolor"
        fill="transparent"
        data-node="3"></circle>
    <!-- Flecha en el nodo "b" -->
    <polygon points="90.4 113.37 84.2 117.04 87.71 120.05"
        fill="currentcolor"
        data-line="3,1"></polygon>
</svg>

El elemento PATH es la curva que une "d" con "b" y tiene el atributo d="M27.43 107.7 Q61.8 153.93 96.17 105.98". Se trata de mover ("M") al punto (c, d) = (27.43, 107.7) que es el centro del nodo "d". Y luego trazar una curva Bezier cuadrática ("Q") hasta el punto (a, b) = (96.17, 105.98) centro de "b", con el punto de control de la cuadrática ubicado en (g, h) = (61.8, 153.93)

Para posicionar la flecha usamos el algoritmo getIntersection() para obtener el punto de intersección entre el círculo y la curva cuadrática o cúbica, donde omitimos parte del código relacionado con la curva cúbica y con el argumento adjust para abreviar, obviando también los argumentos xc, yc pues son el segundo punto de control de la cúbica. Tenemos los puntos (x1, y1) del nodo "b" que se corresponde con (a, b) = (96.17, 105.98) que usaremos en este texto, (x2, y2) del nodo "b" que se corresponde con (c, d) = (27.43, 107.7) y (xb, yb) como punto de control de la curva cuadrática, que se corresponde con (g, h) = (61.8, 153.93). El argumento precision sirve para controlar un bucle en el algoritmo, como veremos más abajo.

function getIntersection({x1=0, y1=0, x2=0, y2=0, xb=0, yb=0, 
    xc=0, yc=0, r=0, curve="quadratic", precision=6, adjust=false}){
    let dev = {error: "", x: 0, y: 0, angle: 0, xm: 0, ym: 0, xr: -Infinity, yr: -Infinity};
    try {
        let [a, b, c, d, e] = [0, 0, 0, 0, 0];
        if (curve==="quadratic") {
            a = x1**2 + 2*x1*x2 - 4*x1*xb + x2**2 - 4*x2*xb + 4 * xb**2 + y1**2 + 2*y1*y2 - 4*y1*yb + y2**2 - 4*y2*yb + 4 * yb**2;
            b = - 4 * x1**2 - 4*x1*x2 + 12*x1*xb + 4*x2*xb - 8 * xb**2 +- 4 * y1**2 - 4*y1*y2 + 12*y1*yb + 4*y2*yb - 8 * yb**2;
            c = 4 * x1**2 - 8*x1*xb + 4 * xb**2 + 4 * y1**2 - 8*y1*yb + 4 * yb**2;
        } else {
            ....
        }
        let ts = [0.025, 0.05, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.95, 0.975];
        let diferPrec = 10**(-precision);
        let maxLoop = 15;
        for (let t0 of ts){
            let difer = 1;
            let iter = 0;
            let t = t0;
            while (iter++, iter<maxLoop && difer>diferPrec) {
                let f, g;
                if (curve==="quadratic") {
                    f = t**2 * (a * t**2 + b * t + c) - r**2;
                    g = 4 * a * t**3 + 3 * b * t**2 + 2 * c * t;
                } else {
                    ...
                }
                let tPrev = t;
                t = t - f/g;
                difer = Math.abs(t-tPrev);
            }
            if (t>0 && t<1 && difer<=diferPrec){
                if (curve==="quadratic") {
                    dev.x = (1-t)**2 * x1 + 2 * t * (1-t) * xb + t**2 * x2;
                    dev.y = (1-t)**2 * y1 + 2 * t * (1-t) * yb + t**2 * y2;
                    let dx = (2 * x1 - 4 * xb + 2 * x2) * t - 2 * x1 + 2 * xb;
                    let dy = (2 * y1 - 4 * yb + 2 * y2) * t - 2 * y1 + 2 * yb;
                    dev.angle = Math.atan(dy/dx);
                    t = 0.5;
                    dev.xm = (1-t)**2 * x1 + 2 * t * (1-t) * xb + t**2 * x2;
                    dev.ym = (1-t)**2 * y1 + 2 * t * (1-t) * yb + t**2 * y2;
                } else {
                    ...
                }
                ...
                break;
            }
        }
    } catch(e){dev.error = `#Error getIntersection(): ${clean(e.message)}`}
    return dev;
}

Para entender ese algoritmo veamos como encontrar la intersección entre curva paramétrica e implícita. La curva implícita será la de una circunferencia con centro en (a, b) y radio r:

La curva paramétrica es la cuadrática de Bezier desde el punto (a,b) hasta (c,d) con punto de control (g,h), con el parámetro t ∈ [0, 1]:

Podemos obtener el punto de intersección sustituyendo las paramétricas en la ímplicita. Si lo hacemos obtenemos esto:

Si pudiéramos despejar t podemos obtener x(t), y(t) de las paramétricas [2] y obtener el punto o puntos de intersección. Pero la ecuación anterior es cuadrática, es decir tiene potencia mayor t⁴ que puede dificultar su resolución. Y peor es con las cúbicas que tendríamos un polinomio en t⁶.

Para encontrar ese punto de intersección es mejor usar un método indirecto, como el de iteración de Newton que dice que si una función es derivable definida en un intervalo, con una variable y dada de forma implícita f(x) = 0, podemos encontrar el valor de x que hace cero la función por aproximaciones sucesivas en un intervalo x ∈ [x₀, x_m], intervalo donde hemos de encontrar el cero de la función. Si x_n no es un cero, un mejor intento se consigue con:

La diferencia entre dos valores sucesivos x_n+1 - x_n irá tendiendo a cero en caso de convergencia, acercándose progresivamente a la raíz buscada. No se necesitan muchas iteraciones para lograrlo, de hecho en el algoritmo he puesto un máximo de maxLoop = 15, pero con menos se consigue. Para implementarlo vamos a simplificar [3] de esta forma:

Donde los valores A, B, C son los siguientes en función de (a,b), (c,d), (g,h) que recordemos que son los puntos de los centros de los nodos "d" y "b" y el punto de control de la curva Bezier respectivamente:

Estos valores A, B, C se corresponden con a, b, c en el algoritmo. Vamos resolverlos manualmente usando los valores del ejemplo:

La función y su derivada son las siguientes:

El intervalo es t ∈ [0, 1]. Empecemos tomando el primer valor t₀ = 0.5 al centro del intervalo. Estos valores los podemos calcular fácilmente usando Wolfram Alpha:

El primer punto t₁ es:

La primera diferencia es la siguiente, observando en amarillo el número de decimales significativos, de tal forma que convergerá a cero. Cuando lleguemos al número de 4 decimales significativos (más abajo explicaremos el motivo de este valor), habremos finalizado, teniendo un valor muy cercano al buscado.

Usemos ahora el punto t₁ = 0.14881185

El segundo punto t₂ es:

La segunda diferencia es la siguiente, con 2 decimales significativos:

Usemos ahora el punto t₂ = 0.09485123

El tercer punto t₃ es:

La tercera diferencia tiene también 2 decimales significativos:

Usemos ahora el punto t₃ = 0.08451511

El cuarto punto t₄ es:

La cuarta diferencia tiene 3 decimales significativos:

Usemos ahora el punto t₄ = 0.08400914

El quinto punto t₅ es:

La quinta diferencia es la siguiente, con 6 decimales significativos, superando los 4 exigidos:

Hemos llegado y superado los decimales significativos especificados y consideramos que nos hemos acercado lo suficiente al valor correcto, finalizando con:

Sustituyendo en

obtenemos las coordenadas del punto intersección de la curva cuadrática con la circunferencia:

Este punto redondeado a dos decimales (90.40, 113.37) es el mismo que el primer punto del elemento POLYGON obtenido en la aplicación que configura la flecha en el punto de intersección del nodo "b":

<polygon points="90.4 113.37 84.2 117.04 87.71 120.05"
    fill="currentcolor"
    data-line="3,1"></polygon>

Los otros dos puntos del polígono se configuran de forma parecida a como hicimos en el apartado anterior para líneas rectas. El algoritmo getIntersection() devuelve ese punto en (dev.x, dev.y) y además el ángulo dev.angle de la pendiente de la curva en el punto de intersección con el nodo "b" y también el punto medio (dev.xm, dev.ym) para t = 0.5, que nos servirá para ubicar la etiqueta de la arista si la llevara. Recordamos que (x1, y1) en el código equivale a (a, b) en las ecuaciones anteriores del nodo "b", (x2, y2) equivale a (c, d) del nodo "d" y (xb, yb) equivale a (g, h) del punto de control de la curva cuadrática:

if (t>0 && t<1 && difer<=diferPrec){
    ...
    dev.x = (1-t)**2 * x1 + 2 * t * (1-t) * xb + t**2 * x2;
    dev.y = (1-t)**2 * y1 + 2 * t * (1-t) * yb + t**2 * y2;
    let dx = (2 * x1 - 4 * xb + 2 * x2) * t - 2 * x1 + 2 * xb;
    let dy = (2 * y1 - 4 * yb + 2 * y2) * t - 2 * y1 + 2 * yb;
    dev.angle = Math.atan(dy/dx);
    t = 0.5;
    dev.xm = (1-t)**2 * x1 + 2 * t * (1-t) * xb + t**2 * x2;
    dev.ym = (1-t)**2 * y1 + 2 * t * (1-t) * yb + t**2 * y2;
}

Con cada obtención de un valor de t comprobamos sus decimales con difer<=diferPrec. Como por defecto los números se redonden a 2 decimales (Figura), pasamos el argumento precision como el doble de esa configuración, es decir, con el valor 4. Así let diferPrec = 10**(-precision) nos dará un valor de 10^-4 = 0.0001 con 4 dígitos decimales significativos, suficiente para esa precisión de 2 decimales.

Cuando la diferencia sea igual o menor a ese valor especificado 0.0001 devolvemos el punto (dev.x, dev.y) y calculamos la pendiente de la función paramétrica:

derivando con respecto a t

cuyo valor en t = 0.08400788 es la pendiente de la curva cuadrática en el punto de intersección con el círculo, pendiente que nos sirve para ubicar la flecha con la inclinación adecuada:

Ponemos un console.log() en el código de la aplicación inmediatamente después de la sentencia que calcula dev.angle obteniendo estos valores, observando que, con redondeos, son los que hemos obtenido en los cálculos anteriores, recordando las equivalencia (x1, y1) ≡ (a, b), (x2, y2) ≡ (c, d), (xb, yb) ≡ (g, h), (dx, dy) ≡ (x'(t), y'(t)), angle ≡ φ

{
    "x1": 96.17,
    "y1": 105.97999999999999,
    "x2": 27.43,
    "y2": 107.7,
    "xb": 61.8,
    "yb": 153.93,
    "t": 0.08400789878813443,
    "x": 90.39529703730365,
    "y": 113.37169843138454,
    "dx": -68.74000000000001,
    "dy": 80.07627218426703,
    "angle": -0.8614276228735817
}

Por último indicar que en el algoritmo tomamos una lista de valores de prueba en el intervalo [0, 1] siguientes:

let ts = [0.025, 0.05, 0.1, 0.2, 0.3, 0.4,
0.5, 0.6, 0.7, 0.8, 0.9, 0.95, 0.975];

Da igual empezar en uno u otro valor, pues el algoritmo irá convergiendo al valor buscado si está en ese intervalo. Para evitar divergencias ponemos los límites inferior y superior en [0.025, 0.975]. Para los ejemplos que he probado la mayor parte de las veces se consigue la convergencia con el primer valor 0.025 y con 5 o 6 iteraciones. Recordemos que hemos puesto un límite de 15 iteraciones, de tal forma que cuando se alcancen pasamos a intentarlo con el siguiente valor de ese intervalo de valores de prueba. El máximo de iteraciones en caso de divergencia, es decir, que no encuentre el valor buscado, será el número de valores de prueba por 15 iteraciones por prueba, resultando 13 × 15 = 195 iteraciones, devolviendo el punto (0, 0) en caso de divergencia. Hasta ahora no he encontrado un ejemplo donde esto se produzca.

Ajustes con estilos CSS

En los ajustes visuales encontramos opciones para cambiar el tamaño de fuente de texto, como se observa en la Figura. El tamaño de la fuente de los textos se obtiene como 1/4 de la altura de línea, que a su vez es 1/10 del alto del SVG. En este caso se refiere al alto de líneas visuales donde se ubican los nodos, algo parecido al line-height de CSS. Así si el alto del SVG es de 250, la altura de línea será 250/10=25 y el tamaño de la fuente será 25/4=6.25. En la Figura hemos cambiado el tamaño de la fuente a 10px, de tal forma que todos los elementos TEXT tiene una propiedad SVG font-size="6.25" y otra propiedad CSS style="font-size: 10px", sobrescribiendo esta última a la anterior, con lo que el texto se renderiza a 10px. En font-size el tamaño es el correspondiente a unidades relativas de ViewBox. Mientras que con CSS son unidades absolutas en píxeles, entendiéndolas absolutas respecto al mismo monitor donde se reproduce.

Veamos ahora que otras posibilidades hay para modificar el estilo visual de los elementos SVG. Ese grafo de la Figura, que también puede encontrar en las muestras de la aplicación, nos servirá para ver como configurar estilos a los elementos del SVG, tomando como ejemplos los colores de los elementos.

El siguiente JSON es la exportación de ese grafo:

{"nodes":[
    {"index":0,"parent":[{"index":-1}],"nodeOffset":"-1 0"},
    {"index":1,"parent":[{"index":0}],"nodeOffset":"-4 0"},
    {"index":2,"parent":[{"index":0}],"nodeOffset":"2 0"}
],
"config":{
    "wv":57,
    "hv":54,
    "width":190,
    "height":180,
    "adjust":false,
    "wvIni":57,
    "nodeColor":"cyan",
    "lineColor":"red",
    "markerEnd":"arrow"
}}

En el código SVG generado a continuación se observa que los PATH tiene color de línea stroke="red" tal como se especifica en la configuración con "lineColor":"red". Los POLYGON que son las flechas que forman parte de las aristas o líneas también tienen ese color. Los CIRCLE tiene color de fondo fill="cyan" como la configuración "nodeColor":"cyan", mientras que el borde es stroke="currentcolor" que es el color negro actual del contenedor, al igual que los TEXT que tienen fill="currentcolor".

<svg viewBox="0 0 57 54" width="190" height="180" xmlns="http://www.w3.org/2000/svg">
    <path d="M15 37.5 L27.5 12.5" stroke-width="0.3" stroke="red" fill="none" data-line="1,0"></path>
    <path d="M40 37.5 L27.5 12.5" stroke-width="0.3" stroke="red" fill="none" data-line="2,0"></path>
    <circle cx="27.5" cy="12.5" r="6.25" stroke-width="0.3" stroke="currentcolor" fill="cyan" data-node="0"></circle>
    <text x="27.5" y="12.5" font-size="6.25" stroke-width="0.3" font-weight="normal" font-style="normal" font-family="Arial" 
        fill="currentcolor" text-anchor="middle" dominant-baseline="central" data-node="0">
        0
    </text>
    <circle cx="15" cy="37.5" r="6.25" stroke-width="0.3" stroke="currentcolor" fill="cyan" data-node="1"></circle>
    <text x="15" y="37.5" font-size="6.25" stroke-width="0.3" font-weight="normal" font-style="normal" font-family="Arial" 
        fill="currentcolor" text-anchor="middle" dominant-baseline="central" data-node="1">
        1
    </text>
    <polygon points="24.7 18.09 21.88 20.33 24.61 21.69" fill="red" data-line="1,0"></polygon>
    <circle cx="40" cy="37.5" r="6.25" stroke-width="0.3" stroke="currentcolor" fill="cyan" data-node="2"></circle>
    <text x="40" y="37.5" font-size="6.25" stroke-width="0.3" font-weight="normal" font-style="normal" font-family="Arial" 
        fill="currentcolor" text-anchor="middle" dominant-baseline="central" data-node="2">
        2
    </text>
    <polygon points="30.3 18.09 30.39 21.69 33.12 20.33" fill="red" data-line="2,0"></polygon>
</svg>

Podemos agregar color magenta al SVG en la configuración CSS estilo SVG como se observa en Figura quedando con el estilo CSS color: magenta, con lo que todos los currentcolor heredan ahora el color magenta, que aplica a los textos y los bordes de los círculos.

El SVG queda así con el estilo style="color: magenta" en su cabecera, siendo el resto igual:

<svg viewBox="0 0 57 54" width="190" height="180" style="color: magenta"
        xmlns="http://www.w3.org/2000/svg">
    ...
</svg>

En la Figura vemos la configuración CSS reglas elementos para incorporar estilo a los elementos del SVG que veremos a continuación. Se trata de incorporar estilo a los elementos sobrescribiendo los que especifiquen en la configuración o en el style del SVG.

Si ahí ponemos circle{stroke: green; stroke-width: 2} obtendremos el grafo de la Figura, dando color verde con grueso 2 a los bordes de todos los CIRCLE del SVG, agregando style="stroke: green; stroke-width: 2;" a esos elementos.

Si ahí ponemos circle[data-node="0"]{stroke: green; stroke-width: 2} path[data-line="2,0"]{stroke: blue; stroke-width: 1; stroke-dasharray: 1} obtendremos el grafo de la Figura, dando color verde con grueso 2 al borde exclusivamente del primer CIRCLE del nodo con índice 0 (data-node="0"). Y al PATH con color línea azul con puntos de la arista "2,0" (data-line="2,0").

El estilo CSS del SVG y las reglas CSS podrían incorporarse en un elemento <style> externo al SVG. En el siguiente ejemplo tomamos el grafo inicial sin nada de lo que hemos añadido y le ponemos la clase example_ a la configuración CSS clase SVG, que debe llevar obligatoriamente un guion bajo al final, siendo añadido si no lo lleva, con objeto de no interferir con otras clases de la página.

<style>
    svg.example_ {
        color: magenta;
    }
    svg.example_ circle[data-node="0"]{
        stroke: green;
        stroke-width: 2
    }
    svg.example_ path[data-line="2,0"]{
        stroke: blue;
        stroke-width: 1;
        stroke-dasharray: 1
    }
}</style>
<svg viewBox="0 0 57 54" width="190" height="180" class="example_"
    xmlns="http://www.w3.org/2000/svg">
    <path d="M15 37.5 L27.5 12.5" stroke-width="0.3" stroke="red" fill="none" data-line="1,0"></path>
    <path d="M40 37.5 L27.5 12.5" stroke-width="0.3" stroke="red" fill="none" data-line="2,0"></path>
    <circle cx="27.5" cy="12.5" r="6.25" stroke-width="0.3" stroke="currentcolor" fill="cyan" data-node="0"></circle>
    <text x="27.5" y="12.5" font-size="6.25" stroke-width="0.3" font-weight="normal" font-style="normal" font-family="Arial" 
        fill="currentcolor" text-anchor="middle" dominant-baseline="central" data-node="0">
        0
    </text>
    <circle cx="15" cy="37.5" r="6.25" stroke-width="0.3" stroke="currentcolor" fill="cyan" data-node="1"></circle>
    <text x="15" y="37.5" font-size="6.25" stroke-width="0.3" font-weight="normal" font-style="normal" font-family="Arial" 
        fill="currentcolor" text-anchor="middle" dominant-baseline="central" data-node="1">
        1
    </text>
    <polygon points="24.7 18.09 21.88 20.33 24.61 21.69" fill="red" data-line="1,0"></polygon>
    <circle cx="40" cy="37.5" r="6.25" stroke-width="0.3" stroke="currentcolor" fill="cyan" data-node="2"></circle>
    <text x="40" y="37.5" font-size="6.25" stroke-width="0.3" font-weight="normal" font-style="normal" font-family="Arial" 
        fill="currentcolor" text-anchor="middle" dominant-baseline="central" data-node="2">
        2
    </text>
    <polygon points="30.3 18.09 30.39 21.69 33.12 20.33" fill="red" data-line="2,0"></polygon>
</svg>

El código SVG debe exportarse usando la opción identificar elementos SVG para que agregue los data-node y data-line que identifican los elementos. Incorporamos ese código directamente en este punto de la página obteniendo lo mismo en la Figura que la vez anterior.

En los ejemplos anteriores hemos agregado estilo CSS de colores de líneas, bordes y textos, así como anchos de líneas y anchos de bordes. Pero esos estilos también pueden agregarse con la aplicación. En la Figura se observa esto con un resultado similar a los anteriores, donde lo único que aplicamos con CSS es el subrayado del texto "2" de ese nodo. Este es el JSON resultante:

{"nodes":[
    {"index":0,"parent":[{"index":-1}],"nodeOffset":-1,
        "nodeBorderColor":"green","nodeBorderWidth":7},
    {"index":1,"parent":[{"index":0}],"nodeOffset":-4},
    {"index":2,"parent":[{"index":0,"nodeOffset":"2",
        "lineColor":"blue","lineDash":1,"lineWidth":2.5}]}
],
"config":{
    "wv":57,
    "hv":54,
    "width":190,
    "height":180,
    "adjust":false,
    "wvIni":57,
    "rulesCss":"text[data-node=2]{text-decoration: underline}",
    "nodeColor":"cyan",
    "nodeFontColor":"magenta",
    "lineColor":"red",
    "markerEnd":"arrow"
}}

Se observan las propiedades nodeBorderColor y nodeBorderWidth que configuran color verde y ancho grueso para el borde del nodo "0". La arista "2-0" tiene color línea azul con lineColor, línea punteada con lineDash y ancho con lineWidth.

En la configuración general, aparte de nodeColor y lineColor que ya aparecía en los ejemplos anteriores, ahora agregamos nodeFontColor para el color magenta de los textos y la regla CSS text[data-node=2]{text-decoration: underline} que configura subrayado de texto para el "2", estilo que no es posible aplicar con la configuración de la aplicación.

Cambiar tamaño del SVG

El tamaño del SVG es el rectángulo señalado con la línea con puntos de la Figura. La mejor forma de configurar el ancho y alto tanto del SVG como del ViewBox es con la opción ajustar SVG activada, pues se ajustarán de forma automática esas medidas para albergar los elementos del SVG. Si tuviéramos que modficar el ancho y alto que se establece automáticamente, podríamos hacerlo cambiando los valores directamente en los controles. Pero es un engorro dada la relación de dependencia que hay entre ancho o alto del SVG y Viewbox, afectando a la altura de línea y otras cosas, especialmente cuando hay desplazamiento de nodos (propiedad nodeOffset).

El siguiente JSON es el que configura el grafo anterior, donde se observa que se pasa la configuración "adjust":false para que no ajuste el SVG, pues por defecto ese valor es verdadero.

{"nodes":[
    {"index":0,"value":1,"parent":[{"index":-1}],"nodeOffset":"-17.5 1.5"},
    {"index":1,"value":"2","parent":[{"index":0}],"nodeOffset":"-1.47 -14.25"},
    {"index":2,"value":"3","parent":[{"index":1},{"index":0}],"nodeOffset":"-1.47 -20.75"},
    {"index":3,"value":4,"parent":[{"index":2},{"index":1}],"nodeOffset":"-17.5 -36.5"},
    {"index":4,"value":5,"parent":[{"index":3},{"index":2},{"index":0}],"nodeOffset":"-33.53 -70.75"},
    {"index":5,"value":6,"parent":[{"index":4},{"index":0},{"index":1},{"index":3}],"nodeOffset":"-33.53 -114.25"}
],
"config":{
    "adjust":false
}}

Para modificar el ancho o alto del SVG es mejor utilizar el ajuste visual para cambiar el tamaño como se observa en la Figura. Al reducir el ancho y alto, obtenemos este JSON, donde se observa que ha actuado también sobre los nodeOffset, para reubicar los nodos y que aparezcan en su posición anterior:

{"nodes":[
    {"index":0,"value":1,"parent":[{"index":-1}],"nodeOffset":"-1.5 1.5"},
    {"index":1,"value":"2","parent":[{"index":0}],"nodeOffset":"14.53 -14.25"},
    {"index":2,"value":"3","parent":[{"index":1},{"index":0}],"nodeOffset":"14.53 -20.75"},
    {"index":3,"value":4,"parent":[{"index":2},{"index":1}],"nodeOffset":"-1.5 -36.5"},
    {"index":4,"value":5,"parent":[{"index":3},{"index":2},{"index":0}],"nodeOffset":"-17.53 -70.75"},
    {"index":5,"value":6,"parent":[{"index":4},{"index":0},{"index":1},{"index":3}],"nodeOffset":"-17.53 -114.25"}
],
"config":{
    "wv":68,
    "hv":68,
    "width":170,
    "height":170,
    "adjust":false,
    "wvIni":68
}}

Ese ajuste visual se encarga de rellenar los controles de medidas del SVG (with, height) y del Viewbox (wv, hv). Observe como la altura de línea sigue conservando el valor inicial 25 = 250/10 pues inicialmente es 1/10 de la altura inicial 250. El ancho inicial ViewBox (propiedad wvIni) se utiliza para aplicar el zoom, modificándose cuando cambiamos las medidas del ViewBox, sirviéndonos para referenciar el valor 100% del zoom.

Mover elementos

Con el grafo del apartado anterior hemos seleccionado el nodo inferior y le aplicamos movimiento hacia abajo, como se observa en la Figura. Con esta funcionalidad se pueden mover también aristas y si no hay nada seleccionado se moverá todo el conjunto.

Aplicar zoom

En la Figura puede ver como aplicamos un zoom del 50% al grafo del apartado anterior. El zoom actua sobre la altura de línea, partiendo de que el valor 100% corresponde al ancho inicial del ViewBox (vwIni = 68), que para ese grafo era de 25, mientras que al aplicar el zoom del 50% la altura de línea se reduce a 12.5.

El zoom no modifica las medidas del SVG, solo actua sobre la altura de línea, pues a partir de ella se configuran los tamaños de los elementos SVG. Si necesita cambiar el tamaño del SVG sin afectar a los elementos debe usar esa funcionalidad que comentamos en un apartado anterior.

Aplicar relleno

Aplicamos relleno (padding) al grafo anterior como se observa en la Figura, agregándose un marco alrededor del grafo que, si no se especifica, sera 1/10 del ancho o alto del ViewBox (wv=68, hv=68), respectivamente para el ancho izquierda y derecha y, por otro lado, para el superior e inferior.

Se añade el estilo CSS al elemento SVG con style="padding: 6.8 6.8 6.8 6.8", donde el orden es "TRBL" top, right, bottom, left tal como usualmente se utiliza en propiedades agrupadas de CSS, recordando que cuando no se especifican las longitudes como píxeles en el CSS de un SVG, entonces se refieren a unidades del ViewBox.

Esparcir elementos

La funcionalidad para esparcir elementos se refiere a desplazar radialmente los nodos desde su centro. En las dos capturas siguientes se observa la primera que es la situación inicial y la segunda tras aplicarle un esparcido positivo con espaciado 1, pulsando dos veces el botón "+" que se observa en la Figura.

El grafo inicial sin esparcir tiene este JSON:

{"nodes":[
    {"index":0,"parent":[{"index":-1}]},
    {"index":1,"parent":[{"index":-1}]},
    {"index":2,"parent":[{"index":-1}]},
    {"index":3,"parent":[{"index":0},{"index":1},{"index":2}]},
    {"index":4,"parent":[{"index":0},{"index":1},{"index":2}]},
    {"index":5,"parent":[{"index":0},{"index":1},{"index":2}]}
],
"config":{
    "wv":87.5,
    "hv":50,
    "width":218.75,
    "height":125,
    "adjust":false,
    "wvIni":87.5
}}

Para esparcir elementos primero tenemos que encontrar el centro geométrico de los nodos o vértices, lo que hacemos con este algoritmo que recorre todos los elementos CIRCLE recopilando las posiciones de sus centros y radios. El objeto nodes proviene del JSON anterior, extrayendo el índice node.index y buscando en el SVG un elemento CIRCLE con data-node igual a ese índice. Los atributos cx, cy, r son los que tiene el CIRCLE para su centro y radio:

for (let node of nodes) {
    let circle = document.querySelector(`#${ui.id} div[data-view] svg circle[data-node="${node.index}"]`);
    let [x, y, r] = [+circle.getAttribute("cx"), +circle.getAttribute("cy"), +circle.getAttribute("r")];
    points.push([x, y]);
    radius = r;
}
let xm = 1/n * points.reduce((p,v) => (p += v[0], p), 0);
let ym = 1/n * points.reduce((p,v) => (p += v[1], p), 0);
    

El punto (xm, ym) podemos denominarlo centro geométrico como promedio de las posiciones de los elementos:

Modificamos radialmente cada posición de los elementos con este código:

let sign = action==="plus" ? 1 : -1;
let gap = spacing * sign / radius;
for (let i=0; i<nodes.length; i++) {
    let node = nodes[i];
    let nodeOffset = graph.getProperty(node, "nodeOffset", config).toString();
    if (!/\s+/.test(nodeOffset.trim())) nodeOffset += " 0";
    let [xo, yo] = nodeOffset.split(/\s+/).map(v => +v);
    let [x, y] = points[i];
    let angle = Math.atan2(y-ym, x-xm);
    let r = Math.sqrt((x-xm)**2 + (y-ym)**2) * gap;
    let xe = xo + r * Math.cos(angle);
    let ye = yo + r * Math.sin(angle);
    let xn = wxG.redondear(xe, config.precision);
    let yn = wxG.redondear(ye, config.precision);
    let offset = `${xn} ${yn}`;
    node.nodeOffset = offset;
}

En (xo, yo) obtenemos el desplazamiento de cada nodo (nodeOffset). Calculamos el ángulo que forma cada nodo en (x, y) con el centro (xm, ym). Aplicamos el radio modificado r = Math.sqrt((x-xm)**2 + (y-ym)**2) * gap, donde gap es una proporción con respecto al radio de los círculos de los nodos (radius). Finalmente obtenemos los nuevos desplazamientos (xn, yn) con xo + r * Math.cos(angle) y yo + r * Math.sin(angle) tras aplicarle el redondeo a los decimales especificado en la configuración.

En el ejemplo no hay desplazamientos de nodos previamente, como se observa en el JSON más arriba, con lo que este caso xo=0, yo=0. Tras aplicar el esparcido el JSON queda así, donde se observan los nodeOffset que desplazan los nodos respecto a su posición original:

{"nodes":[
    {"index":0,"parent":[{"index":-1}],"nodeOffset":"-7.56 -4.32"},
    {"index":1,"parent":[{"index":-1}],"nodeOffset":"0 -4.32"},
    {"index":2,"parent":[{"index":-1}],"nodeOffset":"7.56 -4.32"},
    {"index":3,"parent":[{"index":0},{"index":1},{"index":2}],"nodeOffset":"-7.56 4.32"},
    {"index":4,"parent":[{"index":0},{"index":1},{"index":2}],"nodeOffset":"0 4.32"},
    {"index":5,"parent":[{"index":0},{"index":1},{"index":2}],"nodeOffset":"7.56 4.32"}
],
"config":{
    "wv":87.5,
    "hv":50,
    "width":218.75,
    "height":125,
    "adjust":false,
    "wvIni":87.5
}}

Ajustar a rejilla

La funcionalidad para ajustar a rejilla un grafo puede verse en la Figura. Se trata de construir una rejilla de nodos con tantas columnas como se especifiquen. Si un grafo tiene 15 nodos y especificamos 5 columnas, tendremos una rejilla de 3 filas con 5 ndos en cada fila. Por ejemplo, el grafo de Kneser 6,2 tiene la siguiente matriz de adyacencia:

[[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1],
[0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1],
[0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0],
[0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0],
[0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1],
[0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1],
[0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0],
[0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0],
[1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0],
[1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0],
[1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0],
[1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0]]

Podemos crear el grafo con esta matriz poniéndola en el área de texto de la parte superior, en el control denominado Nodos o matriz de adyacencia, y luego actualizar el grafo con el botón , obteniendo el que se observa en la Figura.

Esa es la disposición inicial de los nodos en niveles, con el JSON obtenido a continuación. Cada nodo tiene una colección parent que son los nodos con los que está relacionado mediante una arista. Así en el primer nivel están los nodos que apuntan a la raíz -1. Y en el segundo están los que apuntan a estos y entre sí. Si hubiese un nodo que apuntase a alguno del segundo nivel pero no al primero, se agregaría un tercer nivel disponiendo ese nodo en una tercera fila y así sucesivamente.

{"nodes":[
    {"index":0,"parent":[{"index":-1}]},
    {"index":1,"parent":[{"index":-1}]},
    {"index":2,"parent":[{"index":-1}]},
    {"index":3,"parent":[{"index":-1}]},
    {"index":4,"parent":[{"index":-1}]},
    {"index":5,"parent":[{"index":2},{"index":3},{"index":4}]},
    {"index":6,"parent":[{"index":1},{"index":3},{"index":4}]},
    {"index":7,"parent":[{"index":1},{"index":2},{"index":4}]},
    {"index":8,"parent":[{"index":1},{"index":2},{"index":3}]},
    {"index":9,"parent":[{"index":0},{"index":3},{"index":4},{"index":7},{"index":8}]},
    {"index":10,"parent":[{"index":0},{"index":2},{"index":4},{"index":6},{"index":8}]},
    {"index":11,"parent":[{"index":0},{"index":2},{"index":3},{"index":6},{"index":7}]},
    {"index":12,"parent":[{"index":0},{"index":1},{"index":4},{"index":5},{"index":8},{"index":11}]},
    {"index":13,"parent":[{"index":0},{"index":1},{"index":3},{"index":5},{"index":7},{"index":10}]},
    {"index":14,"parent":[{"index":0},{"index":1},{"index":2},{"index":5},{"index":6},{"index":9}]}
],
"config":{}}

Esa disposición inicial es automática y no se puede modificar. La disposición por niveles es óptima para representar gráficamente los árboles. Esa fue la primera necesidad que tuve cuando inicié esta aplicación. Pero un árbol también es un grafo, por lo que la aplicación no tiene ningún problema tratando con grafos que no son árboles, pues en cualquier caso siempre podemos modificar posteriormente la posición de los nodos.

O bien utilizar esta funcionalidad ajustando a una rejilla de 5 columnas, disponiéndose entonces como se observa en la Figura. Se van ubicando los nodos en filas completando esas columnas con un espaciado entre nodos que especificamos en la herramienta. Podemos obtener el JSON siguiente donde se observan los desplazamientos de nodos (nodeOffset) que se aplica con respecto a la disposición inicial en niveles que comentamos antes.

{"nodes":[
    {"index":0,"parent":[{"index":-1}],"nodeOffset":"-1.67 2.5"},
    {"index":1,"parent":[{"index":-1}],"nodeOffset":"6.67 2.5"},
    {"index":2,"parent":[{"index":-1}],"nodeOffset":"15 2.5"},
    {"index":3,"parent":[{"index":-1}],"nodeOffset":"23.33 2.5"},
    {"index":4,"parent":[{"index":-1}],"nodeOffset":"31.67 2.5"},
    {"index":5,"parent":[{"index":2},{"index":3},{"index":4}],"nodeOffset":"5.91 2.5"},
    {"index":6,"parent":[{"index":1},{"index":3},{"index":4}],"nodeOffset":"21.82 2.5"},
    {"index":7,"parent":[{"index":1},{"index":2},{"index":4}],"nodeOffset":"37.73 2.5"},
    {"index":8,"parent":[{"index":1},{"index":2},{"index":3}],"nodeOffset":"53.64 2.5"},
    {"index":9,"parent":[{"index":0},{"index":3},{"index":4},{"index":7},{"index":8}],"nodeOffset":"69.55 2.5"},
    {"index":10,"parent":[{"index":0},{"index":2},{"index":4},{"index":6},{"index":8}],"nodeOffset":"-39.55 27.5"},
    {"index":11,"parent":[{"index":0},{"index":2},{"index":3},{"index":6},{"index":7}],"nodeOffset":"-23.64 27.5"},
    {"index":12,"parent":[{"index":0},{"index":1},{"index":4},{"index":5},{"index":8},{"index":11}],"nodeOffset":"-7.73 27.5"},
    {"index":13,"parent":[{"index":0},{"index":1},{"index":3},{"index":5},{"index":7},{"index":10}],"nodeOffset":"8.18 27.5"},
    {"index":14,"parent":[{"index":0},{"index":1},{"index":2},{"index":5},{"index":6},{"index":9}],"nodeOffset":"24.09 27.5"}
],
"config":{}}

Ajustar a círculo

Podemos ajustar a círculo un grafo, como se observa en la Figura. Especificamos un radio para el círculo y un espaciado entre nodos. Podemos disponerlos en varios círculos concéntricos y posicionar un nodo en el centro del círculo. Al igual que para rejilla, aquí también podemos disponer un orden de aparición de los nodos.

Tomando la matriz de adyacencia del grafo Kneser 6,2 que vimos en el apartado anterior, el ajuste a círculo con radio 50 y espaciado 1 se observa en la Figura.

Aunque la parte de ejecución de algoritmos aún no la he explicado, podemos ejecutar el algoritmo Ciclo Hamiltoniano con vuelta atrás, que en caso de que exista, nos devoverá un array, que para este grafo es [0,9,3,5,2,7,4,6,11,12,8,10,13,1,14,0]. Se trata del camino cerrado o ciclo que recorre todos los nodos. Si ponemos esa lista de nodos en el control orden de nodos obtendremos el grafo de la Figura, donde se observa que ahora hay una arista entre cada uno de los nodos recorriendo el círculo, que es precisamente ese ciclo Hamiltoniano.

En la ejecución del algoritmo ese ciclo aparece resaltado en rojo, como se ve en Figura.

Por último, podemos disponer los nodos en 2 círculos concéntricos y ubicar el nodo 0 en el centro, como se observa en la Figura.