도미네이터 트리를 재귀 적으로 계산하는 효율적인 방법?

Question

경로 압축과 함께 Lengauer 및 Tarjan 알고리즘을 사용하여 수백만 개의 노드가있는 그래프의 도미네이터 트리를 계산합니다. 알고리즘은 상당히 복잡하고 그것을 완전히 이해하는 데 시간이 걸리지 않았다는 것을 인정해야합니다. 이제 루트 노드의 직접 어린이의 도미네이터 트리를 계산 하고이 작업을 반복하는 특정 깊이로 그래프를 되돌릴 수 있습니다. 즉, 루트 노드의 자식의 도미네이터 트리를 계산할 때 루트 노드가 그래프에서 제거 된 척하고 싶습니다.

내 질문은 이에 대한 효율적인 솔루션이 루트 노드의 초기 지배자 트리에서 이미 계산 된 즉각적인 지배자 정보를 사용하는지 여부입니다. 다시 말해서, 나는 전체 과정이 시간이 많이 걸리기 때문에 각 어린이들에 대해 처음부터 시작하고 싶지 않습니다.

순진하게 IDOM이 약간만있는 그래프에 깊은 노드가 많고 그래프 상단의 변경에 영향을받지 않기 때문에 가능해야합니다.

BTW와 마찬가지로 : 지배자 나무의 주제가 컴파일러 사람들이 "소유"하는 것은 기괴하며 클래식 그래프 이론에 관한 책에는 언급이 없습니다. 내가 사용하는 응용 프로그램 - 내 FindRoots Java 힙 분석기는 컴파일러 이론과 관련이 없습니다.

설명 : 나는 여기에서 지시 된 그래프에 대해 이야기하고 있습니다. 내가 언급 한 "루트"는 실제로 가장 큰 도달 가능성을 가진 노드입니다. 위의 텍스트를 "Tree"에 대한 참조를 "그래프"로 바꾸는 것을 업데이트했습니다. 나는 모양이 나무라고 생각하는 경향이 있습니다. 주로 나무처럼. 그래프는 실제로 자바 힙에있는 객체이며 상상할 수 있듯이 합리적으로 계층 적입니다. 나는 당신이 관심있는 것이 "이 대상을 살리게하는 것은 무엇입니까?" 그리고 대답은 궁극적으로 지배자입니다. 지배자 나무가 당신을 허용합니다u003Cahem> 나무가 아닌 나무를보십시오. 그러나 때로는 많은 쓰레기가 나무 꼭대기에 떠서 바로 아래에 수천 명의 아이들이있는 뿌리가 있습니다. 그러한 경우에 나는 뿌리의 직접 어린이 (원래 그래프)에 뿌리를 둔 지배자 나무를 계산 한 다음 다음 단계로 이동하여 실험하고 싶습니다. (나는 당분간 백 링크의 가능성에 대해 걱정하지 않으려 고 노력하고있다 :)

Answer 1

boost::lengauer_tarjan_dominator_tree_without_dfs 도움이 될 수 있습니다.

Answer 2

의견이 부족하여 판단하면, StackoverFlow에 관련된 경험이 많은 사람들이 당신을 도울 수있는 사람이 많지 않다고 생각합니다. 나는 그 사람들 중 하나이지만, 그런 흥미로운 질문이 둔한 멍청이와 함께 내려 가기를 원하지 않으므로 손을 빌려줄 것입니다.

첫 번째 생각은 다른 컴파일러에 의해이 그래프가 생성되면 GCC와 같은 오픈 소스 컴파일러를 살펴보면이 문제를 해결하는 방법을 확인할 가치가 있다는 것입니다.

두 번째 생각은, 당신의 질문의 주요 요점은 나무의 근본에 대한 결과를 다시 계산하는 것을 피하는 것 같습니다.

내가 할 일은 노드 자체와 해당 노드와 관련된 미리 컴퓨터 데이터를 포함하는 각 노드 주위에 래퍼를 만드는 것입니다. 그런 다음이 래퍼 클래스를 사용하여 오래된 트리에서 재구성 될 것입니다. 이 트리를 구성 할 때 뿌리에서 시작하여 잎 노드로 나가는 길을 작동시킵니다. 각 노드에 대해 지금까지 모든 조상 계산 결과를 저장합니다. 이렇게하면 새 노드의 값을 계산하기 위해 처리중인 상위 노드와 현재 노드 데이터 만 살펴 봐야합니다.

도움이되기를 바랍니다!

Answer 3

어떤 종류의 그래프로 시작할 수 있습니까? 나는 나무 인 그래프와 그 그래프의 지배자 트리 사이에 어떤 차이가 있는지 알지 못합니다. 모든 노드의 부모는 우려가되어야하며, 물론 나무 위의 모든 것에 의해 지배 될 것입니다.

Answer 4

나는 당신의 질문을 완전히 이해하지 못하지만, 당신은 약간의 증분 업데이트 기능을 갖고 싶어하는 것 같습니다. 나는 얼마 전에 알고리즘이 무엇인지 조사했지만 큰 그래프가 이것을 빨리 수행 할 수있는 알려진 방법이없는 것처럼 보였습니다 (적어도 이론적 관점에서).

"증분 업데이트 도미네이터 트리"를 검색하여 일부 참조를 찾을 수 있습니다.

나는 당신이 알고있는 것 같아요 일식 메모리 분석기 도미네이터 트리를 사용 하므로이 주제는 더 이상 컴파일러 커뮤니티가 완전히 "소유"하지 않습니다. :)