Talk:Dominator (graph theory)

Latest comment: 9 years ago by Jochen Burghardt in topic Nodes 3 and 4 aren't dominators of 5?

Untitled

edit

The definition of immediate dominator is tautological, it uses concept of immediate dominance without explaining what it is. If I understood correctly, immediate dominator would be defined as something like:

"Node d immediately dominates node n, if it is its dominator, and there exists no dominator of n that isn't also dominator of d"

Is that correct? Mathrick 11:39, 22 Apr 2005 (UTC)

I think your definition is correct, but I added a definition in terms of strict dominators, because this seems a little easier to understand. The original "definition" was quite silly. Deco 16:55, 22 Apr 2005 (UTC)

Wrong

edit

Removing this:

<actually this algorithm is wrong, it can't handle circles, e.g , 4 is precedors of 5, and 5 point to 6, 6 point to 7 and 8, 7 point back to 5, 8 also point back to 5, then the algorithm will never put 4 in the dominators of 5, because 7,8 can appear before 5 in the path, so the intersection can't add 4 into it, but for 7,8 Dom(7), Dom(8) all depend on Dom(6) which depends on Dom(5), which never has 4 in it, so Dom(7),Dom(8) will never have 4 in it, well, you got the idea>

because it appears to be someone's confused opinion. It would be true if Dom(n) was initialized to {}, but it is initialized to the set of all nodes. Aij 15:47, 24 October 2007 (UTC)Reply

Suggested move

edit

I suggest moving this article to a different title, because it's not a concept studied graph theory, although it is a property of nodes in data flow graphs. Perhaps Dominator (computer science) or Dominator (compilers). Dcoetzee 22:25, 16 February 2009 (UTC)Reply

Post-dominance

edit

Hi,

I've heard two competing definitions of post-dominance which are not equivalent. Could anyone comment on which is more proper or more widely accepted?

Def 1: A node n post-dominates a node m iff every path from m to the distinguished exit node passes through n. For example, Andrew Appel uses this definition in "Modern Compiler Implementation." Also, the llvm-compiler infrastructure uses this definition in their implementation of ADCE http://74.125.93.132/search?q=cache:sFD2zsFBl-4J:https://llvm.org/svn/llvm-project/llvm/tags/RELEASE_11/lib/Transforms/Scalar/ADCE.cpp+%22post-dominance%22+infinite+loop&cd=2&hl=en&ct=clnk&gl=us&client=firefox-a

Def 2: A node n post-dominates a node m iff every path from m includes n. For example, Muchnick uses this definition in "Advanced Compiler Design and Implementation"


Def 1 requires the existence (and reachability) of an exit node (compare to start node in dominators). Thus, if there is an infinite loop, nothing post-dominates anything else. Def 2 (which is used on wikipedia) does not require an exit node, and is defined for infinite loops. This has real implications when one is trying to compute control dependences using post-dominator information.

Thanks, 128.112.139.195 (talk) —Preceding undated comment added 17:23, 5 November 2009 (UTC).Reply

Be careful: definition 1 doesn't strictly require reachability! If the exit node is not reachable from m, then every node post-dominates m (this is a vacuous truth since the set of all paths to the exit node is empty)--141.58.62.195 (talk) 12:48, 20 December 2012 (UTC)Reply

Clear up what "predecessor" means

edit

Usage of the term "predecessor" among the control flow/data flow analysis related pages of Wikipedia is inconsistent. It would be nice if we always said "immediate predecessor" when we mean immediate predecessors only. I feel like only saying "predecessor" alone is slightly confusing because some may think this means "all predecessors". (e.g. A -> B -> C, where A and B are predecessors of C, but we really only want to mean B is a predecessor of C). 128.62.88.18 (talk) 00:08, 16 October 2010 (UTC)Reply

Nodes 3 and 4 aren't dominators of 5?

edit

According to the documented definition, it looks like nodes 3 and 4 ought to be dominators for node 5; yet the dominator matrix in the figure doesn't list 5 as a dominated node. Why? 173.11.86.22 (talk) 09:08, 14 March 2015 (UTC)Reply

Node 3 isn't a dominator for 5 because there is a path to 5 not going through 3, viz. 1-2-4-5. Similar for node 4 (1-2-3-5). There is no notion of a node set dominating a node (like {3,4} dominating 5) defined here. - Jochen Burghardt (talk) 16:16, 14 March 2015 (UTC)Reply