主親ノードまでのノード集合の取得R

Question

6行3列のデータセットがあります。最初の列は子を表しますが、対応する子の2番目の列の直後の親が割り当てられます。

上記の "a"と "b"には親がないことがわかります。 "c"は親だけを持ち、 "a"です。 "d"には親 "b"と "c"などがあります。

私が必要とするのは、子供としての入力が与えられれば、子供を含むその子供のすべての祖先を私に与えなければならないということです。

"f"、 "d"、 "d"、 "c"、 "a"} {f "、" f "、" d "、" b "} "、" e "、" b "}、{" f "、" e "、" c "、" a "}

注：ノードの順序は関係ありません。

ありがとうございます。ここで

Answer 1

は、すべての可能な家族のラインを作る再帰関数である：

d <- data.frame(list("c" = c("a", "b", "c", "d", "e", "f"), 
     "p1" = c(NA, NA, "a", "b", "b", "d"), 
     "p2" = c(NA, NA, NA, "c", "c", "e")), stringsAsFactors = F) 

# Make data more convenient for the task. 
library(reshape2) 
dp <- melt(d, id = c("c"), value.name = "p") 

# Recursive function builds ancestor vectors. 
getAncestors <- function(data, x, ancestors = list(x)) { 

    parents <- subset(data, c %in% x & !is.na(p), select = c("c", "p")) 

    if(nrow(parents) == 0) { 
    return(ancestors) 
    } 

    x.c <- parents$c 
    p.c <- parents$p 

    ancestors <- lapply(ancestors, function(x) { 
    if (is.null(x)) return(NULL) 

    # Here we want to repeat ancestor chain for each new parent. 
    res <- list() 
    matches <- 0 
    for (i in 1:nrow(parents)) { 
     if (tail(x, 1) == parents[i, ]$c){ 
     res[[i]] <- c(x, parents[i, ]$p) 
     matches <- matches + 1 
     } 
    } 

    if (matches == 0) { # There are no more parents. 
     res[[1]] <- x 
    } 

    return (res) 
    }) 

    # remove one level of lists. 
    ancestors <- unlist(ancestors, recursive = F) 

    res <- getAncestors(data, p.c, ancestors) 
    return (res) 

} 

# Demo of results for the lowest level. 
res <- getAncestors(dp, "f") 
res 
#[[1]] 
#[1] "f" "d" "b" 

#[[2]] 
#[1] "f" "d" "c" "a" 

#[[3]] 
#[1] "f" "e" "b" 

#[[4]] 
#[1] "f" "e" "c" "a" 

あなたは再帰を介して、またはwhileループと同様の方法でこれを実装する必要があります。

Answer 2

サンプルデータを作成します。各行で、データは、長く広くない作るという親子ペア -

> d <- data.frame(list("c" = c("a", "b", "c", "d", "e", "f"), "p1" = c(NA, NA, "a", "b", "b", "d"), "p2" = c(NA, NA, NA, "c", "c", "e")),stringsAsFactors=FALSE) 

まずアップ、それをきちんと：

私はあなたのデータは文字ではなく要因であると仮定しています、ここで stringsAsFactorsの使用を注意してください

> pairs = subset(reshape2::melt(d,id.vars="c",value.name="parent"), !is.na(parent))[,c("c","parent")] 
> pairs 
    c parent 
3 c  a 
4 d  b 
5 e  b 
6 f  d 
10 d  c 
11 e  c 
12 f  e 

ここで、親子関係のグラフを作成できます。だから... ...私は正確に何をしたいかわからない今

> g = graph.data.frame(pairs) 
> plot(g) 

が、igraph機能は何もすることができます。これは、矢印のようにプロットので、親子、監督グラフです。

> d_search = bfs(g,"d",neimode="out", unreachable=FALSE, order=TRUE, dist=TRUE) 

まず、ノードはの祖先です：例えば、ここで私たちは情報の様々なビットを得ることができ、そこからdから始まるグラフの検索です？徹底的経由dから到達することができ、そのもの（ここでは、幅優先）検索：それは同様dを含ん

> d_search$order 
+ 6/6 vertices, named: 
[1] d c b a <NA> <NA> 

注意。このリストから抜け出すには些細なことだ。それはあなたが尋ねたものであるdの先祖のセットを与えます。

これらのノードの関係はdとは何ですか？

> d_search$dist 
    c d e f a b 
    1 0 NaN NaN 2 1 

我々はeとfが到達不能であることがわかり、そのdの祖先ではありません。cとbは親であり、aは祖父母です。これはグラフから確認できます。

shortest_pathsなどの機能を使用して、子から上へのすべてのパスを取得することもできます。