Buscar todas las rutas entre dos vértices (nodos)

Question

Soy nuevo en la programación R y estoy involucrado en la representación de gráficos usando R. Me gustaría preguntar cómo implemento un código que puede encontrar todas las rutas entre dos vértices o nodos basados ​​en una matriz de adyacencia. He visto muchas implementaciones en otros lenguajes de programación, pero la mayoría usaba colas como en (BFS) para que funcionen. Por ejemplo, esta es la lista de mi gráfico.

  [,1] [,2] 
    [1,] 0 1 
    [2,] 1 2 
    [3,] 1 3 
    [4,] 1 4 
    [5,] 2 5 
    [6,] 2 6 
    [7,] 5 7 
    [8,] 5 8 
    [9,] 6 9 
    [10,] 6 10 
    [11,] 8 11 
    [12,] 10 12 
    [13,] 11 13 
    [14,] 11 14 
    [15,] 11 15 
    [16,] 12 16 
    [17,] 12 17 
    [18,] 12 18 
    [19,] 13 19 
    [20,] 16 20 
    [21,] 19 21 
    [22,] 19 22 
    [23,] 20 22 
    [24,] 20 23  

Si quería todos los caminos entre el nodo 0 y el nodo 22, deben ser dos caminos:

[[1]] 
    [1] 0 1 2 6 10 12 16 20 22 

    [[2]] 
    [1] 0 1 2 5 8 11 13 19 22 

Gracias

Answer 1

Usted quiere tener una buena lectura de la vista de tareas modelos gráficos :

http://ftp.heanet.ie/mirrors/cran.r-project.org/web/views/gR.html

Aunque no lo lo que usted está hacer es un modelado gráfico en un sentido estadístico, esta vista de tareas describe los paquetes para el manejo de gráficos y algoritmos.

He utilizado igraph para varias cosas de gráficos.

Answer 2

Asumiendo que usted tiene un simple directed acyclic graph (DAG), el siguiente enfoque de trabajo para el conteo:

(A^n)_ij le da el número de caminos de longitud n entre los nodos y ij. Por lo tanto, debe calcular A + A^2 + ... + A^n + ... para obtener el número total de rutas entre dos nodos. Es esencial que trabaje con un DAG, ya que esto garantiza que sea lo suficientemente grande n, A^n = 0. Entonces el resultado se puede escribir como A . (I - A)^(-1) donde I es la matriz de identidad.

---

EDIT:

Realmente no sé R por lo que sólo puede darle un cierto pseudocódigo o explicaciones.

Primero, vamos a encontrar el conjunto de nodos accesibles desde el nodo i. Definamos el vector v para que contenga solo ceros, excepto en la posición i, donde contiene 1. Por ej. para la primera nodo tendrá

v = (1,0,0, ..., 0) 

Ahora vamos v_(n+1) = sign(v_n + A . v_n), en el que el objetivo de la función es reemplazar sign() elementos no nulos en 1 y 0. mantener ceros hacer esta iteración hasta que llegue al punto fijo, y usted Tendremos un vector v con elementos distintos de cero en las posiciones correspondientes a los nodos accesibles desde el nodo i.

Si en lugar del vector v comienza con la matriz de identidad (del mismo tamaño que A), obtendrá los nodos alcanzables para cada otro nodo de una vez.

Ahora tiene el conjunto de nodos alcanzables para cualquier nodo inicial. De forma similar, puede obtener la lista de nodos a partir de los cuales se puede acceder a cualquier nodo objetivo (simplemente invierta los bordes dirigidos, es decirtransponer A)

A continuación, vamos a recorrer el gráfico y encontrar todas las rutas que necesita.

Esta función recursiva debe hacerlo (pseudocódigo):

traverse(path-so-far, target): 
    let S = the last element of path-so-far 
    if S == target: 
     output path-so-far 
     return 
    let N = the set of nodes reachable from S in one step 
    remove all nodes from N from which the target is not reachable 
    for each K in N: 
     traverse(append(path-so-far, K), target) 

path-so-far es la lista de nodos ya visitados; target es el nodo de destino.

Para un par determinado de nodos de inicio y destino, simplemente haga traverse({start}, target).

Tenga en cuenta que el paso en el que eliminamos todos los nodos de la cual el objetivo no es alcanzable sólo está allí para acelerar el recorrido, y no ingresar en "callejones sin salida"

Answer 3

Sólo hacer una primera búsqueda en profundidad sin comprobar los nodos visitados - esto le puede dar el número de rutas entre dos puntos de una longitud específica

void dfs(int start, int hops) 
{ 
    if(hops == k && start == t) 
    { 
     path++; 
     return; 
    } 
    else if(hops >= k) 
    return; 
    for(int w = 1; w <= n; w++) 
    if(routes[start][w]) 
     dfs(w, hops + 1); 
} 

Y en principal, llame

dfs(start_node, length); 

Cómo hacer Y ¿Qué hacer si hay varias rutas que conectan dos puntos, y cada uno se considera diferente?

Answer 4

he utilizado el código siguiente para crear una matriz de (vértices x vértices) que contiene el número de todos los caminos entre cada dos vértices.

library(igraph) 
setwd("C:/Workspace") 
graph <- read.graph("graph.txt", format="edgelist") 
direct <- get.adjacency(graph) 
indirect <- direct 
max <- vcount(graph)-1 
for(i in 0:max) 
for(j in 0:max) 
    indirect[i,j] <- length(get.all.shortest.paths(graph, from=i, to=j, mode="out")) 

Propongo usar la biblioteca igraph para este propósito.

library(igraph) 

he puesto a su lista de aristas en un archivo llamado "graph.txt", que he puesto en "C: \ espacio de trabajo". Luego utilizo el siguiente código de lectura en ese archivo en I:

setwd("C:/Workspace") 
graph <- read.graph("graph.txt", format="edgelist") 

Es posible que desee trazar la gráfica sólo para estar seguro de que todo 's bien (sin embargo, este paso se puede dejar de distancia):

plot(graph, layout=layout.fruchterman.reingold.grid) 

puedo crear una matriz de adyacencia para ver todos los enlaces directos entre los vértices:

direct <- get.adjacency(graph) 

Luego de crear una matriz ficticia denominada "indirecta" la cual es una copia de la matriz de adyacencia. Sólo necesito esta matriz para llenar más tarde con los valores indirectos:

indirect <- direct 

Finalmente, iterar sobre toda la gráfica para encontrar el número de todas las conexiones indirectas entre cada dos vértices. Puse este número en la matriz indirecta que acabo de crear antes (adicionalmente he creado una cláusula que pone todos los valores en el cero diagonal). El modo "salir" asegura que solo se contabilicen las rutas salientes.Esto también puede ser ajustado a "en" o "total":

max <- vcount(graph)-1 
for(i in 0:max) 
for(j in 0:max) 
    indirect[i,j] <- length(get.all.shortest.paths(graph, from=i, to=j, mode="out")) 

Answer 5

Compruebe la siguiente función igraph a cabo:

http://igraph.org/r/doc/all_simple_paths.html

Se enumeran todos los caminos simples de un solo proveedor.

Descripción Esta función enumera las rutas simples de un vértice fuente a otro vértice o vértices. Un camino es simple si los vértices que visita no se visitan más de una vez.

Uso all_simple_paths (gráfico, de, a = V (gráfico), modo = C ("fuera", "en", "all", "total"))

Argumentos

gráfico
El gráfico de entrada.

de
El vértice fuente.

a
El vértice del objetivo de los vértices. Predeterminado a todos los vértices.

modo
Constante de caracteres, indica si las rutas más cortas hacia o desde los vértices dados deben calcularse para los gráficos dirigidos. Si sale, se considerarán los caminos más cortos desde el vértice, si están en ese momento. Si todo es el predeterminado, se usará el gráfico correspondiente no dirigido, es decir. las rutas no dirigidas se buscan. Este argumento se ignora para los gráficos no dirigidos.

detalles

Nota que potencialmente hay muchos caminos de manera exponencial entre dos vértices de un gráfico, y es posible que se quede sin memoria cuando se utiliza esta función, si la gráfica es en forma de rejilla.

Esta función actualmente ignora los bordes múltiples y de bucle.