Rutas en grafos identifyRoute()

Una ruta en un grafo es una secuencia de visitas a varios nodos con aristas incidentes en el recorrido, diferenciándose entre recorrido (walk), rastro (trail), circuito (circuit), camino (path) y ciclo (cycle). En lugar de rutas suele usarse caminos, tanto en sentido genérico para agrupar todos los anteriores como específico para el propio camino, que es una ruta con vértices y aristas que no pueden repetirse. Para ser coherentes deberíamos titular este tema rutas en grafos en lugar de caminos en grafos.

Recordar que uso los términos vértice y nodo de un grafo como sinónimos, usándose mayormente el último. Los nombres de cada ruta pueden variar según la documentación que consultemos. En cualquier caso lo que interesa es saber diferenciar una ruta de otra.

Una ruta se presenta siempre como una lista de nodos {v₀, v₁, ..., v_k}, con posibles nodos repetidos según el tipo de ruta. Una lista de nodos es una ruta si para todo 1≤i≤k se cumple que existe la arista v_i-1 - v_i en un grafo no dirigido o bien v_i-1 🡒 v_i en un grafo dirigido.

La lista de aristas se conforma entonces como v₀-v₁, v₁-v₂, ..., v_k-1-v_k para un grafo no dirigido y v₀🡒v₁, v₁🡒v₂, ..., v_k-1🡒v_k para un grafo dirigido.

Para un grafo estructurado en una matriz de adyacencia, una ruta queda definida por una lista de nodos o una lista de aristas indistintamente, puesto que entre dos nodos v_i, v_j en un grafo no dirigido solo cabe una arista, dado que las aristas v_i-v_j y v_j-v_i son indistinguibles en un grafo no dirigido. Y en un grafo dirigido caben dos aristas en diferente sentido v_i🡒v_j y v_j🡒v_i, así que v_i, v_j en ese orden en la lista de nodos configura la arista v_i🡒v_j y, por otro lado, v_j,v_i en ese orden en la lista de nodos configura la arista v_j🡒v_i.

Recordemos un par de cosas relacionadas con la aplicación:

• Una arista entre dos nodos u, v se referencia con el Array [u, v]. Si el grafo es no dirigido se entiende la arista u-v o v-u indistintamente. Si el grafo es dirigido se entiende u🡒v, de tal forma que el Array inverso [v, u] se aplica a v🡒u.
• La matriz de adyacencia tiene limitaciones para presentar multigrafos, como explicamos en un tema anterior.

En la Figura puede ver una captura de la aplicación Grafos SVG con el algoritmo identifyRoute() para identificar la ruta 4,5,1,0,4,6,5,4,7, presentado como una una lista de nodos, o mejor dicho, como una lista de índices de nodos, que viene a resultar en un recorrido (walk), tal como veremos en un apartado más abajo.

La opción marcar ruta asignará un número de orden de visita de cada arista que se indica entre corchetes. Más de un número como [1,7] significa que es la primera arista que se visita y, posteriormente, se vuelve a visitar en séptimo orden.

La ruta se resalta con aristas en color configurable, como se observa en la Figura, donde hemos activado la opción marcar ruta, observando que se agrega, por ejemplo, "[3]" al valor de la arista "a" quedando "a [3]". Cuando el grafo es dirigido como este caso, es fácil seguir la ruta siguiendo las flechas de las aristas, pero con un grafo no dirigido marcar la ruta con el número de orden ayuda a seguir ese recorrido.

Si también marcamos la opción ruta con valores nodos, podemos pasar la lista de nodos con una lista de valores de nodos en lugar de una con índices de nodos. Así para esa ejecución pasamos la lista de valores de nodos D,E,B,A en lugar de la de índices 3,4,1,0, obteniéndose el resultado en texto siguiente:

Time: 0 ms

Identificar ruta: ["path",[3,4,1,0],""]

Valores de nodos ⇒ 
D, E, B, A

El resultado devuelve un Array con el tipo de ruta "path" y la propia ruta como lista de índices. También un String (vacío en este caso) con una posible advertencia de error si fuera el caso. Cuando los nodos tienen valores como en este ejemplo, se devuelve también la ruta con los valores de los nodos. Puede importar el ejemplo con el siguiente JSON.

{"nodes":[
    {"index":0,"parent":[{"index":-1}]},
    {"index":1,"parent":[{"index":0,"value":"a"}]},
    {"index":2,"parent":[{"index":0,"value":"b"},{"index":1,"value":"c"}]},
    {"index":3,"parent":[{"index":1,"value":"d"},{"index":4,"value":"e"}]},
    {"index":4,"parent":[{"index":1,"value":"f"},{"index":2,"value":"g"}]}
],
"config":{
    "nodeValueAuto":"alphabetic-upper",
    "markerEnd":"arrow",
    "algorithm":"Identify route",
    "route":"D,E,B,A",
    "routeWithNodeValues":true,
    "markRoute":true
}}

Si pasamos la lista de valores de nodos D,E,B,C obtendríamos el error [1,2] is not valid edge pues la arista B🡒C no existe en el grafo (existe la contraria C🡒B). En caso de error el tipo de ruta devuelto será "none".

Time: 0 ms

Identificar ruta: ["none",[3,4,1,2],"[1,2] is not valid edge;"]

Valores de nodos ⇒ 
D, E, B, C

Recorrido, rastro, circuito, camino y ciclo (walk, trail, circuit, path and cycle)

En los siguientes apartados exponemos ejemplos de cada ruta que resumimos en este cuadro:

El algoritmo JavaScript identifyRoute({matrix=[], route=[]}) identifica el tipo de ruta como walk, trail, circuit, path, cycle o none cuando hay un error en la ruta de entrada. Como todos los algoritmos de la aplicación, el grafo se pasa como una matriz de adyacencia en el argumento matrix. El argumento route es una lista de nodos. Devuelve el Array ["none", route, ""] con el tipo de ruta, la propia ruta del argumento y un mensaje de error si fuera el caso.

Usa las funciones que ya vimos en temas anteriores isGraphDirected({matrix}) para saber si el grafo es dirigido y también getEdges({matrix, edgesCompact:true}) para obtener la lista de aristas.

function identifyRoute({matrix=[], route=[]}) {
    let result = ["none", route, ""];
    try {
        let directed = isGraphDirected({matrix});
        if (typeof directed==="string") throw new Error(directed);
        let n = matrix.length;
        let set = new Set(route);
        let min = Math.min(...set);
        if (min<0) {
            let warning = `Mininum index < 0`;
            result.warnings = [warning];
            result[2] = warning;
            return result;
        }
        let max = Math.max(...set);
        if (max>n-1) {
            let warning = `Maximum index > ${n-1}`;
            result.warnings = [warning];
            result[2] = warning;
            return result;
        }
        let numsVertexs = Array.from({length: n}, (v,i) => i).reduce((p,v) => (p[v] = 0, p), {});
        route.forEach(v => numsVertexs[v]++);
        let repeatVertexs = Object.keys(numsVertexs).some(v => numsVertexs[v]>1);
        let vertexsRepeated = Object.keys(numsVertexs).filter(v => numsVertexs[v]===2);
        let edges = getEdges({matrix, edgesCompact:true});
        if (typeof edges==="string") throw new Error(edges);
        edges = edges.map(v => v.join(","));
        let numsEdges = {};
        for (let i=1; i<route.length; i++){
            let arr = [route[i-1], route[i]];
            let edge = directed ? arr.join(",") : arr.toSorted((v,w) => v-w).join(",");
            if (!edges.includes(edge)) {
                let warning = ` [${arr.join(",")}] is not valid edge;`;
                if (!result.hasOwnProperty("warnings")) result.warnings = [];
                result.warnings.push(warning);
                result[2] += warning;
            } else {
                if (!numsEdges.hasOwnProperty(edge)) numsEdges[edge] = 0;
                numsEdges[edge]++;
            }
        }
        result[2] = result[2].trim();
        if (result[2]!=="") return result;
        let repeatEdges = Object.keys(numsEdges).some(v => numsEdges[v]>1);
        result[0] = !repeatEdges && !repeatVertexs ? "path" :
            !repeatEdges && vertexsRepeated.length===1 && route[0]===route[route.length-1] ?  "cycle" :
            !repeatEdges && route[0]===route[route.length-1] ? "circuit" :
            !repeatEdges && route[0]!==route[route.length-1] ? "trail" :
            "walk";
    } catch(e){result = e.message}
    return result;
}

El algoritmo detecta aristas repetidas en la variable repeatEdges y vértices repetidos en repeatVertexs, contando el número de repeticiones en vertexsRepeated. Con estas variables hacemos un filtrado en orden path, cycle, circuit, trail, walk al final del algoritmo:

• Es un Camino (path) si no repite aristas ni vértices: !repeatEdges && !repeatVertexs ? "path"
• En otro caso es un Ciclo (cycle) si no repite aristas y repite un vértice al principio y final: !repeatEdges && vertexsRepeated.length===1 && route[0]===route[route.length-1] ? "cycle"
• En otro caso es un Circuito (circuit) si no repite aristas y primer y último vértices son iguales !repeatEdges && route[0]===route[route.length-1] ? "circuit"
• En otro caso es un Rastro (rastro) si no repite aristas y primer y último vértices no son iguales !repeatEdges && route[0]!==route[route.length-1] ? "trail"
• En otro caso es un Recorrido (walk)

Recorrido en un grafo (walk)

Un recorrido (walk) en un grafo es una lista de aristas donde al menos una se repite, con lo que obligatoriamente se repetirán al menos dos nodos.

Se obtiene el siguiente resultado:

Time: 0 ms

Identificar ruta: ["walk",[4,5,1,0,4,6,5,4,7],""]

El resultado obtenido es walk que traducimos como recorrido, observando que se recorren las aristas 4-5, 5-1, 1-0, 0-4, 4-6, 6-5, 5-4, 4-7, repitiéndose la misma arista 4-5 y 5-4, pues al ser un grafo no dirigido ambas aristas son la misma. Se observa que el nodo 4 se repite tres veces y el 5 dos veces.

{"nodes":[
    {"index":0,"nodeOffset":"72.13 76.2","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"52.54 61","parent":[{"index":0}]},
    {"index":2,"nodeOffset":"25.2 36.2","parent":[{"index":1}]},
    {"index":3,"nodeOffset":"-18 -1.4","parent":[{"index":2}]},
    {"index":4,"nodeOffset":"25.06 1.8","parent":[{"index":0},{"index":1}]},
    {"index":5,"nodeOffset":"18 8.6","parent":[{"index":1},{"index":2},{"index":4}]},
    {"index":6,"nodeOffset":"-21.2 -47.4","parent":[{"index":2},{"index":3},{"index":4},{"index":5}]},
    {"index":7,"nodeOffset":"38.8 -44.6","parent":[{"index":4}]},
    {"index":8,"nodeOffset":"-26.4 -92.2","parent":[{"index":6}]}
],
"config":{
    "algorithm":"Identify route",
    "route":"4,5,1,0,4,6,5,4,7",
    "markRoute":true
}}

En la Figura vemos un grafo dirigido con múltiples aristas, con lo que es un multigrafo. Debido a las limitaciones de la matriz de adyacencia para representar multigrafos, es por lo que se advierte con la frase El grafo es multigrafo y el algoritmo podría no ejecutarse correctamente. Sin embargo para este ejemplo la ejecución es correcta, pues las aristas dobles "B🡘C" y "A🡘B" si pueden representarse en la matriz de adyacencia al no ser todas las aristas dobles.

Se obtiene el siguiente resultado:

Time: 0 ms

Identificar ruta: ["walk",[3,4,2,1,0,1,2,0,1],""]

Valores de nodos ⇒ 
D, E, C, B, A, B, C, A, B

Resulta un recorrido (walk) dado que se repite la arista "A🡒B" en el orden 5 y 8. Observe como el marcado de las aristas con esos números de orden nos ayudan a seguir visualmente la ruta de aristas visitadas.

{"nodes":[
    {"index":0,"parent":[{"index":-1},{"index":1,"lineType":"quadratic","lineOffset":"-3 -3"}]},
    {"index":1,"parent":[{"index":0},{"index":2,"lineType":"cubic","lineOffset":"0 0 0 0"}]},
    {"index":2,"parent":[{"index":0},{"index":1,"lineType":"quadratic","lineOffset":"0 -2"}]},
    {"index":3,"parent":[{"index":1},{"index":4}]},
    {"index":4,"parent":[{"index":1},{"index":2}]}
],
"config":{
    "nodeValueAuto":"alphabetic-upper",
    "markerEnd":"arrow",
    "algorithm":"Identify route",
    "route":"D,E,C,B,A,B,C,A,B",
    "routeWithNodeValues":true,
    "markRoute":true
}}

Rastro en un grafo (trail)

Un rastro (trail) en un grafo es una lista de aristas que no se repiten y donde hay más de una repetición de nodos o si hay solo una no es el primero y el último, pues sería un circuito. Un rastro es un recorrido de nodos repitiendo al menos uno de ellos sin pasar por las mismas aristas.

En la Figura vemos un rastro con la lista de nodos 4,5,1,0,4,6,5 que supone la lista de aristas 4-5, 5-1, 1-0, 0-4, 4-6, 6-5 no repitiéndose ninguna arista y repitiéndose los nodos 4 y 5 dos veces. Se obtiene este resultado:

Time: 0 ms

Identificar ruta: ["trail",[4,5,1,0,4,6,5],""]

Con este JSON podrá importar el ejemplo.

{"nodes":[
    {"index":0,"nodeOffset":"72.13 76.2","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"52.54 61","parent":[{"index":0}]},
    {"index":2,"nodeOffset":"25.2 36.2","parent":[{"index":1}]},
    {"index":3,"nodeOffset":"-18 -1.4","parent":[{"index":2}]},
    {"index":4,"nodeOffset":"25.06 1.8","parent":[{"index":0},{"index":1}]},
    {"index":5,"nodeOffset":"18 8.6","parent":[{"index":1},{"index":2},{"index":4}]},
    {"index":6,"nodeOffset":"-21.2 -47.4","parent":[{"index":2},{"index":3},{"index":4},{"index":5}]},
    {"index":7,"nodeOffset":"38.8 -44.6","parent":[{"index":4}]},
    {"index":8,"nodeOffset":"-26.4 -92.2","parent":[{"index":6}]}
],
"config":{
    "algorithm":"Identify route",
    "route":"4,5,1,0,4,6,5",
    "markRoute":true
}}

Circuito en un grafo (circuit)

Un circuito (circuit) en un grafo es una lista de aristas que no se repiten y donde hay más de una repetición de nodos y al menos una es el primero y el último. Un circuito es un rastro que se inicia y termina en el mismo nodo.

En la Figura vemos un circuito con la lista de nodos 1,0,4,5,2,3,6,5,1 que supone la lista de aristas 1-0, 0-4, 4-5, 5-2, 2-3, 3-6, 6-5, 5-1 no repitiéndose ninguna arista y repitiéndose los nodos 1 y 5, siendo la repitición de 1 en primer y último lugar. Se obtiene este resultado:

Time: 0 ms

Identificar ruta: ["circuit",[1,0,4,5,2,3,6,5,1],""]

Con este JSON se puede importar el ejemplo:

{"nodes":[
    {"index":0,"nodeOffset":"72.13 76.2","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"52.54 61","parent":[{"index":0}]},
    {"index":2,"nodeOffset":"25.2 36.2","parent":[{"index":1}]},
    {"index":3,"nodeOffset":"-18 -1.4","parent":[{"index":2}]},
    {"index":4,"nodeOffset":"25.06 1.8","parent":[{"index":0},{"index":1}]},
    {"index":5,"nodeOffset":"18 8.6","parent":[{"index":1},{"index":2},{"index":4}]},
    {"index":6,"nodeOffset":"-21.2 -47.4","parent":[{"index":2},{"index":3},{"index":4},{"index":5}]},
    {"index":7,"nodeOffset":"38.8 -44.6","parent":[{"index":4}]},
    {"index":8,"nodeOffset":"-26.4 -92.2","parent":[{"index":6}]}
],
"config":{
    "algorithm":"Identify route",
    "route":"1,0,4,5,2,3,6,5,1",
    "markRoute":true
}}

Aunque aun no he implementado algoritmos para encontrar un ciclo Euleriano, si un grafo tiene todos los nodos con grado par entonces el grafo tiene un ciclo Euleriano y es un grafo Euleriano. Realmente habría que hablar de circuito Euleriano dado que hay que visitar todas las aristas sin repetirlas, aunque podría ser necesario repetir nodos, siendo una de las repeticiones con un mismo nodo al principio y final.

Si obtenemos los grados de los nodos con el algoritmo getVertexDegrees() que ya hemos visto en un tema anterior, obtenemos el resultado de la Figura, donde vemos que los nodos 8, 7, 6 y 4 tienen grado impar y el resto par. El grado de un nodo es el número de aristas incidentes, incluyéndose como un subíndice en los valores de los nodos del grafo de la Figura.

Eliminando los nodos 7 y 8 ahora todos los nodos tienen grado par pues el número de aristas incidentes son pares, como vemos en la Figura. Manualmente confeccionamos la ruta 6,3,2,6,5,2,1,5,4,1,0,4,6 y vemos que es un circuito que recorre todas las aristas una única vez y donde el nodo 6 es primero y último de la ruta. Es por tanto un circuito Euleriano. Resultado:

Time: 1 ms

Identificar ruta: ["circuit",[6,3,2,6,5,2,1,5,4,1,0,4,6],""]

JSON:

{"nodes":[
    {"index":0,"nodeOffset":"72.13 46.2","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"52.54 31","parent":[{"index":0}]},
    {"index":2,"nodeOffset":"16.87 6.2","parent":[{"index":1}]},
    {"index":3,"nodeOffset":"-18 -31.4","parent":[{"index":2}]},
    {"index":4,"nodeOffset":"25.06 -28.2","parent":[{"index":0},{"index":1}]},
    {"index":5,"nodeOffset":"1.33 -21.4","parent":[{"index":1},{"index":2},{"index":4}]},
    {"index":6,"nodeOffset":"-21.2 -77.4","parent":[{"index":2},{"index":3},{"index":4},{"index":5}]}
],
"config":{
    "algorithm":"Identify route",
    "route":"6,3,2,6,5,2,1,5,4,1,0,4,6",
    "markRoute":true
}}

Camino en un grafo (path)

Un camino (path) en un grafo es una lista de aristas que no se repiten con nodos que no se repiten. Un camino visita cada nodo y pasa por cada arista una única vez.

En la Figura vemos un camino con la lista de nodos 8,6,3,2,5,1,0,4,7, observando que no repite aristas ni nodos. No es un ciclo pues el primer nodo y el último son diferentes.

Cuando un camino visita todos los nodos del grafo se le denomina camino Hamiltoniano, que explicaremos en el tema siguiente, obteniéndose el mismo camino 8,6,3,2,5,1,0,4,7 con el algoritmo encontrar camino Hamiltoniano. Resultado:

Time: 0 ms

Identificar ruta: ["path",[8,6,3,2,5,1,0,4,7],""]

JSON:

{"nodes":[
    {"index":0,"nodeOffset":"72.13 76.2","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"52.54 61","parent":[{"index":0}]},
    {"index":2,"nodeOffset":"25.2 36.2","parent":[{"index":1}]},
    {"index":3,"nodeOffset":"-18 -1.4","parent":[{"index":2}]},
    {"index":4,"nodeOffset":"25.06 1.8","parent":[{"index":0},{"index":1}]},
    {"index":5,"nodeOffset":"18 8.6","parent":[{"index":1},{"index":2},{"index":4}]},
    {"index":6,"nodeOffset":"-21.2 -47.4","parent":[{"index":2},{"index":3},{"index":4},{"index":5}]},
    {"index":7,"nodeOffset":"38.8 -44.6","parent":[{"index":4}]},
    {"index":8,"nodeOffset":"-26.4 -92.2","parent":[{"index":6}]}
],
"config":{
    "algorithm":"Identify route",
    "route":"8,6,3,2,5,1,0,4,7",
    "markRoute":true
}}

Ciclo en un grafo (cycle)

Un ciclo (cycle) en un grafo es una lista de aristas que no se repiten y donde sólo se repite el primer nodo con el último. Un ciclo es un camino que se inicia y termina en el mismo nodo.

En la Figura vemos un ciclo (cycle) que a su vez es un ciclo Hamiltoniano pues recorre todos los nodos del grafo y empieza y termina en el mismo nodo, como veremos en el tema siguiente. Se obtiene este resultado:

Time: 0 ms

Identificar ruta: ["cycle",[0,1,2,3,6,5,4,0],""]

Este grafo con un ciclo Hamiltoniano recorre todos los nodos una única vez y el circuito Euleriano de la Figura para el mismo grafo recorre todas las aristas una única vez.

{"nodes":[
    {"index":0,"nodeOffset":"72.13 46.2","parent":[{"index":-1}]},
    {"index":1,"nodeOffset":"52.54 31","parent":[{"index":0}]},
    {"index":2,"nodeOffset":"16.87 6.2","parent":[{"index":1}]},
    {"index":3,"nodeOffset":"-18 -31.4","parent":[{"index":2}]},
    {"index":4,"nodeOffset":"25.06 -28.2","parent":[{"index":0},{"index":1}]},
    {"index":5,"nodeOffset":"1.33 -21.4","parent":[{"index":1},{"index":2},{"index":4}]},
    {"index":6,"nodeOffset":"-21.2 -77.4","parent":[{"index":2},{"index":3},{"index":4},{"index":5}]}
],
"config":{
    "algorithm":"Identify route",
    "route":"0,1,2,3,6,5,4,0",
    "markRoute":true
}}