Introducción mejoras en la aplicación

En 2020 implementé la aplicación Grafos SVG para crear grafos en SVG. En el tema Grafos creados con elementos SVG explicaba 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 nodos y aristas así como contraer y subdivir un grafo, 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.

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, lista de adyacencia y matriz de distancias cuando fuera posible.
• 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. 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 contraer nodos o aristas , para división o reunión en un grafo , para subdivisión o suavizado de un grafo y para eliminar un nodo o una arista

Todas estas operaciones se ejecutan sobre el JSON, pudiendo también ejecutarse sobre la matriz de adyacencia como explicamos en el tema sobre operaciones básicas en un grafo. La diferencia estriba en las limitaciones de la matriz de adyacencia a la hora de representar multigrafos.

Agregar o eliminar 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 el nodo o arista con el botón para editar la arista o crear una nueva, seleccionando que tipo de marcador poner y en que lado de la línea, como vemos en la Figura.

Contraer nodos o aristas

La operación contraer nodos al que se accede con el botón 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. Decimos contraer nodos o aristas pero no es necesario que exista arista entre los dos nodos.

{"nodes":[
    {"index":0,"nodeOffset":"-22.8 65.2","value":"1","parent":[{"index":-1},{"index":0,"lineType":"cubic","lineOffset":"4 0 0 4"}]},
    {"index":1,"nodeOffset":"-16 16.4","value":"2","parent":[{"index":0}]},
    {"index":2,"nodeOffset":"-27.2 -33.4","value":"3","parent":[{"index":1}]},
    {"index":3,"nodeOffset":"1.6 -53.6","value":"4","parent":[{"index":2}]},
    {"index":4,"nodeOffset":"-22 21.2","value":"5","parent":[{"index":0},{"index":1},{"index":3}]},
    {"index":5,"nodeOffset":"18 -94.8","value":"6","parent":[{"index":3}]}
],
"config":{
}}

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

Marcando las opciones mantener valores nodos y omitir autobucles vemos el resultado en la Figura donde el nodo contraído tiene valor "46" que es la contracción de los nodos "4" y "6". Vea que se omiten todos los autobucles, incluso el existente inicialmente en el nodo "1".

Marcando las las opciones mantener valores nodos, omitir autobucles y tipo valor fusionado igual a "suma" obtenemos el grafo contrayendo los nodos "3" y "5" de la Figura. Se observa en el grafo inicial de la Figura que al ser el grafo no dirigido cada arista tiene un peso unitario, así que la suma de las dos aristas "2-3" y "2-5" suponen poner un valor 2 a la nueva arista "2-35" y que la suma de las dos aristas "3-4" y "5-4" supone un valor 2 para la nueva arista "35-4". El tipo valor fusionado puede ser ninguno, primero, último, mínimo, máximo suma y promedio.

En la Figura vemos un grafo etiquetado tanto en nodos como aristas sobre el que contraemos los nodos "d" y "e", marcando la opción mantener valores nodos, sin marcar omitir autobucles y con tipo valor fusionado también "suma". Como las etiquetas son letras la suma se aplica concatenando los valores "D" y "F" en "DF" a la nueva arista "de🡒b" a partir de las aristas "d🡒b" con valor "D" y "e🡒b" con valor "F". No omitiendo autobucles vemos que la arista "d🡒e" se convierte en el autobucle "de🡒de" con el mismo valor "E".

En la Figura vemos para el mismo grafo inicial la contracción de los nodos "c" y "d" sin aristas entre ellos. Los valores "C" de la arista "c🡒b" y "D" de la arista "d🡒b" se concatenan en la nueva arista "cd🡒b" con valor "CD". La arista inicial "e🡒c" con valor "H" sigue en "e🡒cd" con el mismo valor, mientras que "d🡒e" convalor "E" pasa a ser la "cd🡒e" con ese valor "E". Como no hay arista entre los nodos "c" y "d" no hay autobucle.

{"nodes":[
    {"index":0,"parent":[{"index":-1}]},
    {"index":1,"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"},{"index":2,"value":"H","lineTextOffset":1},{"index":0,"lineOffset":"1","markerReverse":true,"value":"G"}]}
],
"config":{
    "nodeValueAuto":"alphabetic-lower",
    "markerEnd":"arrow"
}}

En la Figura vemos un grafo no dirigido y ponderado y la contracción de los nodos "1" y "4" usando la opción tipo valor fusionado igual a "media", marcando mantener valores nodos y desmarcando omitir autobucles. Las aristas iniciales "1-3" con valor 7 y "4-3" con valor 2 tiene un valor medio de (7+2)/2 = 4.5 que aparece en la nueva arisata "14-3". Vemos el autobucle "14-14" con valor 5 igual que la arista inicial "1-5".

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

Subdivisión y suavizado

La operación subdivisión (subdivision) de una arista o generalmente en un grafo se refiere a insertar un nodo en una arista entre dos nodos. Por ejemplo, en la Figura tenemos un grafo dirigido donde seleccionamos la arista "3🡒4" y abrimos el panel de edición de subdivisión con el botón y aplicamos o aceptamos la ejecución.

En la Figura se observa el resultado, donde se ha insertado un nuevo nodo "5" entre ambas aristas. Vea que se conserva la arista anterior con su etiquetado en "3🡒5" y la nueva "5🡒4" tiene la misma dirección. La opción tipo valor fusionado ofrece los valores ninguno, replicar y suma. Con el valor "ninguno" la nueva arista "5🡒4" no tiene etiqueta. Con valor "replicar" se copiaría la etiqueta "E" de la arista 3🡒5" a la nueva "5🡒4". El valor "suma" se aplica a grafos ponderamos (modo valor "0/number"), de tal forma que las dos aristas resultantes tendrían la mitad del valor de la arista inicial.

La operación inversa a la subdivisión es el suavizado (smoothing), que no es otra cosa que eliminar un nodo entre dos aristas. Marcando la opción suavizado que se observa en la Figura, podemos eliminar ese nodo "5" que hemos insertado entre dos nodos reponiéndose la arista anterior "3🡒4".

Se puede suavizar cualquier nodo entre dos aristas pero deben conservar la dirección y no tener otros enlaces. En el grafo de ejemplo no puede suavizar ningún otro nodo puesto que ninguno de ellos está en medio de dos nodos conservando la dirección en grafos dirigidos y además sin otros enlaces. Por ejemplo, el nodo "3" está entre los nodos "X" y "5", pero no conserva la dirección en uno u otro sentido. Otros nodos están entre dos nodos, pero tienen además enlaces adicionales que entran o salen al nodo que se suaviza. En estos casos aparecerá el mensaje de error "El nodo no es apropiado para suavizado".

Puede ver un ejemplo de uso de esta operación en encontrar máximo flujo en un grafo no dirigido.

División y reunión

En un grafo dirigido la operación división (splitting) de un nodo se basa en detectar las aristas salientes de ese nodo, traspasándolas a un nuevo nodo a crear, apuntando el nodo anterior este nuevo nodo. Como entran en juego el sentido de las aristas es por lo que sólo se aplica a grafos dirigidos. En a Figura vemos un grafo dirigido, que puede importar con el siguiente JSON, donde hemos seleccionado el nodo "2" y vamos a dividirlo abriendo el panel correspondiente con el botón

{"nodes":[
    {"index":0,"nodeOffset":"2.5","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"65.54 2.64","parent":[{"index":0,"value":7}]},
    {"index":2,"nodeOffset":"2.5 15","parent":[{"index":0,"value":9},{"index":1,"value":10}]},
    {"index":3,"nodeOffset":"42.68 22.36","parent":[{"index":1,"value":15},{"index":4,"value":6},{"index":2,"value":11}]},
    {"index":4,"nodeOffset":"-37.68 22.36","parent":[{"index":5,"value":9}]},
    {"index":5,"nodeOffset":"-60.54 2.64","parent":[{"index":0,"value":14},{"index":2,"value":2}]}
],
"config":{
    "markerStart":"arrow"
}}

En la Figura vemos el resultado, donde se ha creado el nuevo nodo "6" y las aristas "2🡒5" y "2🡒3" ahora se traspasan a "6🡒5" y "6🡒3", creándose la nueva arista "2🡒6". Con el siguiente JSON puede importar este grafo.

{"nodes":[
    {"index":0,"nodeOffset":"19.17","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"65.54 2.64","parent":[{"index":0,"value":7}]},
    {"index":2,"nodeOffset":"2.5 15","parent":[{"index":0,"value":9},{"index":1,"value":10}]},
    {"index":3,"nodeOffset":"42.68 22.36","parent":[{"index":1,"value":15},{"index":4,"value":6},{"index":6,"value":11}]},
    {"index":4,"nodeOffset":"-37.68 22.36","parent":[{"index":5,"value":9}]},
    {"index":5,"nodeOffset":"-60.54 2.64","parent":[{"index":0,"value":14},{"index":6,"value":2}]},
    {"index":6,"nodeOffset":"-27.6 56","parent":[{"index":-1},{"index":2}]}
],
"config":{
    "markerStart":"arrow"
}}

La operación opuesta a la división es la reunión (unsplitting). En este caso hay que seleccionar la nueva arista "2🡒6" que antes se había creado y abrir el panel, apareciendo el control reunir activado (Figura).

Como vemos en la Figura, al aceptar la operación volvemos a obtener el grafo de origen de la Figura que vemos al inicio de este apartado.

La operación de reunión traspasa las aristas "6🡒5" y "6🡒3" al nodo "2", eliminando la arista "2🡒6" y el nodo "6".

El siguiente JSON obtenido es el mismo que el inicial.

{"nodes":[
    {"index":0,"nodeOffset":"2.5 0","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"65.54 2.64","parent":[{"index":0,"value":7}]},
    {"index":2,"nodeOffset":"2.5 15","parent":[{"index":0,"value":9},{"index":1,"value":10}]},
    {"index":3,"nodeOffset":"42.68 22.36","parent":[{"index":1,"value":15},{"index":4,"value":6},{"index":2,"value":11}]},
    {"index":4,"nodeOffset":"-37.68 22.36","parent":[{"index":5,"value":9}]},
    {"index":5,"nodeOffset":"-60.54 2.64","parent":[{"index":0,"value":14},{"index":2,"value":2}]}
],
"config":{
    "markerStart":"arrow"
}}

La operación reunión puede aplicarse a cualquier arista, no necesariamente que provenga de una operación de división. Por ejemplo, en la Figura vemos la arista "D🡒E", etiquetada con "X", que vamos a reunir. Esa arista debe cumplir lo siguiente:

• - El nodo inicial ("D") solo debe tener una arista saliente al nodo final ("E").
• - El nodo final ("E") solo debe tener una arista entrante desde el nodo inicial ("D").

Si se cumplen esos requisitos entonces las aristas salientes del nodo final ("E") se traspasan al nodo inicial ("D"), eliminando el nodo final ("E") y la arista entre ambos ("D🡒E").

En la Figura vemos el resultado de la reunión "D🡒E". Observe que si la arista "B🡒D" con valor 40 hubiese sido al revés, ahora tendríamos dos aristas "D🡒B" en la misma dirección, una con valor 40 existente y otra con valor 50 que procede de la reunión. Quedará un multigrafo con múltiples aristas, algo que la aplicación soporta pero que no es exportable a la matriz de adyacencia, como explicamos en un tema posterior en multigrafos y las limitaciones de la matriz de adyacencia.

Este es el JSON de ese grafo.

{"nodes":[
    {"index":0,"value":"A","parent":[{"index":-1}]},
    {"index":1,"value":"B","parent":[{"index":0,"value":10}]},
    {"index":2,"value":"C","parent":[{"index":0,"value":20},{"index":1,"value":30}]},
    {"index":3,"value":"D","nodeOffset":"0 7.5","parent":[{"index":1,"value":40,"markerStart":"arrow","markerEnd":"none","lineType":"quadratic","lineOffset":-4},{"index":4,"value":"X"}]},
    {"index":4,"value":"E","nodeOffset":"0 7.5","parent":[{"index":1,"value":50},{"index":2,"value":60}]}
],
"config":{
    "markerEnd":"arrow"
}}

Construyendo arista recta y posicionando su flecha

Con esta mejora de la aplicación incorporo aristas curvas. 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, desplegando el nodo con índice "2" etiquetado con "c" para observar los "lineType":"cubic" mientras que el primero es rect aunque no aparece pues es el valor predeterminado.

{"nodes":[
    {"index":0,"value":"a","parent":[{"index":-1}],"nodeOffset":"14.27 23.7","nodeFontColor":"blue"},
    {"index":1,"value":"b","parent":[{"index":0,"value":"rect","lineOffset":"1.99","lineFontColor":"blue"}],"nodeOffset":"14.11 33.15","nodeFontColor":"maroon"},
    {"index":2,"value":"c","parent":[
        {"index":3,"value":"rect","lineFontColor":"blue"},
        {"index":1,"value":"cubic","lineType":"cubic","lineOffset":"5 -0.2 -4 1","lineFontColor":"green","lineFontBold":false},
        {"index":2,"lineType":"cubic","lineOffset":"6 0 0 -6","value":"cubic","lineFontColor":"red"}
    ],"nodeOffset":"-20.53 -58.3","nodeFontColor":"red"},
    {"index":3,"value":"d","parent":[{"index":1,"value":"quadratic","lineType":"quadratic","lineOffset":"0 5.02","lineFontColor":"red"}],"nodeOffset":"-31.71 9.3","nodeFontColor":"green"}
],
"config":{
    "markerEnd":"arrow"
}}

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:

Para el cálculo también podemos usar la calculadora copiando la ecuación e insertando el operador × donde sea necesario. O la consola del navegador usando Math para las funciones y * para el producto donde sea necesario. La función arctan(y, x) se refiere a la función Math.atan2(y, x) de JavaScript, donde el primer argumento es la coordenada y y el segundo es la coordenada x. En la calculadora y también en Wolfram Alpha, un buen recurso para hacer cálculos, permiten usar la función arctan(), pero en la calculadora funciona como en JavaScript arctan(y, x) mientras que en Wolfram Alpha hay que pasarla como arctan(x, y).

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 método 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.

Radio del círculo de los nodos (nodeRadius)

En la Figura vemos un grafo que puede importar desde la sección de muestras, donde los nodos etiquetados con "A" y "B" tienen un radio del círculo diferente al normal, como los otros dos nodos "C" y "D".

El radio base o normal de los círculos se calcula al crear el SVG del grafo con let radiusBase = wxG.redondear(dev.config.lineHeight/4, dev.config.precision). La altura de línea por defecto es 25, así que el radio base es 25/4 = 6.25 unidades de Viewport del SVG. El nodo "A" tiene un radio 11 algo mayor que el base y el "B" tiene un radio 4, menor que el base, como se observa en el JSON del grafo:

{"nodes":[
    {"index":0,"nodeOffset":"23.87 20.9","nodeFontColor":"blue","nodeRadius":11,"nodeColor":"yellow","nodeBorderColor":"teal","nodeBorderWidth":3,"parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"14.11 33.15","nodeFontColor":"maroon","nodeRadius":4,"parent":[{"index":0,"value":"rect","lineOffset":1.48,"lineFontColor":"blue"}]},
    {"index":2,"nodeOffset":"-20.53 -58.3","nodeFontColor":"red","parent":[{"index":3,"value":"rect","lineFontColor":"blue"},{"index":1,"value":"cubic","lineType":"cubic","lineOffset":"5 -0.2 -4 1","lineFontColor":"green","lineFontBold":false},{"index":2,"lineType":"cubic","lineOffset":"6 0 0 -6","value":"cubic","lineFontColor":"red"}]},
    {"index":3,"nodeOffset":"-31.71 9.3","nodeFontColor":"green","parent":[{"index":1,"value":"quadratic","lineType":"quadratic","lineOffset":"0 5.02","lineFontColor":"red"}]}
],
"config":{
    "nodeValueAuto":"alphabetic-upper",
    "nodeFontFamily":"Courier",
    "nodeFontSizeAdjusted":true,
    "nodeFontBold":true,
    "markerEnd":"arrow"
}}

El tamaño de la fuente del nodo se calcula con el radio del círculo, así que el tamaño del texto del nodo se adapta al tamaño del círculo con "nodeFontSizeAdjusted":true, pues en otro caso tendrá tamaño normal.