die Mindestabstände/Ebenen zwischen den Knoten in einem Diagramm wie Datenrahmen in R

Question

Finding habe ich einige Grafiken in einem data.table gespeicherten Daten, die die Übergänge zwischen einigen Knoten wie beschreiben:

lfs = data.table(from = c(NA, 'x', 'x', 'y'), to = c('x', 'y', 'p', 'z'), level = 0) 
lfs 
# from to level 
#: NA x  0 
#: x y  0 
#: x p  0 
#: y z  0 

Wen möchte ich finden die Entfernung jedes Knotens vom Startknoten NA. Das erwartete Ergebnis ist wie folgt:

# from to level 
#: NA x  1 
#: x y  2 
#: x p  2 
#: y z  3 

ich dieses Problem in einer sehr umständlichen Weise lösen können, wie folgt:

lfs[ is.na(lfs$from) ]$level = 1 
target = lfs$from %in% (lfs[ lfs$level == 1 ]$to) 
lfs[target]$level = 2 
target = lfs$from %in% (lfs[ lfs$level == 2 ]$to) 
lfs[target]$level = 3 

Ich denke, es einfacher und generische Lösungen höchstwahrscheinlich durch die Verwendung Graph Manipulation sein sollte Funktionen in Graph-Bibliotheken wie zB igraph, aber ich kenne sie nicht sehr gut und ich weiß nicht, wonach ich in diesen Bibliotheken gezielt suchen soll.

Wie kann ich die erwartete Ausgabe mit Graphalgorithmen erhalten oder denken Sie an andere einfachere Lösungen?

Answer 1

Sie können das igraph Paket, um das distances

library(igraph) 

lfs = data.frame(from = c('start', 'x', 'x', 'y'), 
        to = c('x', 'y', 'p', 'z'), 
        level = 0) 

# create graph from data.frame 
g <- graph_from_data_frame(lfs) 

# find distances from chosen node 
distances(g, "start") 
#  start x y p z 
#start  0 1 2 2 3 

Answer 2

berechnen, wenn wir, dass jeder eindeutige Wert in from übernehmen in einer vorherigen Zeile in Spalte bereits vorhanden ist to (außer "start") - und die Daten bestellt Wie Sie es beschreiben - wir könnten einfach die form Spalte in numerisch umwandeln, um die erwartete Ausgabe zu erreichen.

lfs$level <- as.numeric(as.factor(lfs$from)) 
> lfs 
# from to level 
#1 start x  1 first 'from' value cannot be NA though 
#2  x y  2 
#3  x p  2 
#4  y z  3 

Answer 3

Wir rleid von data.table

library(data.table) 
lfs[, levels := rleid(from)] 
lfs 
# from to level levels 
#1: NA x  0  1 
#2: x y  0  2 
#3: x p  0  2 
#4: y z  0  3