//=======================================================================

 // Copyright (C) 2005 Jong Soo 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)

 //=======================================================================

 // Dominator tree computation

 #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>

 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),

           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 VerticesSizeType numOfVertices = num_vertices(g);

         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 (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_;

     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;

     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 (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 (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 (tie(vi, viend) = vertices(g)

       } // end of while(change)

     // 2. Build dominator tree

     for (tie(vi, viend) = vertices(g); vi != viend; ++vi)

       get(domMap, *vi).erase(*vi);

     Graph domTree(numOfVertices);

     for (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 (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