1<HTML> 2<!-- 3 Copyright (c) JongSoo Park 2005 4 5 Distributed under the Boost Software License, Version 1.0. (See 6 accompanying file LICENSE_1_0.txt or copy at 7 http://www.boost.org/LICENSE_1_0.txt) 8 --> 9<Head> 10<Title>Boost Graph Library: Lengauer-Tarjan Dominator Tree Algorithm</Title> 11<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 12 ALINK="#ff0000"> 13<IMG SRC="../../../boost.png" 14 ALT="C++ Boost" width="277" height="86"> 15 16<BR Clear> 17 18<H1><A NAME="sec:lengauer-tarjan"></A> 19<TT>lengauer_tarjan_dominator_tree</TT> 20</H1> 21 22 23<P> 24<PRE> 25<i>// The simplest version: 26// Data structures for depth first search is created internally, 27// and depth first search runs internally.</i> 28template <class Graph, class DomTreePredMap> 29void 30lengauer_tarjan_dominator_tree 31 (const Graph& g, 32 const typename graph_traits<Graph>::vertex_descriptor& entry, 33 DomTreePredMap domTreePredMap) 34 35<i>// The version providing data structures for depth first search: 36// After calling this function, 37// user can reuse the depth first search related information 38// filled in property maps.</i> 39template <class Graph, class IndexMap, class TimeMap, class PredMap, 40 class VertexVector, class DomTreePredMap> 41void 42lengauer_tarjan_dominator_tree 43 (const Graph& g, 44 const typename graph_traits<Graph>::vertex_descriptor& entry, 45 const IndexMap& indexMap, 46 TimeMap dfnumMap, PredMap parentMap, VertexVector& verticesByDFNum, 47 DomTreePredMap domTreePredMap) 48 49<i>// The version without depth first search: 50// The caller should provide depth first search related information 51// evaluated before.</i> 52template <class Graph, class IndexMap, class TimeMap, class PredMap, 53 class VertexVector, class DomTreePredMap> 54void 55lengauer_tarjan_dominator_tree_without_dfs( 56 (const Graph& g, 57 const typename graph_traits<Graph>::vertex_descriptor& entry, 58 const IndexMap& indexMap, 59 TimeMap dfnumMap, PredMap parentMap, VertexVector& verticesByDFNum, 60 DomTreePredMap domTreePredMap) 61</PRE> 62 63<P> This algorithm [<A 64HREF="bibliography.html#lengauer-tarjan79">65</A>,<A 65HREF="bibliography.html#muchnick97">66</A>,<A 66HREF="bibliography.html#appel98">67</A>] builds the dominator tree for 67directed graph. There are three options for dealing the depth first 68search related values. The simplest version creates data structures 69and run depth first search internally. However, chances are that a 70user wants to reuse the depth first search data, so we have two 71versions. </P> 72 73<P> A vertex <i>u</i> dominates a vertex <i>v</i>, if every path of 74directed graph from the entry to <i>v</i> must go through <i>u</i>. In 75the left graph of <a href="#fig:dominator-tree-example">Figure 1</a>, 76vertex 1 dominates vertex 2, 3, 4, 5, 6 and 7, because we have to pass 77vertex 1 to reach those vertex. Note that vertex 4 dominates vertex 6, 78even though vertex 4 is a successor of vertex 6. Dominator 79relationship is useful in many applications especially for compiler 80optimization. We can define the immediate dominator for each vertex 81such that <i>idom(n) dominates n</i> but does not dominate any other 82dominator of <i>n</i>. For example, vertex 1, 3 and 4 are dominators 83of vertex 6, but vertex 4 is the immediate dominator, because vertex 1 84and 3 dominates vertex 4. If we make every idom of each vertex as its 85parent, we can build the dominator tree like the right part of <a 86href="#fig:dominator-tree-example">Figure 1</a> </P> 87 88<P></P> 89<DIV ALIGN="CENTER"><A NAME="fig:dominator-tree-example"> 90<TABLE> 91<CAPTION ALIGN="BOTTOM"><STRONG>Figure 1:</STRONG> 92An example graph and its dominator tree.</CAPTION> 93<TR> 94<TD><IMG SRC="./figs/dominator-tree1.gif"></TD> 95<TD> </TD> 96<TD><IMG SRC="./figs/dominator-tree2.gif"></TD> 97</TR> 98</TABLE> 99</DIV><P></P> 100 101<P> An easy way to build dominator tree is to use iterative bit vector 102algorithm, but it may be slow in the worst case. We implemented 103Lengauer-Tarjan algorithm whose time complexity is 104<i>O((V+E)log(V+E))</i>. </P> 105 106<P> Lengauer-Tarjan algorithm utilizes two techniques. The first one 107is, as an intermediate step, finding semidominator which is relatively 108easier to evaluate than immediate dominator, and the second one is the 109path compression. For the detail of the algorithm, see [<A 110HREF="bibliography.html#lengauer-tarjan79">65</A>]. </P> 111 112<h3>Where Defined</h3> 113 114<a href="../../../boost/graph/dominator_tree.hpp"><tt>boost/graph/dominator_tree.hpp</tt></a> 115 116<h3>Parameters</h3> 117 118IN: <tt>const Graph& g</tt> 119<blockquote> 120 The graph object on which the algorithm will be applied. 121 The type <tt>Graph</tt> must be a model of 122 <a href="./VertexListGraph.html">Vertex List Graph</a> 123 and <a href="./BidirectionalGraph.html">Bidirectional Graph</a>.<br> 124</blockquote> 125 126IN: <tt>vertex_descriptor entry</tt> 127<blockquote> 128 The entry vertex. The dominator tree will be rooted at this vertex. 129</blockquote> 130 131IN: <tt>IndexMap indexMap</tt> 132<blockquote> 133 This maps each vertex to an integer in the range <tt>[0, num_vertices(g))</tt>. 134 The type 135 <tt>VertexIndexMap</tt> must be a model of 136 <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. The value type of the map must be an 137 integer type. The vertex descriptor type of the graph needs to be 138 usable as the key type of the map. 139</blockquote> 140 141IN/OUT: <tt>TimeMap dfnumMap</tt> 142<blockquote> 143 The sequence number of depth first search. The type <tt>TimeMap</tt> must be a model of <a href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write Property Map</a>. The vertex descriptor type of the graph needs to be usable as the key type of the <tt>TimeMap</tt>. 144</blockquote> 145 146IN/OUT: <tt>PredMap parentMap</tt> 147<blockquote> 148 The predecessor map records the parent of the depth first search tree. The <tt>PredMap</tt> type must be a <a href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write Property Map</a> whose key and value types are the same as the vertex descriptor type of the graph. 149</blockquote> 150 151IN/OUT: <tt>VertexVector verticesByDFNum</tt> 152<blockquote> 153 The vector containing vertices in depth first search order. If we access this vector sequentially, it's equivalent to access vertices by depth first search order. 154</blockquote> 155 156OUT: <tt>DomTreePredMap domTreePredMap</tt> 157<blockquote> 158 The dominator tree where parents are each children's immediate dominator. 159</blockquote> 160 161<H3>Complexity</H3> 162 163<P> 164The time complexity is <i>O((V+E)log(V+E))</i>. 165 166<H3>Example</H3> 167 168<P> 169See <a href="../test/dominator_tree_test.cpp"> 170<TT>test/dominator_tree_test.cpp</TT></a> for an example of using Dijkstra's 171algorithm. 172 173<br> 174<HR> 175<TABLE> 176<TR valign="top"> 177<TD>Copyright © 2005</TD><TD> 178JongSoo Park, Stanford University 179</TD></TR></TABLE> 180 181</BODY> 182</HTML> 183 184
