부모/자식/형제 관계를 기반으로 트리에서 노드 정리/검색

Question

고유하게 식별 된 노드, 루트 및 여러 개의 분기가있는 트리 구조가 있습니다. 어떤 노드가 새싹을 만들 수 있는지 또는 얼마나 깊게 갈 수 있는지에 대한 제한이 없습니다.

노드의 ID가 주어지면 그 노드의 모든 부모의 ID와 해당 부모의 모든 형제를 효율적으로 반환하고 싶습니다. 내가 원하는 건이 특정 질문에 대한 답은 이러한 유형의 조작을 위해 고안된 패키지/함수를 사용하여 매번 사용자 정의 알고리즘을 작성하지 않고 앞으로 비슷한 문제에 대해 사용할 수 있도록하는 것입니다. 여기

아동 - 부모 폼에있는 나무입니다 :

structure(list(child = 1:20, parent = c(NA, 1L, 2L, 3L, 1L, 5L, 6L, 5L, 8L, 1L, 1L, 11L, 12L, 11L, 14L, 14L, 1L, 17L, 18L, 19L)), .Names = c("child", "parent"), class = "data.frame", row.names = c(NA, -20L)) 

그리고 여기에 시각적 표현입니다 (빨간색) 내 목표 ID가 13 인 특정 문제에 대한

부모 노드의 자식 (오렌지색) 및 부모 형제 (노란색)의 ID를 가져 오려고합니다. 나는 확실히 이것을 할 수있는 알고리즘을 생각해 낼 수있다. (모든 부모를 얻는 것은 쉽다. 형제는 각 부모의 자식을 얻는 것을 의미한다.) 그러나이 모든 것을 효율적으로 수행하기위한 프레임 워크가 이미 존재하기를 바라고있다.

나는 rpart, tree 및 ape에 잠시 보였지만, 나는 그들이 오히려 노드의 조작/검색보다는 나무의 통계 분류를 대상으로, 그것은 다소에 따라 나에게 듯하는 내 고찰에서 알 ​​수까지로 그들이 (나는 완전히 그것을 놓치고/그것을 오해하고있어) 가능성이 후 기능을 제공하지 않는 형식적인 리뷰.

이

다른 옵션이 될 것 같습니다 내 목표를 달성하기 위해 DOM 조작 도구의 일부를 사용할 수 있지만, 조금 손으로 무거운 아마도 최적이 아닌 것 같다 것 XML 또는 xmlTree.

Answer 1

나는 여러 번 비슷한 상황에서 자신을 발견했으며, 보통 내 자신의 솔루션을 굴렸다. 나는 XML 패키지가 이와 같은 집중된 문제들에 대해 지나친 과업이라고 동의한다. iGraph 패키지는 좋지만주의하십시오. 이것은 C 라이브러리에 대한 인터페이스이며 0 인덱싱됩니다 (1 인덱싱 된 R과 달리). 나는 그것을 성공적으로 사용했지만 항상 "변화되지 않은"색인을 찾는 고통스러운 디버깅 프로세스가있는 것 같습니다. (예 : foo[index]은 foo[index-1]으로 변경해야합니다.)

다시 말하지만, 내 자신을 굴릴 가능성이 높습니다. 같은 뭔가 : 내가 거기에 조금 내 깊이 나갈거야하지만 포인터에 대한

foo <- structure(list(child = 1:20, parent = c(NA, 1L, 2L, 3L, 1L, 5L, 6L, 5L, 8L, 1L, 1L, 11L, 12L, 11L, 14L, 14L, 1L, 17L, 18L, 19L)), .Names = c("child", "parent"), class = "data.frame", row.names = c(NA, -20L)) 

get_ancestry <- function(node, data=foo, ancestry=c()) { 
    parent <- data$parent[data$child %in% node] 
    if (is.na(parent)) { 
     return(ancestry) 
    } else { 
     get_ancestry(parent, data, c(ancestry, parent)) 
    } 
} 

get_children <- function(nodes, data=foo) { 
    unlist(lapply(nodes, function(x) {data$child[data$parent %in% x]})) 
} 

orange <- get_ancestry(13) 
yellow <- get_children(orange) 

Answer 2

덕분에, igraph는, 확실히 내가 무엇을 찾고있다. python igraph tutorial의 도움으로 나는

g <- graph(t(as.matrix(df[-1, 2:1])))   # Make graph 
plot(g)           # yes, this matches mine 
parents <- unlist(        # orange nodes 
    neighborhood(
    g, 
    order=ecount(g),        # how many steps to go up, this should guarantee we get to root 
    nodes=13,         # starting point  
    mode="in"         # head in towards root 
) 
)[-1L] 
setdiff(          # yellow nodes 
    unique(          
    unlist(
     lapply(parents, neighborhood, graph=g, order=1, mode="out") 
)), 
    c(parents, 13) 
) 

원하는 대답을 얻었습니다. 불행히도 neighborhood 함수의 반환 형식으로 인해 각 단계마다 약간의 사후 처리가 필요합니다.