Estructuras datos para grafos
Crear grafo desde estructura JSON y desde matriz de adyacencia
Las estructuras de datos para representar un grafo que usa la aplicación Grafos SVG son, básicamente, el propio JSON de la aplicación basado en relaciones
Antes de detallar las distintas estructuras, veamos como funciona la aplicación a partir de una matriz de adyacencia o de un array de nodos en formato JSON. En la Figura vemos un grafo creado con la matriz de adyacencia que vemos a continuación:
[[0, 0, 0, 0, 1], [1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [0, 1, 0, 0, 1], [0, 1, 1, 0, 0]]
Como vemos en la Figura, en el área superior de texto de la aplicación podemos poner esa matriz de adyacencia o bien un objeto JSON "Nodos" en el formato de la aplicación. El JSON de ese grafo es el siguiente, donde se observa que contiene dos objetos: nodes que es un Array de nodos y config que es un objeto con las propiedades de la configuración. Las propiedades que no se incluyan se tomarán de las predeterminadas.
{"nodes":[
{"index":0,"parent":[{"index":-1},{"index":4}]},
{"index":1,"parent":[{"index":0}]},
{"index":2,"parent":[{"index":0},{"index":1}]},
{"index":3,"parent":[{"index":1},{"index":4}]},
{"index":4,"parent":[{"index":1},{"index":2}]}
],
"config":{
"markerEnd":"arrow"
}}La estructura JSON de un nodo, como el nodo "0" del grafo anterior, es {"index":0, "parent": [{"index": -1}, {"index": 4}]}, donde parent es un array que contiene los nodos adonde apunta el nodo "0", es decir, el nodo "0" apunta a los padres "-1" y "4", siendo "-1" el indicativo de que es el raíz, pues en todo grafo debe haber al menos un nodo raíz que se ubica en la parte superior. Y el nodo "0" también apunta al nodo "4", con lo que la flecha estará ubicada al final de la arista "0-4", lo que se establece con "makerEnd":"arrow" y "markerStart":"none", que no aparece en la configuración pues es la predeterminada.
Si copiamos solo el array nodes y lo ponemos en el área de texto (Figura), usando el botón para actualizar el grafo vemos que obtenemos el mismo pero sin las flechas, es decir, obtenemos un grafo no dirigido, cuando el que creábamos desde la matriz de adyacencia era dirigido. Esto es porque el formato JSON necesita la configuración para poder determinar la dirección del grafo. Observamos en el JSON del primer grafo la configuración "markerEnd":"arrow" que hace que las flechas apunten al final de cada arista. Mientras que para un nuevo grafo las propiedades predeterminadas son "markerStart":"none" y "markerEnd":"none", con lo que no se incluirán flechas.
La dirección de un grafo puede determinarse en la matriz de adyacencia a partir de su simetría, como se observa en la segunda matriz de las siguientes que es simétrica respecto a su diagonal.
Primer grafo dirigido: [[0, 0, 0, 0, 1], [1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [0, 1, 0, 0, 1], [0, 1, 1, 0, 0]] Segundo grafo no dirigido: [[0, 1, 1, 0, 1], [1, 0, 1, 1, 1], [1, 1, 0, 0, 1], [0, 1, 0, 0, 1], [1, 1, 1, 1, 0]]
Veamos ahora como podemos escribir de forma altenativa los parent. El array de nodos en formato JSON del grafo no dirigido es el siguiente:
[{"index":0,"parent":[{"index":-1},{"index":4}]},
{"index":1,"parent":[{"index":0}]},
{"index":2,"parent":[{"index":0},{"index":1}]},
{"index":3,"parent":[{"index":1},{"index":4}]},
{"index":4,"parent":[{"index":1},{"index":2}]}]La aplicación permite importar un grafo con la estructura de nodos en JSON simplificada en los parent. Por ejemplo el nodo "1" tiene "parent":[{"index":0}] que puede sustituirse por "parent":0, pues al importar y encontrar un número entero se entenderá que sólo hay un padre con ese índice.
[{"index":0,"parent":[{"index":-1},{"index":4}]},
{"index":1,"parent":0},
{"index":2,"parent":[0, 1]},
{"index":3,"parent":[{"index":1}, 4]},
{"index":4,"parent":[{"index":1},{"index":2}]}]E incluso sustituir [{"index":0},{"index":1}] del nodo "2" por el array [0, 1]. O sustituir [{"index":1},{"index":4}] del nodo "3" por [{"index":1}, 4] con un mezcla de objeto y número entero. En cualquier caso estos formatos sin objetos serán traspasados a {"index":...}, pues las propiedades de las aristas solo pueden incluirse en un objeto.
En la Figura vemos la opción simplificar padres al exportar el JSON del grafo anterior, simplificándose todos los parent pues sólo tienen una única propiedad "index"
{"nodes":[
{"index":0,"parent":[-1,4]},
{"index":1,"parent":0},
{"index":2,"parent":[0,1]},
{"index":3,"parent":[1,4]},
{"index":4,"parent":[1,2]}
],
"config":{
}}Exportar e importar grafos
En la Figura vemos un grafo que vamos a usar como muestra en este apartado, cuyo JSON es el que sigue. Se trata de un grafo dirigido con valores en los nodos y en las aristas. Si tiene valores numéricos en las aristas suele denominarse grafo ponderado.
{"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","parent":[{"index":1,"value":40},{"index":4,"value":"X"}]},
{"index":4,"value":"E","parent":[{"index":1,"value":50},{"index":2,"value":60}]}
],
"config":{
"markerEnd":"arrow"
}}
En la Figura vemos que podemos exportar al tipo JSON anterior. También podemos exportarlo como código SVG. Y en la parte inferior se presenta en varios tipos de imagen como ese mismo SVG, PNG, JPEG y WEBP, descargándose como imagen o bien como base 64. También puede arrastrar la imagen.
Los tipos de estructura del grafo para exportar o importar son:
- Matriz de adyacencia
- Matriz de incidencia
- Lista de adyacencia
- Lista de aristas
- Matriz de distancias
- Código Wolfram Alpha
- Código Wolfram Cloud
El modo de estructurar los datos se aplica sólo a la matriz de adyacencia y se refiere a como se codifican las posiciones de la estructura.
El formato de salida de la estructura se refiere al soporte utilizado, que puede ser CSV comma separated values, valores separados por comas, donde cada fila se separa por un salto de línea. El formato TSV se refiere a tabulation separated values, valores separados por tabulador, donde cada fila también se separa por un salto de línea. El formato SSV se refiere a space separated values, valores separados por espacio, donde cada fila también se separa por un salto de línea.
En el formato JSON tenemos las opciones simplificar padres que ya vimos en un apartado anterior y la opción omitir valores iniciales, que desactivándola nos devuelve todas las propiedades iniciales, como el siguiente JSON de un grafo con un único nodo. Hemos agregado unas líneas horizontales para separar las propiedades en los grupos SVG, nodos, líneas y algoritmos.
{"nodes":[
{"index":0,"parent":[{"index":-1}]}
],
"config":{
"wv":100,
"hv":25,
"width":250,
"height":62.5,
"adjust":true,
"wvIni":100,
"lineHeight":25,
"precision":2,
"lang":"es",
"className":"",
"style":"",
"rulesCss":"",
"xmlns":"http://www.w3.org/2000/svg",
"nodeValue":"",
"nodeValueAuto":"index",
"nodeOrder":"none",
"nodeRadius":-1,
"nodeColor":"white",
"nodeBorderColor":"currentcolor",
"nodeBorderWidth":1,
"nodeFontFamily":"Arial",
"nodeFontSizeAdjusted":false,
"nodeFontColor":"currentcolor",
"nodeFontItalic":false,
"nodeFontBold":false,
"nodeOffset":"0",
"nodeComment":"",
"presetLevel":-1,
"lineValue":"",
"lineColor":"currentcolor",
"lineFontFamily":"Arial",
"lineFontColor":"currentcolor",
"lineFontItalic":false,
"lineFontBold":true,
"lineWidth":1,
"lineType":"rect",
"lineOffset":"0",
"lineTextOffset":"0",
"lineTextPosition":"middle central",
"lineTextStroke":true,
"lineDash":0,
"lineComment":"",
"markerStart":"none",
"markerEnd":"none",
"markerSize":2,
"markerReverse":false,
"showSelfLoops":true,
"algorithm":"none",
"maxIter":10000,
"pathColor":"red",
"textColor":"blue",
"backColor":"lightpink",
"firstIndex":0,
"lastIndex":0,
"forceUndirected":false,
"edgesCompact":false,
"ignoreSelfLoops":false,
"colorsForColoring":"red,blue,green,yellow,cyan,orange, pink,magenta,lime,brown,purple,gray,black,lavenderblush, lightgreen,lightblue,lightyellow,lightcyan,lightgray",
"initialIndexesColoring":"",
"indexesSubgraph":"",
"deleteEdgesSubgraph":"",
"adjacencyMatrix":"",
"methodIsomorphic":"Brute force all perms in order",
"initialPermutation":"",
"sizeClique":-1,
"partition":"",
"partition1":"",
"partition2":"",
"cells":"",
"numberTest":100,
"breakTest":false,
"useMcr":false,
"useImprovement1":false,
"typeCanon":"edges",
"targetCell":"max-length",
"checkEquitables":false,
"traceTree":false,
"permutation1":"",
"permutation2":""
}}
En la Figura vemos las opciones para importar un grafo. En el panel izquierdo vemos una sección para Importar marcado con "1", exclusivamente para importar el JSON de la aplicación, que incluso podemos seleccionar desde un archivo txt, actualizando el grafo con el botón .
En el panel superior marcado con "2" tenemos la sección Nodos o matriz de adyacencia que ya hemos comentado, donde podemos importar el array nodes del JSON o una matriz de adyacencia.
Dentro de la sección anterior encontramos el panel Modos marcado con el "3" y al que se accede con el botón , donde incluiremos la matriz de incidencia, la lista de adyacencia, la lista de aristas o la matriz de distancias. Tras aceptar o aplicar ese modo, se convertirá en una matriz de adyacencia traspasándose al área "2", tras lo cual puede actualizarse el grafo con el botón
Matriz de adyacencia
[[null, null, null, null, null], [10, null, null, null, null], [20, 30, null, null, null], [null, 40, null, null, "X"], [null, 50, 60, null, null]]
El tipo matriz de adyacencia admite los modos null/value, 0/number, 0/1, false/true. Cada uno de ellos puede a su vez exportarse como array, CSV, TSV, SSV.
En la Figura vemos el grafo que estamos usado como muestra para estos apartados. Con matriz adyacencia en modo-formato null/value - array, donde vemos que si no hay arista entre dos nodos se asigna null y si hay se asigna el valor de la arista. El modo null/value es el adecuado para presentar cualquier clase de valor number o string. El formato es un array tal como se escribe en JavaScript. Hay tantas filas y tantas columnas como nodos. Si i, j son los índices de dos nodos y M es la matriz de adyacencia entonces:
- Existe una arista dirigida i🡒j si M[i][j] ≠ null ∧ M[j][i] = null, por ejemplo vemos que M[1][0] = 10 ∧ M[0][1] = null entonces hay una arista 1🡒0 con valor 10.
- Existe una arista dirigida j🡒i si M[i][j] = null ∧ M[j][i] ≠ null, por ejemplo vemos que M[4][3] = null ∧ M[3][4] = "X" entonces hay una arista 3🡒4 con valor "X".
- Existe una arista doble dirigida j⟷i si M[i][j] ≠ null ∧ M[j][i] ≠ null en el caso de que todas las aristas sean dirigidas, pues en otro caso sería un grafo no dirigido, como comentamos en un apartado anterior. En el grafo de muestra no se da este caso.
- Las posiciones de la diagonal de la matriz son los autobucles, con aristas al mismo nodo, i🡒i para dirigidos o bien i-i para no dirigidos, si i = j ∧ M[i][j] ≠ null. Los autobucles no pueden ser doblemente dirigidos en la matriz de adyacencia. En el grafo de muestra no se da este caso.
Observe que las matrices de adyacencia no pueden incluir los valores de los nodos, solo los de las aristas. A vesces se usa la diagonal para incluir los valores de los nodos, pero entonces no pueden representarse los autobucles. Puede probar ese matriz de adyacencia y las siguientes en el área de texto Nodos o matriz adyacencia de la aplicación para observar que se genera el mismo grafo de muestra.
0, 0, 0, 0, 0 10, 0, 0, 0, 0 20, 30, 0, 0, 0 0, 40, 0, 0, 1 0, 50, 60, 0, 0
En la matriz adyacencia en modo-formato 0/number - csv se incluye el número 0 si no hay arista entre dos nodos y en otro caso expone el valor numérico de la arista. Si este valor no es un número, como la "X" de la arista D🡒E, entonces se incluye un 1.
0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 1 1 0 0
En la matriz adyacencia en modo-formato 0/1 - tsv se incluye números 0 si no hay arista y 1 en otro caso. Si este valor no es un número se incluye un 1. Este modo elimina los valores y solo deja constancia de la existencia de una arista entre dos nodos.
false false false false false true false false false false true true false false false false true false false true false true true false false
En la matriz adyacencia en modo-formato false/true - ssv se incluye valor false si no hay arista y true en otro caso. Si este valor no es un booleano se incluye true. Este modo es equivalente al anterior si sustituimos 0 por false y 1 por true.
Al seleccionar exportar a la matriz adyacencia, matriz incidencia, lista adyacencia, lista aristas o matriz de distancias veremos en la parte inferior un botón con el título código exportar en Wolfram Cloud, como se observa en la Figura. Nos lleva a un emergente donde se dispone el código para copiar y pegar en el área de texto de Wolfram Cloud.
El código en los modos 0/1 y false/true da como resultado este código para Wolfram Cloud, donde hemos agregado líneas horizontales para dar a entender que el código se compone de líneas separadas por salto de línea, pues hemos ajustado el texto al ancho de la pantalla:
g = AdjacencyGraph[{{0,0,0,0,0},{1,0,0,0,0},{1,1,0,0,0},{0,1,0,0,1},{0,1,1,0,0}}, ImageSize -> 250, VertexSize -> {"Scaled", 0.13}, VertexLabels -> {1 -> Placed["A",Center], 2 -> Placed["B",Center], 3 -> Placed["C",Center], 4 -> Placed["D",Center], 5 -> Placed["E",Center]}, VertexLabelStyle -> Directive[Black,17.5], EdgeLabelStyle -> Directive[Black,17.5,Bold], EdgeLabels -> {(2->1)->10, (3->1)->20, (3->2)->30, (4->2)->40, (4->5)->"X", (5->2)->50, (5->3)->60}, VertexStyle -> White, DirectedEdges -> True, EdgeStyle -> {{Black,Thickness[0.005]}}]
Normal[AdjacencyMatrix[g]]
MatrixForm[%]Para esos modos se usa la función AdjacencyGraph[] de Wolfram para crear el grafo no ponderado, obteniéndose la matriz de adyacencia con AdjacencyMatrix[g]. Para los modos null/value y 0/number el código Wolfram es el siguiente, usándose la función WeightedAdjacencyGraph[g] para crear el grafo ponderado, obteniéndose la matriz de adyacencia ponderada con WeightedAdjacencyMatrix:
g = WeightedAdjacencyGraph[{{∞,∞,∞,∞,∞},{10,∞,∞,∞,∞},{20,30,∞,∞,∞},{∞,40,∞,∞,1},{∞,50,60,∞,∞}}, ImageSize -> 250, VertexSize -> {"Scaled", 0.13}, VertexLabels -> {1 -> Placed["A",Center], 2 -> Placed["B",Center], 3 -> Placed["C",Center], 4 -> Placed["D",Center], 5 -> Placed["E",Center]}, VertexLabelStyle -> Directive[Black,17.5], EdgeLabelStyle -> Directive[Black,17.5,Bold], EdgeLabels -> {(2->1)->10, (3->1)->20, (3->2)->30, (4->2)->40, (4->5)->"X", (5->2)->50, (5->3)->60}, VertexStyle -> White, DirectedEdges -> True, EdgeStyle -> {{Black,Thickness[0.005]}}]
Normal[WeightedAdjacencyMatrix[g]]
MatrixForm[%]
Cuando exportamos la matriz de adyacencia encontramos el modo auto que detecta de forma automática el modo de valores. Por ejemplo, en la Figura vemos un grafo donde todas las aristas tienen valor numérico menos la arista "D→E" que tiene valor String "X". La detección automática considera que se debe aplicar el modo null/value pues no todos los valores son números. Si cambiamos esa "X" por un número, detectará el modo 0/number. Si ninguna arista tiene valor se aplicará el modo 0/1.
Matriz de incidencia
[[-1, -1, 0, 0, 0, 0, 0], [ 1, 0, -1, -1, 0, -1, 0], [0, 1, 1, 0, 0, 0, -1], [0, 0, 0, 1, 1, 0, 0], [0, 0, 0, 0, -1, 1, 1]]
En la matriz incidencia no hay modos, solo formatos array, csv, tsv, ssv. Este ejemplo es un array con 5 filas, una para cada nodo del grafo. Y con 7 columnas, una para cada arista del grafo. Detallamos a continuación el array anterior con cabeceras de filas y columnas y el grafo de muestra otra vez para explicar mejor la estructura de esta matriz de incidencia.
k 0 1 2 3 4 5 6
i,j B🡒A C🡒A C🡒B D🡒B D🡒E E🡒B E🡒C
-------------------------------------------------
0 A -1 -1 0 0 0 0 0
1 B 1 0 -1 -1 0 -1 0
2 C 0 1 1 0 0 0 -1
3 D 0 0 0 1 1 0 0
4 E 0 0 0 0 -1 1 1En la Figura volvemos a reproducir el grafo de muestra desde el que hemos exportado la matriz de incidencia, para explicar mejor esta parte.
Si i, j son dos filas de la matriz de adyacencia y k es una columna de la matriz de incidencia, hay una arista entre los nodos i🡒j si M[i][k] = 1 ∧ M[j][k] = -1.
Observando las dos primeras filas de los nodos i=0 del nodo "A" y j=1 del nodo "B" y la primera columna k=0 de la primera arista, vemos que M[0][0] = -1 y M[1][0] = 1, indicando que la primera arista sale del nodo "B" pues el valor es 1 y entra en el nodo "A" pues el valor es -1, con lo que tenemos la arista B🡒A. El resto de la columna son ceros, de tal forma que en cada columna sólo hay dos posiciones, pues las aristas que entran en un nodo deben cancelarse con las que salen del otro nodo.
Vea que no es necesaria ninguna cabecera de columna, por ejemplo, en la última columna tenemos un 1 en la fila "E" y un -1 en la fila "C", así que la arista es E🡒C, en la dirección +1 🡒 -1. Podría usarse el criterio inverso, con la dirección -1 🡒 +1, opción que está disponible en la aplicación como explicamos más abajo. Así como usar números para valores de aristas, con la dirección +n 🡒 -n, pero esta opción no se contempla en la aplicación.
En la Figura se observa el grafo obtenido desde la matriz de incidencia, igual que el anterior sólo que no tiene los nodos ni las aristas etiquetadas, pues la matriz de incidencia no lo permite.
Otra posibilidad de etiquetar las aristas podrías ser agregando una primera fila a la matriz de incidencia con los valores de la aristas. Y una primera columna con las etiquetas de los nodos. Pero la aplicación no contempla esto.
Un autobucle como i🡒i supone que M[i][k] = -2, entendiendo que sale del nodo y entra en el mismo nodo, como se observa en la Figura, donde al JSON inicial agregamos un autobucle en el nodo 2 y una arista doble 3⟷4.Esta es la matriz de incidencia en formato SSV:
-1 -1 0 0 0 0 0 0 0 1 0 -1 0 -1 0 -1 0 0 0 1 1 -2 0 0 0 -1 0 0 0 0 0 1 1 0 0 -1 0 0 0 0 0 -1 1 1 1
Recordando que 3⟷4 realmente son dos aristas 3🡒4 y 4🡒3, antes teníamos 7 columnas y ahora tenemos 9, pues hemos agregado el autobucle que aparece en la cuarta columna y una segunda arista 4🡒3 en la última columna.
En un grafo no dirigido todos los valores son positivos, como el de la Figura cuya matriz de incidencia es la siguiente:
[[2, 1, 0, 0, 1, 0, 0, 0],
[0, 1, 1, 0, 0, 1, 0, 0],
[0, 0, 1, 1, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 1, 1],
[0, 0, 0, 0, 1, 1, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 1]]Se observa el "2" en la primera posición que indica el autobucle en el nodo "0".
En un grafo con n nodos y m aristas, vemos que la matriz de adyacencia tiene un tamaño de n2 y la matriz de incidencia tiene un tamaño de n×m. Cuando m es mucho menor que n, es obvio que la matriz de incidencia ocupará menos espacio de almacenamiento.
El código Wolfram para obtener la matriz de incidencia del grafo dirigido de muestra del inicio de este apartado es el siguiente, donde observamos que se obtiene con [IncidenceMatrix[g]]
g = AdjacencyGraph[{{0,0,0,0,0},{1,0,0,0,0},{1,1,0,0,0},{0,1,0,0,1},{0,1,1,0,0}}, ImageSize -> 250, VertexSize -> {"Scaled", 0.13}, VertexLabels -> {1 -> Placed["A",Center], 2 -> Placed["B",Center], 3 -> Placed["C",Center], 4 -> Placed["D",Center], 5 -> Placed["E",Center]}, VertexLabelStyle -> Directive[Black,17.5], EdgeLabelStyle -> Directive[Black,17.5,Bold], EdgeLabels -> {(2->1)->10, (3->1)->20, (3->2)->30, (4->2)->40, (4->5)->"X", (5->2)->50, (5->3)->60}, VertexStyle -> White, DirectedEdges -> True, EdgeStyle -> {{Black,Thickness[0.005]}}]
Normal[IncidenceMatrix[g]]
MatrixForm[%]
Recordamos que obtuvimos esta matriz de incidencia que está al inicio de esta apartado:
[[-1, -1, 0, 0, 0, 0, 0], [1, 0, -1, -1, 0, -1, 0], [0, 1, 1, 0, 0, 0, -1], [0, 0, 0, 1, 1, 0, 0], [0, 0, 0, 0, -1, 1, 1]]
Y Wolfram ofrece la siguiente matriz de incidencia para el mismo grafo (los vectores y matrices se encierran con llaves en lugar de corchetes):
{{1, 1, 0, 0, 0, 0, 0},
{-1, 0, 1, 1, 0, 1, 0},
{0, -1, -1, 0, 0, 0, 1},
{0, 0, 0, -1, -1, 0, 0},
{0, 0, 0, 0, 1, -1, -1}}Se observa que son los mismos valores con signo contrario, pues nosotros considerábamos que un valor +1 es que una arista sale de un nodo y -1 que entra, mientras que Wolfram considera lo contrario. En la Figura vemos un recorte de Wikipedia Incidence Matrix, observando que Wolfram usa ese criterio, pero también se anota que muchos autores usan la convención de signo contraria
.
El cambio de signo significa cambiar la direccionalidad del grafo. Para dar la posibilidad de exportar con uno u otro signo, agregamos la opción signo salida/entrada, como se observa en la Figura, usando la opción contraria -1 sale, +1 entra vemos que se obtiene la misma matriz que la de Wolfram.
En la Figura vemos que podemos importar la matriz de incidencia con signo opuesto -1 sale, +1 entra, obteniéndose el mismo grafo de muestra original.
Lista de adyacencia
En la lista de adyacencia no hay modos, solo formatos array, csv, tsv, ssv. En la Figura vemos como exportamos a este tipo en formato array.
[[-1], [0], [0, 1], [1, 4], [1, 2]]
En la Figura vemos el grafo de muestra que estamos exportando. La matriz tiene tantas filas como nodos del grafo. Cada fila es una array con los nodos que son adyacentes al nodo dado, es decir, cada fila es un lista de adyacencias. Como el grafo es dirigido y el nodo 0 ("A") no apunta a ningún nodo, se agrega -1 para indicar que es un nodo raíz. Como ejemplo, el nodo 4 ("E") apunta a los nodos 1 ("B") y 2 ("C") y por tanto su lista de adyacencia es [1, 2].
En la Figura vemos el grafo creado con esa lista de adyacencia, igual que la muestra pero sin etiquetas de nodos o aristas, pues la lista de adyacencia no puede representar esas etiquetas.
Al exportar la lista de adyacencia podemos marcar la opción vecinos, exportándose los vecinos de cada nodo, tanto padres como hijos. Este es lo que obtenemos:
1 2 0 2 3 4 0 1 4 1 4 1 2 3
En la Figura vemos como se importa esa lista de adyacencia, que es un grafo no dirigido pues cada nodo tiene enlaces a los padres y a los hijos.
Wolfram usa la misma configuración de vecinos para obtener la lista de adyacencia, como puede ver en Wolfram Adjacency List. Este es el código a ejecutar en Wolfram Cloud usando la función AdjacencyList[g]:
g = AdjacencyGraph[{{0,0,0,0,0},{1,0,0,0,0},{1,1,0,0,0},{0,1,0,0,1},{0,1,1,0,0}}, ImageSize -> 250, VertexSize -> {"Scaled", 0.13}, VertexLabels -> {1 -> Placed[0,Center], 2 -> Placed[1,Center], 3 -> Placed[2,Center], 4 -> Placed[3,Center], 5 -> Placed[4,Center]}, VertexLabelStyle -> Directive[Black,17.5], EdgeLabelStyle -> Directive[Black,17.5,Bold], VertexStyle -> White, DirectedEdges -> True, EdgeStyle -> {{Black,Thickness[0.005]}}]
AdjacencyList[g]
{{2,3},
{1,3,4,5},
{1,2,5},
{2,5},
{2,3,4}}El resultado es el mismo que con nuestra opción vecinos activada, teniendo en cuenta que en Wolfram los nodos se enumeran desde 1 y en la aplicación se hace desde 0. La lista de adyacencia con opción vecinos es una forma de obtener los vecinos de un nodo, algo que también se puede hacer con el algoritmo getNeighbors({matrix, index}) que puede encontrar en la sección de algoritmos y que explicamos en un tema posterior, iterando por todos los nodos del grafo obtendríamos la misma lista de adyacencia.
Lista de aristas
En la lista de aristas no hay modos, solo formatos array, csv, tsv, ssv. A diferencia de los tipos anteriores, ahora vemos las opciones con raíz, ordenado y no dirigido compacto que luego explicaremos.
Se trata de un array con una lista de aristas en formato [i, j], que para un grafo dirigido indica una arista en la dirección i🡒j, con la flecha siempre desde la primera posición a la segunda posición de ese array. La dirección contraria j🡒i sería [j, i]. En caso de ser doblemente dirigida se incluirían ambos [i, j], [j, i]. Un autobucle i🡒i se expresaría con [i, i]. La arista [i, -1] indica un nodo raíz.
En la Figura vemos el grafo de muestra desde donde exportamos la lista de aristas [[0, -1], [1, 0], [2, 0], [2, 1], [3, 1], [3, 4], [4, 1], [4, 2]], una lista de arrays con dos posiciones para los dos nodos de cada arista.
En la Figura vemos el grafo creado con esa lista de aristas, igual que la muestra pero sin etiquetas de nodos o aristas, pues la lista de aristas no puede representar esas etiquetas.
En Figura vemos el mismo grafo pero no dirigido y al que le hemos agregado un autobucle. La lista de aristas con la opción con raíz activada y con las opciones ordenado y no dirigido compacto desactivadas es [[0, -1], [1, 0], [0, 1], [2, 0], [0, 2], [2, 1], [1, 2], [2, 2], [2, 2], [3, 1], [1, 3], [4, 1], [1, 4], [4, 2], [2, 4], [4, 3], [3, 4]]. Se observa que, al ser dirigido, encontramos la arista 0-1 como [1, 0], [0, 1]. Y el autobucle aparece como [2, 2], [2, 2].
Si activamos no dirigido compacto obtenemos [[0, -1], [0, 1], [0, 2], [1, 2], [2, 2], [1, 3], [1, 4], [2, 4], [3, 4]], observando que la arista 0-1 se presenta solo con [0, 1] obviando [1, 0]. Pero cuando importemos esa lista en el panel de modos de la parte superior de la aplicación, como se observa en la Figura, hemos de activar la opción no dirigido compacto (Para lista aristas), pues en otro caso se entendería como un grafo dirigido.
La opción con raíz agrega [0, -1] y la opción ordenado solo tiene efecto en el orden de las aristas en la lista de salida. Si exportamos sin raíz y ordenado, la lista es [[0, 1], [0, 2], [1, 2], [1, 3], [1, 4], [2, 2], [2, 4], [3, 4]], donde cada arista [i, j] se ordena por por el primer nodo i y cuando los primeros nodos son iguales se ordenan por el segundo nodo j. Vemos que no se exporta el nodo raíz [0, -1] pues en el fondo no es necesario para presentar el grafo, así como el orden tampoco afecta a esa presentación.
En Wolfram Cloud exportamos la lista de aristas con EdgeList. Veamos como exportamos el grafo de muestra del inicio de este apartado:
g = AdjacencyGraph[{{0,0,0,0,0},{1,0,0,0,0},{1,1,0,0,0},{0,1,0,0,1},{0,1,1,0,0}}, ImageSize -> 250, VertexSize -> {"Scaled", 0.13}, VertexLabels -> {1 -> Placed["A",Center], 2 -> Placed["B",Center], 3 -> Placed["C",Center], 4 -> Placed["D",Center], 5 -> Placed["E",Center]}, VertexLabelStyle -> Directive[Black,17.5], EdgeLabelStyle -> Directive[Black,17.5,Bold], EdgeLabels -> {(2->1)->10, (3->1)->20, (3->2)->30, (4->2)->40, (4->5)->"X", (5->2)->50, (5->3)->60}, VertexStyle -> White, DirectedEdges -> True, EdgeStyle -> {{Black,Thickness[0.005]}}]
EdgeList[g]En las siguientes la primera línea es la lista de aristas de Wolfram y la segunda es la de la aplicación, siendo iguales a excepción de que Wolfram enumera desde 1 y la aplicación desde 0:
{2⟶1, 3⟶1, 3⟶2, 4⟶2, 4⟶5, 5⟶2, 5⟶3}
[1, 0], [2, 0], [2, 1], [3, 1], [3, 4], [4, 1], [4, 2]]Recuerde que en un grafo dirigido y en nuestra aplicación algo como [1, 0] significa 1⟶0 y [0, 1] significa 0⟶1. Si es no dirigido ambas significarán lo mismo 1-0 o 0-1 indistintamente.
Matriz de distancias
[[0, ∞, ∞, ∞, ∞], [10, 0, ∞, ∞, ∞], [20, 30, 0, ∞, ∞], [50, 40, 61, 0, 1], [60, 50, 60, ∞, 0]]
En el tipo matriz de distancias no hay modos, solo formatos array, csv, tsv, ssv. Para un grafo ponderado con n nodos, se trata de una matriz con tamaño n × n, donde cada posición entre dos nodos i, j es M[i][j] = ∞ si no hay arista entre ellos. En otro caso será M[i][j] = m, siendo m la suma de pesos del camino mínimo desde i hasta j. Si i=j entonces M[i][j] = 0.
Si la etiqueta de la arista no es un valor numérico, se le asigna peso 1, como es el caso de la arista D🡒E (valor "X") en el grafo de muestra de la Figura que estamos usando en estos apartados y del que exportamos la matriz de distancias anterior. Como ejemplo vemos la última fila de la matriz de distancias [60, 50, 60, ∞, 0] correspondiente al último nodo "E", donde el camino mínimo para llegar al primer nodo "A" es a través de "B" con un peso acumulado de 50+10=60, pues a través de "C" el peso es superior (60+20=80).
En la Figura vemos las opciones para exportar a matriz de distancias que vamos a explicar a continuación.
Con la opción reemplazar Infinity con ∞, en caso de estar activada se usará el caracter ∞ en lugar del valor de JavaScript Infinity que expresa un número infinito. Pero realmente la aplicación devuelve la matriz con valores Infinity. Para importar podemos usar Infinity o ∞ indistintamente. Con las matrices que importamos en formato de texto usamos JSON.parse() para convertirlas en un array. JSON no soporta el valor numérico Infinity y lo reemplazamos por 1e309, pues en JavaScript Infinity ≥ 1.7976931348623159e+308, como puede ver en el tema dónde empieza Infinity.
Para encontrar el camino mínimo usaremos la opción algoritmo, entre los que podemos elegir el algoritmo de Dijkstra de caminos mínimos o el o algoritmo de Floyd para descubrir los caminos mínimos, temas que ya publiqué en el año 2020 y que ahora he integrado en la aplicación, en la sección de algoritmos. Los dos producen el mismo resultado, como es de esperar.
[[0, ∞, ∞, ∞, ∞], [1, 0, ∞, ∞, ∞], [1, 1, 0, ∞, ∞], [2, 1, 2, 0, 1], [2, 1, 1, ∞, 0]]
Con la opción omitir pesos obtenemos la matriz de distancias adjunta a este párrafo usando el grafo ponderado de muestra. En este caso se supone que todas las aristas tiene peso unitario. La definición que pusimos en el primer párrafo podría sutituirse para cuando el valor de una posición i, j es distinto de infinito siendo M[i][j] = m, pudiendo considerar m como la distancia en nodos a recorrer desde el nodo i al nodo j. O bien m nos indica a cuántos nodos están separados i, j.
Vemos en la Figura como se importa el grafo de la matriz de distancias anterior de un grafo no ponderado, o bien exportado sin considerar los pesos. Es el mismo grafo que el de muestra sin etiquetas de nodos o de aristas (pesos). Se trata de cambiar cada posición M[i][j] > 1 por un cero, quedándonos la matriz de adyacencia que da lugar a ese grafo:
[[0, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [0, 1, 0, 0, 1], [0, 1, 1, 0, 0]]
Una posición en la matriz de distancias no ponderada en un nodo con valor mayor que 1 y no infinito en una columna, significa que ese nodo no está conectado directamente con el nodo de la columna, pues si es 2, por ejemplo, tendrá que recorrer 2 nodos para llegar. Así que sólo los 1 de la matriz de distancias configuran las aristas de la matriz de adyacencia resultante. Si es infinito es que no hay arista y eso equivale también a un 0 en la matriz de adyacencia.
No es posible importar desde una matriz de distancias que provenga de un grafo ponderado, al menos de una forma simple que yo conozca.
[[0, ∞, ∞, ∞, ∞], [10, 0, ∞, ∞, ∞], [20, 30, 0, ∞, ∞], [50, 40, 61, 0, 1], [60, 50, 60, ∞, 0]]
Recordando la primera matriz de distancias adjunta que obtuvimos en este apartado, intentaremos importarla.
[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 1], [0, 0, 0, 0, 0]]
Al hacer la misma sustitución M[i][j] > 1 por un cero nos quedará la matriz de adyacencia adjunta, con un único 1, dando por resultado el grafo de la Figura que no representa el grafo de origen pues faltan el resto de aristas.
En la Figura vemos como se exporta el grafo de muestra en Wolfram Cloud, cuya matriz coincide con la que obtuvimos más arriba con la opción de omitir pesos activada:
[[0, ∞, ∞, ∞, ∞], [1, 0, ∞, ∞, ∞], [1, 1, 0, ∞, ∞], [2, 1, 2, 0, 1], [2, 1, 1, ∞, 0]]
Este es el código Wolfram para obtener la matriz de distancias con el uso de la función GraphDistanceMatrix[g] obteniéndose la forma de matriz de la Figura con la función MatrixForm[%]:
g = AdjacencyGraph[{{0,0,0,0,0},{1,0,0,0,0},{1,1,0,0,0},{0,1,0,0,1},{0,1,1,0,0}}, ImageSize -> 250,
VertexSize -> {"Scaled", 0.13}, VertexLabels -> {1 -> Placed["A",Center], 2 -> Placed["B",Center],
3 -> Placed["C",Center], 4 -> Placed["D",Center], 5 -> Placed["E",Center]}, VertexLabelStyle -> Directive[Black,17.5],
EdgeLabelStyle -> Directive[Black,17.5,Bold], EdgeLabels -> {(2->1)->10, (3->1)->20, (3->2)->30, (4->2)->40, (4->5)->"X", (5->2)->50, (5->3)->60},
VertexStyle -> White, DirectedEdges -> True, EdgeStyle -> {{Black,Thickness[0.005]}}]
GraphDistanceMatrix[g, Method->"Dijkstra"]
MatrixForm[%]
Desactivando la opción omitir pesos exportamos a Wolfram obteniendo la misma matriz que nuestra aplicación:
[[0, ∞, ∞, ∞, ∞], [10, 0, ∞, ∞, ∞], [20, 30, 0, ∞, ∞], [50, 40, 61, 0, 1], [60, 50, 60, ∞, 0]]
g = WeightedAdjacencyGraph[{{∞,∞,∞,∞,∞},{10,∞,∞,∞,∞},{20,30,∞,∞,∞},{∞,40,∞,∞,1},{∞,50,60,∞,∞}},
ImageSize -> 250, VertexSize -> {"Scaled", 0.13}, VertexLabels -> {1 -> Placed["A",Center],
2 -> Placed["B",Center], 3 -> Placed["C",Center], 4 -> Placed["D",Center], 5 -> Placed["E",Center]},
VertexLabelStyle -> Directive[Black,17.5], EdgeLabelStyle -> Directive[Black,17.5,Bold],
EdgeLabels -> {(2->1)->10, (3->1)->20, (3->2)->30, (4->2)->40, (4->5)->"X", (5->2)->50, (5->3)->60},
VertexStyle -> White, DirectedEdges -> True, EdgeStyle -> {{Black,Thickness[0.005]}}]
GraphDistanceMatrix[g, Method->"Dijkstra"]
MatrixForm[%]Wolfram Alpha
Podemos exportar a Wolfram Alpha, como se observa en la Figura. No todas las características están disponibles, como por ejemplo las etiquetas de las aristas o la ubicación de las etiquetas de los nodos y su estilo.
Recordamos que el grafo original es el de la Figura.
La aplicación ofrece un enlace a Wolfram Alpha que nos ejecutará la presentación del grafo. El código que se ejecutará es el siguiente:
AdjacencyGraph[{{0,0,0,0,0},{1,0,0,0,0},{1,1,0,0,0},{0,1,0,0,1},{0,1,1,0,0}}, VertexSize -> 0.2, VertexLabels -> {1 -> "A", 2 -> "B", 3 -> "C", 4 -> "D", 5 -> "E"}]
Wolfram Cloud
También podemos exportar a Wolfram Cloud, que es una herramienta para ejecutar código Wolfram de uso gratuito para hacer pequeñas pruebas, tras darse de alta. Vemos la ejecución en la Figura, donde ahora es posible adaptar más cosas que con Wolfram Alpha.
La disposición de los nodos es opuesta a nuestro grafo que hemos reproducido otra vez en la Figura, pero se trata del mismo grafo.
El código Wolfram Cloud que se obtiene es el siguiente, observando que es una sentencia sin saltos de línea. Debemos copiar ese código y pegarlo en el área de trabajo de Wolfram Cloud para su ejecución.
g = AdjacencyGraph[{{0,0,0,0,0},{1,0,0,0,0},{1,1,0,0,0},{0,1,0,0,1},{0,1,1,0,0}}, ImageSize -> 250, VertexSize -> {"Scaled", 0.08}, VertexLabels -> {1 -> Placed["A",Center], 2 -> Placed["B",Center], 3 -> Placed["C",Center], 4 -> Placed["D",Center], 5 -> Placed["E",Center]}, VertexLabelStyle -> Directive[Black,17.5], EdgeLabelStyle -> Directive[Black,17.5,Bold], EdgeLabels -> {(2->1)->10, (3->1)->20, (3->2)->30, (4->2)->40, (4->5)->"X", (5->2)->50, (5->3)->60}, VertexStyle -> White, DirectedEdges -> True, EdgeStyle -> {{Black,Thickness[0.005]}}]
Hay varias opciones para configurar la exportación, como ocultar resultados previos que activado añade un punto y coma a final de cada sentencia, pues en Wolfram Cloud cada sentencia se reproduce visualmente, dando la posibilidad de ocultar su presentación visual y solo ofrecer aquellas que no tengan un punto y coma al final.
Las otras opciones son ajustar tamaño de vértices y ajustar tamaño texto, ambos factores sobre la unidad, si es menor se reduce y si es mayor se incrementa, en ambos casos respecto a lo que usa Wolfram Cloud.
Convertir a matriz de adyacencia convertToAdjacencyMatrix()
En la aplicación, tenemos la función convertToAdjacencyMatrix() que recibe una lista de aristas (edgeList), lista de adyacencia (adjacencyList), matriz de incidencia (incidenceMatrix) o matriz de distancias (distanceMatrix) y la convierte en una matriz de adyacencia.
function convertToAdjacencyMatrix({array=[], mode="edgeList", compactUndirected=false,
signIncidence=1}) {
let dev = {error: "", matrix: []}, temp;
try {
if (mode==="edgeList") {
if (array.some(v => !Array.isArray(v) || v.length!==2))
throw new Error(`Some array does not have length 2`);
let vertexs = [...new Set(array.flat())].sort().filter(v => v>-1).map(v => +v);
let n = vertexs.length;
if (vertexs.every((v, i) => i===0 || v[i]===v[i-1]+1))
throw new Error(`Vertices are not correlative`);
let vertexsNum = vertexs.filter(v => v>-1);
if (![0,1].includes(vertexsNum[0]))
throw new Error(`The first vertex is not 0 or 1`);
if (vertexs[0]===1) {
for (let i=0; i<array.length; i++) {
for (let j=0; j<array.length; j++) {
if (array[i][j]>0) array[i][j]--;
}
}
}
dev.matrix = Array.from({length:n}, () => Array.from({length:n}, () => 0));
for (let k=0; k<array.length; k++) {
let [i, j] = array[k];
if (j>-1) {
dev.matrix[i][j] = 1;
if (compactUndirected) {
dev.matrix[j][i] = 1;
}
}
}
} else if (mode==="adjacencyList") {
let n = array.length;
let m = Math.max(...array.flat())+1;
if (m!==n) throw new Error(`The array does not have the expected length (${m})`);
dev.matrix = Array.from({length: m}, () => Array.from({length: m}, () => 0));
for (let i=0; i<n; i++) {
for (let k=0; k<array[i].length; k++) {
let j = array[i][k];
if (j>-1) dev.matrix[i][j] = 1;
}
}
} else if (mode==="incidenceMatrix") {
let n = array.length;
let m = array[0].length;
let directed = array.flat().some(v => v===-1);
let edges = [];
for (let j=0; j<m; j++){
let edge = directed ? [-1, -1] : [];
for (let i=0; i<n; i++) {
if (directed) {
if (array[i][j]===-1*signIncidence) {
edge[1] = i;
} else if (array[i][j]===1*signIncidence) {
edge[0] = i;
} else if (array[i][j]===2*signIncidence) {
edge = [i, i];
} else if (array[i][j]===-2*signIncidence) {
edge = [i, i];
}
if (edge[0]>-1 && edge[1]>-1) break;
} else if (array[i][j]!==0) {
edge.push(i);
if (array[i][j]===2) edge.push(i);
if (edge.length===2) break;
}
}
edges.push(edge);
}
temp = convertToAdjacencyMatrix({array:edges, mode:"edgeList",
compactUndirected:!directed});
if (typeof temp==="string") throw new Error(temp);
dev.matrix = temp.matrix;
} else if (mode==="distanceMatrix") {
let n = array.length;
dev.matrix = Array.from({length:n}, () => Array.from({length:n}, () => 0));
for (let i=0; i<n; i++) {
for (let j=0; j<n; j++) {
if (i!==j) {
let d = array[i][j];
dev.matrix[i][j] = (d===Infinity || d==="∞") ? 0 : d===1 ? 1 : 0;
}
}
}
}
} catch(e) {dev.error = `#Error convertToAdjacencyMatrix(): ${clean(e.message)}`}
return dev;
}Multigrafos y las limitaciones de la matriz de adyacencia
En el apartado anterior vimos que no es representable la matriz de adyacencia de un grafo dirigido con todas las aristas dobles. Pero si cuando no todas sean dobles. En la Figura usamos la última matriz de adyacencia que expusimos en el apartado anterior obteniendo ese grafo con una arista doble 3⟷4":
0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 1 1 1 0
La aplicación determina el tipo de grafo, presentando que es un grafo dirigido y multigrafo, con múltiples aristas. Esta información se deduce del JSON y no de la matriz de adyacencia.
En la sección de muestras de la aplicación encontrará el grafo de la Figura que puede importar. Se trata de un grafo creado en la aplicación con el formato JSON, no dirigido, multigrafo con múltiples aristas y autobucles. La matriz de adyacencia es [[1, 1], [1, 1]], que no representa el grafo:
Si usamos esa matriz para crear un grafo nuevo obtenemos el que vemos en la Figura, no pudiendo representarse en la matriz de adyacencia múltiples aristas ni múltiples autobucles en un grafo no dirigido.
Y tampoco en un grafo dirigido, como el de la Figura creado también usando el JSON de la aplicación, que devuelve la misma matriz de adyacencia [[1, 1], [1, 1]].
Forzando a dirigido arriba el grafo de la Figura con esa matriz de adyacencia vemos que no reproduce todas las aristas.
Como hemos visto, la matriz de adyacencia tiene algunas limitaciones, pero en general suele ser la mejor forma de sustentar la estructura de un grafo. De hecho la uso para todo el conjunto de operaciones sobre grafos, generar nuevos grafos y todos los algoritmos que se ejecutan sobre grafos, aspectos que comentaré en algún tema posterior. El motivo de usar la matriz de adyacencia para operar sobre la estructura del grafo es que, por un lado, es ampliamente reconocida y utilizada, y por otro lado, los algoritmos que presento basados en la matriz de adyacencia pueden ser usados por terceros sin necesidad de implementar el JSON de la aplicación.