Operaciones en un grafo
Operaciones en grafos
En la aplicación Grafos SVG podemos acceder al asistente de generación mediante el botón . El desplegable de la acción tiene dos partes: una primera con las operaciones que podemos ejecutar sobre un grafo que veremos en este tema y otra segunda para generar nuevos grafos que se expondrá en otro tema.
Las operaciones en grafos producen nuevos grafos diferentes de los iniciales. Se ejecutan sobre la matriz de adyacencia modificándola y, por tanto, modificando también el grafo.
Una clasificación de las operaciones en grafos es la siguiente:
- Operaciones unarias sobre un único grafo:
- Operaciones elementales o de edición, son las que modifican el grafo agregando o eliminado nodos o aristas. También se incluye la contracción de nodos y/o aristas. Esto lo explicamos en el tema edición de nodos y aristas. Se lleva a cabo con los botones
- Operaciones avanzadas crean un nuevo grafo con un cambio más complejo y son las siguientes:
- Cambiar dirección con
operateDirectionGraph(), que ya vimos en el tema anterior, cambiando la dirección de toda las aristas siguiendo un criterio particular de la aplicación. - Grafo complemento con
operateComplementGraph() - Grafo transpuesto con
operateTransposeGraph()que ya vimos en el tema anterior, transponiendo la matriz de adyacencia. - Grafo línea con
operateLineGraph() - Pemutar un grafo con
operatePermuteGraph() - Grafo cociente con
operateQuotientGraph()
- Cambiar dirección con
- Operaciones binarias que involucran dos grafos, como principalmente la unión, la intersección y el producto de dos grafos que tampoco he implementado.
El asistente de generación, al que se accede mediante el botón , se muestra en la Figura. Ahí podemos ejecutar las operaciones.
Tras la ejecución ofrece el resultado como un objeto con el posible mensaje de error y la matriz de adyacencia resultante. El botón "Restablecer" permite deshacer la acción y volver al grafo original. La opción "Posicionar" fija la posición original de los nodos.
El icono es un vínculo que nos lleva a una página de información en este sitio, explicando los detalles de la operación. El botón abre un panel con el código JavaScript de la operación.
En la parte de "Código Wolfram" se ofrece el código para ejecutar en Wolfram Cloud, con enlaces a información en Wolfram Language y Wolfram MathWorld cuando esté disponible.
Grafo complemento operateComplementGraph()
La operación grafo complemento (o grafo complementario) es otro grafo con los mismos nodos donde las aristas son sólo aquellas que el grafo original no incluye. La unión de aristas del grafo y su complemento producirán un grafo completo.
Para ver un ejemplo tomaremos el Grafo de Petersen que se observa en la Figura. Podemos generarlo en la aplicación en la sección asistente generación, con los parámetros n = 5, k = 2, Radio = 20.
El JSON que también puede importar es el siguiente:
{"nodes":[
{"index":0,"nodeOffset":"2.5","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"65.54 2.64","parent":[{"index":0}]},
{"index":2,"nodeOffset":"51.01 22.36","parent":[{"index":1}]},
{"index":3,"nodeOffset":"-4.34 -2.64","parent":[{"index":2}]},
{"index":4,"nodeOffset":"-35.54 2.64","parent":[{"index":0},{"index":3}]},
{"index":5,"nodeOffset":"-22.5 -5","parent":[{"index":0}]},
{"index":6,"nodeOffset":"21.52 -16.18","parent":[{"index":1}]},
{"index":7,"nodeOffset":"-2.41 -18.82","parent":[{"index":2},{"index":5}]},
{"index":8,"nodeOffset":"-9.26 -43.82","parent":[{"index":3},{"index":5},{"index":6}]},
{"index":9,"nodeOffset":"-41.52 -16.18","parent":[{"index":4},{"index":6},{"index":7}]}
],
"config":{}}
Otra forma de presentar visualmente el Grafo de Petersen es hacerlo en forma de círculo. Para ello aplicaremos el ajuste visual ajustar a círculo, con parámetros Radio = 45, Orden nodos = 0,9,3,7,1,5,4,8,2,6 obteniéndose el resultado que observamos en la Figura.
0 1 0 0 1 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 1 1 0 0
Esta es la matriz de adyacencia en formato SSV (space separated values, valores separados por espacios). El JSON es el siguiente:
{"nodes":[
{"index":0,"nodeOffset":"7.5","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"58.95 56.41","parent":[{"index":0}]},
{"index":2,"nodeOffset":"-10.3 -18.91","parent":[{"index":1}]},
{"index":3,"nodeOffset":"66.97 -43.91","parent":[{"index":2}]},
{"index":4,"nodeOffset":"-18.95 56.41","parent":[{"index":0},{"index":3}]},
{"index":5,"nodeOffset":"-17.5 65","parent":[{"index":0}]},
{"index":6,"nodeOffset":"-18.95 -41.41","parent":[{"index":1}]},
{"index":7,"nodeOffset":"33.63 -16.09","parent":[{"index":2},{"index":5}]},
{"index":8,"nodeOffset":"-35.3 -41.09","parent":[{"index":3},{"index":5},{"index":6}]},
{"index":9,"nodeOffset":"8.95 -41.41","parent":[{"index":4},{"index":6},{"index":7}]}
],
"config":{}}
Al aplicar la operación grafo complemento obtenemos el de la Figura. Se observa que hay una arista "0-6" cuando antes no existía. Y que ahora no existe la arista "6-9".
0 0 1 1 0 0 1 1 1 1 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 1 1 0 1 0 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 0 0 1 1 0 1 1 0 1 0 1 0 1 1 1 0 1 0 0 1 0 1 1 1 1 1 0 1 0 0 1 0
La matriz de adyacencia es tal que, sin contar con la diagonal que son todos ceros y no se modifica, cada posición es la inversa de la anterior.
{"nodes":[
{"index":0,"nodeOffset":"24.17","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"17.28 81.41","parent":[{"index":-1}]},
{"index":2,"nodeOffset":"3.59 6.09","parent":[{"index":0}]},
{"index":3,"nodeOffset":"78.08 6.09","parent":[{"index":0},{"index":1}]},
{"index":4,"nodeOffset":"-2.28 56.41","parent":[{"index":1},{"index":2}]},
{"index":5,"nodeOffset":"13.06 65","parent":[{"index":1},{"index":2},{"index":3},{"index":4}]},
{"index":6,"nodeOffset":"-24.51 -16.41","parent":[{"index":0},{"index":2},{"index":3},{"index":4},{"index":5}]},
{"index":7,"nodeOffset":"33.63 33.91","parent":[{"index":0},{"index":1},{"index":3},{"index":4},{"index":6}]},
{"index":8,"nodeOffset":"-63.08 33.91","parent":[{"index":0},{"index":1},{"index":2},{"index":4},{"index":7}]},
{"index":9,"nodeOffset":"-4.94 -16.41","parent":[{"index":0},{"index":1},{"index":2},{"index":3},{"index":5},{"index":8}]}
],
"config":{}}
El grafo completo de 10 nodos que vemos en la Figura es la unión del grafo de Petersen y su complementario. El grafo completo también puede crearse en el asistente de generación.
0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0
La matriz de adyacencia de un grafo completo son todos "1" a excepción de la diagonal, pues hay arista entre cada dos nodos cualesquiera.
{"nodes":[
{"index":0,"nodeOffset":"7.5","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"73.95 56.41","parent":[{"index":0}]},
{"index":2,"nodeOffset":"-5.3 6.09","parent":[{"index":0},{"index":1}]},
{"index":3,"nodeOffset":"70.3 6.09","parent":[{"index":0},{"index":1},{"index":2}]},
{"index":4,"nodeOffset":"-8.95 56.41","parent":[{"index":0},{"index":1},{"index":2},{"index":3}]},
{"index":5,"nodeOffset":"7.5 65","parent":[{"index":0},{"index":1},{"index":2},{"index":3},{"index":4}]},
{"index":6,"nodeOffset":"-28.95 -16.41","parent":[{"index":0},{"index":1},{"index":2},{"index":3},{"index":4},{"index":5}]},
{"index":7,"nodeOffset":"30.3 33.91","parent":[{"index":0},{"index":1},{"index":2},{"index":3},{"index":4},{"index":5},{"index":6}]},
{"index":8,"nodeOffset":"-65.3 33.91","parent":[{"index":0},{"index":1},{"index":2},{"index":3},{"index":4},{"index":5},{"index":6},{"index":7}]},
{"index":9,"nodeOffset":"-6.05 -16.41","parent":[{"index":0},{"index":1},{"index":2},{"index":3},{"index":4},{"index":5},{"index":6},{"index":7},{"index":8}]}
],
"config":{}}
También puede aplicarse el grafo complemento a un grafo dirigido, como es el de la Figura.
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
Esta es su matriz de adyacencia, que puede usar para importarlo en la aplicación, o bien con el siguiente JSON:
{"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"
}}
En la Figura se observa el grafo complemento del anterior.
0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 1 0 0 1 0 0 1 0
La matriz de adyencia tiene todas las posiciones invertidas a excepción de la diagonal. Vemos que existía la arista "1🡒0" que ahora sólo incluye "0🡒1". Donde antes no había ninguna arista como entre los nodos "0" y "3" ahora vemos la arista doble "0⟷3" (que también denominamos arista toda dirigida), siendo realmente dos aristas "0🡒3" y "3🡒0".
Como vemos en la Figura, podemos separar las aristas anteriores "0🡒3" y "3🡒0" evidenciándose que realmente son dos aristas.
{"error":"","matrix":
[[0,1,1,1,0],
[0,0,1,1,1],
[0,0,0,1,1],
[1,0,1,0,0],
[1,0,0,1,0]]}La operaración devuelve un objeto con el posible error y la nueva matriz de adyacencia del grafo complemento.
La aplicación también devuelve el código para ejecutar en Wolfram Cloud mediante la función GraphComplement[g]. En la Figura vemos el grafo inicial y su complementario. Se obtiene el mismo resultado, aunque en Wolfram la disposición gráfica en el plano de los nodos es distinta.
Puede ver información de GraphComplement[g] en Wolfram Reference y Graph Complement en Wolfram MathWorld, enlaces que la aplicación también ofrece.
g = AdjacencyGraph[{{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}}, 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]}}];
GraphComplement[g]La aplicación ofrece el código JavaScript de la operación operateComplementGraph()
function operateComplementGraph({matrix=[]}) {
let dev = {error: "", matrix: []}, temp;
try {
let n = matrix.length;
dev.matrix = Array.from({length: n}, (v, i) =>
Array.from({length: n}, (w, j) => i===j ? 0 : 1));
for (let i=0; i<n; i++){
for (let j=0; j<n; j++) {
if (matrix[i][j]!==0) dev.matrix[i][j] = 0;
if (matrix[j][i]!==0) dev.matrix[j][i] = 0;
}
}
} catch(e){dev.error = `#Error operateComplementGraph(): ${clean(e.message)}`}
return dev;
}Grafo línea operateLineGraph()
La operación grafo línea sobre un grafo no dirigido G genera otro grafo línea L(G) donde sus nodos representan las aristas del grafo original G y donde cada dos nodos del grafo línea L(G) son adyacentes si y sólo si comparten un vértice común en el grafo original G.
Una forma resumida de decirlo es que para un grafo no dirigido G, dos nodos en su grafo línea L(G) son adyacentes si sus aristas correspondientes comparten un vértice común en G.
También es posible operar el grafo línea sobre un grafo dirigido, que expondremos más abajo. Por ahora veamos el ejemplo del grafo completo K4 de la Figura del que operaremos su grafo línea:
0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0
Su matriz de adyacencia tiene "1" en todas las posiciones menos en la diagonal, pues es un grafo completo. Puede importarlo en la aplicación con este JSON:
{"nodes":[
{"index":0,"nodeOffset":"2.5 40","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"27.5 -25","parent":[{"index":0}]},
{"index":2,"nodeOffset":"37.14 35","parent":[{"index":0},{"index":1}]},
{"index":3,"nodeOffset":"-57.14 35","parent":[{"index":0},{"index":1},{"index":2}]}
],
"config":{}}En la aplicación puede crear este grafo completo en la sección asistente generación al que se accede con el botón , ejecutar la entrada nuevo grafo completo con parámetros Nodos = 4, Radio = 40 generándose un grafo completo K4. Luego puede ira a los ajustes visuales con , acción ajustar a círculo con parámetros Radio = 40, Nodo centro = 0 y obtendremos el grafo de la Figura.
Para ver como generamos el grafo línea, primero etiquetamos las aristas del grafo original tal como se muestra en la Figura. Cada etiqueta dará lugar a una vértice o nodo en el grafo línea.
El resultado lo vemos en la Figura. Por ejemplo, entre los nodos "0,1" y "1,2" del grafo línea hay una arista pues las aristas "0-1" y "1-2" del grafo original comparten el mismo nodo "1".
0 1 1 1 1 0 1 0 1 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 1 0 1 0 1 1 1 1 0
Esta es la matriz de adyacencia del grafo línea obtenido, que puede ver en la aplicación con el siguiente JSON:
{"nodes":[
{"index":0,"nodeOffset":"2.5 10.4","value":"0,1","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"58.13 29.8","value":"0,2","parent":[{"index":0}]},
{"index":2,"nodeOffset":"-13.13 29.8","value":"0,3","parent":[{"index":0},{"index":1}]},
{"index":3,"nodeOffset":"18.13 0.2","value":"1,2","parent":[{"index":0},{"index":1}]},
{"index":4,"nodeOffset":"-53.13 0.2","value":"1,3","parent":[{"index":0},{"index":2},{"index":3}]},
{"index":5,"nodeOffset":"2.5 19.6","value":"2,3","parent":[{"index":1},{"index":2},{"index":3},{"index":4}]}
],
"config":{}}
La aplicación ofrece el código para ejecutar en Wolfram Cloud mediante la función LineGraph[g], cuyo resultado vemos en la Figura, aunque no he podido reubicar los nodos del grafo original K4 ni conseguir trasladar los etiquetados al grafo línea.
La aplicación ofrece enlaces a documentación en Wolfram Reference y Wolfram MathWorld, como se observa en la Figura. Para este caso usamos la función LineGraph[g] que se explica en Wolfram Reference y también hay más información en Line Graph de Wolfram MathWorld.
g = AdjacencyGraph[{{0,1,1,1},{1,0,1,1},{1,1,0,1},{1,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]},
VertexLabelStyle -> Directive[Black,17.5], EdgeLabelStyle -> Directive[Black,17.5,Bold],
VertexStyle -> White, EdgeStyle -> {{Black,Thickness[0.005]}}]
LineGraph[g]
Para un grafo dirigido G, dos nodos en el grafo línea L(G) son adyacentes si sus aristas correspondientes están conectadas en G. Tomemos como ejemplo el de la Figura.
0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0
Puede importarlo con esta matriz de adyacencia, pero para que aparezca posicionado como el de la Figura debe usar el siguiente JSON:
{"nodes":[
{"index":0,"nodeOffset":"-18.75 18.75","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"29.17 -6.25","parent":[{"index":0}]},
{"index":2,"nodeOffset":"60.42 -31.25","parent":[{"index":1}]},
{"index":3,"nodeOffset":"-35.42 25","parent":[{"index":0,"markerStart":"none","markerEnd":"arrow"}]},
{"index":4,"nodeOffset":"-4.17","parent":[{"index":1,"markerStart":"none","markerEnd":"arrow"},{"index":3}]},
{"index":5,"nodeOffset":"43.75 -25","parent":[{"index":2,"markerStart":"none","markerEnd":"arrow"},{"index":4}]}
],
"config":{
"markerStart":"arrow"
}}
En la Figura vemos el grafo línea del grafo dirigido anterior, usando los parámetros Posicionar = false y Esparcir = 0. Recordemos que esparcir es un ajuste visual que expande radialmente los nodos desde el centro geométrico.
Se observan que los caminos que podemos seguir en el grafo línea se corresponden con el original. Así, por ejemplo, tenemos el camino "3,0 🡒 0,1 🡒 1,2" en L(G) se corresponde con el camino "3 🡒 0 🡒 1 🡒 2" en G. E igual con el resto.
La operación grafo línea devuelve el siguiente objeto, con un mensaje de error si fuera el caso, la matriz de adyacencia resultante y una lista con los valores de los nodos del nuevo grafo.
{"error":"",
"matrix":
[[0,1,0,0,0,0,0],
[0,0,0,0,0,0,0],
[1,0,0,0,0,0,0],
[0,0,0,0,1,1,0],
[0,1,0,0,0,0,0],
[0,0,0,0,0,0,1],
[0,0,0,0,0,0,0]],
"vertexs":
["0,1","1,2","3,0","3,4","4,1","4,5","5,2"]}Con este JSON puede importar el grafo línea resultante:
{"nodes":[
{"index":0,"value":"0,1","parent":[{"index":2}]},
{"index":1,"value":"1,2","parent":[{"index":0},{"index":4}]},
{"index":2,"value":"3,0","parent":[{"index":-1}]},
{"index":3,"value":"3,4","parent":[{"index":-1}]},
{"index":4,"value":"4,1","parent":[{"index":3}]},
{"index":5,"value":"4,5","parent":[{"index":3}]},
{"index":6,"value":"5,2","parent":[{"index":5}]}
],
"config":{
"markerStart":"arrow"
}}
En la Figura puede ver la la ejecución en Wolfram Cloud con el siguiente código.
g = AdjacencyGraph[{{0,1,0,0,0,0},{0,0,1,0,0,0},{0,0,0,0,0,0},{1,0,0,0,1,0},{0,1,0,0,0,1},{0,0,1,0,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], 6 -> Placed[5,Center]},
VertexLabelStyle -> Directive[Black,17.5], EdgeLabelStyle -> Directive[Black,17.5,Bold],
VertexStyle -> White, DirectedEdges -> True, EdgeStyle -> {{Black,Thickness[0.005]}}];
LineGraph[g]El código JavaScript es el siguiente, donde usamos el algoritmo getEdges() que explicamos en un siguiente apartado. También usamos la operación isGraphDirected() que ya vimos en un tema anterior.
function operateLineGraph({matrix=[]}){
let dev = {error: "", matrix: [], vertexs: []}, temp;
try {
let n = matrix.length;
let directed = isGraphDirected({matrix});
if (typeof directed==="string") throw new Error(directed);
let edgesSource = getEdges({matrix, forceUndirected:true, edgesCompact:true});
if (typeof edgesSource==="string") throw new Error(edgesSource);
let edges = [];
dev.vertexs = new Set();
for(let i=0; i<edgesSource.length; i++) {
let [p1, p2] = edgesSource[i];
for (let j=0; j<edgesSource.length; j++) {
let [q1, q2] = edgesSource[j];
if (directed) {
let p = `${p1},${p2}`;
let q = `${q1},${q2}`;
if (q1===p2 && q2!==p1){
edges.push([p, q]);
dev.vertexs.add(p);
dev.vertexs.add(q);
} else if (p1===q2 && p2===q1) {
edges.push([p, q]);
dev.vertexs.add(p);
dev.vertexs.add(q);
}
} else {
if (i!==j && (q1===p2 || q2===p1)) {
let p = `${p1},${p2}`;
let q = `${q1},${q2}`;
edges.push([p, q]);
dev.vertexs.add(p);
dev.vertexs.add(q);
}
if (i!==j && (q1===p1 || q2===p2)) {
let p = `${p1},${p2}`;
let q = `${q1},${q2}`;
edges.push([p, q]);
dev.vertexs.add(p);
dev.vertexs.add(q);
}
}
}
}
dev.vertexs = Array.from(dev.vertexs);
if (directed && dev.vertexs.length<edgesSource.length) {
for (let edge of edgesSource) {
let edgeJoin = edge.join(",")
if (!dev.vertexs.includes(edgeJoin)){
dev.vertexs.push(edgeJoin)
}
}
}
let m = dev.vertexs.length;
dev.matrix = Array.from({length: m}, () => Array.from({length: m}, () => 0));
for (let edge of edges) {
let [p, q] = edge;
let i = dev.vertexs.indexOf(p);
let j = dev.vertexs.indexOf(q);
if (i>-1 && j>-1) {
dev.matrix[i][j] = 1;
if (!directed) dev.matrix[j][i] = 1;
}
}
if (!directed) {
for (let i=0; i<dev.matrix.length; i++) {
for (let j=0; j<dev.matrix.length; j++) {
if (dev.matrix[i][j]===1){
dev.matrix[j][i] = 1;
}
}
}
}
} catch(e){dev.error = `#Error operateLineGraph(): ${clean(e.message)}`}
return dev;
}Obtener aristas getEdges()
En la seccion de acciones podemos encontrar el algoritmo getEdges() para obtener las aristas de un grafo. En la Figura se muestran los parámetros forzar no dirigido y salida compacta que explicaremos a continuación.
Para todos los algoritmos y otras partes de la aplicación he incluido el enlace con el icono que remite a temas en este sitio que explican cada parte, como a este mismo apartado.
El icono es el del mismo botón que antes tenía con la leyenda "Código", que ahora abre un panel emergente con el código JavaScript del algoritmo.
En la parte inferior se muestra el resultado al ejecutar el algoritmo, con el tiempo de ejecución y el propio resultado convertido en texto.
Veamos un ejemplo en ejecución para el grafo de la Figura.
0 7 9 0 0 14 0 0 10 15 0 0 0 0 0 11 0 2 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 9 0
Este grafo dirigido y ponderado se encuentra entre las muestras de la aplicación. También puede importarlo con esta matriz de adyacencia en formato SSV.
Time: 0 ms
Obtener aristas: {
"0,1":7, "0,2":9, "0,5":14,
"1,2":10, "1,3":15, "2,3":11,
"2,5":2, "4,3":6, "5,4":9}Al ejecutarlo sin activar forzar no dirigido y salida compacta obtenemos el resultado adjunto. Devuelve un objeto cuyas claves son las aristas y sus valores el valor de cada arista. Así, por ejemplo, "0,1":7 se refiere a la arista "0🡒1" que tiene el valor "7".
[[0,1],[0,2],[0,5], [1,2],[1,3],[2,3], [2,5],[4,3],[5,4]]
En caso de activar salida compacta obtenemos un array en lugar de un objeto. Así, por ejemplo, [0, 1] se refiere a la arista "0🡒1". En cualquier caso con [i, j] siempre entenderemos "i🡒j" en un grafo dirigido e "i-j" en uno no dirigido. Vea que con este parámetro activado perdemos el valor de la arista.
Time: 0 ms
Obtener aristas: {
"0,1":7, "1,0":7, "0,2":9,
"2,0":9, "0,5":14, "5,0":14,
"1,2":10, "2,1":10, "1,3":15,
"3,1":15, "2,3":11, "3,2":11,
"2,5":2, "5,2":2, "4,3":6,
"3,4":6, "5,4":9, "4,5":9}Si activamos forzar no dirigido sobre un grafo dirigido, sin usar salida compacta, obtenemos un objeto con las claves. Así, por ejemplo, tenemos "0,1":7, "1,0":7 que, para un no dirigido, viene a ser la arista "0-1" con valor "7".
La aplicación permite exportar las distintas acciones a Wolfram Cloud, como explicamos en un tema anterior cuando exponíamos las estructuras de datos. Como se observa en la Figura, al ejecutar el ejemplo anterior obtenemos el código Wolfram y un enlace para ir a Wolfram Cloud, donde tiene que abrir su sesión y pegar ese código que vemos también a continuación:
g = AdjacencyGraph[{{0,1,1,0,0,1},{0,0,1,1,0,0},{0,0,0,1,0,1},{0,0,0,0,0,0},{0,0,0,1,0,0},{0,0,0,0,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],
EdgeLabels -> {(1->2)->7, (1->3)->9, (2->3)->10, (2->4)->15, (3->4)->11, (5->4)->6, (6->5)->9, (1->6)->14, (3->6)->2},
VertexStyle -> White, DirectedEdges -> True, EdgeStyle -> {{Black,Thickness[0.005]}}]
EdgeList[g]
En la Figura vemos el resultado en Wolfram Cloud, presentando el grafo original que es estructuralmente igual que el de la Figura obtenido en nuestra aplicación.
Y también ofrece la lista de aristas {1🡒2, 1🡒3, 1🡒6, 2🡒3, 2🡒4, 3🡒4, 3🡒6, 5🡒4, 6🡒5} que es la misma que la que obtuvimos [[0, 1], [0, 2], [0, 5], [1, 2], [1, 3], [2, 3], [2, 5], [4, 3], [5, 4]] si tenemos en cuenta que en Wolfram los índices se inician en 1 y en nuestra aplicación en 0. Tenga en cuenta que los nodos están etiquetados desde 0 como en nuestra aplicación, pero en Wolfram se inician en 1.
En el texto anterior he usado la flecha "🡒" en lugar de la que usa Wolfram que es el UNICODE 0F3D5 "", tal como explica en \[DirectedEdge] para una arista dirigida, pues no es representable directamente en los navegadores dado que está en una sección de uso privado en Unicode.
Nuestra aplicación nunca utiliza internamente caracteres flecha para representar una arista, pues tal como hemos explicado, el array [1, 2] significa "1🡒2" en un grafo dirigido e "1-2" en un grafo no dirigido. En el código de Wolfram puede escribirse la relación como 1\[DirectedEdge]2, para dirigido y 1\[UndirectedEdge]2 para no dirigido.
Incluso también puede escribirse como 1->2 para dirigido y 1<->2 para no dirigido usando caracteres ASCII "-, <, >" disponibles en todos los teclados, pues Wolfram Cloud se encarga de convertirlas en sus caracteres propios.
En el código siguiente de getEdges() usamos la operación isGraphDirected() que ya vimos en un tema anterior.
function getEdges({matrix=[], forceUndirected=false, edgesCompact=false}) {
let result = edgesCompact ? [] : {};
try {
let n = matrix.length;
let directed = isGraphDirected({matrix});
if (typeof directed==="string") throw new Error(directed);
for (let i=0; i<n; i++) {
let k = (edgesCompact && !directed) ? i : 0;
for (let j=k; j<n; j++) {
if (matrix[i][j]!==0) {
if (edgesCompact) {
result.push([i, j])
} else {
result[`${i},${j}`] = matrix[i][j];
}
}
if (!edgesCompact) {
if (!directed) {
if (matrix[j][i]!==0) result[`${j},${i}`] = matrix[j][i];
} else if (forceUndirected && matrix[i][j]!==0) {
result[`${j},${i}`] = matrix[i][j];
}
}
}
}
} catch(e) {result = e.message}
return result;
}El argumento edgesCompact se refiere al modo de salida compacta que hemos explicado más arriba. Y también forceUndirected a forzar no dirigido.
Permutar un grafo
En la Figura vemos la sección de operaciones del asistente de generación, con la operación para permutar un grafo que intentaremos explicar a continuación.
Si tenemos el grafo G con matriz de adyacencia A con n nodos y una permutación del conjunto de índices M = {0, 1, 2,..., n-1} que genera la matriz permutación P, siendo P⊤ su matriz transpuesta, decimos que Gp es una permutación del grafo G con matriz de adyacencia Ap como el resultado de la operación:
Un grafo y sus permutaciones son isomórficos. Conocer como permutar un grafo es básico para implementar algoritmos para saber si dos grafos son isomórficos, como el algoritmo isGraphIsomorphic() que puede encontrar en la sección de algoritmos, aunque esto no lo explico por ahora.
Hay que diferenciar entre permutación de un grafo que estamos viendo y obtener el grafo de una permutación, que puede ver en la misma sección del asistente de generación en la entrada nuevo grafo permutación, que se basa en el concepto de inversiones de una permutación cíclica y que espero publicar en un tema posterior.
Y también es diferente del grafo de una permutación cíclica, que también tenemos en el asistente de generación en la entrada nuevo grafo permutación cíclica.
Permutación de un grafo
Permutar un grafo no es sólo permutar los nodos, sino además matener la relación de aristas. Esto se consigue con esa operación que acabamos de ver. Pero veamos esto con un ejemplo sin hacer uso de esa fórmula.
Por ejemplo, si en un grafo con 4 nodos tenemos la lista de aristas [[0, 1], [2, -1], [3, -1]] que puede exportar en la aplicación o bien con la siguiente matriz de adyacencia:
0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0
Se observa que hay una arista "0-1" mientras que los nodos "2" y "3" no tienen aristas con el resto de nodos.
Si aplicamos la permutación π = [2, 3, 0, 1] lo que estamos haciendo es permutar "0" y "2" por un lado y "3" y "1" por otro. La arista "0-1" se traspasa a "2-3", como se observa en la Figura. Por lo tanto no es sólo permutar los nodos, sino además conservar la relación de aristas.
Observe que la aplicación mantiene la ubicación en el plano de cada nodo, puesto que la opción posicionar está activada, según se observa en la Figura. Si la desactiva se obtiene el grafo de la Figura, ubicándose los nodos de forma automática.
En la aplicación Combine Tools podemos generar las permutaciones del conjunto de elementos {0, 1, 2}, obteniéndose las siguientes seis permutaciones: [0,1,2], [0,2,1], [1,0,2], [1,2,0], [2,0,1], [2,1,0]. De forma compacta cuando los elementos sólo tienen un caracter suelen representase así: 012, 021, 102, 120, 201, 210. Con un conjunto de n elementos hay P(n) = n! permutaciones, siendo para este ejemplo 3! = 6 permutaciones.
Cuando el grafo no tiene las aristas etiquetadas, el número de permutaciones es inferior, estimándose en P(n) = n para el siguiente ejemplo, como se observa con los 3 posibles grafos en la Figura, un grafo estrella (Star graph) no dirigido y no etiquetado que puede importar de la primera matriz de adyacencia que se expone a continuación o crear en el asistente de generación, en la parte de nuevos grafos.
012, 021 ⇒ 0 1 1 1 0 0 1 0 0 102,201 ⇒ 0 1 0 1 0 1 0 1 0 120, 210 ⇒ 0 0 1 0 0 1 1 1 0
Las permutaciones [0, 1, 2] y [0, 2, 1] no modifican el grafo. Las permutaciones [1, 0, 2] y [2, 0, 1] producen una permutación del grafo original. Las permutaciones [1, 2, 0] y [2, 1, 0] producen otra permutación del grafo original.
Como se observa en la Figura, sólo hay tres formas de disponer los nodos. En el primer caso desde el nodo "0" salen dos aristas a los otros dos nodos. En el siguiente es el nodo "1" el que ocupa ese lugar. Y finalmente en el último caso es el nodo "2" el que ocupa ese lugar. Cambiar de lugar los otros dos nodos en cualquier caso no modifica el grafo.
Con un grafo ponderado donde se diferencian las aristas, el número de permutaciones si es de P(n) = n!, 6 en este caso como se observa en la Figura, con los dos primeros para las permutaciones 012, 021, los dos siguientes para 102, 201 y los dos últimos con 120, 210.
012 0 10 20 10 0 0 20 0 0 021 0 20 10 20 0 0 10 0 0 102 0 10 0 10 0 20 0 20 0
201 0 20 0 20 0 10 0 10 0 120 0 0 10 0 0 20 10 20 0 210 0 0 20 0 0 10 20 10 0
Estas son las 6 matrices ponderadas de la permutaciones obtenidas en formato SSV.
En la Figura puede ver las permutaciones del grafo estrella no dirigido con 4 nodos sin etiquetar las aristas. De las 4! = 24 permutaciones posibles, vemos que sólo hay 4 permutaciones diferentes, la primera con las permutaciones 0123, 0132, 0213, 0231, 0312, 0321, la segunda con 1023, 1032, 2012, 2031, 3012, 3021, la tercera con 1203, 1320, 2130, 2310, 3120, 3210 y la cuarta con 1230, 1320, 2130, 2310, 3120, 3210.
En general para un grafo estrella no dirigido y no etiquetado de n nodos habrán también n permutaciones, pues se trata de ubicar en cada permutación uno de los nodos en el centro, desde donde parten todas las aristas al resto de nodos. Como las aristas no se etiquetan, habrán (n-1)! permutaciones de aristas equivalentes, por lo que el número de permutaciones que originan grafos distintos es de P(n) = n!/(n-1)! = n. Otros tipos de grafos no dirigidos y no etiqueados darán lugar a cálculos distintos según su estructura.
También es posible permutar un grafo dirigido. En la Figura vemos uno con modo valores null/value. Todas las etiquetas de las aristas son letras mayúsculas a excepción de "3"🡒"4" con el número "34" y otra "4"🡒"2" sin valor.
[[null, null, null, null, null], ["A", null, null, null, null], ["B", "C", null, null, null], [null, "D", null, null, 34], [null, "F", "", null, null]]
Se puede importar con la matriz de adyacencia anterior en modo null/value. Aplicando la permutación 3, 0, 4, 1, 2 obtenemos el grafo permutado de la derecha donde vemos que, antes de aplicar la operación, todas las aristas que no tengan un número se les asigna el valor "1", mientras que la arista "34" se mantiene. Esto es necesario pues para llevar a cabo la operación Ap = P · A · P⊤ es necesario multiplicar números de las matrices, como veremos en los siguientes párrafos.
Matriz permutacion y operación para permutar un grafo
Para explicar como construir la matriz permutación tomaremos el conjunto de índices M = {0, 1, 2} y una permutación de ejemplo como π = [1, 2, 0], que representamos como un Array pues hay que mantener el orden de los elementos.
P = 0 1 2 0 0 0 0 1 0 0 0 2 0 0 0
En primer lugar construimos una matriz vacía P que albergará la matriz permutación, de tamaño 3 × 3, pues n = 3 es el tamaño del conjunto de índices. Como se observa, incluimos cabeceras de los índices de filas y columnas para visualizarlo mejor, representando los valores en color azul, todos cero inicialmente.
π = [1, 2, 0] i j=π[i] P[i][j] ----------------------- 0 1 P[0][1] = 1 1 2 P[1][2] = 1 2 0 P[2][0] = 1 P = 0 1 2 0 0 1 0 1 0 0 1 2 1 0 0
A continuación iteramos por la permutación π = [1, 2, 0] extrayendo el índice y el valor de cada posición, haciendo P[i][j]=1, con lo que finalmente obtenemos la matriz permutación. Se observa que en cada fila y en cada columna sólo hay un 1 en una única posición.
Veamos la aplicación de la fórmula Ap = P · A · P⊤ usando el grafo original de ese ejemplo anterior y la permutación π = [1, 2, 0], cuya matriz permutación acabamos de ver, siendo la transpuesta la resultante de cambiar filas por columnas:
| A = | ⎧ | 0 | 1 | 1 | ⎫ |
| ⎪ | 1 | 0 | 0 | ⎪ | |
| ⎩ | 1 | 0 | 0 | ⎭ |
| P = | ⎧ | 0 | 1 | 0 | ⎫ |
| ⎪ | 0 | 0 | 1 | ⎪ | |
| ⎩ | 1 | 0 | 0 | ⎭ |
| P⊤ = | ⎧ | 0 | 0 | 1 | ⎫ |
| ⎪ | 1 | 0 | 0 | ⎪ | |
| ⎩ | 0 | 1 | 0 | ⎭ |
Aplicando la fórmula que vimos Ap = P · A · P⊤ para lo cual podemos usar WolframAlpha con la multiplicación de matrices {{0,1,0},{0,0,1},{1,0,0}} * {{0,1,1},{1,0,0},{1,0,0}} * {{0,0,1},{1,0,0},{0,1,0}} en el formato adecuado para Wolfram, obtendremos la matriz de adyacencia del grafo permutado con la permutación π = [1, 2, 0]:
| Ap = P · A · P⊤ = | ⎧ | 0 | 0 | 1 | ⎫ |
| ⎪ | 0 | 0 | 1 | ⎪ | |
| ⎩ | 1 | 1 | 0 | ⎭ |
Observe que P · A supone intercambiar las filas según la permutación P:
| B = P · A = | ⎧ | 0 | 1 | 0 | ⎫ | · | ⎧ | 0 | 1 | 1 | ⎫ | = | ⎧ | 1 | 0 | 0 | ⎫ |
| ⎪ | 0 | 0 | 1 | ⎪ | ⎪ | 1 | 0 | 0 | ⎪ | ⎪ | 1 | 0 | 0 | ⎪ | |||
| ⎩ | 1 | 0 | 0 | ⎭ | ⎩ | 1 | 0 | 0 | ⎭ | ⎩ | 0 | 1 | 1 | ⎭ |
En lo anterior vemos que P[0] = [0, 1, 0] significa que en la primera fila hemos de poner la segunda de la matriz A[1] = [1, 0, 0], mientras que P[1] = [0, 0, 1] dice que en la segunda fila hemos de poner la tercera A[2] = [1, 0, 0] y que P[2] = [1, 0, 0] dice que en la tercera fila hemos de poner la primera A[0] = [0, 1, 1].
Y que A · P⊤ supone intercambiar las columnas según la permutación P, que se construye haciendo lo mismo que antes pero tomando columnas en lugar de filas:
| C = A · P⊤ = | ⎧ | 0 | 1 | 1 | ⎫ | · | ⎧ | 0 | 0 | 1 | ⎫ | = | ⎧ | 1 | 1 | 0 | ⎫ |
| ⎪ | 1 | 0 | 0 | ⎪ | ⎪ | 1 | 0 | 0 | ⎪ | ⎪ | 0 | 0 | 1 | ⎪ | |||
| ⎩ | 1 | 0 | 0 | ⎭ | ⎩ | 0 | 1 | 0 | ⎭ | ⎩ | 0 | 0 | 1 | ⎭ |
Observe que B = C⊤, una es la transpuesta de otra.
La multiplicación de matrices no es conmutativa, puesto que P · A ≠ A · P, donde este último producto A · P es un reordenamiento distinto de las columnas:
| A · P = | ⎧ | 0 | 1 | 1 | ⎫ | · | ⎧ | 0 | 1 | 0 | ⎫ | = | ⎧ | 1 | 0 | 1 | ⎫ |
| ⎪ | 1 | 0 | 0 | ⎪ | ⎪ | 0 | 0 | 1 | ⎪ | ⎪ | 0 | 1 | 0 | ⎪ | |||
| ⎩ | 1 | 0 | 0 | ⎭ | ⎩ | 1 | 0 | 0 | ⎭ | ⎩ | 0 | 1 | 0 | ⎭ |
Dos grafos con matrices de adyacencia A y B son isomórficos si existe una matriz permutación P tal que A = P⊤ · B · P, o bien P · A = B · P que es equivalente a lo anterior. Observe que es lo mismo que decir B = P · A · P⊤, si consideramos A como el grafo original y B el grafo permutando A con la permutación P.
Permutar un grafo desde la lista de aristas
En la Figura, donde se presentaba una captura del panel de la operación para permutar un grafo, podíamos ver las opciones desde aristas, compacto no dirigido y aristas ordenadas, la primera no chequeada y las otras dos desactivadas. En esa situación la permutación recibe y devuelve matrices de adyacencia usando el producto de matrices Ap = P · A · P⊤. Pero si nos dan el grafo con una estructura de lista de aristas podemos permutar el grafo a partir de esa lista. En la aplicación usando la opción desde aristas convierte la matriz de adyacencia en una lista de aristas antes de aplicar la operación.
Veamos un ejemplo. Como vemos en la Figura, activamos desde aristas y compacto no dirigido, pues vamos a usar un ejemplo de grafo no dirigido (ver más sobre esto en lista de aristas), y desactivamos aristas ordenadas y posicionar, cuyo cometido de esta última opción hemos explicado más arriba y lo de aristas ordenadas lo explicaremos más abajo.
En la Figura, a la izquierda, tenemos el grafo no dirigido original que puede importar con la lista de aristas [[0, 0], [0, 1], [0, 4], [1, 2], [1, 4], [2, 3], [3, 4], [3, 5]] o, indistintamente, con esta matriz de adyacencia:
1 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 1 1 1 1 0 1 0 0 0 0 0 1 0 0
Y a la derecha el grafo permutado a partir de su lista de aristas con la permutación 3, 2, 0, 1, 4, 5 , con las opciones desde aristas y compacto no dirigido activadas y aristas ordenadas desactivada, obteniéndose el siguiente resultado donde vemos la lista de aristas del grafo permutado:
{"error":"","matrix":[],"edges":
[[2,2],[2,3],[2,4],[3,1],[3,4],[1,0],[0,4],[0,5]],
"permutation":[]}No se devuelve la matriz de adyacencia, pues con la lista de aristas podemos importar el grafo. Y como no necesitamos la matriz permutación tampoco se calcula ni se devuelve.
Si enfrentamos la lista de índices de nodos del grafo original Io = 0 1 2 3 4 5 con la permutación Ip = 3, 2, 0, 1, 4, 5 y por otro lado la lista de aristas del grafo Lo original con el permutado Lp:
Io = 0 1 2 3 4 5 Ip = 3, 2, 0, 1, 4, 5 Lo = [[0, 0], [0, 1], [0, 4], [1, 2], [1, 4], [2, 3], [3, 4], [3, 5]] Lp = [[2, 2], [2, 3], [2, 4], [3, 1], [3, 4], [1, 0], [0, 4], [0, 5]]
Vemos que, por ejemplo, la arista original [0, 1] se referencia buscando en Ip los índices 0 y 1 que se enfrentan en Io con 2 y 3 respectivamente, de tal forma que la arista original [0, 1] permuta en [2, 3]. Esta técnica no supone hacer cálculos de multiplicación de matrices, solo correspondencias entre índices, por lo que tiene un coste algorítmico menor.
Para explicar lo anterior obtuvimos la lista de aristas no ordenada para poder compararla con la original, pues si hubiésemos activado la opción aristas ordenadas obtendríamos [[0,1],[0,4],[0,5],[1,3],[2,2],[2,3],[2,4],[3,4]], ordenadas por el primer índice y segundo índice de cada arista. En cualquier caso no es necesario ordenarlas, pues con o si orden son estructuralmente equivalentes, representando el mismo grafo. Pero en este caso no las ordenamos para poder enfrentarlas con la lista original y explicar lo anterior.
Permutar un grafo en Wolfram
La aplicación también nos da el código para ejecutar en Wolfram Cloud, que se basa en la función PermutationMatrix[p] de Wofram Reference , siendo p una permutación de índices del conjunto M = {1, 2, 3, ..., n} pues los índices se inician en 1. También podemos ver más información en Permutation Matrix de Wolfram MathWorld .
En la Figura puede ver el grafo original y el permutado a la derecha en Wolfram Cloud del último ejemplo, que aparte de la disposición en el plano, son los mismos que obtuvimos nosotros. Este es el código usado, donde separamos cada sentencia con una barra horizontal, pues en Wolfram las sentencencias se separan por un salto de línea:
g = AdjacencyGraph[{{1,1,0,0,1,0},{1,0,1,0,1,0},{0,1,0,1,0,0},{0,0,1,0,1,1},{1,1,0,1,0,0},{0,0,0,1,0,0}},
ImageSize -> 312.5, VertexSize -> {"Scaled", 0.1}, 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]}}]
a = AdjacencyMatrix[g];
p = Normal[PermutationMatrix[{4,3,1,2,5,6}]];
t = Normal[Transpose[p]];
AdjacencyGraph[p.a.t, ImageSize-> 312.5, VertexSize -> {"Scaled", 0.1},
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]}}]Se observa que obtenemos la matriz de adyacencia del grafo original con a = AdjacencyMatrix[g]; la matriz permutación con p = PermutationMatrix[{4, 3, 1, 2, 5, 6}]; teniendo en cuenta que se corresponde con la permutación 3, 2, 0, 1, 4, 5 de nuestro ejemplo, pues los índices se enumeran desde 1; su transpuesta con t = Transpose[p]; y el grafo permutado final con la multiplicación de matrices p.a.t, usando la operación que ya vimos Ap = P · A · P⊤. No he encontrado en Wolfram una operación específica para permutar un grafo.
Función JavaScript para permutar un grafo operatePermuteGraph()
Veamos ahora el código JavaScript que usamos en la aplicación para permutar un grafo:
function operatePermuteGraph({matrix=[], edges=[], fromEdges=false, indexes=[],
verify=true, compactUndirected=true, sortedEdges=false}) {
let dev = {error: "", matrix: [], edges: []};
try {
if (fromEdges) {
if (edges.length===0) {
if (matrix.hasOwnProperty("edges")) {
edges = matrix.edges;
} else {
edges = getEdges({matrix, edgesCompact:true});
if (typeof edges==="string") throw new Error(edges);
}
}
for (let edge of edges) {
let [v, w] = edge;
let i = indexes.indexOf(v);
let j = indexes.indexOf(w);
if (compactUndirected) {
dev.edges.push(i<j ? [i, j] : [j, i]);
} else {
dev.edges.push([i, j]);
}
}
if (sortedEdges) {
dev.edges.sort((v,w) => v[0]===w[0] ? v[1]-w[1] : v[0]-w[0]);
}
} else {
let n = matrix.length;
if (verify && indexes.length!==n)
throw new Error(`Length indexes not is equal to length of matrix`);
if (verify && indexes.some(v => typeof v!=="number"))
throw new Error(`Indexes are not values`);
let permute = Array.from({length:n}, () => Array.from({length: n}, () => 0));
// p
for (let i=0; i<indexes.length; i++) {
let j = indexes[i];
permute[i][j] = 1;
}
// pt
let tpermute = [];
for (let i=0; i<n; i++) {
tpermute.push([]);
for (let j=0; j<n; j++){
tpermute[i].push(permute[j][i]);
}
}
// p.a
let pa = [];
for (let i=0; i<n; i++){
pa.push([]);
for (let j=0; j<n; j++) {
pa[i].push(0);
for (let k=0; k<n; k++) {
pa[i][j] += permute[i][k] * matrix[k][j];
}
}
}
// p.a.pt
for (let i=0; i<n; i++){
dev.matrix.push([]);
for (let j=0; j<n; j++) {
dev.matrix[i].push(0);
for (let k=0; k<n; k++) {
dev.matrix[i][j] += pa[i][k] * tpermute[k][j];
}
}
}
}
} catch(e){dev.error = `#Error operatePermuteGraph(): ${clean(e.message)}`}
return dev;
}Esta función para permutar un grafo puede usarse con la matriz de adyacencia en el argumento matrix o con la lista de aristas en el argumento edges, en cuyo caso ha de pasarse el argumento fromEdges=true. En indexes pasamos el array con la permutación. El argumento verify verificará la consistencia de los datos de entrada para el caso de la matriz de adyacencia.
Si se pasa fromEdges=true y el array edges está vacío, entonces se observa si matrix contiene una propiedad matrix.edges conteniendo la lista de aristas. En otro caso se construye con getEdges() que ya hemos explicado en un apartado anterior. Una vez tengamos la lista de aristas procedemos a intercambiarlas tal como explicamos más arriba en permutar un grafo desde lista aristas.
Si fromEdges=false usamos la operación para permutar un grafo que ya expusimos a partir de la matriz de adyacencia que viene en el argumento matrix.
Los otros argumentos compactUndirected y sortedEdges se usan para el caso de la lista de aristas. Si compactUndirected=true significa que con una sola arista [i, j] que se pase se entiende que hay implicítamente la otra [j, i] para representar la arista "i-j" no dirigida. En otro caso si compactUndirected=false entonces [i, j] significa la arista "i🡒j" y si además se pasa [j, i] significa que también existe la arista "j🡒i"
Con sortedEdges ordenamos las aristas antes de devolverlas. El orden de la lista de aristas no modificará la estructura del grafo.
Grafo cociente operateQuotientGraph
La operación cociente de un grafo G es otro grafo G' cuyos nodos representan los subconjuntos disjuntos (o bloques) de una partición de los nodos de G, de tal forma que dos nodos de G' son adyacentes si un nodo en un bloque es adyacente a otro nodo en otro bloque en G.
En la Figura puede ver la parte del asistente de generación para ejecutar la operación cociente de un grafo. Con el grafo del ejemplo que veremos a continuación con 9 nodos, usaremos la partición (0)(1)(2)(3)(4 5)(6 9)(7 8) en notación de ciclos o biene como array [[0],[1],[2],[3],[4,5],[6,9],[7,8]].
El modo salida del grafo puede ser lista de aristas, matriz de adyacencia o matriz de adyacencia ponderada. Más abajo explicaremos con el ejemplo este último modo. La opción con valores nodos traslada los valores del grafo inicial al final. Con ella activada y activando con colores nodos se trasladan además los colores de los nodos, lo que nos puede servir para comparar el grafo original con el cociente. La opción posicionar trata de mantener los nodos en o cerca de sus posiciones originales, pues en otro caso se reubican automáticamente.
Como ejemplo usaremos el grafo de la Figura que podemos ver en la página Nauty and Traces, un grafo con la referencia "(A)" y su cociente más abajo con la leyenda "QUOTIENT GRAPH OF (A)".
Puede importarlo en la aplicación usando el siguiente JSON. Hemos adaptado las posiciones y colores como el original en esa página web. Observe que damos un color a cada bloque o subconjunto de la partición (0)(1)(2)(3)(4 5)(6 9)(7 8).
{"nodes":[
{"index":0,"nodeOffset":"-20.93 93.6","nodeColor":"orange","nodeFontColor":"white","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"65.6 14.4","nodeColor":"red","nodeFontColor":"white","parent":[{"index":-1}]},
{"index":2,"nodeOffset":"32.6 62.6","nodeColor":"lightgreen","parent":[{"index":0}]},
{"index":3,"nodeOffset":"-4.8 34.6","nodeColor":"yellow","parent":[{"index":0}]},
{"index":4,"nodeOffset":"30.93 -20.6","nodeColor":"lightblue","parent":[{"index":1}]},
{"index":5,"nodeOffset":"50.11 28.2","nodeColor":"lightblue","parent":[{"index":1}]},
{"index":6,"nodeOffset":"42.9 -10.8","nodeColor":"darkgreen","nodeFontColor":"white","parent":[{"index":2},{"index":4}]},
{"index":7,"nodeOffset":"42.09 11.6","nodeColor":"blue","nodeFontColor":"white","parent":[{"index":3},{"index":5}]},
{"index":8,"nodeOffset":"-27.8 -35.2","nodeColor":"blue","nodeFontColor":"white","parent":[{"index":3},{"index":6},{"index":4}]},
{"index":9,"nodeOffset":"50.51 17","nodeColor":"darkgreen","nodeFontColor":"white","parent":[{"index":7},{"index":2},{"index":5}]}
],
"config":{}}
Como hemos dicho vamos a aplicar la partición (0)(1)(2)(3)(4 5)(6 9)(7 8), obteniéndose el grafo cociente de la Figura, usando las opciones con valores nodos, con lo que, por ejemplo, el bloque (7 8) se convierte en el nodo con valor "7,8". Al usar la opción con colores nodos trasladamos los colores del grafo original.
Con el modo salida matriz adyacencia ponderada agregamos etiquetas a las aristas indicando el número de vecinos entre los dos nodos del grafo original. Así, por ejemplo, el nodo "1" tiene dos vecinos "4" y "5" en el original, con lo que en el cociente tenemos una arista con valor 2 entre los nodos "1" y "4,5".
En la web de donde tomamos el ejemplo se muestra el resultado del grafo cociente en la Figura, observando que es el mismo grafo, aunque la disposición en el plano es distinta y además no incluye los valores de los nodos, aunque si incluye los colores y las etiquetas de las aristas.
No he encontrado en Wolfram esta operación de forma directa y creo que es algo compleja para llevarla a cabo usando otras funciones de Wolfram, pues mi conocimiento del lenguaje Wolfram es bastante limitado.
El código JavaScript para operar el cociente de un grafo es el siguiente. El argumento mode puede ser edges, matrix, weighted-matrix para devolver la lista de aristas, matriz de adyacencia o matriz de adyacencia ponderada respectivamente. El argumento partition espera un array como el del ejemplo [[0],[1],[2],[3],[4,5],[6,9],[7,8]].
function operateQuotientGraph({matrix=[], partition=[], mode="edges"}) {
let dev = {error: "", edges: [], matrix: []}, temp;
try {
let n = matrix.length;
if (!Array.isArray(partition)) throw new Error(`Partition is not an array`);
let m = partition.length;
if (m.length===0) throw new Error(`Partition length is 0`);
if (partition.flat().toSorted((v,w) => v-w).
join(",") !== Array.from({length: n}, (v,i) => i).
join(",")) throw new Error(`Partition has not all vertexs`);
let refs = Array.from({length: n}, () => -1);
for (let i=0; i<m; i++) {
let cell = partition[i];
for (let vertex of cell) {
refs[vertex] = i;
}
}
if (!matrix.hasOwnProperty("neighbors")){
matrix.neighbors = [];
for (let index=0; index<n; index++) {
let neighbors = getNeighbors({matrix, index});
if (typeof neighbors==="string") throw new Error(neighbors);
matrix.neighbors.push(neighbors);
}
}
let edges = [];
for (let i=0; i<m; i++) {
let cell = partition[i];
let neighbors = new Set();
for (let vertex of cell) {
neighbors = neighbors.union(new Set(matrix.neighbors[vertex]));
}
let items = [];
for (let j of [...neighbors]){
let k = refs[j];
if (!items.includes(k)) {
items.push(k);
}
}
for (let k of items) {
let key = i<k ? `${i},${k}` : `${k},${i}`;
if (!edges.includes(key)) {
edges.push(key);
}
}
}
let vertexs = [...(new Set(...edges.flat()))];
if (vertexs.length<m) {
for (let i=0; i<m; i++) {
if (!vertexs.includes(i)) {
edges.push(`${i},-1`);
}
}
}
dev.edges = edges.map(v => v.split(",").map(v => +v)).
toSorted((v,w) => v[0]===w[0] ? v[1]-w[1] : v[0]-w[0]);
if (mode.indexOf("matrix")>-1) {
temp = convertToAdjacencyMatrix({array:dev.edges, mode:"edgeList",
compactUndirected:true});
if (typeof temp==="string") throw new Error(temp);
dev.matrix = temp.matrix;
}
if (mode==="weighted-matrix") {
temp = getEdges({matrix, edgesCompact:true});
if (typeof temp==="string") throw new Error(temp);
let edgesIni = temp.map(v => v.join(","));
refs = refs.map((v,i) => [i, v]);
for (let edge of dev.edges) {
let [u, v] = edge;
if (v>-1) {
let p1 = refs.filter(w => w[1]===u).map(w => w[0]);
let p2 = refs.filter(w => w[1]===v).map(w => w[0]);
let s = 0;
for (let i=0; i<p1.length; i++) {
for (let j=0; j<p2.length; j++) {
let [x, y] = [p1[i], p2[j]];
let xy = x<y ? [x, y].join(",") : [y, x].join(",");
if (edgesIni.includes(xy)) s++;
}
}
if (u===v) s = s/2;
dev.matrix[u][v] = s;
dev.matrix[v][u] = s;
}
}
}
} catch(e){dev.error = `#Error operateQuotientGraph(): ${clean(e.message)}`}
return dev;
}Usamos la función getNeighbors() que ya explicamos en un tema anterior para obtener los vecinos de un nodo, en caso de que no nos venga como una propiedad de la matriz de adyacencia matrix de entrada. También usa la función convertToAdjacencyMatrix() para convertir a matriz de adyacencia la lista de aristas, función que expusimos en otro tema. Y getEdges() que explicamos en un apartado de este tema.