123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183 |
- <HTML>
- <!--
- Copyright (c) JongSoo Park 2005
-
- Distributed under the Boost Software License, Version 1.0. (See
- accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt)
- -->
- <Head>
- <Title>Boost Graph Library: Lengauer-Tarjan Dominator Tree Algorithm</Title>
- <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
- ALINK="#ff0000">
- <IMG SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86">
- <BR Clear>
- <H1><A NAME="sec:lengauer-tarjan"></A>
- <TT>lengauer_tarjan_dominator_tree</TT>
- </H1>
- <P>
- <PRE>
- <i>// The simplest version:
- // Data structures for depth first search is created internally,
- // and depth first search runs internally.</i>
- template <class Graph, class DomTreePredMap>
- void
- lengauer_tarjan_dominator_tree
- (const Graph& g,
- const typename graph_traits<Graph>::vertex_descriptor& entry,
- DomTreePredMap domTreePredMap)
- <i>// The version providing data structures for depth first search:
- // After calling this function,
- // user can reuse the depth first search related information
- // filled in property maps.</i>
- template <class Graph, class IndexMap, class TimeMap, class PredMap,
- class VertexVector, class DomTreePredMap>
- void
- lengauer_tarjan_dominator_tree
- (const Graph& g,
- const typename graph_traits<Graph>::vertex_descriptor& entry,
- const IndexMap& indexMap,
- TimeMap dfnumMap, PredMap parentMap, VertexVector& verticesByDFNum,
- DomTreePredMap domTreePredMap)
- <i>// The version without depth first search:
- // The caller should provide depth first search related information
- // evaluated before.</i>
- template <class Graph, class IndexMap, class TimeMap, class PredMap,
- class VertexVector, class DomTreePredMap>
- void
- lengauer_tarjan_dominator_tree_without_dfs(
- (const Graph& g,
- const typename graph_traits<Graph>::vertex_descriptor& entry,
- const IndexMap& indexMap,
- TimeMap dfnumMap, PredMap parentMap, VertexVector& verticesByDFNum,
- DomTreePredMap domTreePredMap)
- </PRE>
- <P> This algorithm [<A
- HREF="bibliography.html#lengauer-tarjan79">65</A>,<A
- HREF="bibliography.html#muchnick97">66</A>,<A
- HREF="bibliography.html#appel98">67</A>] builds the dominator tree for
- directed graph. There are three options for dealing the depth first
- search related values. The simplest version creates data structures
- and run depth first search internally. However, chances are that a
- user wants to reuse the depth first search data, so we have two
- versions. </P>
- <P> A vertex <i>u</i> dominates a vertex <i>v</i>, if every path of
- directed graph from the entry to <i>v</i> must go through <i>u</i>. In
- the left graph of <a href="#fig:dominator-tree-example">Figure 1</a>,
- vertex 1 dominates vertex 2, 3, 4, 5, 6 and 7, because we have to pass
- vertex 1 to reach those vertex. Note that vertex 4 dominates vertex 6,
- even though vertex 4 is a successor of vertex 6. Dominator
- relationship is useful in many applications especially for compiler
- optimization. We can define the immediate dominator for each vertex
- such that <i>idom(n) dominates n</i> but does not dominate any other
- dominator of <i>n</i>. For example, vertex 1, 3 and 4 are dominators
- of vertex 6, but vertex 4 is the immediate dominator, because vertex 1
- and 3 dominates vertex 4. If we make every idom of each vertex as its
- parent, we can build the dominator tree like the right part of <a
- href="#fig:dominator-tree-example">Figure 1</a> </P>
- <P></P>
- <DIV ALIGN="CENTER"><A NAME="fig:dominator-tree-example">
- <TABLE>
- <CAPTION ALIGN="BOTTOM"><STRONG>Figure 1:</STRONG>
- An example graph and its dominator tree.</CAPTION>
- <TR>
- <TD><IMG SRC="./figs/dominator-tree1.gif"></TD>
- <TD> </TD>
- <TD><IMG SRC="./figs/dominator-tree2.gif"></TD>
- </TR>
- </TABLE>
- </DIV><P></P>
- <P> An easy way to build dominator tree is to use iterative bit vector
- algorithm, but it may be slow in the worst case. We implemented
- Lengauer-Tarjan algorithm whose time complexity is
- <i>O((V+E)log(V+E))</i>. </P>
- <P> Lengauer-Tarjan algorithm utilizes two techniques. The first one
- is, as an intermediate step, finding semidominator which is relatively
- easier to evaluate than immediate dominator, and the second one is the
- path compression. For the detail of the algorithm, see [<A
- HREF="bibliography.html#lengauer-tarjan79">65</A>]. </P>
- <h3>Where Defined</h3>
- <a href="../../../boost/graph/dominator_tree.hpp"><tt>boost/graph/dominator_tree.hpp</tt></a>
- <h3>Parameters</h3>
- IN: <tt>const Graph& g</tt>
- <blockquote>
- The graph object on which the algorithm will be applied.
- The type <tt>Graph</tt> must be a model of
- <a href="./VertexListGraph.html">Vertex List Graph</a>
- and <a href="./BidirectionalGraph.html">Bidirectional Graph</a>.<br>
- </blockquote>
- IN: <tt>vertex_descriptor entry</tt>
- <blockquote>
- The entry vertex. The dominator tree will be rooted at this vertex.
- </blockquote>
- IN: <tt>IndexMap indexMap</tt>
- <blockquote>
- This maps each vertex to an integer in the range <tt>[0, num_vertices(g))</tt>.
- The type
- <tt>VertexIndexMap</tt> must be a model of
- <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. The value type of the map must be an
- integer type. The vertex descriptor type of the graph needs to be
- usable as the key type of the map.
- </blockquote>
- IN/OUT: <tt>TimeMap dfnumMap</tt>
- <blockquote>
- 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>.
- </blockquote>
- IN/OUT: <tt>PredMap parentMap</tt>
- <blockquote>
- 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.
- </blockquote>
- IN/OUT: <tt>VertexVector verticesByDFNum</tt>
- <blockquote>
- 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.
- </blockquote>
- OUT: <tt>DomTreePredMap domTreePredMap</tt>
- <blockquote>
- The dominator tree where parents are each children's immediate dominator.
- </blockquote>
- <H3>Complexity</H3>
- <P>
- The time complexity is <i>O((V+E)log(V+E))</i>.
- <H3>Example</H3>
- <P>
- See <a href="../test/dominator_tree_test.cpp">
- <TT>test/dominator_tree_test.cpp</TT></a> for an example of using Dijkstra's
- algorithm.
- <br>
- <HR>
- <TABLE>
- <TR valign="top">
- <TD>Copyright © 2005</TD><TD>
- JongSoo Park, Stanford University
- </TD></TR></TABLE>
- </BODY>
- </HTML>
|