third_party/boost/include/boost/graph/dominator_tree.hpp - webm/webmlive - Git at Google

 //=======================================================================
 // Copyright (C) 2005-2009 Jongsoo Park <jongsoo.park -at- gmail.com>
 //
 // 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)
 //=======================================================================

 #ifndef BOOST_GRAPH_DOMINATOR_HPP
 #define BOOST_GRAPH_DOMINATOR_HPP

 #include <boost/config.hpp>
 #include <deque>
 #include <set>
 #include <boost/graph/depth_first_search.hpp>

 // Dominator tree computation

 namespace boost {
   namespace detail {
     /**
      * An extended time_stamper which also records vertices for each dfs number
      */
     template<class TimeMap, class VertexVector, class TimeT, class Tag>
     class time_stamper_with_vertex_vector
       : public base_visitor<
       time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT, Tag> >
     {
     public :
       typedef Tag event_filter;
       time_stamper_with_vertex_vector(TimeMap timeMap, VertexVector& v,
                                       TimeT& t)
         : timeStamper_(timeMap, t), v_(v) { }

       template<class Graph>
       void
       operator()(const typename property_traits<TimeMap>::key_type& v,
                  const Graph& g)
       {
         timeStamper_(v, g);
         v_[timeStamper_.m_time] = v;
       }

     private :
       time_stamper<TimeMap, TimeT, Tag> timeStamper_;
       VertexVector& v_;
     };

     /**
      * A convenient way to create a time_stamper_with_vertex_vector
      */
     template<class TimeMap, class VertexVector, class TimeT, class Tag>
     time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT, Tag>
     stamp_times_with_vertex_vector(TimeMap timeMap, VertexVector& v, TimeT& t,
                                    Tag)
     {
       return time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT,
                                              Tag>(timeMap, v, t);
     }

     template<class Graph, class IndexMap, class TimeMap, class PredMap,
              class DomTreePredMap>
     class dominator_visitor
     {
       typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
       typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;

     public :
       /**
        * @param g [in] the target graph of the dominator tree
        * @param entry [in] the entry node of g
        * @param domTreePredMap [out] the immediate dominator map
        *                             (parent map in dominator tree)
        */
       dominator_visitor(const Graph& g, const Vertex& entry,
                         DomTreePredMap domTreePredMap)
         : semi_(num_vertices(g)),
           ancestor_(num_vertices(g), graph_traits<Graph>::null_vertex()),
           samedom_(ancestor_),
           best_(semi_),
           semiMap_(make_iterator_property_map(semi_.begin(),
                                               get(vertex_index, g))),
           ancestorMap_(make_iterator_property_map(ancestor_.begin(),
                                                   get(vertex_index, g))),
           bestMap_(make_iterator_property_map(best_.begin(),
                                               get(vertex_index, g))),
           buckets_(num_vertices(g)),
           bucketMap_(make_iterator_property_map(buckets_.begin(),
                                                 get(vertex_index, g))),
           entry_(entry),
           domTreePredMap_(domTreePredMap),
           numOfVertices_(num_vertices(g)),
           samedomMap(make_iterator_property_map(samedom_.begin(),
                                                 get(vertex_index, g)))
       {
       }

       void
       operator()(const Vertex& n, const TimeMap& dfnumMap,
                  const PredMap& parentMap, const Graph& g)
       {
         if (n == entry_) return;

         const Vertex p(get(parentMap, n));
         Vertex s(p);

         // 1. Calculate the semidominator of n,
         // based on the semidominator thm.
         // * Semidominator thm. : To find the semidominator of a node n,
         //   consider all predecessors v of n in the CFG (Control Flow Graph).
         //  - If v is a proper ancestor of n in the spanning tree
         //    (so dfnum(v) < dfnum(n)), then v is a candidate for semi(n)
         //  - If v is a non-ancestor of n (so dfnum(v) > dfnum(n))
         //    then for each u that is an ancestor of v (or u = v),
         //    Let semi(u) be a candidate for semi(n)
         //   of all these candidates, the one with lowest dfnum is
         //   the semidominator of n.

         // For each predecessor of n
         typename graph_traits<Graph>::in_edge_iterator inItr, inEnd;
         for (boost::tie(inItr, inEnd) = in_edges(n, g); inItr != inEnd; ++inItr)
           {
             const Vertex v = source(*inItr, g);
             // To deal with unreachable nodes
             if (get(dfnumMap, v) < 0 || get(dfnumMap, v) >= numOfVertices_)
               continue;

             Vertex s2;
             if (get(dfnumMap, v) <= get(dfnumMap, n))
               s2 = v;
             else
               s2 = get(semiMap_, ancestor_with_lowest_semi_(v, dfnumMap));

             if (get(dfnumMap, s2) < get(dfnumMap, s))
               s = s2;
           }
         put(semiMap_, n, s);

         // 2. Calculation of n's dominator is deferred until
         // the path from s to n has been linked into the forest
         get(bucketMap_, s).push_back(n);
         get(ancestorMap_, n) = p;
         get(bestMap_, n) = n;

         // 3. Now that the path from p to v has been linked into
         // the spanning forest, these lines calculate the dominator of v,
         // based on the dominator thm., or else defer the calculation
         // until y's dominator is known
         // * Dominator thm. : On the spanning-tree path below semi(n) and
         //   above or including n, let y be the node
         //   with the smallest-numbered semidominator. Then,
         //
         //  idom(n) = semi(n) if semi(y)=semi(n) or
         //            idom(y) if semi(y) != semi(n)
         typename std::deque<Vertex>::iterator buckItr;
         for (buckItr = get(bucketMap_, p).begin();
              buckItr != get(bucketMap_, p).end();
              ++buckItr)
           {
             const Vertex v(*buckItr);
             const Vertex y(ancestor_with_lowest_semi_(v, dfnumMap));
             if (get(semiMap_, y) == get(semiMap_, v))
               put(domTreePredMap_, v, p);
             else
               put(samedomMap, v, y);
           }

         get(bucketMap_, p).clear();
       }

     protected :

       /**
        * Evaluate function in Tarjan's path compression
        */
       const Vertex
       ancestor_with_lowest_semi_(const Vertex& v, const TimeMap& dfnumMap)
       {
         const Vertex a(get(ancestorMap_, v));

         if (get(ancestorMap_, a) != graph_traits<Graph>::null_vertex())
           {
             const Vertex b(ancestor_with_lowest_semi_(a, dfnumMap));

             put(ancestorMap_, v, get(ancestorMap_, a));

             if (get(dfnumMap, get(semiMap_, b)) <
                 get(dfnumMap, get(semiMap_, get(bestMap_, v))))
               put(bestMap_, v, b);
           }

         return get(bestMap_, v);
       }

       std::vector<Vertex> semi_, ancestor_, samedom_, best_;
       PredMap semiMap_, ancestorMap_, bestMap_;
       std::vector< std::deque<Vertex> > buckets_;

       iterator_property_map<typename std::vector<std::deque<Vertex> >::iterator,
                             IndexMap> bucketMap_;

       const Vertex& entry_;
       DomTreePredMap domTreePredMap_;
       const VerticesSizeType numOfVertices_;

     public :

       PredMap samedomMap;
     };

   } // namespace detail

   /**
    * @brief Build dominator tree using Lengauer-Tarjan algorithm.
    *                It takes O((V+E)log(V+E)) time.
    *
    * @pre dfnumMap, parentMap and verticesByDFNum have dfs results corresponding
    *      indexMap.
    *      If dfs has already run before,
    *      this function would be good for saving computations.
    * @pre Unreachable nodes must be masked as
    *      graph_traits<Graph>::null_vertex in parentMap.
    * @pre Unreachable nodes must be masked as
    *      (std::numeric_limits<VerticesSizeType>::max)() in dfnumMap.
    *
    * @param domTreePredMap [out] : immediate dominator map (parent map
    * in dom. tree)
    *
    * @note reference Appel. p. 452~453. algorithm 19.9, 19.10.
    *
    * @todo : Optimization in Finding Dominators in Practice, Loukas Georgiadis
    */
   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)
   {
     // Typedefs and concept check
     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
     typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;

     function_requires< BidirectionalGraphConcept<Graph> >();

     const VerticesSizeType numOfVertices = num_vertices(g);
     if (numOfVertices == 0) return;

     // 1. Visit each vertex in reverse post order and calculate sdom.
     detail::dominator_visitor<Graph, IndexMap, TimeMap, PredMap, DomTreePredMap>
       visitor(g, entry, domTreePredMap);

     VerticesSizeType i;
     for (i = 0; i < numOfVertices; ++i)
       {
         const Vertex u(verticesByDFNum[numOfVertices - 1 - i]);
         if (u != graph_traits<Graph>::null_vertex())
           visitor(u, dfnumMap, parentMap, g);
       }

     // 2. Now all the deferred dominator calculations,
     // based on the second clause of the dominator thm., are performed
     for (i = 0; i < numOfVertices; ++i)
       {
         const Vertex n(verticesByDFNum[i]);

         if (n == entry || n == graph_traits<Graph>::null_vertex())
           continue;

         Vertex u = get(visitor.samedomMap, n);
         if (u != graph_traits<Graph>::null_vertex())
           {
             put(domTreePredMap, n, get(domTreePredMap, u));
           }
       }
   }

   /**
    * Unlike lengauer_tarjan_dominator_tree_without_dfs,
    * dfs is run in this function and
    * the result is written to dfnumMap, parentMap, vertices.
    *
    * If the result of dfs required after this algorithm,
    * this function can eliminate the need of rerunning dfs.
    */
   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)
   {
     // Typedefs and concept check
     typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;

     function_requires< BidirectionalGraphConcept<Graph> >();

     // 1. Depth first visit
     const VerticesSizeType numOfVertices = num_vertices(g);
     if (numOfVertices == 0) return;

     VerticesSizeType time =
       (std::numeric_limits<VerticesSizeType>::max)();
     std::vector<default_color_type>
       colors(numOfVertices, color_traits<default_color_type>::white());
     depth_first_visit
       (g, entry,
        make_dfs_visitor
          (make_pair(record_predecessors(parentMap, on_tree_edge()),
                     detail::stamp_times_with_vertex_vector
                       (dfnumMap, verticesByDFNum, time, on_discover_vertex()))),
        make_iterator_property_map(colors.begin(), indexMap));

     // 2. Run main algorithm.
     lengauer_tarjan_dominator_tree_without_dfs(g, entry, indexMap, dfnumMap,
                                                parentMap, verticesByDFNum,
                                                domTreePredMap);
   }

   /**
    * Use vertex_index as IndexMap and make dfnumMap, parentMap, verticesByDFNum
    * internally.
    * If we don't need the result of dfs (dfnumMap, parentMap, verticesByDFNum),
    * this function would be more convenient one.
    */
   template<class Graph, class DomTreePredMap>
   void
   lengauer_tarjan_dominator_tree
     (const Graph& g,
      const typename graph_traits<Graph>::vertex_descriptor& entry,
      DomTreePredMap domTreePredMap)
   {
     // typedefs
     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
     typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;
     typedef typename property_map<Graph, vertex_index_t>::const_type IndexMap;
     typedef
       iterator_property_map<typename std::vector<VerticesSizeType>::iterator,
                             IndexMap> TimeMap;
     typedef
       iterator_property_map<typename std::vector<Vertex>::iterator, IndexMap>
       PredMap;

     // Make property maps
     const VerticesSizeType numOfVertices = num_vertices(g);
     if (numOfVertices == 0) return;

     const IndexMap indexMap = get(vertex_index, g);

     std::vector<VerticesSizeType> dfnum(numOfVertices, 0);
     TimeMap dfnumMap(make_iterator_property_map(dfnum.begin(), indexMap));

     std::vector<Vertex> parent(numOfVertices,
                                graph_traits<Graph>::null_vertex());
     PredMap parentMap(make_iterator_property_map(parent.begin(), indexMap));

     std::vector<Vertex> verticesByDFNum(parent);

     // Run main algorithm
     lengauer_tarjan_dominator_tree(g, entry,
                                    indexMap, dfnumMap, parentMap,
                                    verticesByDFNum, domTreePredMap);
   }

   /**
    * Muchnick. p. 182, 184
    *
    * using iterative bit vector analysis
    */
   template<class Graph, class IndexMap, class DomTreePredMap>
   void
   iterative_bit_vector_dominator_tree
     (const Graph& g,
      const typename graph_traits<Graph>::vertex_descriptor& entry,
      const IndexMap& indexMap,
      DomTreePredMap domTreePredMap)
   {
     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
     typedef typename graph_traits<Graph>::vertex_iterator vertexItr;
     typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;
     typedef
       iterator_property_map<typename std::vector< std::set<Vertex> >::iterator,
                             IndexMap> vertexSetMap;

     function_requires<BidirectionalGraphConcept<Graph> >();

     // 1. Finding dominator
     // 1.1. Initialize
     const VerticesSizeType numOfVertices = num_vertices(g);
     if (numOfVertices == 0) return;

     vertexItr vi, viend;
     boost::tie(vi, viend) = vertices(g);
     const std::set<Vertex> N(vi, viend);

     bool change = true;

     std::vector< std::set<Vertex> > dom(numOfVertices, N);
     vertexSetMap domMap(make_iterator_property_map(dom.begin(), indexMap));
     get(domMap, entry).clear();
     get(domMap, entry).insert(entry);

     while (change)
       {
         change = false;
         for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi)
           {
             if (*vi == entry) continue;

             std::set<Vertex> T(N);

             typename graph_traits<Graph>::in_edge_iterator inItr, inEnd;
             for (boost::tie(inItr, inEnd) = in_edges(*vi, g); inItr != inEnd; ++inItr)
               {
                 const Vertex p = source(*inItr, g);

                 std::set<Vertex> tempSet;
                 std::set_intersection(T.begin(), T.end(),
                                       get(domMap, p).begin(),
                                       get(domMap, p).end(),
                                       std::inserter(tempSet, tempSet.begin()));
                 T.swap(tempSet);
               }

             T.insert(*vi);
             if (T != get(domMap, *vi))
               {
                 change = true;
                 get(domMap, *vi).swap(T);
               }
           } // end of for (boost::tie(vi, viend) = vertices(g)
       } // end of while(change)

     // 2. Build dominator tree
     for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi)
       get(domMap, *vi).erase(*vi);

     Graph domTree(numOfVertices);

     for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi)
       {
         if (*vi == entry) continue;

         // We have to iterate through copied dominator set
         const std::set<Vertex> tempSet(get(domMap, *vi));
         typename std::set<Vertex>::const_iterator s;
         for (s = tempSet.begin(); s != tempSet.end(); ++s)
           {
             typename std::set<Vertex>::iterator t;
             for (t = get(domMap, *vi).begin(); t != get(domMap, *vi).end(); )
               {
         typename std::set<Vertex>::iterator old_t = t;
         ++t; // Done early because t may become invalid
                 if (*old_t == *s) continue;
                 if (get(domMap, *s).find(*old_t) != get(domMap, *s).end())
                   get(domMap, *vi).erase(old_t);
               }
           }
       }

     for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi)
       {
         if (*vi != entry && get(domMap, *vi).size() == 1)
           {
             Vertex temp = *get(domMap, *vi).begin();
             put(domTreePredMap, *vi, temp);
           }
       }
   }

   template<class Graph, class DomTreePredMap>
   void
   iterative_bit_vector_dominator_tree
     (const Graph& g,
      const typename graph_traits<Graph>::vertex_descriptor& entry,
      DomTreePredMap domTreePredMap)
   {
     typename property_map<Graph, vertex_index_t>::const_type
       indexMap = get(vertex_index, g);

     iterative_bit_vector_dominator_tree(g, entry, indexMap, domTreePredMap);
   }
 } // namespace boost

 #endif // BOOST_GRAPH_DOMINATOR_HPP
	//=======================================================================
	// Copyright (C) 2005-2009 Jongsoo Park <jongsoo.park -at- gmail.com>
	//
	// 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)
	//=======================================================================

	#ifndef BOOST_GRAPH_DOMINATOR_HPP
	#define BOOST_GRAPH_DOMINATOR_HPP

	#include <boost/config.hpp>
	#include <deque>
	#include <set>
	#include <boost/graph/depth_first_search.hpp>

	// Dominator tree computation

	namespace boost {
	namespace detail {
	/**
	* An extended time_stamper which also records vertices for each dfs number
	*/
	template<class TimeMap, class VertexVector, class TimeT, class Tag>
	class time_stamper_with_vertex_vector
	: public base_visitor<
	time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT, Tag> >
	{
	public :
	typedef Tag event_filter;
	time_stamper_with_vertex_vector(TimeMap timeMap, VertexVector& v,
	TimeT& t)
	: timeStamper_(timeMap, t), v_(v) { }

	template<class Graph>
	void
	operator()(const typename property_traits<TimeMap>::key_type& v,
	const Graph& g)
	{
	timeStamper_(v, g);
	v_[timeStamper_.m_time] = v;
	}

	private :
	time_stamper<TimeMap, TimeT, Tag> timeStamper_;
	VertexVector& v_;
	};

	/**
	* A convenient way to create a time_stamper_with_vertex_vector
	*/
	template<class TimeMap, class VertexVector, class TimeT, class Tag>
	time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT, Tag>
	stamp_times_with_vertex_vector(TimeMap timeMap, VertexVector& v, TimeT& t,
	Tag)
	{
	return time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT,
	Tag>(timeMap, v, t);
	}

	template<class Graph, class IndexMap, class TimeMap, class PredMap,
	class DomTreePredMap>
	class dominator_visitor
	{
	typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
	typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;

	public :
	/**
	* @param g [in] the target graph of the dominator tree
	* @param entry [in] the entry node of g
	* @param domTreePredMap [out] the immediate dominator map
	* (parent map in dominator tree)
	*/
	dominator_visitor(const Graph& g, const Vertex& entry,
	DomTreePredMap domTreePredMap)
	: semi_(num_vertices(g)),
	ancestor_(num_vertices(g), graph_traits<Graph>::null_vertex()),
	samedom_(ancestor_),
	best_(semi_),
	semiMap_(make_iterator_property_map(semi_.begin(),
	get(vertex_index, g))),
	ancestorMap_(make_iterator_property_map(ancestor_.begin(),
	get(vertex_index, g))),
	bestMap_(make_iterator_property_map(best_.begin(),
	get(vertex_index, g))),
	buckets_(num_vertices(g)),
	bucketMap_(make_iterator_property_map(buckets_.begin(),
	get(vertex_index, g))),
	entry_(entry),
	domTreePredMap_(domTreePredMap),
	numOfVertices_(num_vertices(g)),
	samedomMap(make_iterator_property_map(samedom_.begin(),
	get(vertex_index, g)))
	{
	}

	void
	operator()(const Vertex& n, const TimeMap& dfnumMap,
	const PredMap& parentMap, const Graph& g)
	{
	if (n == entry_) return;

	const Vertex p(get(parentMap, n));
	Vertex s(p);

	// 1. Calculate the semidominator of n,
	// based on the semidominator thm.
	// * Semidominator thm. : To find the semidominator of a node n,
	// consider all predecessors v of n in the CFG (Control Flow Graph).
	// - If v is a proper ancestor of n in the spanning tree
	// (so dfnum(v) < dfnum(n)), then v is a candidate for semi(n)
	// - If v is a non-ancestor of n (so dfnum(v) > dfnum(n))
	// then for each u that is an ancestor of v (or u = v),
	// Let semi(u) be a candidate for semi(n)
	// of all these candidates, the one with lowest dfnum is
	// the semidominator of n.

	// For each predecessor of n
	typename graph_traits<Graph>::in_edge_iterator inItr, inEnd;
	for (boost::tie(inItr, inEnd) = in_edges(n, g); inItr != inEnd; ++inItr)
	{
	const Vertex v = source(*inItr, g);
	// To deal with unreachable nodes
	if (get(dfnumMap, v) < 0 \|\| get(dfnumMap, v) >= numOfVertices_)
	continue;

	Vertex s2;
	if (get(dfnumMap, v) <= get(dfnumMap, n))
	s2 = v;
	else
	s2 = get(semiMap_, ancestor_with_lowest_semi_(v, dfnumMap));

	if (get(dfnumMap, s2) < get(dfnumMap, s))
	s = s2;
	}
	put(semiMap_, n, s);

	// 2. Calculation of n's dominator is deferred until
	// the path from s to n has been linked into the forest
	get(bucketMap_, s).push_back(n);
	get(ancestorMap_, n) = p;
	get(bestMap_, n) = n;

	// 3. Now that the path from p to v has been linked into
	// the spanning forest, these lines calculate the dominator of v,
	// based on the dominator thm., or else defer the calculation
	// until y's dominator is known
	// * Dominator thm. : On the spanning-tree path below semi(n) and
	// above or including n, let y be the node
	// with the smallest-numbered semidominator. Then,
	//
	// idom(n) = semi(n) if semi(y)=semi(n) or
	// idom(y) if semi(y) != semi(n)
	typename std::deque<Vertex>::iterator buckItr;
	for (buckItr = get(bucketMap_, p).begin();
	buckItr != get(bucketMap_, p).end();
	++buckItr)
	{
	const Vertex v(*buckItr);
	const Vertex y(ancestor_with_lowest_semi_(v, dfnumMap));
	if (get(semiMap_, y) == get(semiMap_, v))
	put(domTreePredMap_, v, p);
	else
	put(samedomMap, v, y);
	}

	get(bucketMap_, p).clear();
	}

	protected :

	/**
	* Evaluate function in Tarjan's path compression
	*/
	const Vertex
	ancestor_with_lowest_semi_(const Vertex& v, const TimeMap& dfnumMap)
	{
	const Vertex a(get(ancestorMap_, v));

	if (get(ancestorMap_, a) != graph_traits<Graph>::null_vertex())
	{
	const Vertex b(ancestor_with_lowest_semi_(a, dfnumMap));

	put(ancestorMap_, v, get(ancestorMap_, a));

	if (get(dfnumMap, get(semiMap_, b)) <
	get(dfnumMap, get(semiMap_, get(bestMap_, v))))
	put(bestMap_, v, b);
	}

	return get(bestMap_, v);
	}

	std::vector<Vertex> semi_, ancestor_, samedom_, best_;
	PredMap semiMap_, ancestorMap_, bestMap_;
	std::vector< std::deque<Vertex> > buckets_;

	iterator_property_map<typename std::vector<std::deque<Vertex> >::iterator,
	IndexMap> bucketMap_;

	const Vertex& entry_;
	DomTreePredMap domTreePredMap_;
	const VerticesSizeType numOfVertices_;

	public :

	PredMap samedomMap;
	};

	} // namespace detail

	/**
	* @brief Build dominator tree using Lengauer-Tarjan algorithm.
	* It takes O((V+E)log(V+E)) time.
	*
	* @pre dfnumMap, parentMap and verticesByDFNum have dfs results corresponding
	* indexMap.
	* If dfs has already run before,
	* this function would be good for saving computations.
	* @pre Unreachable nodes must be masked as
	* graph_traits<Graph>::null_vertex in parentMap.
	* @pre Unreachable nodes must be masked as
	* (std::numeric_limits<VerticesSizeType>::max)() in dfnumMap.
	*
	* @param domTreePredMap [out] : immediate dominator map (parent map
	* in dom. tree)
	*
	* @note reference Appel. p. 452~453. algorithm 19.9, 19.10.
	*
	* @todo : Optimization in Finding Dominators in Practice, Loukas Georgiadis
	*/
	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)
	{
	// Typedefs and concept check
	typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
	typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;

	function_requires< BidirectionalGraphConcept<Graph> >();

	const VerticesSizeType numOfVertices = num_vertices(g);
	if (numOfVertices == 0) return;

	// 1. Visit each vertex in reverse post order and calculate sdom.
	detail::dominator_visitor<Graph, IndexMap, TimeMap, PredMap, DomTreePredMap>
	visitor(g, entry, domTreePredMap);

	VerticesSizeType i;
	for (i = 0; i < numOfVertices; ++i)
	{
	const Vertex u(verticesByDFNum[numOfVertices - 1 - i]);
	if (u != graph_traits<Graph>::null_vertex())
	visitor(u, dfnumMap, parentMap, g);
	}

	// 2. Now all the deferred dominator calculations,
	// based on the second clause of the dominator thm., are performed
	for (i = 0; i < numOfVertices; ++i)
	{
	const Vertex n(verticesByDFNum[i]);

	if (n == entry \|\| n == graph_traits<Graph>::null_vertex())
	continue;

	Vertex u = get(visitor.samedomMap, n);
	if (u != graph_traits<Graph>::null_vertex())
	{
	put(domTreePredMap, n, get(domTreePredMap, u));
	}
	}
	}

	/**
	* Unlike lengauer_tarjan_dominator_tree_without_dfs,
	* dfs is run in this function and
	* the result is written to dfnumMap, parentMap, vertices.
	*
	* If the result of dfs required after this algorithm,
	* this function can eliminate the need of rerunning dfs.
	*/
	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)
	{
	// Typedefs and concept check
	typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;

	function_requires< BidirectionalGraphConcept<Graph> >();

	// 1. Depth first visit
	const VerticesSizeType numOfVertices = num_vertices(g);
	if (numOfVertices == 0) return;

	VerticesSizeType time =
	(std::numeric_limits<VerticesSizeType>::max)();
	std::vector<default_color_type>
	colors(numOfVertices, color_traits<default_color_type>::white());
	depth_first_visit
	(g, entry,
	make_dfs_visitor
	(make_pair(record_predecessors(parentMap, on_tree_edge()),
	detail::stamp_times_with_vertex_vector
	(dfnumMap, verticesByDFNum, time, on_discover_vertex()))),
	make_iterator_property_map(colors.begin(), indexMap));

	// 2. Run main algorithm.
	lengauer_tarjan_dominator_tree_without_dfs(g, entry, indexMap, dfnumMap,
	parentMap, verticesByDFNum,
	domTreePredMap);
	}

	/**
	* Use vertex_index as IndexMap and make dfnumMap, parentMap, verticesByDFNum
	* internally.
	* If we don't need the result of dfs (dfnumMap, parentMap, verticesByDFNum),
	* this function would be more convenient one.
	*/
	template<class Graph, class DomTreePredMap>
	void
	lengauer_tarjan_dominator_tree
	(const Graph& g,
	const typename graph_traits<Graph>::vertex_descriptor& entry,
	DomTreePredMap domTreePredMap)
	{
	// typedefs
	typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
	typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;
	typedef typename property_map<Graph, vertex_index_t>::const_type IndexMap;
	typedef
	iterator_property_map<typename std::vector<VerticesSizeType>::iterator,
	IndexMap> TimeMap;
	typedef
	iterator_property_map<typename std::vector<Vertex>::iterator, IndexMap>
	PredMap;

	// Make property maps
	const VerticesSizeType numOfVertices = num_vertices(g);
	if (numOfVertices == 0) return;

	const IndexMap indexMap = get(vertex_index, g);

	std::vector<VerticesSizeType> dfnum(numOfVertices, 0);
	TimeMap dfnumMap(make_iterator_property_map(dfnum.begin(), indexMap));

	std::vector<Vertex> parent(numOfVertices,
	graph_traits<Graph>::null_vertex());
	PredMap parentMap(make_iterator_property_map(parent.begin(), indexMap));

	std::vector<Vertex> verticesByDFNum(parent);

	// Run main algorithm
	lengauer_tarjan_dominator_tree(g, entry,
	indexMap, dfnumMap, parentMap,
	verticesByDFNum, domTreePredMap);
	}

	/**
	* Muchnick. p. 182, 184
	*
	* using iterative bit vector analysis
	*/
	template<class Graph, class IndexMap, class DomTreePredMap>
	void
	iterative_bit_vector_dominator_tree
	(const Graph& g,
	const typename graph_traits<Graph>::vertex_descriptor& entry,
	const IndexMap& indexMap,
	DomTreePredMap domTreePredMap)
	{
	typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
	typedef typename graph_traits<Graph>::vertex_iterator vertexItr;
	typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;
	typedef
	iterator_property_map<typename std::vector< std::set<Vertex> >::iterator,
	IndexMap> vertexSetMap;

	function_requires<BidirectionalGraphConcept<Graph> >();

	// 1. Finding dominator
	// 1.1. Initialize
	const VerticesSizeType numOfVertices = num_vertices(g);
	if (numOfVertices == 0) return;

	vertexItr vi, viend;
	boost::tie(vi, viend) = vertices(g);
	const std::set<Vertex> N(vi, viend);

	bool change = true;

	std::vector< std::set<Vertex> > dom(numOfVertices, N);
	vertexSetMap domMap(make_iterator_property_map(dom.begin(), indexMap));
	get(domMap, entry).clear();
	get(domMap, entry).insert(entry);

	while (change)
	{
	change = false;
	for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi)
	{
	if (*vi == entry) continue;

	std::set<Vertex> T(N);

	typename graph_traits<Graph>::in_edge_iterator inItr, inEnd;
	for (boost::tie(inItr, inEnd) = in_edges(*vi, g); inItr != inEnd; ++inItr)
	{
	const Vertex p = source(*inItr, g);

	std::set<Vertex> tempSet;
	std::set_intersection(T.begin(), T.end(),
	get(domMap, p).begin(),
	get(domMap, p).end(),
	std::inserter(tempSet, tempSet.begin()));
	T.swap(tempSet);
	}

	T.insert(*vi);
	if (T != get(domMap, *vi))
	{
	change = true;
	get(domMap, *vi).swap(T);
	}
	} // end of for (boost::tie(vi, viend) = vertices(g)
	} // end of while(change)

	// 2. Build dominator tree
	for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi)
	get(domMap, vi).erase(vi);

	Graph domTree(numOfVertices);

	for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi)
	{
	if (*vi == entry) continue;

	// We have to iterate through copied dominator set
	const std::set<Vertex> tempSet(get(domMap, *vi));
	typename std::set<Vertex>::const_iterator s;
	for (s = tempSet.begin(); s != tempSet.end(); ++s)
	{
	typename std::set<Vertex>::iterator t;
	for (t = get(domMap, vi).begin(); t != get(domMap, vi).end(); )
	{
	typename std::set<Vertex>::iterator old_t = t;
	++t; // Done early because t may become invalid
	if (old_t == s) continue;
	if (get(domMap, s).find(old_t) != get(domMap, *s).end())
	get(domMap, *vi).erase(old_t);
	}
	}
	}

	for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi)
	{
	if (vi != entry && get(domMap, vi).size() == 1)
	{
	Vertex temp = get(domMap, vi).begin();
	put(domTreePredMap, *vi, temp);
	}
	}
	}

	template<class Graph, class DomTreePredMap>
	void
	iterative_bit_vector_dominator_tree
	(const Graph& g,
	const typename graph_traits<Graph>::vertex_descriptor& entry,
	DomTreePredMap domTreePredMap)
	{
	typename property_map<Graph, vertex_index_t>::const_type
	indexMap = get(vertex_index, g);

	iterative_bit_vector_dominator_tree(g, entry, indexMap, domTreePredMap);
	}
	} // namespace boost

	#endif // BOOST_GRAPH_DOMINATOR_HPP