Lengauer-Tarjan Dominator Tree Algorithm
Builds the dominator tree for a directed graph using the Lengauer-Tarjan algorithm.
Complexity: OV+E)log(V+E
Defined in: <boost/graph/dominator_tree.hpp>
Example
#include <iostream>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dominator_tree.hpp>
int main() {
using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS>;
using Vertex = boost::graph_traits<Graph>::vertex_descriptor;
Graph g(6);
// CFG-like: 0 is entry
boost::add_edge(0, 1, g); boost::add_edge(0, 2, g);
boost::add_edge(1, 3, g); boost::add_edge(2, 3, g);
boost::add_edge(3, 4, g); boost::add_edge(4, 5, g);
std::vector<Vertex> dom(num_vertices(g), boost::graph_traits<Graph>::null_vertex());
auto dom_map = boost::make_iterator_property_map(dom.begin(), get(boost::vertex_index, g));
boost::lengauer_tarjan_dominator_tree(g, Vertex{0}, dom_map);
std::cout << "Immediate dominators (entry = 0):\n";
for (std::size_t v = 0; v < num_vertices(g); ++v) {
if (dom[v] != boost::graph_traits<Graph>::null_vertex())
std::cout << " idom(" << v << ") = " << dom[v] << "\n";
else
std::cout << " idom(" << v << ") = none (entry)\n";
}
}Immediate dominators (entry = 0):
idom(0) = none (entry)
idom(1) = 0
idom(2) = 0
idom(3) = 0
idom(4) = 3
idom(5) = 4(1) Simple version
The simplest version: data structures for depth first search are created internally, and depth first search runs internally.
template <class Graph, class DomTreePredMap>
void lengauer_tarjan_dominator_tree(
const Graph& g,
const typename graph_traits<Graph>::vertex_descriptor& entry,
DomTreePredMap domTreePredMap);| Direction | Parameter | Description |
|---|---|---|
IN |
|
The graph object on which the algorithm will be applied.
The type |
IN |
|
The entry vertex. The dominator tree will be rooted at this vertex. |
OUT |
|
The dominator tree where parents are each children’s immediate dominator. |
(2) Version providing DFS data structures
After calling this function, the user can reuse the depth first search related information filled in property maps.
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);| Direction | Parameter | Description |
|---|---|---|
IN |
|
The graph object on which the algorithm will be applied.
The type |
IN |
|
The entry vertex. The dominator tree will be rooted at this vertex. |
IN |
|
This maps each vertex to an integer in the range |
IN/OUT |
|
The sequence number of depth first search. The type |
IN/OUT |
|
The predecessor map records the parent of the depth first search tree.
The |
IN/OUT |
|
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. |
OUT |
|
The dominator tree where parents are each children’s immediate dominator. |
(3) Version without depth first search
The caller should provide depth first search related information evaluated before calling this function.
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);| Direction | Parameter | Description |
|---|---|---|
IN |
|
The graph object on which the algorithm will be applied.
The type |
IN |
|
The entry vertex. The dominator tree will be rooted at this vertex. |
IN |
|
This maps each vertex to an integer in the range |
IN/OUT |
|
The sequence number of depth first search. The type |
IN/OUT |
|
The predecessor map records the parent of the depth first search tree.
The |
IN/OUT |
|
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. |
OUT |
|
The dominator tree where parents are each children’s immediate dominator. |
Description
This algorithm [59,60,61] builds the dominator tree for a directed graph. There are three options for dealing with the depth first search related values. The simplest version creates data structures and runs depth first search internally. However, chances are that a user wants to reuse the depth first search data, so we have two additional versions.
A vertex u dominates a vertex v, if every path of the directed graph from the entry to v must go through u. In the left graph of Figure 1, vertex 1 dominates vertex 2, 3, 4, 5, 6 and 7, because we have to pass vertex 1 to reach those vertices. 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 idom(n) dominates n but does not dominate any other dominator of n. For example, vertex 1, 3 and 4 are dominators of vertex 6, but vertex 4 is the immediate dominator, because vertex 1 and 3 dominate vertex 4. If we make every idom of each vertex as its parent, we can build the dominator tree like the right part of Figure 1.
|
|
An easy way to build a dominator tree is to use an iterative bit vector algorithm, but it may be slow in the worst case. We implemented the Lengauer-Tarjan algorithm whose time complexity is OV+E)log(V+E.
Lengauer-Tarjan algorithm utilizes two techniques. The first one is, as an intermediate step, finding the semidominator which is relatively easier to evaluate than the immediate dominator, and the second one is path compression. For the detail of the algorithm, see [59].