Componentes conectados en grafos
Obtener componentes conectados getConnectedComponents()
Un grafo conectado es aquel donde desde un nodo podemos llegar a cualquier otro del grafo. En otro caso pueden existir subgrafos conectados que son aquellos donde todos los nodos del subgrafo están conectados. Si el grafo es dirigido podemos hablar de débilmente conectado si no consideramos la dirección de las aristas, es decir, si consideramos el grafo como no dirigido. Y fuertemente conectado cuando se considera la dirección de las aristas.
Los términos conectado y conexo son sinónimos en este contexto. Así por ejemplo a veces diremos en estos temas grafo conectado o grafo conexo refiriéndonos a lo mismo.
Si un grafo es conectado tendrá un único componente conectado. En otro caso habrá tantos componentes conectados como subgrafos conectados.
Componentes conectados: [
{"visited":[0,1,4,7],
"path":[[0,1],[1,4],[4,7]]},
{"visited":[2,3,6,5,8],
"path":[[2,3],[3,6],[6,5],[6,8]]}
]En la Figura vemos los dos componentes conectados de un grafo no dirigido. El grafo no es conectado pero tiene 2 subgrafos conectados. La aplicación devuelve este resultado, con dos entradas, donde vemos los nodos de cada componente en "visited" y el camino seguido para descubrirlos en "path". Esta estructura del resultado es la que devuelve el algoritmo de búsqueda en profundidad recursiva getDepthFirstSearchRecursive() que vimos en un tema anterior, que sirve de base para obtener los componentes conectados de un grafo no dirigido, como veremos después.
En la aplicación accedemos a cada componente conectado con los botones de navegación que se encuentran junto al grafo. Y para presentarlo aquí hemos compuesto la imagen de la Figura separando cada grafo con una línea.
Con el siguiente JSON puede importar ese ejemplo:
{"nodes":[
{"index":0,"nodeOffset":"-23.36 0.77","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"17.74 -24.06","parent":[{"index":0}]},
{"index":2,"nodeOffset":"-8.02 0.71","parent":[{"index":-1}]},
{"index":3,"nodeOffset":"48.85 -24.57","parent":[{"index":2}]},
{"index":4,"nodeOffset":"-22.12 11.84","parent":[{"index":0},{"index":1}]},
{"index":5,"nodeOffset":"-15.38 -2.81","parent":[{"index":2}]},
{"index":6,"nodeOffset":"-6.81 10.47","parent":[{"index":2},{"index":3},{"index":5}]},
{"index":7,"nodeOffset":"-5.42 10.54","parent":[{"index":4}]},
{"index":8,"nodeOffset":"11.73 11.99","parent":[{"index":6}]}
],
"config":{
"algorithm":"Get connected components"
}}
En la Figura vemos los mismos dos componentes conectados del grafo no dirigido en Wolfram que obtuvimos en nuestra aplicación, donde Wolfram colorea cada componente. Usa la función ConnectedComponents.
g = AdjacencyGraph[{{0,1,0,0,1,0,0,0,0},{1,0,0,0,1,0,0,0,0},{0,0,0,1,0,1,1,0,0},{0,0,1,0,0,0,1,0,0},{1,1,0,0,0,0,0,1,0},
{0,0,1,0,0,0,1,0,0},{0,0,1,1,0,1,0,0,1},{0,0,0,0,1,0,0,0,0},{0,0,0,0,0,0,1,0,0}}, ImageSize->219,
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], 7->Placed[6,Center], 8->Placed[7,Center], 9->Placed[8,Center]},
VertexLabelStyle->Directive[Black,17.5], EdgeLabelStyle->Directive[Black,17.5,Bold], VertexStyle->White, EdgeStyle->{{Black,Thickness[0.005]}}];
ConnectedComponents[g];
HighlightGraph[g, %]
En la Figura vemos las opciones de la aplicación, con color camino y color fondo nodo para el resaltado de los componentes. La opción forzar no dirigido sólo aplica a grafos dirigidos como veremos a continuación.
En la Figura vemos un grafo dirigido con los mismos nodos y aristas que el visto al inicio en la Figura al que hemos dado dirección a las aristas, obteniéndose los componentes conectados marcando la opción forzar no dirigido. Los componentes conectados son los mismos que los del grafo no dirigido, conociéndose como componentes débilmente conectados cuando se trata el grafo dirigido como no dirigido.
Componentes conectados: [
{"visited":[0,1,4,7],
"path":[[0,1],[1,4],[4,7]]},
{"visited":[2,3,6,5,8],
"path":[[3,2],[6,3],[5,6],[8,6]]}
]El resultado para los nodos visitados ("visited") es el mismo que para el grafo no dirigido que vimos al inicio. Las aristas también son las mismas y debemos pensar que aunque se resalten con color en el grafo, se han obtenido tomando el grafo como no dirigido.
{"nodes":[
{"index":0,"nodeOffset":"-23.36 0.77","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"9.41 -24.06","parent":[{"index":0}]},
{"index":2,"nodeOffset":"-8.02 0.71","parent":[{"index":-1}]},
{"index":3,"nodeOffset":"32.18 -24.57","parent":[{"index":2}]},
{"index":4,"nodeOffset":"-5.45 -13.16","parent":[{"index":1},{"index":0,"markerStart":"none","markerEnd":"arrow"}]},
{"index":5,"nodeOffset":"-23.71 -2.81","parent":[{"index":2}]},
{"index":6,"nodeOffset":"9.85 -14.53","parent":[{"index":3},{"index":5},{"index":2,"markerStart":"none","markerEnd":"arrow"}]},
{"index":7,"nodeOffset":"-5.42 -14.46","parent":[{"index":4}]},
{"index":8,"nodeOffset":"11.73 -13.01","parent":[{"index":6}]}
],
"config":{
"lineHeight":18.75,
"markerStart":"arrow",
"algorithm":"Get connected components"
}}
En la Figura vemos los mismos dos componentes débilmente conectados en Wolfram, usándose en este caso otra función WeaklyConnectedComponents.
g = AdjacencyGraph[{{0,1,0,0,0,0,0,0,0},{0,0,0,0,1,0,0,0,0},{0,0,0,1,0,1,0,0,0},{0,0,0,0,0,0,1,0,0},
{1,0,0,0,0,0,0,1,0},{0,0,0,0,0,0,1,0,0},{0,0,1,0,0,0,0,0,1},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}},
ImageSize->164, 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], 7->Placed[6,Center],
8->Placed[7,Center], 9->Placed[8,Center]}, VertexLabelStyle->Directive[Black,13.13], EdgeLabelStyle->Directive[Black,13.13,Bold],
VertexStyle->White, DirectedEdges->True, EdgeStyle->{{Black,Thickness[0.005]}}];
WeaklyConnectedComponents[g];
HighlightGraph[g, %]
Cuando se consideran la dirección de las aristas en un grafo dirigido, entonces obtenemos los componentes fuertemente conectados. En la Figura vemos que se encuentran 4 componentes fuertemente conectados en el grafo dirigido usando el ejemplo anterior.
Componentes conectados: [
{"visited":[0,1,4],"path":[]},
{"visited":[2,3,5,6],"path":[]},
{"visited":[7],"path":[]},
{"visited":[8],"path":[]}
]
En la Figura vemos los mismos 4 componentes fuertemente conectados que se obtienen en Wolfram, cada uno con un color diferente. Utiliza la misma función ConnectedComponents que para el grafo no dirigido.
g = AdjacencyGraph[{{0,1,0,0,0,0,0,0,0},{0,0,0,0,1,0,0,0,0},{0,0,0,1,0,1,0,0,0},{0,0,0,0,0,0,1,0,0},
{1,0,0,0,0,0,0,1,0},{0,0,0,0,0,0,1,0,0},{0,0,1,0,0,0,0,0,1},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}},
ImageSize->164, 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], 7->Placed[6,Center],
8->Placed[7,Center], 9->Placed[8,Center]}, VertexLabelStyle->Directive[Black,13.13], EdgeLabelStyle->Directive[Black,13.13,Bold],
VertexStyle->White, DirectedEdges->True, EdgeStyle->{{Black,Thickness[0.005]}}];
ConnectedComponents[g];
HighlightGraph[g, %]
El grafo dirigido de la Figura no es conectado, pues desde cualquiera de los nodos 0,1,2,4 no podemos llegar al nodo 3. Pero tiene 2 componentes fuertemente conectados.
Componentes conectados: [
{"visited":[0,1,2,4],"path":[]},
{"visited":[3],"path":[]}
]
{"nodes":[
{"index":0,"parent":[{"index":-1}]},
{"index":1,"value":"X","parent":[{"index":0,"value":"A"}]},
{"index":2,"parent":[{"index":0,"value":"B"},{"index":1,"value":"C"}]},
{"index":3,"parent":[{"index":1,"value":"D","lineTextOffset":"-0.75 0.25"},{"index":4,"value":"E"}]},
{"index":4,"parent":[{"index":1,"value":"F"},{"index":2},{"index":0,"lineOffset":"1","markerReverse":true,"value":"G"}]}
],
"config":{
"markerEnd":"arrow",
"algorithm":"Get connected components"
}}
Vemos en la Figura los 2 mismos componentes fuertemente conectados en Wolfram.
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->188, VertexSize->{"Scaled", 0.17},
VertexLabels->{1->Placed[0,Center], 2->Placed["X",Center], 3->Placed[2,Center], 4->Placed[3,Center], 5->Placed[4,Center]},
VertexLabelStyle->Directive[Black,17.5], EdgeLabelStyle->Directive[Black,17.5,Bold], EdgeLabels->{(2->1)->"A", (3->1)->"B", (3->2)->"C",
(4->2)->"D", (4->5)->"E", (5->2)->"F", (1->5)->"G"}, VertexStyle->White, DirectedEdges->True, EdgeStyle->{{Black,Thickness[0.005]}}];
ConnectedComponents[g];
HighlightGraph[g, %]A continuación vemos el JavaScript para ejecutar getConnectedComponents(). Su ejecución se desglosa en dos partes. La primera es para grafos no dirigidos o dirigidos que se fuerzan a no dirigidos con el argumento forceUndirected = true, usándose la búsqueda en profundidad recursiva mediante el algoritmo getDepthFirstSearchRecursive(), pues cada búsqueda devolverá un subconjunto de nodos conectados.
La segunda parte es para obtener los componentes fuertemente conectados de un grafo dirigido, para los que tenemos que usar otra estrategia. Se trata de ver los caminos que hay entre dos nodos del grafo, en una y otra dirección, usando el algoritmo para encontrar caminos entre dos nodos findPath(). Si hay camino en las dos direcciones se agrega ese nodo a un componente. Los nodos que al final no estén en ningún componente serán componentes con nodos aislados.
Se usa isGraphDirected() para saber si el grafo es dirigido.
function getConnectedComponents({matrix=[], forceUndirected=true}){
let result = [], temp;
try {
let directed = isGraphDirected({matrix});
if (typeof directed==="string") throw new Error(directed);
let n = matrix.length;
let isInComponent = Array.from({length: n}, () => false);
if (!directed || forceUndirected) {
for (let index=0; index<n; index++) {
if (!isInComponent[index]) {
let temp = getDepthFirstSearchRecursive({matrix, index, forceUndirected});
if (typeof temp==="string") throw new Error(temp);
temp.visited.forEach(v => isInComponent[v]=true);
result.push(temp);
}
}
} else {
let components = [];
for (let i=0; i<n; i++) {
if (!isInComponent[i]) {
isInComponent[i] = true;
let newComponent = [i];
for (let j=i+1; j<n; j++) {
if (!isInComponent[j]) {
let paths = findPath({matrix, firstIndex:i, lastIndex:j});
if (typeof paths==="string") throw new Error(paths);
let pathsReverse = findPath({matrix, firstIndex:j, lastIndex:i});
if (typeof pathsReverse==="string") throw new Error(pathsReverse);
if (paths.length>0 && pathsReverse.length>0) {
isInComponent[j] = true;
newComponent.push(j);
}
}
}
components.push(newComponent);
}
}
components.forEach(v => result.push({visited: v, path: []}));
let notInComponent = isInComponent.map((v,i) => [i, v]).filter(v => !v[1]).map(v => v[0]);
notInComponent.forEach(v => result.push({visited: [v], path: []}));
}
} catch(e){result = e.message}
return result;
}El algoritmo anterior no es el más eficiente para obtener los componentes fuertemente conectados en grafos dirigidos, pudiendo encontrar otros como los algoritmos de Kosaraju, Tarjan y el algoritmo basado en caminos con varias versiones, una de ella de Dijkstra. No he implentado ninguno de estos algoritmos en la aplicación.
Es el grafo conectado isGraphConnected()
Con el algoritmo isGraphConnected() verificamos si un grafo es conectado, o equivalentemente si es conexo. Un grafo es conectado si desde cualquier nodo podemos llegar a cualquier otro nodo siguiendo las aristas.
Time: 0 ms Es el grafo conectado: false
En la Figura vemos un grafo no dirigido que no es conectado, devolviendo la aplicación sólo el booleano verdadero o falso.
{"nodes":[
{"index":0,"nodeOffset":"-23.36 0.77","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"17.74 -24.06","parent":[{"index":0}]},
{"index":2,"nodeOffset":"-8.02 0.71","parent":[{"index":-1}]},
{"index":3,"nodeOffset":"48.85 -24.57","parent":[{"index":2}]},
{"index":4,"nodeOffset":"-22.12 11.84","parent":[{"index":0},{"index":1}]},
{"index":5,"nodeOffset":"-15.38 -2.81","parent":[{"index":2}]},
{"index":6,"nodeOffset":"-6.81 10.47","parent":[{"index":2},{"index":3},{"index":5}]},
{"index":7,"nodeOffset":"-5.42 10.54","parent":[{"index":4}]},
{"index":8,"nodeOffset":"11.73 11.99","parent":[{"index":6}]}
],
"config":{
"nodeValueAuto":"alphabetic-lower",
"algorithm":"Is graph connected"
}}
En la Figura vemos la exportación a Wolfram que usa la función ConnectedGraphQ[g], devolviendo también falso. Se ajusta el tamaño de los vértices tal como se observa en la Figura.
g = AdjacencyGraph[{{0,1,0,0,1,0,0,0,0},{1,0,0,0,1,0,0,0,0},{0,0,0,1,0,1,1,0,0},{0,0,1,0,0,0,1,0,0},{1,1,0,0,0,0,0,1,0},
{0,0,1,0,0,0,1,0,0},{0,0,1,1,0,1,0,0,1},{0,0,0,0,1,0,0,0,0},{0,0,0,0,0,0,1,0,0}},
ImageSize->219, VertexSize->{"Scaled", 0.1}, VertexLabels->{1->Placed["a",Center], 2->Placed["b",Center],
3->Placed["c",Center], 4->Placed["d",Center], 5->Placed["e",Center], 6->Placed["f",Center], 7->Placed["g",Center],
8->Placed["h",Center], 9->Placed["i",Center]}, VertexLabelStyle->Directive[Black,17.5], EdgeLabelStyle->Directive[Black,17.5,Bold],
VertexStyle->White, EdgeStyle->{{Black,Thickness[0.005]}}];
ConnectedGraphQ[g]
En la Figura vemos la opción forzar no dirigido, única opción para saber si un grafo es conectado. Si el grafo es no dirigido se ignora esa opción. Si el grafo es dirigido y se marca la opción se trata el grafo como si fuera no dirigido, con lo que estaríamos cuestionando si el grafo es débilmente conectado. Si el grafo es dirigido y no se marca la opción, entonces la cuestión es saber si el grafo es fuertemente conectado.
En la Figura vemos un grafo dirigido NO fuertemente conectado pero SÍ débilmente conectado. La aplicación sólo devuelve true o false, con lo que se determina si está conectado, débilmente conectado o fuertemente conectado observado la direccionalidad del grafo y el argumento para forzar no dirigido:
| Dirigido | Forzar no dirigido | isGraphConnected() |
|---|---|---|
| NO | - | ¿Conectado? |
| SÍ | SÍ | ¿Débilmente conectado? |
| SÍ | NO | ¿Fuertemente conectado? |
Observe que en la Figura del apartado anterior obtuvimos 2 componentes fuertemente conectados, con lo que el grafo NO es fuertemente conectado pues para serlo sólo debería tener UN único componente fuertemente conectado.
Con este JSON se importa el ejemplo cuestionando si el grafo es fuertemente conectado, pues es dirigido y no activamos la opción forzar no dirigido. El resultado es que NO es fuertemente conectado:
{"nodes":[
{"index":0,"parent":[{"index":-1}]},
{"index":1,"value":"X","parent":[{"index":0,"value":"A"}]},
{"index":2,"parent":[{"index":0,"value":"B"},{"index":1,"value":"C"}]},
{"index":3,"parent":[{"index":1,"value":"D","lineTextOffset":"-0.75 0.25"},{"index":4,"value":"E"}]},
{"index":4,"parent":[{"index":1,"value":"F"},{"index":2},{"index":0,"lineOffset":"1","markerReverse":true,"value":"G"}]}
],
"config":{
"markerEnd":"arrow",
"algorithm":"Is graph connected"
}}Con este JSON se importa el ejemplo cuestionando si el grafo es débilmente conectado, pues es dirigido y activamos la opción forzar no dirigido. El resultado es que SÍ es débilmente conectado:
{"nodes":[
{"index":0,"parent":[{"index":-1}]},
{"index":1,"value":"X","parent":[{"index":0,"value":"A"}]},
{"index":2,"parent":[{"index":0,"value":"B"},{"index":1,"value":"C"}]},
{"index":3,"parent":[{"index":1,"value":"D","lineTextOffset":"-0.75 0.25"},{"index":4,"value":"E"}]},
{"index":4,"parent":[{"index":1,"value":"F"},{"index":2},{"index":0,"lineOffset":"1","markerReverse":true,"value":"G"}]}
],
"config":{
"markerEnd":"arrow",
"algorithm":"Is graph connected",
"forceUndirected":true
}}
En Wolfram obtenemos lo mismo, pues en la Figura vemos que el grafo SÍ es débilmente conectado aplicando la función WeaklyConnectedGraphQ[g]. Y en la Figura vemos que NO es fuertemente conectado aplicando la función ConnectedGraphQ[g].
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->188,
VertexSize->{"Scaled", 0.17}, VertexLabels->{1->Placed[0,Center], 2->Placed["X",Center], 3->Placed[2,Center],
4->Placed[3,Center], 5->Placed[4,Center]}, VertexLabelStyle->Directive[Black,17.5],
EdgeLabelStyle->Directive[Black,17.5,Bold], EdgeLabels->{(2->1)->"A", (3->1)->"B", (3->2)->"C", (4->2)->"D", (4->5)->"E", (5->2)->"F", (1->5)->"G"},
VertexStyle->White, DirectedEdges->True, EdgeStyle->{{Black,Thickness[0.005]}}]
WeaklyConnectedGraphQ[g]Hay que entender que todo grafo fuertemente conectado es también débilmente conectado pero no necesariamente al revés, con lo que es mejor aclarar todas las posibilidades que tenemos para un grafo dirigido en la siguiente tabla, donde se expone un grafo dirigido de ejemplo para cada caso:
| Grafo dirigido | Débilmente conectado | Fuertemente conectado | Matriz | JSON |
|---|---|---|---|---|
 | NO | NO | 0 0 0 1 0 0 0 0 0 | {"nodes":[ {"index":0,"parent":[{"index":-1}]}, {"index":1,"parent":[{"index":0}]}, {"index":2,"parent":[{"index":-1}]} ], "config":{ "markerEnd":"arrow", "algorithm":"Is graph connected" }} |
| No existe | NO | SÍ | Todo grafo fuertemente conectado es también débilmente conectado | |
 | SÍ | NO | 0 0 0 1 0 0 1 1 0 | {"nodes":[ {"index":0,"parent":[{"index":-1}]}, {"index":1,"parent":[{"index":0}]}, {"index":2,"parent":[{"index":-1},{"index":0},{"index":1}]} ], "config":{ "markerEnd":"arrow", "algorithm":"Is graph connected", "forceUndirected":true }} |
 | SÍ | SÍ | 0 0 1 1 0 0 0 1 0 | {"nodes":[ {"index":0,"parent":[{"index":-1},{"index":2}]}, {"index":1,"parent":[{"index":0}]}, {"index":2,"parent":[{"index":-1},{"index":1}]} ], "config":{ "markerEnd":"arrow", "algorithm":"Is graph connected" }} |
El código JavaScript para ejecutar isGraphConnected() que se expone a continuación usa lo siguiente:
isGraphDirected()para saber si un grafo es dirigido.getDepthFirstSearchRecursive()para realizar una búsqueda en profundidad.getConnectedComponentspara obtener los componentes conectados.
Si el grafo no es dirigido o se fuerza a no dirigido sólo basta hacer una búsqueda en profundidad y observar que el total de nodos visitados coincide con el total de nodos del grafo.
Si el grafo es dirigido y no se fuerza a no dirigido obtenemos los componentes fuertemente conectados como vimos en el apartado anterior, observando que sólo se obtiene un único componente.
function isGraphConnected({matrix=[], forceUndirected=false}){
let result = false, temp;
try {
let directed = isGraphDirected({matrix});
if (typeof directed==="string") throw new Error(directed);
let n = matrix.length;
if (!directed || forceUndirected) {
if (temp = getDepthFirstSearchRecursive({matrix, index:0, forceUndirected}), typeof temp==="string") throw new Error(temp);
result = temp.visited.length === n;
} else {
if (temp = getConnectedComponents({matrix, forceUndirected:false}), temp.error) throw new Error(temp.error);
result = temp.length===1;
}
} catch(e){result = e.message}
return result;
}Es el grafo totalmente desconectado isGraphAllDisconnected()
En el apartado anterior vimos el algoritmo IsGraphConnected() que nos decía si un grafo es o no conectado. Pero esa información no es suficiente para saber si el grafo está totalmente desconectado en el sentido de que todos sus nodos están desconectados, o lo que es lo mismo, que el grafo no tiene aristas. Los dos grafos de la Figura y de la Figura son ambos desconectados, pero sólo el primero es totalmente desconectado.
Con estos dos JSON puede importar esos ejemplos:
{"nodes":[
{"index":0,"nodeOffset":"7.5","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"-0.18 30","parent":[{"index":-1}]},
{"index":2,"nodeOffset":"-59.82 30","parent":[{"index":-1}]}
],
"config":{
"algorithm":"Is graph all disconnected"
}}
{"nodes":[
{"index":0,"nodeOffset":"7.5 0","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"-0.18 30","parent":[{"index":-1}]},
{"index":2,"nodeOffset":"-59.82 30","parent":[{"index":-1},{"index":0}]}
],
"config":{
"algorithm":"Is graph connected"
}}El código JavaScript para ejecutar isGraphAllDisconnected() es el siguiente, usando getMatrixModeValue() para obtener el modo valores de la matriz y el valor nulo nullValue. Así cuando una matriz de adyacencia tiene todo los valores nulos significa que no tiene aristas y, por tanto, es totalmente desconectado.
function isGraphAllDisconnected({matrix=[]}){
let result = false, temp;
try {
if (temp = getMatrixModeValue({matrix}), typeof temp==="string") throw new Error (temp);
let [modeValue, nullValue] = temp;
result = matrix.flat().every(v => v===nullValue);
} catch(e){result = e.message}
return result;
}No veo en Wolfram una función específica para esto. Podría pensarse que usando getConnectedComponents(), o su equivalente ConnectedComponents en Wolfram, podría deducirse si un grafo es totalmente desconectado. Pero el siguiente ejemplo demuestra que no es tan simple como se plantea.
En la Figura vemos los 3 componentes conectados de un grafo sin aristas, siendo por ello totalmente desconectado.
Componentes conectados: [
{"visited":[0],"path":[]},
{"visited":[1],"path":[]},
{"visited":[2],"path":[]}]Podría deducirse que es totalmente desconectado pues el número de componentes conectados es igual que el número de nodos del grafo, con cada componente conectado con un único nodo. Pero a continuación veremos que no es suficiente.
{"nodes":[
{"index":0,"nodeOffset":"7.5","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"-0.18 30","parent":[{"index":-1}]},
{"index":2,"nodeOffset":"-59.82 30","parent":[{"index":-1}]}
],
"config":{
"markerEnd":"arrow",
"algorithm":"Get connected components"
}}
El grafo dirigido de la Figura también tienes 3 componentes fuertemente conectados, pero no es totalmente desconectado dado que existe la arista "2🡒0".
Componentes conectados: [
{"visited":[0],"path":[]},
{"visited":[1],"path":[]},
{"visited":[2],"path":[]}]Se obtienen los mismos componentes conectados que para el otro ejemplo, con lo que no es suficiente para decidir si el grafo es totalmente desconectado.
{"nodes":[
{"index":0,"nodeOffset":"7.5","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"-0.18 30","parent":[{"index":-1}]},
{"index":2,"nodeOffset":"-59.82 30","parent":[{"index":-1},{"index":0}]}
],
"config":{
"markerEnd":"arrow",
"algorithm":"Get connected components"
}}Existe la posibilidad de usar getEdges() de tal forma que si no se obtienen aristas será totalmente desconectado, pero el algoritmo que usamos en nuestra aplicación es mucho más simple y eficiente que el de obtención de aristas. Para exportar a Wolfram sí usamos la obtención de aristas para hacer esa comprobación:
e = EdgeList[g]
Length[e]==0
Es vértice articulación isVertexArticulation()
Un vértice articulación es aquel que al eliminarlo hace que el grafo tenga más componenes conectados. El algoritmo isVertexArticulation() nos dice si un vértice es articulación. En la Figura podemos ver que lo es el nodo "1", pero también los nodos "2", "4" y "6". Puede denominarse también vértice separador, pero estos pueden darse en subconjuntos de tamaños mayor que uno como veremos en un apartado siguiente para encontrar conjunto separador de vértices, reservándose el término vértice articulación cuando se trata de un único vértice.
En la Figura se observan las opciones para ejecutar el algoritmo. Con el siguiente JSON puede importar el ejemplo anterior.
{"nodes":[
{"index":0,"nodeOffset":"-23.36 0.77","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"17.74 -24.06","parent":[{"index":0}]},
{"index":2,"nodeOffset":"-8.02 0.71","parent":[{"index":-1},{"index":1}]},
{"index":3,"nodeOffset":"48.85 -24.57","parent":[{"index":2}]},
{"index":4,"nodeOffset":"-22.12 11.84","parent":[{"index":0},{"index":1}]},
{"index":5,"nodeOffset":"-15.38 -2.81","parent":[{"index":2}]},
{"index":6,"nodeOffset":"-6.81 10.47","parent":[{"index":2},{"index":3},{"index":5}]},
{"index":7,"nodeOffset":"-5.42 10.54","parent":[{"index":4}]},
{"index":8,"nodeOffset":"11.73 11.99","parent":[{"index":6}]}
],
"config":{
"algorithm":"Is vertex articulation",
"firstIndex":1
}}
En la Figura vemos la exportación a Wolfram encontrando el nodo etiquetado con "1" como vértice articulación, recordando que los nodos están etiquetados desde "0", por lo que ese nodo tiene índice "2" para Wolfram pues se inician en "1" mientras que en nuestra aplicación se inician en "0".
No encontré una función específica en Wolfram para saber si un vértice es articulación aparte de ArticulationVertices[g] que se considera obsoleta y remite a FindVertexCut[g] que encuentre un corte mínimo de vértices en un grafo. Lo mismo dice una referencia en Wolfram MathWorld Articulation Vertex remitiendo a FindVertexCut[g]. Pero no veo que esa función haga exactamente lo mismo, pues es verdad que encuentra un primer vértice de corte (que es también de articulación), pero no todos ni comprueba alguno específicamente.
Aunque obsoleto ArticulationVertices[g] sigue funcionando y es lo que usamos. Vemos que obtiene los vértices {2, 3, 5, 7}, que se corresponden con [1, 2, 4, 6] en nuestra aplicación pues en Wolfram los índices se inician en "1" y en nuestra aplicación en "0". Y que el nodo "2" ("1" para nosotros) que cuestionamos es vértice articulación pues está incluido en esa lista.
g = AdjacencyGraph[{{0,1,0,0,1,0,0,0,0},{1,0,1,0,1,0,0,0,0},{0,1,0,1,0,1,1,0,0},{0,0,1,0,0,0,1,0,0},{1,1,0,0,0,0,0,1,0},
{0,0,1,0,0,0,1,0,0},{0,0,1,1,0,1,0,0,1},{0,0,0,0,1,0,0,0,0},{0,0,0,0,0,0,1,0,0}}, ImageSize->300, 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], 7->Placed[6,Center], 8->Placed[7,Center], 9->Placed[8,Center]}, VertexLabelStyle->Directive[Black,17.5],
EdgeLabelStyle->Directive[Black,17.5,Bold], VertexStyle->White, EdgeStyle->{{Black,Thickness[0.005]}}];
v = 2;
a = ResourceFunction["ArticulationVertices"][g]
ContainsAll[a, {v}]
If[%,HighlightGraph[g, v, VertexLabelStyle-> Directive[White, 17.5]],g]
Con el grafo dirigido de la Figura si en las opciones que se observan en la Figura marcamos la opción forzar no dirigido, el algoritmo considerará el grafo como no dirigido obteniéndose lo mismo que vimos en el ejemplo anterior.
En otro caso para un grafo dirigido un vértice es articulación si su eliminación supone incrementar el número de componentes fuertemente conectados como explicamos más arriba.
En la Figura vemos los componentes fuertemente conectados en el grafo dirigido, grafo que ya vimos en un apartado anterior cuando explicábamos esto en la Figura.
Se observa que si eliminamos el nodo "0" desaparece el primer componente fuertemente conectado "0🡒1, 1🡒4, 4🡒0" pasando a ser dos componentes fuertemente conectados separados "1" y "4", con lo que el total de componentes fuertementes conectados del grafo se incrementa.
Podemos encontrar todos los vértices de corte o articulación con findVertexSeparator() marcando la opción encontrar todos obteniendo [[0],[1],[2],[4],[6]]. Se puede analizar fácilmente que eliminando cualquiera de estos vértices se incrementa el número de componentes fuertemente conectados.
{"nodes":[
{"index":0,"nodeOffset":"-23.36 0.77","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"9.41 -24.06","parent":[{"index":0}]},
{"index":2,"nodeOffset":"-8.02 0.71","parent":[{"index":-1}]},
{"index":3,"nodeOffset":"32.18 -24.57","parent":[{"index":2}]},
{"index":4,"nodeOffset":"-5.45 -13.16","parent":[{"index":1},{"index":0,"markerStart":"none","markerEnd":"arrow"}]},
{"index":5,"nodeOffset":"-23.71 -2.81","parent":[{"index":2}]},
{"index":6,"nodeOffset":"9.85 -14.53","parent":[{"index":3},{"index":5},{"index":2,"markerStart":"none","markerEnd":"arrow"}]},
{"index":7,"nodeOffset":"-5.42 -14.46","parent":[{"index":4}]},
{"index":8,"nodeOffset":"11.73 -13.01","parent":[{"index":6}]}
],
"config":{
"markerStart":"arrow",
"algorithm":"Is vertex articulation"
}}
Para exportar isVertexArticulation() a Wolfram usábamos ResourceFunction["ArticulationVertices"][g] como vimos antes para un grafo no dirigido. Pero como se observa en la Figura resultando que el nodo "1" (etiquetado con "0") no es un vértice articulación, es posible que no funcione adecuadamente con grafos dirigidos.
g = AdjacencyGraph[{{0,1,0,0,0,0,0,0,0},{0,0,0,0,1,0,0,0,0},{0,0,0,1,0,1,0,0,0},{0,0,0,0,0,0,1,0,0},{1,0,0,0,0,0,0,1,0},
{0,0,0,0,0,0,1,0,0},{0,0,1,0,0,0,0,0,1},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}}, ImageSize->219,
VertexSize->{"Scaled", 0.14}, 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], 7->Placed[6,Center], 8->Placed[7,Center], 9->Placed[8,Center]},
VertexLabelStyle->Directive[Black,17.5], EdgeLabelStyle->Directive[Black,17.5,Bold], VertexStyle->White, DirectedEdges->True,
EdgeStyle->{{Black,Thickness[0.005]}}];
v = 1;
a = ResourceFunction["ArticulationVertices"][g];
ContainsAll[a, {v}]
If[%,HighlightGraph[g, v, VertexLabelStyle-> Directive[White, 17.5]],g]El código JavaScript para ejecutar isVertexArticulation() se muestra a continuación. Usa getConnectedComponents() que vimos al inicio de este tema, contando los componentes del grafo, eliminando el vértice en cuestión y volviendo a contar componentes para ver si han aumentado, en cuyo caso el vértice será de articulación. Hacemos una copia de la matriz para no modificar la original que se recibe por referencia.
function isVertexArticulation({matrix=[], index=-1, forceUndirected=true}) {
let result = false;
try {
let components1 = getConnectedComponents({matrix, forceUndirected});
if (typeof components1==="string") throw new Error(components1);
let n = matrix.length;
if (index<0 || index>=n) throw new Error(`Vertex '${index}' does not exists`);
let matrixCopy = JSON.parse(JSON.stringify(matrix));
for (let i=0; i<n; i++){
matrixCopy[i].splice(index, 1);
}
matrixCopy.splice(index, 1);
let components2 = getConnectedComponents({matrix:matrixCopy, forceUndirected});
if (typeof components2==="string") throw new Error(components2);
result = components2.length>components1.length;
} catch(e){result = e.message}
return result;
}Es arista puente isEdgeBridge()
Una arista puente es aquella que al eliminarla hace que el grafo tenga más componenes conectados. También podemos denominarla arista de separación como veremos en un apartado siguiente para encontrar un conjunto separador de aristas, donde pueden darse en subconjuntos de tamaños mayores que uno, reservándose así el término arista puente para el caso de una única arista. En la Figura vemos la arista puente "1-2" pues al eliminar tendremos un grafo con 2 componentes conectados. También son aristas puentes "4-7" y "6-8".
{"nodes":[
{"index":0,"nodeOffset":"-23.36 0.77","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"17.74 -24.06","parent":[{"index":0}]},
{"index":2,"nodeOffset":"-8.02 0.71","parent":[{"index":-1},{"index":1}]},
{"index":3,"nodeOffset":"48.85 -24.57","parent":[{"index":2}]},
{"index":4,"nodeOffset":"-22.12 11.84","parent":[{"index":0},{"index":1}]},
{"index":5,"nodeOffset":"-15.38 -2.81","parent":[{"index":2}]},
{"index":6,"nodeOffset":"-6.81 10.47","parent":[{"index":2},{"index":3},{"index":5}]},
{"index":7,"nodeOffset":"-5.42 10.54","parent":[{"index":4}]},
{"index":8,"nodeOffset":"11.73 11.99","parent":[{"index":6}]}
],
"config":{
"algorithm":"Is edge bridge",
"edge":"1,2"
}}
En la Figura vemos la exportación a Wolfram cuestionando si la arista "2-3" es una arista puente. Vea que se corresponde con las etiquetas "1-2", pues en Wolfram los índices se inician en "1" y en nuestra aplicación en "0".
Usamos FindEdgeCut[g, 2, 3] comprobando que esa arista es de corte. En el siguiente tema veremos la función equivalente en nuestra aplicación a FindEdgeCut[g, s, t] que es encontrar corte mínimo de aristas s-t con findSTEdgeCut(), donde el mínimo para grafos no ponderados se refiere al mínimo número de aristas que son necesarias separar los nodos "s" y "t" en distintos componentes conectados, observando que cuando el grafo tiene una arista puente entre nodos "s" y "t" entonces el corte mínimo entre "s" y "t" es uno y coincide con esa arista puente.
g = AdjacencyGraph[{{0,1,0,0,1,0,0,0,0},{1,0,1,0,1,0,0,0,0},{0,1,0,1,0,1,1,0,0},{0,0,1,0,0,0,1,0,0},{1,1,0,0,0,0,0,1,0},
{0,0,1,0,0,0,1,0,0},{0,0,1,1,0,1,0,0,1},{0,0,0,0,1,0,0,0,0},{0,0,0,0,0,0,1,0,0}}, ImageSize->300, 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], 7->Placed[6,Center], 8->Placed[7,Center], 9->Placed[8,Center]}, VertexLabelStyle->Directive[Black,17.5],
EdgeLabelStyle->Directive[Black,17.5,Bold], VertexStyle->White, EdgeStyle->{{Black,Thickness[0.005]}}];
e = {2, 3};
f = FindEdgeCut[g, First[e], Last[e]];
v = VertexList[f];
h = HighlightGraph[g, f];
Or[And[First[e]==First[v], Last[e]==Last[v]], And[First[e]==Last[v], Last[e]==First[v]]]
If[%, HighlightGraph[h, e, VertexLabelStyle-> Directive[White, 17.5]], h]Luego veremos que con findEdgeSeparator() podemos encontrar todas los conjuntos separadores de aristas de tamaño 1 resultando [[1,2]], [[4,7]], [[6,8]].
isEdgeBridge() En la Figura vemos las opciones arista que si es no dirigido puede pasarse como "u,v" o "v,u" pero si es dirigido y se pasa "u,v" se entiende "u🡒v" y si se pasa "v,u" se entiende "v🡒u". Con la opción arista con valores nodos en lugar de usar los índices de los nodos podemos usar sus etiquetas. Con forzar no dirigido se tratara el grafo como no dirigido.
Las opciones color camino, color texto y color fondo nodo no forma parte del algoritmo isEdgeBridge() y se aplican al resultado obtenido para mostrarlo en el SVG.
Con un grafo dirigido como el de la Figura, si marcamos la opción forzar no dirigido, el algoritmo tratará el grafo como no dirigido, en cuyo caso eliminar la arista "0🡒1" no incrementa el número de componentes débilmente conectados. En otro caso la arista "0🡒1" es puente pues su eliminación incrementará el número de componentes fuertemente conectados.
En la Figura vemos los componentes fuertemente conectados en el grafo dirigido, grafo que ya vimos en un apartado anterior cuando explicábamos esto en la Figura.
Se observa que al eliminar la arista "0🡒1" el componente fuertemente conectado "0🡒1", 1🡒4, 4🡒0" deja de serlo, con lo que tendremos 3 componentes fuertemente conectados "0", "1" y "4", incrementándose el número total.
Con findEdgeSeparator() con la opción encontrar todos obtenemos todas las aristas puente o de separación del grafo: [[[0,1]], [[1,4]], [[2,3]], [[2,5]], [[3,6]], [[4,0]], [[5,6]], [[6,2]]], observando que son las aristas de los dos primeros componentes de la Figura. Eliminar cualquiera de ellas incrementará el número de componentes. Es obvio que eliminar alguna del resto de aristas "4🡒7" o "6🡒8" no modificará el número de componentes.
{"nodes":[
{"index":0,"nodeOffset":"-23.36 0.77","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"9.41 -24.06","parent":[{"index":0}]},
{"index":2,"nodeOffset":"-8.02 0.71","parent":[{"index":-1}]},
{"index":3,"nodeOffset":"32.18 -24.57","parent":[{"index":2}]},
{"index":4,"nodeOffset":"-5.45 -13.16","parent":[{"index":1},{"index":0,"markerStart":"none","markerEnd":"arrow"}]},
{"index":5,"nodeOffset":"-23.71 -2.81","parent":[{"index":2}]},
{"index":6,"nodeOffset":"9.85 -14.53","parent":[{"index":3},{"index":5},{"index":2,"markerStart":"none","markerEnd":"arrow"}]},
{"index":7,"nodeOffset":"-5.42 -14.46","parent":[{"index":4}]},
{"index":8,"nodeOffset":"11.73 -13.01","parent":[{"index":6}]}
],
"config":{
"markerStart":"arrow",
"algorithm":"Is edge bridge",
"edge":"0,1",
"findAll":true
}}
En la Figura vemos la exportación a Wolfram, con el mismo resultado usando FindEdgeCut[g, 1, 2] que no está concebida realmente para ese uso, pero nos remitimos a lo expuesto para el ejemplo de la Figura.
g = AdjacencyGraph[{{0,1,0,0,0,0,0,0,0},{0,0,0,0,1,0,0,0,0},{0,0,0,1,0,1,0,0,0},{0,0,0,0,0,0,1,0,0},{1,0,0,0,0,0,0,1,0},{0,0,0,0,0,0,1,0,0},
{0,0,1,0,0,0,0,0,1},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}}, ImageSize->219, VertexSize->{"Scaled", 0.14},
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], 7->Placed[6,Center], 8->Placed[7,Center], 9->Placed[8,Center]}, VertexLabelStyle->Directive[Black,17.5],
EdgeLabelStyle->Directive[Black,17.5,Bold], VertexStyle->White, DirectedEdges->True, EdgeStyle->{{Black,Thickness[0.005]}}];
e = {1, 2};
f = FindEdgeCut[g, First[e], Last[e]];
v = VertexList[f];
h = HighlightGraph[g, f];
And[First[e]==First[v], Last[e]==Last[v]]
If[%, HighlightGraph[h, e, VertexLabelStyle-> Directive[White, 17.5]], h]A continuación se muestra el JavaScript del algoritmo isEdgeBridge() que usa isGraphDirected() para saber si el grafo es dirigido. También usamos getEdges() para obtener las aristas comprobar si la arista en cuestión existe. Y getConnectedComponents() que vimos al inicio de este tema, contando los componentes del grafo, eliminando la arista en cuestión y volviendo a contar componentes para ver si han aumentado, en cuyo caso la arista será puente. Hacemos una copia de la matriz para no modificar la original que se recibe por referencia.
function isEdgeBridge({matrix=[], edge=[-1, -1], forceUndirected=true}) {
let result = false;
try {
let directed = isGraphDirected({matrix});
if (typeof directed==="string") throw new Error(directed);
let components1 = getConnectedComponents({matrix, forceUndirected});
if (typeof components1==="string") throw new Error(components1);
let n = matrix.length;
if (edge[0]<0 || edge[1]<0 || edge[0]>n-1 || edge[1]>n-1) throw new Error(`Edge '[${edge.toString()}]' is wrong`);
let edges = getEdges({matrix, edgesCompact:false});
if (typeof edges==="string") throw new Error(edges);
edges = Object.keys(edges);
if (!edges.some(v => v.toString()===edge.toString())) throw new Error(`Edge '[${edge.toString()}]' doesn't exist`);
let matrixCopy = JSON.parse(JSON.stringify(matrix));
let [i, j] = edge;
matrixCopy[i][j] = 0;
if (!directed || forceUndirected) matrixCopy[j][i] = 0;
let components2 = getConnectedComponents({matrix:matrixCopy, forceUndirected});
if (typeof components2==="string") throw new Error(components2);
result = components2.length>components1.length;
} catch(e){result = e.message}
return result;
}Encontrar todos los vértices articulación findAllArticulationVertex()
Todos los vértices articulación en un grafo son todos aquellos vértices cuya eliminación individual incrementa el número de componentes conectados. En la Figura vemos que "4" y "6" son todos los vértices de articulación del grafo.
Encontrar todos los vértices articulación: [4,6]
{"nodes":[
{"index":0,"nodeOffset":"-23.36 0.77","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"17.74 -24.06","parent":[{"index":0}]},
{"index":2,"nodeOffset":"-8.02 0.71","parent":[{"index":-1}]},
{"index":3,"nodeOffset":"48.85 -24.57","parent":[{"index":2}]},
{"index":4,"nodeOffset":"-22.12 11.84","parent":[{"index":0},{"index":1}]},
{"index":5,"nodeOffset":"-15.38 -2.81","parent":[{"index":2}]},
{"index":6,"nodeOffset":"-6.81 10.47","parent":[{"index":2},{"index":3},{"index":5}]},
{"index":7,"nodeOffset":"-5.42 10.54","parent":[{"index":4}]},
{"index":8,"nodeOffset":"11.73 11.99","parent":[{"index":6}]}
],
"config":{
"lineHeight":18.75,
"algorithm":"Find all articulation vertex"
}}
Para un grafo dirigido todos los vértices de articulación son los que incrementan el número de componentes fuertemente conectados. En la Figura vemos que "0" y "4" son todos los vértices de articulación de ese grafo.
Para entender el motivo vemos en la Figura los dos componentes fuertemente conectados del grafo, que recordamos que son así pues desde cualquier nodo en un componente podemos acceder a cualquier otro del mismo componente. Sólo si eliminamos el nodo "0" o el "4" no tendremos ese acceso en el primer componente y el número de componentes pasa de 2 a 4.
{"nodes":[
{"index":0,"parent":[{"index":-1}]},
{"index":1,"value":"X","parent":[{"index":0,"value":"A"}]},
{"index":2,"parent":[{"index":0,"value":"B"},{"index":1,"value":"C"}]},
{"index":3,"parent":[{"index":1,"value":"D","lineTextOffset":"-0.75 0.25"},{"index":4,"value":"E"}]},
{"index":4,"parent":[{"index":1,"value":"F"},{"index":2},{"index":0,"lineOffset":"1","markerReverse":true,"value":"G"}]}
],
"config":{
"markerEnd":"arrow",
"algorithm":"Find all articulation vertex"
}}El JavaScript de findAllArticulationVertex() se muestra a continuación, usando getConnectedComponents() para obtenerlos al inicio y luego iterar por todos los vértices y comprobar que eliminando ese vértice se incrementa el número de componentes.
function findAllArticulationVertex({matrix=[]}) {
let result = [], temp;
try {
let n = matrix.length;
let components1 = getConnectedComponents({matrix, forceUndirected:false});
if (typeof components1==="string") throw new Error(components1);
for (let index=0; index<n; index++) {
let matrixCopy = JSON.parse(JSON.stringify(matrix));
matrixCopy.map(v => v.splice(index, 1));
matrixCopy.splice(index, 1);
let components2 = getConnectedComponents({matrix:matrixCopy, forceUndirected:false});
if (typeof components2==="string") throw new Error(components2);
if (components2.length>components1.length) result.push(index);
}
} catch(e){result = e.message}
return result;
}Encontrar todas las aristas puente findAllEdgeBridge()
Todas las aristas puente de un grafo dirigido son aquellas aristas que al eliminarlas individualmente incrementan el número de componentes fuertemente conectados del grafo. En la Figura vemos que hay 3 de estas aristas:
Encontrar todas aristas puente: [[0,4],[1,0],[4,2]]
Para entender ese resultado debemos recordar el número de componentes fuertemente conectados que ya vimos para este mismo ejemplo en el primer apartado:
Se observa en la Figura que tiene 2 componentes fuertemente conectados, recordando que estos componentes se caracterizan porque hay un camino desde cualquier nodo a otro dentro del componente. Si eliminamos la arista "0🡒4" ya no existirá ese camino, al igual que al elminar la arista "1🡒0" o la arista "4🡒2", creándose en estos casos tantos componentes como nodos "0,1,2,4" con lo que el número de componentes del grafo pasa de 2 a 5.
{"nodes":[
{"index":0,"parent":[{"index":-1}]},
{"index":1,"value":"X","parent":[{"index":0,"value":"A"}]},
{"index":2,"parent":[{"index":0,"value":"B"},{"index":1,"value":"C"}]},
{"index":3,"parent":[{"index":1,"value":"D","lineTextOffset":"-0.75 0.25"},{"index":4,"value":"E"}]},
{"index":4,"parent":[{"index":1,"value":"F"},{"index":2},{"index":0,"lineOffset":"1","markerReverse":true,"value":"G"}]}
],
"config":{
"markerEnd":"arrow",
"algorithm":"Find all edge bridge"
}}Tal como veremos después en el código JavaScript del algoritmo findAllEdgeBridge() para un grafo dirigido, se trata de obtener los componentes conectados del grafo inicial con getConnectedComponents(), luego obtener todas las aristas del grafo e iterar por ellas eliminando una y comprobar si el número de componentes fuertemente conectados se incrementa, en cuyo caso es una arista puente.
La misma técnica que acabamos de explicar para encontrar todas las aristas puente a de un grafo dirigido podría aplicarse a uno no dirigido. Sin embargo existe un algoritmo más eficiente que vamos a explicar ahora. En la Figura vemos las 4 aristas puente de un grafo dirigido, de tal forma que son todas las aristas que eliminadas invididualmente incrementan el número de componentes conectados.
Encontrar todas aristas puente: [[6,8],[6,9],[1,2],[4,7]]
{"nodes":[
{"index":0,"nodeOffset":"-15.03 0.77","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"17.74 -24.06","parent":[{"index":0},{"index":2}]},
{"index":2,"nodeOffset":"8.65 0.71","parent":[{"index":-1}]},
{"index":3,"nodeOffset":"48.85 -24.57","parent":[{"index":2}]},
{"index":4,"nodeOffset":"-22.12 11.84","parent":[{"index":0},{"index":1}]},
{"index":5,"nodeOffset":"-15.38 -2.81","parent":[{"index":2}]},
{"index":6,"nodeOffset":"-6.81 10.47","parent":[{"index":2},{"index":3},{"index":5}]},
{"index":7,"nodeOffset":"-5.42 10.5","parent":[{"index":4}]},
{"index":8,"nodeOffset":"-9.07 10.5","parent":[{"index":6}]},
{"index":9,"nodeOffset":"8.8 60.5","parent":[{"index":-1},{"index":6}]}
],
"config":{
"lineHeight":18.75,
"algorithm":"Find all edge bridge"
}}Encontrar todas las aristas puente puede también hacerse con findEdgeSeparator({matrix, findAll:true, sizeSeparator:1}) especificando encontrar todos y tamaño separador igual a 1.
En la Figura vemos la ejecución del algoritmo findAllEdgeBridge() que encuentra la única arista puente [2, 3] en un grafo no dirigido más sencillo, con el que intentaré explicar como funciona. Es una adaptación de algunos que pueden verse en Internet, como Finding bridges in a graph.
Se basa en el algoritmo DFS, búsqueda en profundidad recursivo que ya vimos en un tema anterior. En la Figura vemos la ejecución del DFS donde los nodos son visitados según indica el número de orden de los subíndices de los nodos con índices 0, 1, 2, 3, que coincide con el mismo orden 1°, 2°, 3°, 4°. Puede importar el ejemplo con este JSON:
{"nodes":[
{"index":0,"nodeOffset":"-10 -2.5","parent":[{"index":-1},{"index":1},{"index":2}]},
{"index":1,"nodeOffset":"-30 17.5","parent":[{"index":-1}]},
{"index":2,"nodeOffset":"-25 7.5","parent":[{"index":-1},{"index":1},{"index":3}]},
{"index":3,"nodeOffset":"-20 7.5","parent":[{"index":-1}]}
],
"config":{
"algorithm":"Find all edge bridge"
}}Cuando avanzamos por un DFS estaremos en un nodo "i" que tiene una arista a otro nodo "p". Esta arista "i-p" es un puente sí y sólo sí el nodo "p" y todos a los que pudiéramos acceder desde "p" no tiene una arista de vuelta (back) al nodo "i" o alguno por encima desde el que se pueda acceder a "i". Esto significa que el único camino posible entre "i" y "p" es a través de la única arista "i-p".
En la Figura vemos que esto sólo sucede con la arista "2-3" donde desde "3" no podemos acceder a nodos anteriores si no es por esa arista.
Como todo recursivo, no es fácil seguir los acontecimientos. Pero si después de dfs(parent, index), es decir, al retorno de las llamadas recursivas, ponemos la sentencia console.log(index, parent, visited, back), obtenemos estos datos en los retornos de las llamadas recursivas:
| i (index) | p (parent) | visited | back | back[p] | visited[i] | Bridge |
|---|---|---|---|---|---|---|
| 2 | 3 | [1,2,3,4] | [1,2,1,4] | back[3]=4 | visited[2]=3 | 4>3 ⇒ [2, 3] |
| 1 | 2 | [1,2,3,4] | [1,2,1,4] | back[2]=1 | visited[1]=2 | 1<2 |
| 0 | 1 | [1,2,3,4] | [1,1,1,4] | back[1]=1 | visited[0]=1 | 1=1 |
Los números 1,2,3,4 son los números de orden de visita de los nodos que vamos incrementando en la variable orderNumVisit en el algoritmo en cada llamada. En un recursivo como este se producen todas las llamadas primero y luego los retornos en orden inverso, así que el primer retorno se corresponde con la última llamada.
Vea que visited = [1, 2, 3, 4] coincide con el orden de visita del DFS. En back = [1, 2, 1, 4] vamos poniendo el orden de visita cuando se descubre ese nodo, así back[2]=1 significa que el nodo "2" se descubrió con el primer orden de visita (con i=0) al descubrir la arista "0-2" pues "2" es un nodo conectado con "0" por esa arista. Si elimináramos esa arista "0-2" back sería igual que visited en todos los retornos de llamadas, así que back nos informa de lazos entre los nodos.
Se observa que cuando estamos en el nodo "i=2" y vemos "p=3" sucede que tendremos back=[1,2,1,4] donde back[3]=4 > visited[2]=3 con lo que [2, 3] será una arista puente. Si es "<" entonces hay un camino de vuelta desde "p" a alguno por encima de "i", como sucede con "i=1, p=2" donde hay un camino de vuelta "1-2-0-1" a través de "0" que está por encima de "1". Y si es estrictamente "=" el camino de vuelta es al propio "i", como con "i=0, p=1" donde el camino "0-1-2-0" no pasa por nodos que estén por encima.
En el algoritmo findAllEdgeBridge() siguiente usamos isGraphDirected(), getParents(), getEdges() y getConnectedComponents().
function findAllEdgeBridge({matrix=[]}) {
let result = [], temp;
try {
let directed = isGraphDirected({matrix});
if (typeof directed==="string") throw new Error(directed);
let n = matrix.length;
if (!directed) {
let visited = Array.from({length:n}, ()=>-1);
let back = Array.from({length:n}, ()=>-1);
let orderNumVisit = 0;
function dfs(index, lastIndex){
if (iter++, iter>maxIter) return `Maximum iterations '${maxIter}' reached`;
orderNumVisit++;
visited[index] = orderNumVisit;
back[index] = orderNumVisit;
let parents = getParents({matrix, index:index});
if (typeof parents==="string") throw new Error(parents);
for (let parent of parents) {
if (parent!==lastIndex) {
if (visited[parent]===-1) {
dfs(parent, index);
//console.log(index, parent, visited, back)
if (back[parent]>visited[index]) {
result.push([index, parent]);
}
back[index] = Math.min(back[index], back[parent]);
} else {
back[index] = Math.min(back[index], visited[parent]);
}
}
}
}
for (let i=0; i<n; i++) {
if (visited[i]===-1) {
dfs(i, -1);
}
}
} else {
let components1 = getConnectedComponents({matrix, forceUndirected:false});
if (typeof components1==="string") throw new Error(components1);
let edges = getEdges({matrix, edgesCompact:true});
if (typeof edges==="string") throw new Error(edges);
for (let edge of edges) {
let matrixCopy = JSON.parse(JSON.stringify(matrix));
let [i, j] = edge;
matrixCopy[i][j] = 0;
if (!directed) matrixCopy[j][i] = 0;
let components2 = getConnectedComponents({matrix:matrixCopy, forceUndirected:false});
if (typeof components2==="string") throw new Error(components2);
if (components2.length>components1.length) result.push(edge);
}
}
} catch(e){result = e.message}
return result;
}Encontrar conjunto separador de vértices findVertexSeparator()
Encontrar un conjunto separador de vértices con tamaño "k" en un grafo no dirigido supone encontrar "k" vértices cuya eliminación hace que se incremente el número de componentes conectados del grafo. Cuando "k" es 1 entonces equivale a un vértice articulación.
Encontrar separador vértices: [[0,1,3,4],[0,2,3,5], [1,2,4,5]]
En la Figura vemos que la eliminación del subconjunto de vértices [0,1,3,4] de tamaño 4 desconecta el grafo. En total hay 3 de estos subconjuntos de tamaño 4 que desconectan el grafo. Es más, no hay ningún subconjunto inferior a 4 que lo desconecte, por el motivo que explicaremos después.
En la Figura vemos la opciones para ejecutar el algoritmo, con encontrar todos para obtener todos los conjuntos separadores con un tamaño separador determinado, conjuntos con vértices que si se eliminan incrementan el número de componentes conectados, que para el ejemplo hemos puesto que se deben encontrar conjuntos con 4 elementos.
Si se activa mínimo tamaño separador se ignorará la opción tamaño separador, iterando desde tamaño 1 hasta el total de vértices de tal forma que cuando encuentre un primer tamaño del conjunto separador de vértices devolverá ese conjunto encontrado, o todos de ese tamaño en caso de estar marcado encontrar todos. En el ejemplo si se activa esa opcion mínimo tamaño separador se intentará encontrar subconjuntos de tamaño 1, 2 y 3 sin éxito, siendo 4 el primer tamaño que desconecta el grafo.
Con forzar no dirigido se tratará el grafo dirigido como no dirigido. Luego veremos la opción con arista puente con un ejemplo. La opción color fondo nodo no se aplica en el algoritmo, sino posteriormente para presentar el grafo en el SVG. Por ahora este es el JSON del ejemplo:
{"nodes":[
{"index":0,"nodeOffset":"2.5","parent":[{"index":-1}]},
{"index":1,"nodeOffset":"37.14 -5","parent":[{"index":0}]},
{"index":2,"nodeOffset":"37.14 10","parent":[{"index":1},{"index":0}]},
{"index":3,"nodeOffset":"2.5 5","parent":[{"index":2},{"index":1}]},
{"index":4,"nodeOffset":"-32.14 -40","parent":[{"index":3},{"index":2},{"index":0}]},
{"index":5,"nodeOffset":"-32.14 -105","parent":[{"index":4},{"index":0},{"index":1},{"index":3}]}
],
"config":{
"algorithm":"Find vertex separator",
"findAll":true,
"sizeSeparator":4
}}
En la Figura vemos el Grafo de Petersen 5,2 encontrando un conjunto separador de vértices con la opción mínimo tamaño separador marcada, con lo que resulta que son de tamaño 3. Con la opción encontrar todos marcada obtenemos los siguientes 10 conjuntos separadores:
Encontrar separador vértices: [[0,2,6],[0,3,9],[0,7,8], [1,3,7],[1,4,5],[1,8,9], [2,4,8],[2,5,9],[3,5,6], [4,6,7]]
Si marcamos además la opción con arista puente de tal forma que sólo se seleccionan aquellos conjuntos de vértices que estén conectados por una arista, resulta que necesitamos llegar hasta subconjuntos de tamaño 7, obteniéndose 60 posibilidades de las que exponemos sólo algunas para no extendernos, mostrando en la Figura la primera.
Encontrar separador vértices: [[0,1,2,3,4,5,6], [0,1,2,3,4,5,9], ... 56 más ... [2,3,4,5,6,8,9], [2,4,5,6,7,8,9]]
Dado que tiene que comprobar muchas posibilidades hay que imponer la opción máximas iteraciones con un valor de 40000 cuando por defecto está en 10000.
{"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":{
"algorithm":"Find vertex separator",
"maxIter":40000,
"findAll":true,
"minimumSizeSeparator":true,
"withEdgeBridge":true
}}
En la Figura vemos los dos únicos vértices "0" y "4" con tamaño mínimo de separador del grafo dirigido, marcando las opciones mínimo tamaño separador y encontrar todos.
Recordemos que los 2 componentes fuertementes conectados de este grafo son los que vemos en la Figura, de tal forma que si eliminamos el nodo "0" tendremos 4 componentes conectados, uno por cada nodo restante del grafo pues no hay forma de recorrer todos los nodos si empezamos en cualquiera de ellos. Y de la misma forma con el nodo "4", pues en cualquier caso se incrementa el número de componentes conectados. Vea que la arista "0🡒4" es la que habilita que haya un camino entre cualquier nodo del subgrafo del primer componente, por lo que eliminar el "0" o el "4", incluso esa arista "0🡒4", quita esa posibilidad.
{"nodes":[
{"index":0,"parent":[{"index":-1}]},
{"index":1,"value":"X","parent":[{"index":0,"value":"A"}]},
{"index":2,"parent":[{"index":0,"value":"B"},{"index":1,"value":"C"}]},
{"index":3,"parent":[{"index":1,"value":"D","lineTextOffset":"-0.75 0.25"},{"index":4,"value":"E"}]},
{"index":4,"parent":[{"index":1,"value":"F"},{"index":2},{"index":0,"lineOffset":"1","markerReverse":true,"value":"G"}]}
],
"config":{
"markerEnd":"arrow",
"algorithm":"Find vertex separator",
"findAll":true,
"minimumSizeSeparator":true
}}A continuación vemos el JavaScript para ejecutar findVertexSeparator():
function findVertexSeparator({matrix=[], findAll=false, sizeSeparator=1, minimumSizeSeparator=false, withEdgeBridge=false, forceUndirected=true}) {
let result = [];
result.warnings = [];
try {
let components1 = getConnectedComponents({matrix, forceUndirected});
if (typeof components1==="string") throw new Error(components1);
let n = matrix.length;
let indexes = Array.from({length: n}, (v,i) => i);
sizeSeparator = Math.max(0, Math.min(sizeSeparator, n));
let [from, to] = [sizeSeparator, sizeSeparator];
if (minimumSizeSeparator) [from, to] = [1, n-1];
for (let sc=from; sc<=to; sc++) {
let combinations = combine(indexes, sc);
if (typeof combinations==="string") throw new Error(combinations);
if (combinations.hasOwnProperty("warning")){
result.warnings.push(combinations.warning);
}
for (let listVertexs of combinations) {
if (withEdgeBridge && listVertexs.length>1) {
let path = findCoveragePath({matrix, indexes:listVertexs});
if (typeof path==="string") throw new Error(path);
if (path.length===0) listVertexs = [];
}
let matrixCopy = [];
for (let i=0; i<n; i++){
let arr = [];
for (let j=0; j<n; j++) {
if (!(listVertexs.includes(i) || listVertexs.includes(j))) {
arr.push(matrix[i][j]);
}
}
if (arr.length>0) matrixCopy.push(arr);
}
iter = 0;
let components2 = getConnectedComponents({matrix:matrixCopy, forceUndirected});
if (typeof components2==="string") throw new Error(components2);
if (components2.length>components1.length) {
result.push([...listVertexs]);
if (!findAll) return result;
}
}
if (result.length>0) break;
}
} catch(e){result = e.message}
return result;
}Se usan las siguientes funciones:
getConnectedComponents()para obtener los componentes conectados que vimos al inicio en este tema.combine(list, k)para obtener las combinaciones de una lista de nodos, con el código que vemos después de esta lista.findCoveragePath()para encontrar un camino de cobertura de un conjunto de nodos.
function combine(list=[], k=0, n=list.length, res=Array.from({length:k}, ()=>""), result=[], n0=list.length, k0=res.length){
try {
if (k===0){
result.push([...res]);
} else {
for (let j=n; j>=k; j--){
res[k0-k] = list[n0-j];
combine(list, k-1, j-1, res, result);
}
}
} catch(e) {result = e.message}
return result;
}El funcionamiento es obtener los componentes conectados del grafo inicial y hacer un bucle que itere por tamaños de conjuntos separadores de vértices para ir probando aquellos que incrementen el número de componentes conectados. Con findCoveragePath() comprobamos si ese conjunto está unido por aristas, para el caso de que se pase la opción con arista puente (withEdgeBridge).
Este algoritmo no es eficiente para grafos con muchos vértices o cuando hay que encontrar todos los resultados. En el ejemplo que vimos más arriba tuvimos que imponer máximas iteraciones a 40000, cuando por defecto se establecen en 10000.
Para el grafo de la Figura con 20 nodos para encontrar todos los conjuntos separadores con mínimo tamaño separador y con arista puente marcados también, necesitamos 4500000 máximas iteraciones, con un tiempo de ejecución de casi 6 segundos.
Time: 5908 ms Encontrar separador vértices: [[0,1,2,3,8,9,10],[0,1,2,3,10,11,12], ...56 más... [11,12,13,15,16,17,18],[11,12,13,15,16,17,19]]
Se encuentran 60 resultados con tamaño 7 exigiendo que los nodos estén conectados con aristas.
{"nodes":[
{"index":0,"nodeOffset":"22.54 57.27","parent":[{"index":-1},{"index":1},{"index":14}]},
{"index":1,"nodeOffset":"44.52 -43.2","parent":[{"index":3},{"index":6}]},
{"index":2,"nodeOffset":"17.4 48.75","parent":[{"index":0},{"index":12}]},
{"index":3,"nodeOffset":"83.9 -1.06","parent":[{"index":4},{"index":8}]},
{"index":4,"nodeOffset":"32.7 36.8","parent":[{"index":2},{"index":10}]},
{"index":5,"nodeOffset":"71.71 -176.86","parent":[{"index":6},{"index":15}]},
{"index":6,"nodeOffset":"86.62 -162.22","parent":[{"index":7}]},
{"index":7,"nodeOffset":"100.97 -144.59","parent":[{"index":8},{"index":16}]},
{"index":8,"nodeOffset":"81.92 -115.15","parent":[{"index":9}]},
{"index":9,"nodeOffset":"62.27 -87.71","parent":[{"index":10},{"index":17}]},
{"index":10,"nodeOffset":"26.75 -88.91","parent":[{"index":11}]},
{"index":11,"nodeOffset":"-8.56 -88.44","parent":[{"index":12},{"index":18}]},
{"index":12,"nodeOffset":"-26.56 -117.68","parent":[{"index":13}]},
{"index":13,"nodeOffset":"-44.32 -145.05","parent":[{"index":14},{"index":19}]},
{"index":14,"nodeOffset":"-32.12 -161.29","parent":[{"index":5}]},
{"index":15,"nodeOffset":"52.8 -75.39","parent":[{"index":16}]},
{"index":16,"nodeOffset":"110.07 -22.57","parent":[{"index":17}]},
{"index":17,"nodeOffset":"64.51 58.23","parent":[{"index":18}]},
{"index":18,"nodeOffset":"-29.03 58.18","parent":[{"index":19}]},
{"index":19,"nodeOffset":"-70.45 -27.13","parent":[{"index":15}]}
],
"config":{
"lineHeight":18.75,
"algorithm":"Find vertex separator",
"maxIter":4500000,
"findAll":true,
"minimumSizeSeparator":true,
"withEdgeBridge":true
}}
Para el grafo de la Figura con 400 nodos, con la opción más simple que es sólo imponer tamaño separador con valor 3, pues sabemos previamente que es el mínimo tamaño de separador, necesitará 160000 iteraciones para encontrar en 1661 ms el primer conjunto [0, 2, 4].
Time: 1661 ms Encontrar separador vértices: [[0,2,4]]
Puede abrir cfi-400-nodes.txt con la lista de aristas de ese grafo en formato de texto que puede copiar e importar en la aplicación tal como explicamos en un tema anterior sobre como importar una lista de aristas.
Encontrar conjunto separador de aristas findEdgeSeparator()
Encontrar un conjunto separador de aristas con tamaño "k" supone encontrar "k" aristas que si se eliminan incrementarán el número de componentes conectados del grafo. Cuando "k" es 1 entonces estaríamos hablando de una arista puente. En la Figura vemos un grafo dirigido con el conjunto separador de aristas [[0,1],[0,6]], encontrándose en total 5 conjuntos con 2 aristas siguiente:
Encontrar separador aristas: [[[0,1],[0,6]], [[3,4],[3,5]], [[3,4],[4,5]], [[3,5],[4,5]], [[6,9],[8,9]]]
Para la ejecución del ejemplo anterior se pasan las opciones encontrar todos y mínimo tamaño separador ambas marcadas, que tal como comentamos en el apartado anterior, con esta última marcada se ignora la opción tamaño separador y buscará desde 1 el primer tamaño, resultando ser en el ejemplo el tamaño 2. La opción forzar no dirigido sólo se aplica a grafos dirigidos, que en caso de marcarse lo tratará como no dirigido.
{"nodes":[
{"index":0,"nodeOffset":"121.05 29","parent":[{"index":6}]},
{"index":1,"nodeOffset":"78.15 25.8","parent":[{"index":0},{"index":7}]},
{"index":2,"nodeOffset":"-0.39 81.8","parent":[{"index":-1}]},
{"index":3,"nodeOffset":"12.09 12","parent":[{"index":2},{"index":7},{"index":8},{"index":11}]},
{"index":4,"nodeOffset":"-9.53 -63.8","parent":[{"index":5},{"index":3}]},
{"index":5,"nodeOffset":"-53.88 -12.8","parent":[{"index":3}]},
{"index":6,"nodeOffset":"44.79 27.2","parent":[{"index":-1}]},
{"index":7,"nodeOffset":"45.54 24.8","parent":[{"index":6}]},
{"index":8,"nodeOffset":"26.74 -2","parent":[{"index":6},{"index":7}]},
{"index":9,"nodeOffset":"44.69 -27.2","parent":[{"index":6},{"index":8}]},
{"index":10,"nodeOffset":"0.26 26.2","parent":[{"index":1},{"index":11},{"index":2}]},
{"index":11,"nodeOffset":"-26 40.2","parent":[{"index":2},{"index":7},{"index":8}]}
],
"config":{
"lineHeight":21.25,
"algorithm":"Find edge separator",
"findAll":true,
"minimumSizeSeparator":true
}}
Para el grafo dirigido de la Figura encontrar todos los conjuntos separadores de vértices con la opción mínimo tamaño separador marcada devuelve los 3 siguientes conjuntos con una única arista, resaltándose la primera [0,4]:
Encontrar separador aristas: [[[0,4]], [[1,0]], [[4,2]]]
Para entender el motivo de que esas 3 aristas incrementan el número de componentes, vemos en la Figura los dos componentes fuertemente conectados, de tal forma que eliminando alguna de las aristas "0🡒4", "1🡒0" o "4🡒2" del primer componente hace que se incremente el número de componentes fuertemente conectados, hasta tantos como vértices de ese subgrafo, pues ya no podremos acceder desde cualquiera de sus nodos a otro.
{"nodes":[
{"index":0,"parent":[{"index":-1}]},
{"index":1,"value":"X","parent":[{"index":0,"value":"A"}]},
{"index":2,"parent":[{"index":0,"value":"B"},{"index":1,"value":"C"}]},
{"index":3,"parent":[{"index":1,"value":"D","lineTextOffset":"-0.75 0.25"},{"index":4,"value":"E"}]},
{"index":4,"parent":[{"index":1,"value":"F"},{"index":2},{"index":0,"lineOffset":"1","markerReverse":true,"value":"G"}]}
],
"config":{
"markerEnd":"arrow",
"algorithm":"Find edge separator",
"findAll":true,
"minimumSizeSeparator":true
}}A continuación vemos el JavaScript para ejecutar findEdgeSeparator().
function findEdgeSeparator({matrix=[], firstIndex=0, lastIndex=0, sizeSeparator=1, minimumSizeSeparator=false, findAll=false, forceUndirected=true}) {
let result = [], temp;
result.warnings = [];
try {
let directed = isGraphDirected({matrix});
if (typeof directed==="string") throw new Error(directed);
let components1 = getConnectedComponents({matrix, forceUndirected});
if (typeof components1==="string") throw new Error(components1);
let n = matrix.length;
if (temp = getEdges({matrix, edgesCompact:true}), typeof temp==="string") throw new Error(temp);
let edges = temp;
sizeSeparator = Math.max(0, Math.min(sizeSeparator, edges.length));
let [from, to] = [sizeSeparator, sizeSeparator];
if (minimumSizeSeparator) {
[from, to] = [1, edges.length];
}
for (let sc=from; sc<=to; sc++) {
let combinations = combine(edges, sc);
if (typeof combinations==="string") throw new Error(combinations);
if (combinations.hasOwnProperty("warning")){
result.warnings.push(combinations.warning + ` (testing cut size ${sc})`);
}
for (let listEdges of combinations) {
let matrixCopy = JSON.parse(JSON.stringify(matrix));
for (let edge of listEdges) {
let [i, j] = edge;
matrixCopy[i][j] = 0;
if (!directed) matrixCopy[j][i] = 0;
}
iter = 0;
let components2 = getConnectedComponents({matrix:matrixCopy, forceUndirected});
if (typeof components2==="string") throw new Error(components2);
if (components2.length>components1.length) {
result.push([...listEdges]);
if (!findAll) return result;
}
}
if (result.length>0) break;
}
} catch(e){result = e.message}
return result;
}Se usan las siguientes funciones:
getConnectedComponents()para obtener los componentes conectados que vimos al inicio en este tema.getEdges()para obtener las aristas del grafo.combine(list, k)para obtener las combinaciones de una lista de nodos, con el código que vemos a continuación.
function combine(list=[], k=0, n=list.length, res=Array.from({length:k}, ()=>""), result=[], n0=list.length, k0=res.length){
try {
if (k===0){
result.push([...res]);
} else {
for (let j=n; j>=k; j--){
res[k0-k] = list[n0-j];
combine(list, k-1, j-1, res, result);
}
}
} catch(e) {result = e.message}
return result;
}El funcionamiento es obtener los componentes conectados del grafo inicial y hacer un bucle que itere por tamaños de conjuntos separadores de aristas para ir probando aquellas que incrementen el número de componentes conectados.