ceph/src/boost/libs/graph/doc/lengauer_tarjan_dominator.htm

   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>
  28 template &lt;class Graph, class DomTreePredMap&gt;
  29 void
  30 lengauer_tarjan_dominator_tree
  31   (const Graph&amp; g,
  32    const typename graph_traits&lt;Graph&gt;::vertex_descriptor&amp; 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>
  39 template &lt;class Graph, class IndexMap, class TimeMap, class PredMap,
  40              class VertexVector, class DomTreePredMap&gt;
  41 void
  42 lengauer_tarjan_dominator_tree
  43   (const Graph&amp; g,
  44    const typename graph_traits&lt;Graph&gt;::vertex_descriptor&amp; entry,
  45    const IndexMap&amp; indexMap,
  46    TimeMap dfnumMap, PredMap parentMap, VertexVector&amp; 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>
  52 template &lt;class Graph, class IndexMap, class TimeMap, class PredMap,
  53              class VertexVector, class DomTreePredMap&gt;
  54 void
  55 lengauer_tarjan_dominator_tree_without_dfs(
  56   (const Graph&amp; g,
  57    const typename graph_traits&lt;Graph&gt;::vertex_descriptor&amp; entry,
  58    const IndexMap&amp; indexMap,
  59    TimeMap dfnumMap, PredMap parentMap, VertexVector&amp; verticesByDFNum,
  60    DomTreePredMap domTreePredMap)
  61 </PRE>
  62
  63 <P> This algorithm&nbsp;[<A
  64 HREF="bibliography.html#lengauer-tarjan79">65</A>,<A
  65 HREF="bibliography.html#muchnick97">66</A>,<A
  66 HREF="bibliography.html#appel98">67</A>] builds the dominator tree for
  67 directed graph. There are three options for dealing the depth first
  68 search related values. The simplest version creates data structures
  69 and run depth first search internally. However, chances are that a
  70 user wants to reuse the depth first search data, so we have two
  71 versions.  </P>
  72
  73 <P> A vertex <i>u</i> dominates a vertex <i>v</i>, if every path of
  74 directed graph from the entry to <i>v</i> must go through <i>u</i>. In
  75 the left graph of <a href="#fig:dominator-tree-example">Figure 1</a>,
  76 vertex 1 dominates vertex 2, 3, 4, 5, 6 and 7, because we have to pass
  77 vertex 1 to reach those vertex. Note that vertex 4 dominates vertex 6,
  78 even though vertex 4 is a successor of vertex 6. Dominator
  79 relationship is useful in many applications especially for compiler
  80 optimization. We can define the immediate dominator for each vertex
  81 such that <i>idom(n) dominates n</i> but does not dominate any other
  82 dominator of <i>n</i>. For example, vertex 1, 3 and 4 are dominators
  83 of vertex 6, but vertex 4 is the immediate dominator, because vertex 1
  84 and 3 dominates vertex 4. If we make every idom of each vertex as its
  85 parent, we can build the dominator tree like the right part of <a
  86 href="#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>
  92 An example graph and its dominator tree.</CAPTION>
  93 <TR>
  94 <TD><IMG SRC="./figs/dominator-tree1.gif"></TD>
  95 <TD>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</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
 102 algorithm, but it may be slow in the worst case. We implemented
 103 Lengauer-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
 107 is, as an intermediate step, finding semidominator which is relatively
 108 easier to evaluate than immediate dominator, and the second one is the
 109 path compression. For the detail of the algorithm, see [<A
 110 HREF="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
 118 IN: <tt>const Graph&amp; 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
 126 IN: <tt>vertex_descriptor entry</tt>
 127 <blockquote>
 128   The entry vertex. The dominator tree will be rooted at this vertex.
 129 </blockquote>
 130
 131 IN: <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
 141 IN/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
 146 IN/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
 151 IN/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
 156 OUT: <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>
 164 The time complexity is <i>O((V+E)log(V+E))</i>.
 165
 166 <H3>Example</H3>
 167
 168 <P>
 169 See <a href="../test/dominator_tree_test.cpp">
 170 <TT>test/dominator_tree_test.cpp</TT></a> for an example of using Dijkstra's
 171 algorithm.
 172
 173 <br>
 174 <HR>
 175 <TABLE>
 176 <TR valign="top">
 177 <TD>Copyright &copy; 2005</TD><TD>
 178 JongSoo Park, Stanford University
 179 </TD></TR></TABLE>
 180
 181 </BODY>
 182 </HTML>
 183