Dado es un árbol:

library(igraph)

# setup graph
g= graph.formula(A -+ B,
                 A -+ C,
                 B -+ C,
                 B -+ D,
                 B -+ E
)
plot(g, layout = layout.reingold.tilford(g, root="A"))

Vértice"A" es la raíz del árbol, mientras que los vértices"C", "D", "E" se consideran como hojas terminales.

Problema:

La tarea es encontrar todos los caminos entre la raíz y las hojas. Fallo con el siguiente código, ya que solo proporciona las rutas más cortas:

# find root and leaves
leaves= which(degree(g, v = V(g), mode = "out")==0, useNames = T)
root= which(degree(g, v = V(g), mode = "in")==0, useNames = T)

# find all paths
paths= lapply(root, function(x) get.all.shortest.paths(g, from = x, to = leaves, mode = "out")$res)
named_paths= lapply(unlist(paths, recursive=FALSE), function(x) V(g)[x])
named_paths

Salida:

$A1
Vertex sequence:
[1] "A" "C"

$A2
Vertex sequence:
[1] "A" "B" "D"

$A3
Vertex sequence:
[1] "A" "B" "E"

Pregunta:

¿Cómo puedo encontrar todas las rutas, incluida la secuencia de vértices:"A" "B" "C"?

Entiendo que la secuencia que falta"A" "B" "C" no es proporcionado porget.all.shortest.paths() como el camino desde"A" a"C" a través de la secuencia de vértices:"A" "C" (que se encuentra en el elemento de lista$A1) es más corto. Entoncesigraph trabaja apropiadamente.Sin embargo, estoy buscando una solución de código para obtener todas las rutas desde la raíz a todas las hojas en forma deR list.

Comentario:

Soy consciente de que para árboles grandes, el algoritmo que cubre todas las combinaciones puede resultar costoso, pero mi aplicación real es relativamente pequeña.