Mejoras aplicación grafos (2)
Nuevos tipos para importar y exportar grafos
Agregamos nuevos tipos para exportar e importar un grafo como DIMACS, DREADNAUT, GRAPH6, SPARSE6 y DIGRAPH6, como se observa en la Figura para la exportación y en la Figura para la importación.
Para el tipo DIMACS puede consultar como se construyen en la web The graph file format (DIMACS), página de la aplicación Bliss.
La aplicación nauty and Traces contiene grafos de ejemplos en el formato DIMACS y también en DREADNAUT, del que puede consultar un manual en la sección User's guide, donde también se encuentra la especificación de GRAPH6, SPARSE6 y DIGRAPH6. En la web House of Graphs también hay grafos de ejemplos en esos formatos.
Puede probar esos nuevos tipos en la aplicación Grafos SVG como vemos en la Figura y en la Figura. Y también en la siguiente aplicación que usa el código JavaScript y muestras que se acceden con el botón que veremos en siguientes apartados.
Import/export Dimacs, Dreadnaut, Graph6, Sparse6 and Digraph6
Tipo DIMACS para importar y exportar grafos
p edge 6 14 e 1 2 e 1 3 e 2 1 e 2 3 e 2 5 e 3 1 e 3 2 e 3 4 e 4 3 e 4 6 e 5 2 e 5 6 e 6 4 e 6 5
En la Figura vemos las opciones para exportar al tipo DIMACS. El grafo no dirigido de la Figura se exporta sin activar la opción no dirigido compacto como se observa en la Figura. Se trata de una lista de aristas, donde en la primera línea encontramos "p edge 6 14", siendo siempre "p edge" invariable para este cometido. Los números a continuación son el número de nodos 6 y el número de aristas 14.
A continuación vemos entradas como la primera "e 1 2" significando "e" una arista (de "edge") y los números 1 2 es la arista [1, 2] con índices en base 1 significando que los índices se inician en 1, así que esa será la arista [0, 1] en base 0. Vemos que esa lista de aristas puede obtenerse con la estructura lista de aristas [[0,1],[0,2],[1,0],[1,2],[1,4],[2,0],[2,1],[2,3],[3,2],[3,5],[4,1],[4,5],[5,3],[5,4]] que se devuelven en base 0.
p edge 6 7 e 1 2 e 1 3 e 2 3 e 2 5 e 3 4 e 4 6 e 5 6
Si el grafo es no dirigido y activamos la opción no dirigido compacto evitamos las aristas inversas, pues para un grafo no dirigido la arista 0-1 y 1-0 es la misma así que obviamos la segunda. El DIMACS obtenido se corresponde con la lista de aristas [[0,1],[0,2],[1,2],[1,4],[2,3],[3,5],[4,5]] en base 0 que manejamos en la aplicación con la opción no dirigido compacto activada.
En la Figura vemos como Wolfram exporta a DIMACS usando ExportString[g, "DIMACS"]. Observamos que Wolfram añade dos primeras líneas con comentarios, iniciándose con la letra "c", siendo el resto del texto igual que lo que obtuvimos antes.
Nuestra aplicación nos devuelve el código siguiente para ejecutar en Wolfram Cloud.
g = AdjacencyGraph[{{0,1,1,0,0,0},{1,0,1,0,1,0},{1,1,0,1,0,0},{0,0,1,0,0,1},{0,1,0,0,0,1},{0,0,0,1,1,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], 6 -> Placed[5,Center]}, VertexLabelStyle -> Directive[Black,17.5], EdgeLabelStyle -> Directive[Black,17.5,Bold],
VertexStyle -> White, EdgeStyle -> {{Black,Thickness[0.005]}}]
ExportString[g, "DIMACS"]
Si el grafo es dirigido como el de la Figura entonces la opción no dirigido compacto se ignora.
p edge 6 7 e 2 1 e 3 1 e 3 2 e 4 3 e 5 2 e 6 4 e 6 5
Se devuelve este DIMACS donde vemos la primera arista "e 2 1" que en base 0 se corresponde con la arista 1🡒0 que vemos en la Figura, no existiendo la inversa 0🡒1.
Exportar a DIMACS es tán fácil como tener previamente una lista de aristas en edgeList y el total de nodos en n:
// Export DIMACS
function exportDimacs(edgeList=[], n=0) {
let codeExport = "";
try {
edgeList = edgeList.filter(v => v[0]>-1 && v[1]>-1);
let maxn = Math.max(...edgeList.flat());
if (n-1<maxn) throw new Error(`n-1=${n-1} is less than the maximum node index ${maxn}`);
codeExport = `p edge ${n} ${edgeList.length}\n`;
for (let edge of edgeList) {
codeExport += `e ${edge[0]+1} ${edge[1]+1}\n`
}
} catch (e) {return `#ERROR ${e.message}`}
return codeExport;
}
Para importar DIMACS usaremos el panel superior de la aplicación insertando en "Modos" el texto del DIMACS del ejemplo del grafo dirigido de la Figura, desmarcando la opción no dirigido compacto que vemos en la Figura. Tras "Aceptar" ese texto veremos en el área inferior el JSON del grafo, que se importará tras actualizar con el botón
El código JavaScript para importar un DIMACS obteniendo una lista de aristas es algo más complejo, pues hemos de tener en cuenta las posibles inconformidades con el formato.
// Import DIMACS
function importDimacs(text="") {
let edgeList = [];
try {
text = text.replace(/^c.*$/gm, "").replace(/\r\n/g, "\n").replace(/\r/g, "\n").replace(/\n{2,}/g, "\n");
let arr = text.trim().split("\n");
let desc = arr[0].split(/\s+/);
if (desc.length===4) {
let [str1, str2, n, m] = desc.map(v => v.trim());
if (str1!=="p") throw new Error(`Descriptor 'p' is wrong: ${str1}`);
if (str2!=="edge") throw new Error(`Descriptor 'edge' is wrong: ${str2}`);
if (isNaN(n) || isNaN(m)) throw new Error(`Total nodes or edges in initial descriptor is wrong`);
n = +n;
m = +m;
arr = arr.slice(1).map(v => v.split(/\s+/).map(v => v.trim()));
for (let lin of arr) {
if (lin.length!==3) throw new Error("Error in a line, has not 3 positions");
if (!(lin[0]==="e" || lin[0]==="n")) throw new Error("No descriptor 'e' or 'n' in a line");
if (lin[0]==="e") { // no contemplamos líneas "n"
if (isNaN(lin[1]) || isNaN(lin[2])) throw new Error("Error in a line");
let u = +lin[1]-1;
if (u<0 || u>n-1) throw new Error(`Error in a node u ${u}`);
let v = +lin[2]-1;
if (v<0 || v>n-1) throw new Error(`Error in a node v ${v}`);
edgeList.push([u, v]);
}
}
if (edgeList.length!==m) throw new Error(`Total edges ${m} is wrong`);
let maxN = Math.max(...edgeList.flat());
if (n<maxN+1) throw new Error(`Total nodes ${n} is wrong`);
} else {
throw new Error(`Wrong length first descriptor`);
}
} catch(e) {return `#ERROR ${e.message}`}
return edgeList;
}
En primer lugar dividimos el texto DIMACS que viene en el argumento text en líneas. En este formato las líneas que empiecen con la letra "c" son comentarios, que hemos de eliminar. Entonces la primera línea será el descriptor como "p edge n m", con "p edge" como literal, siendo n y m números para el total de nodos y aristas, verificándose su corrección.
A partir de ahí las siguientes líneas serán como "e u v" con "e" como literal, siendo u y v números de índices de los nodos en base 1. Pueden haber líneas que empiecen con el literal "n" que ignoramos, pues se usan para el formato de los nodos que no contemplamos. Al final tras verificar los índices de los nodos obtenemos una lista de aristas en base 0 en la variable edgeList.
Tipo DREADNAUT para importar y exportar grafos
En la Figura vemos las opciones para exportar al tipo DREADNAUT y en la Figura el grafo no dirigido K10. La opción base 1 aparece desmarcada, con lo que los índices se referencian desde 0, apareciendo en el resultado el indicador "$=0" al inicio. Si se marca se referenciarán desde 1 indicándose con "$=1".
$=0 n=10 g 0: 1 2 3 4 5 6 7 8 9 1: 0 2 3 4 5 6 7 8 9 2: 0 1 3 4 5 6 7 8 9 3: 0 1 2 4 5 6 7 8 9 4: 0 1 2 3 5 6 7 8 9 5: 0 1 2 3 4 6 7 8 9 6: 0 1 2 3 4 5 7 8 9 7: 0 1 2 3 4 5 6 8 9 8: 0 1 2 3 4 5 6 7 9 9: 0 1 2 3 4 5 6 7 8. $$
Este es el resultado, donde en la primera línea aparece el descriptor "$=0 n=10 g" con la base 0, el número de 10 nodos y el literal "g" de grafo no dirigido que es invariable en estos casos. La última entrada tiene un punto "." al final. Y el texto se finaliza con "$$".
Cada línea que se inicia con un índice como la primera "0: 1 2 3 4 5 6 7 8 9" son los nodos adyacentes al nodo "0", pues DREADNAUT viene a ser una lista de adyacencia tal como también podemos exportar en la aplicación.
$=1 n=10 g 1: 2 3 4 5 6 7 8 9 10 2: 3 4 5 6 7 8 9 10 3: 4 5 6 7 8 9 10 4: 5 6 7 8 9 10 5: 6 7 8 9 10 6: 7 8 9 10 7: 8 9 10 8: 9 10 9: 10. $$
Activando no dirigido compacto en grafos no dirigidos como el de este ejemplo podemos ahorrarnos las aristas inversas, como este resultado en base 1. En caso de existir la arista 1-2 (en base 1) como vemos en la segunda línea podemos omitir la 2-1 en la tercera línea, pues en grafos no dirigidos ambas son indistinguibles. En grafos dirigidos esto no tiene efecto, pues la arista 1🡒2 es distinta de la 2🡒1.
En la Figura vemos un grafo dirigido y a continuación como se exporta en DREADNAUT:
$=0 n=5 d g 0: 4 1: 0 2: 0 1 3: 1 4 4: 1 2. $$
Vemos el descriptor "$=0 n=5 d g" donde ahora el literal "d" indica grafo dirigido. En este caso tomamos base 0.
En la Figura vemos como importamos el DREADNAUT del grafo dirigido anterior.
Tras aceptar el texto DREADNAUT y actualizar el grafo con el botón obtenemos el grafo de la Figura, observando que estos nuevos tipo no manejan los valores de las aristas. Por supuesto tampoco se trasladan las separaciones como la de la arista "G", que en la aplicación sólo pueden reflejarse en la estructura de datos JSON.
A continuación vemos el JavaScript para exportar a DREADNAUT:
// Export DREADNAUT
function exportDreadnaut(adjacenyList=[], n=0, directed=false, base1=false) {
let codeExport = "";
try {
let d = directed ? " d" : "";
let b = base1 ? 1 : 0;
codeExport = `$=${b} n=${n}${d} g\n`;
for (let i=0; i<adjacenyList.length; i++){
if (adjacenyList[i].length>0) {
codeExport += `${i+b}: ${adjacenyList[i].map(v => v+b).join(" ")}\n`;
}
}
codeExport += "$$";
codeExport = codeExport.replace(/(\d+:(?:\s+\d+)*)\n\$\$/g, "$1.\n$$$$");
} catch(e) {return `#ERROR ${e.message}`}
return codeExport;
}Para exportar necesitamos una lista de adyacencia adjacencyList, el número de nodos del grafo, si el grafo es dirigido y si aplicamos base 1. Al final tendremos en codeExport el texto del DREADNAUT.
Y ahora vemos el código para importar DREADNAUT:
// Import DREADNAUT
function importDreadnaut(text=""){
let result = {edgeList:[], directed:false};
try {
let lines = text.replace(/\./, "").split("\n");
if (lines[lines.length-1]==="$$");
lines.pop();
let ini = lines.shift();
if (!/^\$=[01]\s+n=\d+(?:\s+d)?\s+g$/.test(ini)) throw new Error(`Wrong first descriptor`);
let s = ini.indexOf("$=1")===0 ? 1 : 0;
for (let line of lines) {
let parts = line.split(/\s+/);
let v1 = +(parts[0].replace(":", ""));
for (let i=1; i<parts.length; i++) {
let v2 = +parts[i];
result.edgeList.push([v1-s, v2-s]);
}
}
result.directed = ini.includes("d");
} catch(e) {return `#ERROR ${e.message}`}
return result;
}Como argumento sólo necesitamos el texto en DREADNAUT, devolviéndose una lista de aristas y si el grafo es dirigido con result = {edgeList:[], directed:false}, pues una lista de aristas por si sóla no diferencia la direccionalidad del grafo.
Tipo GRAPH6 para importar y exportar grafos
En la Figura vemos el grafo de Petersen y en la Figura como lo exportamos a GRAPH6. Se obtiene el resultado de texto IheA@GUAo, donde el inicio >>graph6<< es una cabecera opcional que podemos agregar. Este tipo GRAPH6 es exclusivamente para grafos no dirigidos. Si exportamos un grafo dirigido lo tratará como no dirigido. Para grafos dirigidos veremos más abajo el tipo DIGRAPH6.
En la Figura vemos como Wolfram exporta a GRAPH6 usando ExportString[g, "Graph6"], obteniéndose el mismo resultado >>graph6<<IheA@GUAo, agregando siempre la cabecera que en nuestra aplicación es opcional.
Cuando exportamos un grafo a Wolfram tratamos de mantener los tamaños tanto del conjunto como de los círculos de los nodos, gruesos de aristas y tamaños de textos. Pero no controlamos donde se posicionan los nodos en el plano. En este caso Wolfram los ubica en otros puntos del plano.
En la Figura vemos como importamos el texto >>graph6<<IheA@GUAo en GRAPH6. Tras aceptar el texto y actualizar el grafo con el botón obtenemos el mismo grafo de Petersen inicial, que vemos en la siguiente Figura, a excepción de las posiciones de los nodos en el plano.
Podemos ajustar a círculo ese grafo con 2 círculos concéntricos como vemos en la Figura, obteniéndose exactamente el mismo grafo inicial de Petersen de la Figura.
Exportar a JavaScript en el tipo GRAPH6, SPARSE6 y DIGRAPH6 necesita una función común setInitial6() para configurar el descriptor inicial que es el mismo en los tres casos:
function setInitial6(n=0, format="graph6") {
let chars = [];
try {
if (n > 2**36-1) throw new Error(`n=${n} is greather than 2^36-1`);
chars = format==="graph6" ? [] : format==="sparse6" ? [":"] : ["&"];
let s126 = String.fromCharCode(126);
if (n<=62) {
chars.push(String.fromCharCode(n+63));
} else if (n>=63 && n<=258047) {
chars.push(s126);
let b = n.toString(2).padStart(18, "0");
for (let i=0; i<3; i++) {
chars.push(String.fromCharCode(Number(`0b${b.slice(6*i, 6*(i+1))}`) + 63));
}
} else if (n>=258048 && n<=68719476735) {
chars.push(s126, s126);
let b = n.toString(2).padStart(36, "0");
for (let i=0; i<7; i++) {
chars.push(String.fromCharCode(Number(`0b${b.slice(6*i, 6*(i+1))}`) + 63));
}
} else {
throw new Error(`Error length n for ${format}`);
}
} catch(e) {return e.message}
return chars;
}
En el capítulo 20 de la guía de usuarios de nauty and Traces vemos la especificación de GRAPH6, SPARSE6 y DIGRAPH6. Expone que el número de nodos del grafo debe exportarse tal como sigue:
Let n be an integer in the range 0-68719476735 (236-1).Examples:
- If 0 <= n <= 62, define N(n) to be the single byte n+63.
- If 63 <= n <= 258047, define N(n) to be the four bytes 126 R(x), where x is the bigendian 18-bit binary form of n.
- If 258048 <= n <= 68719476735, define N(n) to be the eight bytes 126 126 R(x), where x is the bigendian 36-bit binary form of n.
N(30) = 60+63 = 93N(12345) = N(000011 000000 111001) = 126 66 63 120N(460175067) = N(000000 011011 011011 011011 011011 011011)= 126 126 63 90 90 90 90 90
La función anterior setInitial6() implementa lo anterior. El inicio del texto tras la posible cabecera como >>>graph6<<< son 1, 4 u 8 caracteres que especifican el número de nodos del grafo.
El grafo de la Figura lo exportamos como >>graph6<<DQc y lo vamos a usar como ejemplo para explicar la exportación. Vemos que tiene n = 5 nodos entonces 5 ≤ 62 así que N(5) = 5+63 = 68, correspondiéndose con el caracter String.fromCharCode(68) que es la letra "D", usando el método estático de JavaScript que nos devuelve el carácter de un determinado código numérico. Vea que al sumar 63 los posibles caracteres van desde 0+63 = 63 ⇒ "?" hasta 63+63 = 126 ⇒ "~", caracteres que en ASCII son imprimibles, es decir, no incluyen espacios ni caracteres de control.
El rango de números binarios de 0 a 63 puede codificarse con solo 6 bits, pues 63 en binario es 111111 con 6 bits uno y el siguiente ya tiene 7 bits. Ese es el motivo de elegir 0 a 63 como dígitos de codificación y como los 6 bits dan lugar al 6 en los nombres GRAPH6, SPARSE6 y DIGRAPH6.
La siguiente función exportGraph6() exporta a GRAPH6.
// Export Graph6
// The argument matrix is of an undirected graph
function exportGraph6(matrix=[], header=false) {
let codeExport = "", temp;
try {
let n = matrix.length;
if (temp = setInitial6(n, "graph6"), typeof temp==="string") throw new Error(temp);
let chars = temp;
let bin = [];
for (let j=1; j<n; j++){
for (let i=0; i<j; i++){
bin.push(matrix[i][j]);
}
}
let m = bin.length;
let zeros = Math.ceil(m/6) * 6 - m;
bin.push(...Array.from({length: zeros}, ()=>0));
for (let i=0; i<bin.length; i+=6){
let s = bin.slice(i, i+6).join("");
let b = Number(`0b${s}`) + 63;
chars.push(String.fromCharCode(b));
}
codeExport = chars.join("");
if (header) codeExport = `>>graph6<<${codeExport}`;
} catch(e) {return `#ERROR ${e.message}`}
return codeExport;
}El argumento matrix es la matriz de adyacencia de un grafo obligatoriamente no dirigido. Si el grafo es dirigido se ignorará y lo tomará como no dirigido, pues GRAPH6 es sólo para no dirigidos. El argumento header es para agregar la cabecera opcional >>graph6<<.
0 1 2 3 4 0 0 0 1 0 1 1 0 0 0 1 0 2 1 0 0 0 0 3 0 1 0 0 1 4 1 0 0 1 0
Aquí vemos la matriz de adyacencia del grafo no dirigido de la Figura que tomaremos como ejemplo para ver el proceso de exportar a GRAPH6. En color verde vemos los índices de las filas y columnas. De esta matriz vamos a extraer los bits verticales de las columnas 1 a la 4 (en azul), resultando ser 0 10 010 1001. Vea que extraemos el triángulo superior derecho sobre la diagonal derecha de la matriz, pues al ser un grafo no dirigido esa matriz es simétrica, con lo que con una parte tenemos suficiente para definir el grafo no dirigido. Ignorar la diagonal supone que se ignoran también los autobucles.
El vector bit obtenido 0 10 010 1001 tiene m = 10 bits y ahora agregamos "0" para que sea múltiplo de 6. Para ello hacemos zeros = Math.ceil(m/6) * 6 - m = 2 con lo que tendremos que agregar 2 ceros para que tenga 12 bits, el múltipo de 6 superior más cercano, quedando 0 10 010 1001 00. A continuación los dividimos en grupos de 6 quedando 010010 100100 con 12 bits.
El siguiente paso es obtener el número decimal de cada parte de 6 bits. Así el primero es 010010 que se corresponde con el decimal 18, como podemos comprobar usando la calculadora binaria y observar en la Figura.
Le sumamos 63 quedando 18+63 = 81 que se corresponde con el caracter String.fromCharCode(68) = "Q". El segundo era 100100 que es el decimal 36 quedando 36+63 = 99 siendo el caracter String.fromCharCode(99) = "c", así que esta parte se codifica con "Qc" que junto al descriptor inicial "D" con el número de nodos queda finalmente "DQc", que si agregamos la cabecera se exporta como >>graph6<<DQc
Importar a JavaScript en el tipo GRAPH6, SPARSE6 y DIGRAPH6 necesita una función común getInitial6() para obtener el descriptor inicial que es el mismo en los tres casos:
// text whithout header
function getInitial6(text="", format="graph6") {
let result = {n: null, chars: null, firstChar: null};
try {
text = text.trim();
let car = format==="graph6" ? "" : format==="sparse6" ? ":" : "&";
if (car!=="") {
if (text.length>0 && text[0]!==car) throw new Error(`Missing '${car}'`);
text = text.substring(1);
}
result.chars = Array.from({length: text.length}, (v,i) => text.charCodeAt(i));
if (result.chars[0]<63) throw new Error(`First character is less than 63`);
if (result.chars[0]>126) throw new Error(`First character is greater than 126`);
result.n = null, result.firstChar = null;
if (result.chars[0]===126 && result.chars[1]===126){
//258048 <= n <= 68719476735 ---> 6 next bytes for R(x)
//126 126 R(x), where x is the bigendian 36-bit binary form of n. (36/6 = 6 chars)
let c = [result.chars[2], result.chars[3], result.chars[4], result.chars[5], result.chars[6], result.chars[7]].map(v => (v-63).toString(2).padStart(6, "0")).join("");
result.n = Number(`0b${c}`);
result.firstChar = 8;
} else if (result.chars[0]===126) {
//63 <= n <= 258047 ---> 3 next bytes for R(x)
//126 R(x), where x is the bigendian 18-bit binary form of n (18/6 = 3 chars)
let c = [result.chars[1], result.chars[2], result.chars[3]].map(v => (v-63).toString(2).padStart(6, "0")).join("");
result.n = Number(`0b${c}`);
result.firstChar = 4;
} else {
//0 <= n <= 62
result.n = result.chars[0]-63;
result.firstChar = 1;
}
if (result.n===null || result.firstChar===null) throw new Error(`Error in first chararacters`);
} catch(e) {return e.message}
return result;
}Esta función getInitial6() es la opuesta de setInitial6(), que ahora obtiene el total de nodos "n" desde el texto en formato GRAPH6, SPARSE6 o DIGRAPH6. Aparte de obtener el valor de n también obtenemos los códigos de todos los caracteres en chars así como la posición del primer caracter firstChar donde empiezan los datos tras ese descriptor. El texto debe venir sin la cabecera como >>graph6<< por ejemplo.
La siguiente función importGraph6() importa desde GRAPH6.
// Import Graph6
function importGraph6(text="") {
let matrix = [], temp;
try {
let reg = new RegExp(`>>graph6<<`);
text = text.replace(reg, "");
if (temp = getInitial6(text, "graph6"), typeof temp==="string") throw new Error(temp);
let {n, chars, firstChar} = temp;
let m = Math.ceil((n*(n-1)/2)/6) + firstChar;
if (chars.length!==m) throw new Error(`Length characters is wrong`);
let bin = [];
for (let i=firstChar; i<chars.length; i++){
let char = chars[i];
if (char<63) throw new Error(`There is a character smaller than 63`);
if (char>126) throw new Error(`There is a character greather than 126`);
bin.push(...(char-63).toString(2).padStart(6, "0"));
}
matrix = Array.from({length: n}, () => Array.from({length: n}, () => 0));
for (let j=1; j<n; j++){
for (let i=0; i<j; i++){
let k = +bin.shift();
matrix[i][j] = k;
matrix[j][i] = k;
}
}
} catch(e) {return `#ERROR ${e.message}`}
return matrix;
}Importando >>graph6<<DQc resultará que getInitial6() nos devuelve el objeto {n: 5, chars:[68,81,99], firstChar:1} pues el grafo tiene n=5 nodos, la cadena "DQc" tiene los códigos [68,81,99] en ASCII y el primer caracter donde empiezan los datos es el 1, es decir, los datos están en los caracteres [81,99]. Restamos 81-63=18 que en binario es "10010" y completamos hasta 6 dígitos con ceros a la izquierda quedando "010010" que agregamos al array bin = [0,1,0,0,1,0]. El siguiente es 99-63=36 en binario "100100" que ya tiene 6 dígitos y lo agregamos a bin = [0,1,0,0,1,0,1,0,0,1,0,0].
A continuación construimos una matriz de adyacencia de tamaño n×n con ceros en todas las posiciones y vamos iterando por el triángulo de la mitad superior de la matriz sin incluir la diagonal, lo mismo que hicimos al importar pero ahora trasladando cada bit de bin a la matriz de adyacencia. Esa mitad de matriz tiene 10 posiciones y en la variable bin teníamos 12 dígitos binarios, pues siempre habrán los mismos o más, desechándose los últimos que serán ceros, pues fueron los que agregamos al exportar para tener un total de bits múltiplo de 6.
Tipo SPARSE6 para importar y exportar grafos. Grafos densos y dispersos
Exportando a SPARSE6 el grafo no dirigido de la Figura obtenemos el texto >>sparse6<<:EAHi@M~, donde el caracter ":" nos permite identificar este tipo SPARSE6 en caso de que no se pase la cabecera >>sparse6<<. Recordemos que GRAPH6 exportaba desde la mitad de la matriz de adyacencia que se suponía simétrica, sin incluir los autobucles que se encuentran en la diagonal, obteniéndose >>graph6<<EhsO. Sin embargo con SPARSE6 se usa la lista de aristas permitiendo los autobucles.
Para el grafo de la Figura su lista de aristas es [[0,0],[0,1],[1,2],[2,3],[0,4],[1,4],[3,4],[3,5]] observando la arista [0,0] que es un autobucle.
En la Figura vemos la exportación en Wolfram con ExportString[g, "Sparse6"] observando que se obtiene >>sparse6<<:EAHi@M~~~ agregando dos caracteres "~~" adicionales al final, cuando nosotros obteníamos >>sparse6<<:EAHi@M~. No sé el motivo por el que Wolfram los agrega, pero en cualquier caso serán ignorados cuando importemos ese texto.
Para entender el uso de SPARSE6 tenemos que ver la diferencia entre grafos densos y dispersos (dense and sparse graphs). Un ejemplo de grafo denso es el grafo completo, como el de la Figura con 20 nodos, que tiene aristas entre todos sus n nodos con n(n-1)/2 aristas. Decimos que el número de aristas es O(n2). Es, por tanto, el tipo de grafo con el mayor número posible de aristas simples, si consideramos el grafo como no dirigido con una única arista entre cada dos nodos y sin autobucles. En este sentido es el tipo de grafo más denso posible.
Para los grafos densos es preferible usar la matriz de adyacencia, habiendo en total n2 posiciones en la matriz de adyacencia y en la mitad superior sin la diagonal hay un total de (n-1)2/2 posiciones, que siempre será menor que el total de aristas n(n-1)/2, con lo que para grafos no dirigidos con aristas simples es preferible usar la matriz de adyacencia.
En un grafo disperso, como el grafo círculo de la Figura con 20 nodos, el número de aristas es O(n), que para este grafo tiene n-1 aristas (19 aristas), siendo en este caso mejor usar la lista de aristas, ventaja que se incrementa cuanto mayor sea el número de nodos. Ese es el motivo de la existencia del tipo SPARSE6 que usa la lista de aristas como base de datos en lugar de la matriz de adyacencia.
En la siguiente tabla vemos las diferencias entre ambos tipos, con ventaja GRAPH6 para densos y SPARSE6 para dispersos, indicándose el número de caracteres de cada tipo:
| Graph | Nodes | Edges | Graph6 | Sparse6 |
|---|---|---|---|---|
| Dense (Complete) | 20 | 190 | 33 S~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~{ | 192 :S__@_@A_@AB_@ABC_@ABCD_@ABCDE_@ABCDEF_@ABCDEFG_@ABCDEFGH_@ABCDEFGHI_@ABCDEFGHIJ_@ABCDEFGHIJK_@ABCDEFGHIJKL_@ABCDEFGHIJKLM_@ABCDEFGHIJKLMN_@ABCDEFGHIJKLMNO_@ABCDEFGHIJKLMNOP_@ABCDEFGHIJKLMNOPQ |
| Sparse (Circle) | 20 | 19 | 33 ShCGGC@?G?_@?@??_?G?@??C??G??K??C | 22 :S_`abcdefghijklmnop_Q |
A continuación vemos el JavaScript para exportar a SPARSE6 exportSparse6() que usa setInitial6() que vimos con GRAPH6 y que ahora establece el primer caracter ":" que indentifica el tipo Sparse6 así como los siguientes primeros caracteres descriptores del número de nodos. Toma de entrada una lista de aristas de un grafo no dirigido debiendo especificar el número de nodos, pues pueden haber nodos finales aislados, es decir, sin aristas.
// Export Sparse6
// The argumen edgeList is of an undirected graph
function exportSparse6(edgeList=[], n=0, header=false) {
let codeExport = "", temp;
try {
let maxn = Math.max(...edgeList.flat());
if (n-1<maxn) throw new Error(`n-1=${n-1} is less than the maximum node index ${maxn}`);
if (temp = setInitial6(n, "sparse6"), typeof temp==="string") throw new Error(temp);
let chars = temp;
// (1) chars
let edges = edgeList.toSorted((u,v) => u[1]===v[1] ? u[0]-v[0] : u[1]-v[1]);
// (2) edges
let bin = [];
let x = 0;
for (let [u, v] of edges.values()) {
if (v===x) { // current vertex edge
bin.push([0, u]);
} else if (v==x+1) { // next vertex edge
x++;
bin.push([1, u])
} else { // skip to vertex x and add edge to y
x = v;
bin.push([1, v]);
bin.push([0, u]);
}
}
// (3) bin
let k = Math.floor(Math.log2(n-1)) + 1;
// (4) k
let bits = [];
for (let [b, c] of bin.values()) {
bits.push(b, ...c.toString(2).padStart(k, "0"));
}
bits = bits.map(v => +v);
// (5) bits
let nk = `${n},${k}`;
let m = bits.length;
let pad = Math.ceil(m/6) * 6 - m;
// (6) pad
if (pad>k && ["2,1", "4,2", "8,3", "16,4"].includes(nk) && x<n-1) {
// Avoid looping at the last isolated node
let b = Array.from({length:pad-1}, ()=>1);
bits.push(0, ...b);
} else {
let b = Array.from({length:pad}, ()=>1)
bits.push(...b);
}
if (maxn<n-1) {
// Add if last node is isolated
let b = Array.from({length:6}, ()=>1)
bits.push(...b);
}
// (7) bits
for (let i=0; i<bits.length; i+=6){
let s = bits.slice(i, i+6).join("");
let b = Number(`0b${s}`) + 63;
chars.push(String.fromCharCode(b));
}
// (8) chars
codeExport = chars.join("");
if (header) codeExport = `>>sparse6<<${codeExport}`;
} catch(e) {return `#ERROR ${e.message}`}
return codeExport;
}
Para explicar como se exporta a SPARSE6 tomaremos el grafo de la Figura que tiene la lista de aristas [[0,1],[0,2],[0,3],[1,2],[2,3]] y que se exporta con >>sparse6<<:CcKV.
En el código anterior hemos puesto unos comentarios numerados de (1) a (8) donde consultamos las variables significativas que exponemos a continuación.
chars=[":","C"]: al ejecutarsetInitial6(n, "sparse6")obtenemos dos caracteres, siendo el primero ":" que identifica el tipo SPARSE6 y el otro "C" que describe el número de nodos, pues el grafo tiene 4 nodos y 4+63=67 que se corresponde con el código ASCII de la letra "C".edges=[[0,1],[0,2],[1,2],[0,3],[2,3]]: tomamos la lista de aristas de entrada[[0,1],[0,2],[0,3],[1,2],[2,3]]que suele estar ordenada por el primer índice para ordenarla por el segundo.bin=[[1,0],[1,0],[0,1],[1,0],[0,2]]: componemos esta lista donde cada entrada es[bit, index]con un bit 0 o 1 y luego un índice de nodo del grafo. El bit 0 o 1 indica un cambio de vértice en la lista de aristas que se obtiene en el bucle del código, mostrando a continuación como evoluciona ese bucle para obtener esa variablebin:x u v ------------------------------------------------------------------------- 0 0 1 v==x+1 ⇒ x++, bin.push([1,u]) ⇒ x=1, bin.push([1,0]) 1 0 2 v==x+1 ⇒ x++, bin.push([1,u]) ⇒ x=2, bin.push([1,0]) 2 1 2 v==x ⇒ bin.push([0,u]) ⇒ x=2, bin.push([0,1]) 2 0 3 v==x+1 ⇒ x++, bin.push([1,u]) ⇒ x=3, bin.push([1,0]) 3 2 3 v==x ⇒ bin.push([0,u]) ⇒ x=3, bin.push([0,2]) bin = [[1,0],[1,0],[0,1],[1,0],[0,2]]
k=2con lo que obtenemos el número de bits necesarios para codificar el total de nodos del grafo conlet k = Math.floor(Math.log2(n-1)) + 1bits=[1,0,0,1,0,0,0,0,1,1,0,0,0,1,0]que es el resultado de tomarbin = [[1,0],[1,0],[0,1],[1,0],[0,2]]y en cada posición[bit, index]convertir el número enteroindex(índice de nodo) en un binario con k=2 bits, así por ejemplo index=1 es el binario "1" que se completa con k=2 bits agregando entonces un "0" a la izquierda quedando "01". Así tenemos finalmentebitsen partes1,0,0, - 1,0,0, - 0,0,1, - 1,0,0, - 0,1,0cada una con k+1 bits, que se empaquetan en una lista de 15 bits.pad=3, que es el total de bits que necesitamos agregar a los 15 bits anteriores para que resulten 18 bits que es un múltiplo de 6.bits=[1,0,0,1,0,0,0,0,1,1,0,0,0,1,0,1,1,1]los pad=3 bits se agregan como "1" al finalchars=[":","C","c","K","V"], separando bits en partes de 6 bits obtenemos "1,0,0,1,0,0" que supone el binario 100100 y decimal 36 que sumamos 63 quedando 36+63=99 cuyo código ASCII es la letra "c"; la siguiente parte es "0,0,1,1,0,0" que supone el binario 001100 y decimal 12 que sumamos 63 quedando 12+63=75 cuyo código ASCII es la letra "K"; la última parte es "0,1,0,1,1,1" que supone el binario 010111 y decimal 23 que sumamos 63 quedando 23+63=86 cuyo código ASCII es la letra "V". Así que obtenemos "cKV" que con los caracteres descriptores del inicio finalmente obtenemos":CcKV".
Y este es importSparse6() para importar SPARSE6 usando getInitial6() que obtiene el número de nodos a partir de los primeros caracteres. Se devuelve una lista de aristas.
// Import Sparse6
function importSparse6(text="") {
let edgeList = [], temp;
try {
let reg = new RegExp(`>>sparse6<<`);
text = text.replace(reg, "");
if (temp = getInitial6(text, "sparse6"), typeof temp==="string") throw new Error(temp);
let {n, chars, firstChar} = temp;
// (1)
let k = Math.floor(Math.log2(n-1)) + 1;
// (2)
let bits = [];
for (let i=firstChar; i<chars.length; i++){
let char = chars[i];
if (char<63) throw new Error(`There is a character smaller than 63`);
if (char>126) throw new Error(`There is a character greather than 126`);
bits.push(...(char-63).toString(2).padStart(6, "0"));
}
// (3)
let bin = [];
for (let i=0; i<bits.length; i+=k+1) {
bin.push([+bits[i], Number(`0b${bits.slice(i+1, i+k+1).join("")}`)]);
}
// (4)
let v = 0;
for (let i=0; i<bin.length; i++) {
let [b, x] = bin[i];
if (b===1) v++;
if (x>v) {
v = x;
} else if (x<n && v<n) {
edgeList.push([x, v]);
}
}
let maxn = Math.max(...edgeList.flat());
if (maxn<n-1) edgeList.push([n-1, -1]);
// (5)
} catch(e) {return `#ERROR ${e.message}`}
return edgeList;
}Para explicar como importar desde SPARSE6 indicamos en el código anterior las posiciones 1 a 5 donde consultamos las variables significativas. Recordemos que la lista de aristas ordenadas por el segundo índice del grafo de ejemplo de la Figura era [[0,1],[0,2],[1,2],[0,3],[2,3]], que es el resultado que ahora debemos obtener al importar con el texto >>sparse6<<:CcKV.
{n: 4, chars: '[67,99,75,86]', firstChar: 1}es el resultado degetInitial6(text, "sparse6")obteniendo n=4 nodos que tiene el grafo, los códigos ASCII de la cadena "CcKV" y la posición del primer caracter tras el descriptor de número de nodos, que en este caso es la posición 1, con lo que debemos procesar "cKV".k=2con lo que obtenemos el número de bits necesarios para codificar el total de nodos del grafo conlet k = Math.floor(Math.log2(n-1)) + 1bits=[1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1]que son los bits obtenidos iterando porcharsdesde la posición 1, iterando por los códigos ASCII [99, 75, 86] de la cadena "cKV". Así restamos 99-63=36 que convertimos en binario quedando "100100", 75-63=12 que en binario es "1100" y rellenamos con "0" para que tenga 6 bits quedando "001100", 86-63=23 que en binario es "10111" y rellenado a 6 bits queda "010111". Finalizamos con todos estos dígitos binarios enbits.bin=[[1,0],[1,0],[0,1],[1,0],[0,2],[1,3]]es el resultado de obtener las posiciones[bit, index]iterando porbitsen partes de k+1=2+1=3 dígitos binarios100, 100, 001, 100, 010, 111así que, por ejemplo, con la penúltima 010 tenemos el bit "0" y el index "10" que se corresponde con el decimal "2" con lo que obtenemos la penúltima entrada [0,2] enbin.edgeList=[[0,1],[0,2],[1,2],[0,3],[2,3]]es el resultado de convertirbinen la lista de aristas, exponiendo el siguiente esquema de evolución del último bucle del código anterior:n=4 [b,x] = bin iteration v b x ---------------------------------------------------------------- 0 1 0 b==1 ⇒ v++ ⇒ v=1 x≤v ⇒ 0≤1 ⇒ x<n ∧ v<n ⇒ edgeList.push([x,v]) ⇒ [0,1] 1 1 0 b==1 ⇒ v++ ⇒ v=2 x≤v ⇒ 0≤2 ⇒ x<n ∧ v<n ⇒ edgeList.push([x,v]) ⇒ [0,2] 2 0 1 x≤v ⇒ 1≤2 ⇒ x<n ∧ v<n ⇒ edgeList.push([x,v]) ⇒ [1,2] 2 1 0 b==1 ⇒ v++ ⇒ v=3 x≤v ⇒ 0≤3 ⇒ x<n ∧ v<n ⇒ edgeList.push([x,v]) ⇒ [0,3] 3 0 2 x≤v ⇒ 2≤3 ⇒ x<n ∧ v<n ⇒ edgeList.push([x,v]) ⇒ [2,3] 3 1 3 b==1 ⇒ v++ ⇒ v=4 x≤v ⇒ 3≤4 ⇒ x<n ∧ v<n ⇒ FALSE, Do not add to edgeList edgeList=[[0,1],[0,2],[1,2],[0,3],[2,3]]
Tipo DIGRAPH6 para importar y exportar grafos
En la Figura vemos un grafo dirigido y como lo exportamos a DIGRAPH6 en la Figura obteniéndose >>digraph6<<&EXKD?CA
Vimos en apartados anteriores GRAPH6 y SPARSE6 exclusivamente para grafos no dirigidos. Para dirigidos hemos de usar este tipo DIGRAPH6, usando como entrada la matriz de adyacencia para exportar y en caso de importar también se devolverá una matriz de adyacencia. Vemos el primer caracter "&" que si no usamos >>digraph6<< nos permite identificar este tipo.
A continuación vemos el JavaScript para exportDigraph6() e importDigraph6() que usan setInitial6() y getInitial6() para establecer y obtener los descriptores iniciales respectivamente.
El funcionamiento es igual que los vistos para GRAPH6 sólo que ahora en lugar de tomar la mitad superior de la matriz de adyacencia usamos todas las posiciones de dicha matriz.
// Export Digraph6
// The argument matrix is of an directed graph
function exportDigraph6(matrix=[], header=false) {
let codeExport = "", temp;
try {
let n = matrix.length;
if (temp = setInitial6(n, "digraph6"), typeof temp==="string") throw new Error(temp);
let chars = temp;
let bin = [];
for (let i=0; i<n; i++) {
for (let j=0; j<n; j++) {
bin.push(matrix[i][j]);
}
}
let m = bin.length;
let zeros = Math.ceil(m/6) * 6 - m;
bin.push(...Array.from({length: zeros}, ()=>0));
for (let i=0; i<bin.length; i+=6){
let s = bin.slice(i, i+6).join("");
let b = Number(`0b${s}`) + 63;
chars.push(String.fromCharCode(b));
}
codeExport = chars.join("");
if (header) codeExport = `>>digraph6<<${codeExport}`;
} catch(e) {return `#ERROR ${e.message}`}
return codeExport;
}
// Import Digraph6
function importDigraph6(text="") {
let matrix = [], temp;
try {
let reg = new RegExp(`>>digraph6<<`);
text = text.replace(reg, "");
if (temp = getInitial6(text, "digraph6"), typeof temp==="string") throw new Error(temp);
let {n, chars, firstChar} = temp;
let m = Math.ceil(n**2/6) + firstChar;
if (chars.length!==m) throw new Error(`Length characters is wrong`);
let bin = [];
for (let i=firstChar; i<chars.length; i++){
let char = chars[i];
if (char<63) throw new Error(`There is a character smaller than 63`);
if (char>126) throw new Error(`There is a character greather than 126`);
bin.push(...(char-63).toString(2).padStart(6, "0"));
}
matrix = Array.from({length: n}, () => Array.from({length: n}, () => 0));
for (let i=0; i<n; i++) {
for (let j=0; j<n; j++) {
let k = +bin.shift();
matrix[i][j] = k;
}
}
} catch(e) {return `#ERROR ${e.message}`}
return matrix;
}
Ya dijimos que DIGRAPH6 es sólo para grafos dirigidos. Pero exportando en la aplicación Grafos SVG el grafo no dirigido de la Figura a DIGRAPH6 obtenemos >>digraph6<<&C]lg. Si luego lo importamos en esa aplicación obtendremos el grafo dirigido de la Figura, observando aristas dobles y que se ha creado el nuevo nodo "4".
[[0,1,1,1], [1,0,1,0], [1,1,0,1], [1,0,1,0]]
El motivo es que al importar >>digraph6<<&C]lg desde el grafo no dirigido obtenemos una matriz simétrica como la adjunta, que no puede representar un grafo dirigido, pues hay aristas u🡒v y v🡒u para todos los nodos del grafo dando lugar a un grafo no dirigido. Para evitarlo hacemos lo que ya explicamos en el tema para operar todo dirigido un grafo, que se basa en la operación operateSubdivisionGraph(), observando que subdividimos la arista 0🡒1 insertando el nuevo nodo "4" en medio, con lo que ahora la matriz de adyacencia no es simétrica y, por tanto, refleja un grafo dirigido.
Esta operación de subdivisión no afecta a muchos procesos que ejecutemos sobre grafos y es una forma de representar un grafo todo dirigido con una matriz de adyacencia. Vea que si ahora exportamos el grafo dirigido de la Figura obtenemos >>digraph6<<&DNRTC? que es otra cosa que la obtenida antes, pues no es el mismo grafo.
Exportar e importar matriz de adyacencia con formato salida NSV
En un tema anterior explicábamos las estructuras de datos para exportar e importar un grafo, donde una de ellas es la matriz de adyacencia. Esta matriz puede manejarse con varios modos como "0/1", "0/number", "null/value" y "false/true". Y también en varios formatos de salida como array, CSV, TSV, SSV y ahora agregamos el nuevo formato NSV, como se observa en la Figura.
Esos formatos se conocen como CSV comma separated values, TSV tabulation separated values, SSV space separatad values y este nuevo que agrego ahora es NSV new-line separated values.
A continuación vemos todos los formatos de salida de la matriz de adyacencia del grafo de ejemplo de la Figura usando el modo valores "0/1":
ARRAY [[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]] CSV 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 TSV 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 SSV 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 NSV 00000 10000 11000 01001 01100
Todos los formatos menos NSV permiten cualquiera de los modos, pero obviamente el NSV sólo es para numéricos pues sólo registra un único dígito del valor de la arista.
Vemos en la Figura el grafo de ejemplo usado con valores numéricos en las aristas que tienen dos dígitos. Al usar el modo "0/1" donde haya un valor en una arista distinta de 0 se incluiría un 1. Con el modo "0/number" se hubiese incluido el número completo con todos sus dígitos, a excepción del formato NSV que sólo tomaría el primer digito, obteniéndose lo siguiente:
00000 10000 23000 04007 05600
Para importar una matriz de adyacencia usamos el campo Nodos o matriz de adyacencia como vemos en la Figura, donde importamos el NSV anterior, observando en la Figura el grafo importado con valores en las aristas con un único dígito numérico.
En resumen, este nuevo formato de salida NSV es óptimo para modos valores "0/1" o bien "0/number" cuando sólo hay un dígito numérico en los valores de las aristas.
Atajos de teclado
En el tema inicial sobre mejora aplicación para editar grafos exponíamos en el año 2025 el apartado edición de vértices y aristas, donde se explicaba el uso de botones para agregar nodos , agregar o editar aristas y para eliminar nodos o aristas .
La aplicación Grafos SVG ha venido estando enfocada para usar mediante el ratón del ordenador, no habiendo incorporado atajos de teclado (keyboard shortcuts), algo que voy a acometer en este momento. Por un lado daremos uso a las teclas Ctrl, Alt y Mayús (Shift). Y por otro a las teclas del teclado extendido que vemos en la Figura.
En la Figura vemos el área de vista que incluye el SVG con el grafo. El SVG es el área interior con el borde punteado. El área de vista es el exterior con un contorno que ahora aparece cuando lo seleccionamos. Esto quiere decir que esa área puede recibir el foco necesario para detectar los eventos de teclado.
Vemos que el nodo "2" está seleccionado, pudiendo hacerlo con el desplegable de la parte superior o, ahora, con los atajos de teclado que veremos a continuación. Seleccionando un nodo o una arista podíamos entonces aplicar los botones de edición que vimos antes y otros que ejecutan operaciones en el grafo, como contraer, dividir y subdividir. Ahora además podemos ejecutar algunas ediciones con solo el teclado.
Recordar que estas acciones solo se ejecutarán si el área de vista fue previamente seleccionada, tal como aparece en la Figura con el contorno que usualmente aplica cada navegador a los elementos de la página que pueden recibir el foco del usuario.
- Con Insert que vemos en la Figura agregamos un nuevo nodo que se ubicará en el área del SVG en un lugar no controlado por el usuario, pues la aplicación lo ubica a la derecha y a continuación de la primera fila de nodos de la parte superior.
- Con Ctrl + click pulsando con el ratón en un lugar del SVG se agregará el nuevo nodo exactamente en esa ubicación. Si previamente había un nodo seleccionado, se creará también una arista entre ese nodo y el nuevo agregado.
- Con Supr que vemos en la Figura eliminamos un nodo o arista seleccionada previamente.
- Con Mayús + click teniendo previamente un nodo seleccionado y pulsando en otro nodo se creará una arista entre esos dos nodos. En caso de que existiera previamente una arista sería eliminada. Si pulsamos sobre el mismo nodo se creará una arista autobucle.
- Para seleccionar un nodo tenemos las opciones que usan el teclado extendido de la Figura como las Flechas, la tecla Inicio para seleccionar el nodo "0", Fin para seleccionar el último nodo, Re Pág para seleccionar un nodo que esté 10 veces por debajo y Av Pág uno que esté 10 veces por encima. También podemos usar la tecla Tab para ir adelante o Mayús + Tab para ir hacia atrás. O las teclas del teclado numérico, aunque sólo seleccionará nodos con valores entre "0" y "9".
- Con Alt + flechas teniendo un nodo previamente seleccionado podemos mover el nodo en las cuatro direcciones.
- Con Ctrl + z deshacemos una acción y con Ctrl + y la rehacemos.