Editing Dominator (graph theory) (section)

{{Short description|When every path in a control-flow graph must go through one node to reach another}}
{{distinguish|dominating set}}
{| style="float:right"
| [[File:Dominator control flow graph.svg|thumb|200px|Example control-flow graph with entry node 1]]
|}
{| style="float:right" class=wikitable
|-
! 1 
| dom &nbsp; &nbsp; || {{color|#c0c0c0|1}} || {{color|#F00000|2}} || 3 || 4 || 5 || 6
|-
! 2 
| dom ||   || {{color|#c0c0c0|2}} || {{color|#F00000|3}} || {{color|#F00000|4}} || {{color|#F00000|5}} ||{{color|#F00000|6}}
|-
! 3 
| dom ||   ||   || {{color|#c0c0c0|3}} ||   || ||
|-
! 4 
| dom ||   ||   ||   || {{color|#c0c0c0|4}} || ||
|-
! 5 
| dom ||   ||   ||   ||   || {{color|#c0c0c0|5}} ||  
|-
! 6 
| dom ||   ||   ||   ||   ||   || {{color|#c0c0c0|6}}
|-
| colspan=8 | Corresponding domination relation:<br>{{color|#c0c0c0|Grey nodes}} are not strictly dominated<br>{{color|#F00000|Red nodes}} are immediately dominated
|}
[[File:Dominator tree.svg|thumb|200px|Corresponding ''dominator tree'' of the control flow graph]]

In [[computer science]], a [[basic block|node]] {{mvar|d}} of a [[control-flow graph]] '''dominates''' a node {{mvar|n}} if every path from the ''entry node'' to {{mvar|n}} must go through {{mvar|d}}. Notationally, this is written as {{math|''d'' dom ''n''}} (or sometimes {{math|''d'' ≫ ''n''}}). By definition, every node dominates itself.

There are a number of related concepts:

* A node {{mvar|d}} ''strictly dominates'' a node {{mvar|n}} if {{mvar|d}} dominates {{mvar|n}} and {{mvar|d}} does not equal {{mvar|n}}.
* The ''immediate dominator'' or '''idom''' of a node {{mvar|n}} is the unique node that strictly dominates {{mvar|n}} but does not strictly dominate any other node that strictly dominates {{mvar|n}}. Every node reachable from the entry node has an immediate dominator (except the entry node).<ref name="fastdom"/>
* The ''dominance frontier'' of a node {{mvar|d}} is the set of all nodes {{mvar|n{{sub|i}}}} such that {{mvar|d}} dominates an immediate predecessor of {{mvar|n{{sub|i}}}}, but {{mvar|d}} does not strictly dominate {{mvar|n{{sub|i}}}}. It is the set of nodes where {{mvar|d}}'s dominance stops.
* A ''dominator tree'' is a [[tree (graph theory)|tree]] where each node's children are those nodes it immediately dominates. The start node is the root of the tree.