O que é um nó dominador e uma árvore dominadora?

Question

Eu tentei ler a wikipedia sobre Dominador (teoria dos grafos), que fornece a seguinte definição de nó dominador:

Um nó D domina um nó n se todo caminho do nó de entrada para n deverá passar por d.

Preciso entender o conceito de nó dominador mas não preciso me aprofundar em gráficos, então estou tentando entender essas definições.Estou tentando ver as imagens do artigo:

Este é um gráfico:

Esta deve ser uma árvore dominadora para o gráfico acima:

Com base na definição acima, penso

o nó 2 domina o nó 3 porque todo caminho de 3 deve passar por 2.Por que?Para ir do 3 até ele mesmo, devo passar para o 2.É por isso que 2 vai para 3 na árvore do dominador.

Estou pensando certo?

Posso saber também por que isso é útil em compiladores?

Answer 1

A razão que você dá não é exatamente correta;a definição de um nó dominador funciona a partir de um nó inicial ($1$ no exemplo).A única maneira de chegar $3$ de $1$ é passar $2$ pois é o único nó sucessor de $1$ no gráfico fornecido.Por isso $2$ domina $3$.Pela mesma razão, os nós $4$ através $6$ também são dominados por $2$ e ainda mais, $2$ é o imediato dominador desses nós (como $1$ domina $2$) e esses nós também não são dominados por nenhum outro nó além $1$ e $2$:

• $3, 4$ e $6$ pode ser imediatamente alcançado a partir de $1$ através da $2$.
• $5$ pode ser alcançado a partir de $2$ quer através $3$ ou $4$ e, portanto, os únicos nós comuns nesses caminhos para $5$ são $1$ e $2$.

Quanto à aplicação desses conceitos a compiladores, considere um gráfico de fluxo de controle em nível de bloco (ou CFG para abreviar) de um programa.Se algum bloquear $B$ domina um bloco $B'$ na CFG, então $B$ deve ter sido executado no momento em que o programa atinge $B'$.Esse conhecimento pode ser usado para remover trechos de código redundantes:Considere o programa

a = (something)
b = True

if a == True:
   b = True
else:
   b = False
   

Aqui, o bloco que consiste nas duas primeiras linhas domina o bloco if e também o bloco else.Portanto, sabemos que no momento em que saltamos para o bloco if onde definiríamos b como True, ele já está definido como True pelo primeiro bloco e, portanto, o compilador poderia otimizar o código excluindo a atribuição no bloco if.

Você também pode detectar loops no código analisando se o CFG possui arestas do formato $B' para B$ onde novamente $B$ domina $B'$.Tal caminho indica a existência de um loop onde $B$ representaria então o cabeçalho do loop enquanto $B'$ é (a última) parte do corpo do loop.