williamr@2: //=======================================================================
williamr@2: // Copyright (C) 2005 Jong Soo Park <jongsoo.park -at- gmail.com>
williamr@2: //
williamr@2: // Distributed under the Boost Software License, Version 1.0.
williamr@2: // (See accompanying file LICENSE_1_0.txt or copy at
williamr@2: // http://www.boost.org/LICENSE_1_0.txt)
williamr@2: //=======================================================================
williamr@2: // Dominator tree computation
williamr@2: #ifndef BOOST_GRAPH_DOMINATOR_HPP
williamr@2: #define BOOST_GRAPH_DOMINATOR_HPP
williamr@2: 
williamr@2: #include <boost/config.hpp>
williamr@2: #include <deque>
williamr@2: #include <set>
williamr@2: #include <boost/graph/depth_first_search.hpp>
williamr@2: 
williamr@2: namespace boost {
williamr@2:   namespace detail {
williamr@2:     /**
williamr@2:      * An extended time_stamper which also records vertices for each dfs number
williamr@2:      */
williamr@2:     template<class TimeMap, class VertexVector, class TimeT, class Tag>
williamr@2:     class time_stamper_with_vertex_vector
williamr@2:       : public base_visitor<
williamr@2:       time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT, Tag> >
williamr@2:     {
williamr@2:     public :
williamr@2:       typedef Tag event_filter;
williamr@2:       time_stamper_with_vertex_vector(TimeMap timeMap, VertexVector& v, 
williamr@2:                                       TimeT& t)
williamr@2:         : timeStamper_(timeMap, t), v_(v) { }
williamr@2: 
williamr@2:       template<class Graph>
williamr@2:       void 
williamr@2:       operator()(const typename property_traits<TimeMap>::key_type& v, 
williamr@2:                  const Graph& g)
williamr@2:       {
williamr@2:         timeStamper_(v, g);
williamr@2:         v_[timeStamper_.m_time] = v;
williamr@2:       }
williamr@2: 
williamr@2:     private :
williamr@2:       time_stamper<TimeMap, TimeT, Tag> timeStamper_;
williamr@2:       VertexVector& v_;
williamr@2:     };
williamr@2: 
williamr@2:     /**
williamr@2:      * A convenient way to create a time_stamper_with_vertex_vector
williamr@2:      */
williamr@2:     template<class TimeMap, class VertexVector, class TimeT, class Tag>
williamr@2:     time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT, Tag>
williamr@2:     stamp_times_with_vertex_vector(TimeMap timeMap, VertexVector& v, TimeT& t,
williamr@2:                                    Tag)
williamr@2:     {
williamr@2:       return time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT, 
williamr@2:                                              Tag>(timeMap, v, t);
williamr@2:     }
williamr@2: 
williamr@2:     template<class Graph, class IndexMap, class TimeMap, class PredMap,
williamr@2:              class DomTreePredMap>
williamr@2:     class dominator_visitor
williamr@2:     {
williamr@2:       typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
williamr@2:       typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;
williamr@2: 
williamr@2:     public :
williamr@2:       /**
williamr@2:        * @param g [in] the target graph of the dominator tree
williamr@2:        * @param entry [in] the entry node of g
williamr@2:        * @param domTreePredMap [out] the immediate dominator map
williamr@2:        *                             (parent map in dominator tree)
williamr@2:        */
williamr@2:       dominator_visitor(const Graph& g, const Vertex& entry,
williamr@2:                         DomTreePredMap domTreePredMap)
williamr@2:         : semi_(num_vertices(g)),
williamr@2:           ancestor_(num_vertices(g), graph_traits<Graph>::null_vertex()),
williamr@2:           samedom_(ancestor_),
williamr@2:           best_(semi_),
williamr@2:           semiMap_(make_iterator_property_map(semi_.begin(), 
williamr@2:                                               get(vertex_index, g))),
williamr@2:           ancestorMap_(make_iterator_property_map(ancestor_.begin(), 
williamr@2:                                                   get(vertex_index, g))),
williamr@2:           bestMap_(make_iterator_property_map(best_.begin(), 
williamr@2:                                               get(vertex_index, g))),
williamr@2:           buckets_(num_vertices(g)),
williamr@2:           bucketMap_(make_iterator_property_map(buckets_.begin(), 
williamr@2:                                                 get(vertex_index, g))),
williamr@2:           entry_(entry),
williamr@2:           domTreePredMap_(domTreePredMap),
williamr@2:           samedomMap(make_iterator_property_map(samedom_.begin(), 
williamr@2:                                                 get(vertex_index, g)))
williamr@2:       {
williamr@2:       }
williamr@2:                 
williamr@2:       void 
williamr@2:       operator()(const Vertex& n, const TimeMap& dfnumMap, 
williamr@2:                  const PredMap& parentMap, const Graph& g)
williamr@2:       {
williamr@2:         if (n == entry_) return;
williamr@2: 
williamr@2:         const VerticesSizeType numOfVertices = num_vertices(g);
williamr@2:         const Vertex p(get(parentMap, n));
williamr@2:         Vertex s(p);
williamr@2: 
williamr@2:         // 1. Calculate the semidominator of n,
williamr@2:         // based on the semidominator thm.
williamr@2:         // * Semidominator thm. : To find the semidominator of a node n,
williamr@2:         //   consider all predecessors v of n in the CFG (Control Flow Graph).
williamr@2:         //  - If v is a proper ancestor of n in the spanning tree
williamr@2:         //    (so dfnum(v) < dfnum(n)), then v is a candidate for semi(n)
williamr@2:         //  - If v is a non-ancestor of n (so dfnum(v) > dfnum(n))
williamr@2:         //    then for each u that is an ancestor of v (or u = v),
williamr@2:         //    Let semi(u) be a candidate for semi(n)
williamr@2:         //   of all these candidates, the one with lowest dfnum is
williamr@2:         //   the semidominator of n.
williamr@2:                                 
williamr@2:         // For each predecessor of n
williamr@2:         typename graph_traits<Graph>::in_edge_iterator inItr, inEnd;
williamr@2:         for (tie(inItr, inEnd) = in_edges(n, g); inItr != inEnd; ++inItr)
williamr@2:           {
williamr@2:             const Vertex v = source(*inItr, g);
williamr@2:             // To deal with unreachable nodes
williamr@2:             if (get(dfnumMap, v) < 0 || get(dfnumMap, v) >= numOfVertices)
williamr@2:               continue;
williamr@2: 
williamr@2:             Vertex s2;
williamr@2:             if (get(dfnumMap, v) <= get(dfnumMap, n))
williamr@2:               s2 = v;
williamr@2:             else
williamr@2:               s2 = get(semiMap_, ancestor_with_lowest_semi_(v, dfnumMap));
williamr@2: 
williamr@2:             if (get(dfnumMap, s2) < get(dfnumMap, s))
williamr@2:               s = s2;
williamr@2:           }
williamr@2:         put(semiMap_, n, s);
williamr@2: 
williamr@2:         // 2. Calculation of n's dominator is deferred until
williamr@2:         // the path from s to n has been linked into the forest
williamr@2:         get(bucketMap_, s).push_back(n);
williamr@2:         get(ancestorMap_, n) = p;
williamr@2:         get(bestMap_, n) = n;
williamr@2: 
williamr@2:         // 3. Now that the path from p to v has been linked into
williamr@2:         // the spanning forest, these lines calculate the dominator of v,
williamr@2:         // based on the dominator thm., or else defer the calculation
williamr@2:         // until y's dominator is known
williamr@2:         // * Dominator thm. : On the spanning-tree path below semi(n) and
williamr@2:         //   above or including n, let y be the node
williamr@2:         //   with the smallest-numbered semidominator. Then,
williamr@2:         //      
williamr@2:         //  idom(n) = semi(n) if semi(y)=semi(n) or
williamr@2:         //            idom(y) if semi(y) != semi(n)
williamr@2:         typename std::deque<Vertex>::iterator buckItr;
williamr@2:         for (buckItr = get(bucketMap_, p).begin();
williamr@2:              buckItr != get(bucketMap_, p).end();
williamr@2:              ++buckItr)
williamr@2:           {
williamr@2:             const Vertex v(*buckItr);
williamr@2:             const Vertex y(ancestor_with_lowest_semi_(v, dfnumMap));
williamr@2:             if (get(semiMap_, y) == get(semiMap_, v))
williamr@2:               put(domTreePredMap_, v, p);
williamr@2:             else
williamr@2:               put(samedomMap, v, y);
williamr@2:           }
williamr@2: 
williamr@2:         get(bucketMap_, p).clear();
williamr@2:       }
williamr@2: 
williamr@2:     protected :
williamr@2: 
williamr@2:       /**
williamr@2:        * Evaluate function in Tarjan's path compression
williamr@2:        */
williamr@2:       const Vertex 
williamr@2:       ancestor_with_lowest_semi_(const Vertex& v, const TimeMap& dfnumMap)
williamr@2:       {
williamr@2:         const Vertex a(get(ancestorMap_, v));
williamr@2: 
williamr@2:         if (get(ancestorMap_, a) != graph_traits<Graph>::null_vertex())
williamr@2:           {
williamr@2:             const Vertex b(ancestor_with_lowest_semi_(a, dfnumMap));
williamr@2: 
williamr@2:             put(ancestorMap_, v, get(ancestorMap_, a));
williamr@2: 
williamr@2:             if (get(dfnumMap, get(semiMap_, b)) <
williamr@2:                 get(dfnumMap, get(semiMap_, get(bestMap_, v))))
williamr@2:               put(bestMap_, v, b);
williamr@2:           }
williamr@2: 
williamr@2:         return get(bestMap_, v);
williamr@2:       }
williamr@2: 
williamr@2:       std::vector<Vertex> semi_, ancestor_, samedom_, best_;
williamr@2:       PredMap semiMap_, ancestorMap_, bestMap_;
williamr@2:       std::vector< std::deque<Vertex> > buckets_;
williamr@2: 
williamr@2:       iterator_property_map<typename std::vector<std::deque<Vertex> >::iterator,
williamr@2:                             IndexMap> bucketMap_;
williamr@2: 
williamr@2:       const Vertex& entry_;
williamr@2:       DomTreePredMap domTreePredMap_;
williamr@2: 
williamr@2:     public :
williamr@2:                         
williamr@2:       PredMap samedomMap;
williamr@2:     };
williamr@2: 
williamr@2:   } // namespace detail
williamr@2: 
williamr@2:   /**
williamr@2:    * @brief Build dominator tree using Lengauer-Tarjan algorithm.
williamr@2:    *                It takes O((V+E)log(V+E)) time.
williamr@2:    *
williamr@2:    * @pre dfnumMap, parentMap and verticesByDFNum have dfs results corresponding
williamr@2:    *      indexMap.
williamr@2:    *      If dfs has already run before,
williamr@2:    *      this function would be good for saving computations.
williamr@2:    * @pre Unreachable nodes must be masked as
williamr@2:    *      graph_traits<Graph>::null_vertex in parentMap.
williamr@2:    * @pre Unreachable nodes must be masked as
williamr@2:    *      (std::numeric_limits<VerticesSizeType>::max)() in dfnumMap.
williamr@2:    * 
williamr@2:    * @param domTreePredMap [out] : immediate dominator map (parent map
williamr@2:    * in dom. tree)
williamr@2:    *
williamr@2:    * @note reference Appel. p. 452~453. algorithm 19.9, 19.10.
williamr@2:    *
williamr@2:    * @todo : Optimization in Finding Dominators in Practice, Loukas Georgiadis
williamr@2:    */
williamr@2:   template<class Graph, class IndexMap, class TimeMap, class PredMap, 
williamr@2:            class VertexVector, class DomTreePredMap>
williamr@2:   void
williamr@2:   lengauer_tarjan_dominator_tree_without_dfs
williamr@2:     (const Graph& g,
williamr@2:      const typename graph_traits<Graph>::vertex_descriptor& entry,
williamr@2:      const IndexMap& indexMap,
williamr@2:      TimeMap dfnumMap, PredMap parentMap, VertexVector& verticesByDFNum,
williamr@2:      DomTreePredMap domTreePredMap)
williamr@2:   {
williamr@2:     // Typedefs and concept check
williamr@2:     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
williamr@2:     typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;
williamr@2: 
williamr@2:     function_requires< BidirectionalGraphConcept<Graph> >();
williamr@2: 
williamr@2:     const VerticesSizeType numOfVertices = num_vertices(g);
williamr@2:     if (numOfVertices == 0) return;
williamr@2: 
williamr@2:     // 1. Visit each vertex in reverse post order and calculate sdom.
williamr@2:     detail::dominator_visitor<Graph, IndexMap, TimeMap, PredMap, DomTreePredMap>
williamr@2:       visitor(g, entry, domTreePredMap);
williamr@2: 
williamr@2:     VerticesSizeType i;
williamr@2:     for (i = 0; i < numOfVertices; ++i)
williamr@2:       {
williamr@2:         const Vertex u(verticesByDFNum[numOfVertices - 1 - i]);
williamr@2:         if (u != graph_traits<Graph>::null_vertex())
williamr@2:           visitor(u, dfnumMap, parentMap, g);
williamr@2:       }
williamr@2: 
williamr@2:     // 2. Now all the deferred dominator calculations,
williamr@2:     // based on the second clause of the dominator thm., are performed
williamr@2:     for (i = 0; i < numOfVertices; ++i)
williamr@2:       {
williamr@2:         const Vertex n(verticesByDFNum[i]);
williamr@2: 
williamr@2:         if (n == entry || n == graph_traits<Graph>::null_vertex())
williamr@2:           continue;
williamr@2: 
williamr@2:         Vertex u = get(visitor.samedomMap, n);
williamr@2:         if (u != graph_traits<Graph>::null_vertex())
williamr@2:           {
williamr@2:             put(domTreePredMap, n, get(domTreePredMap, u));
williamr@2:           }
williamr@2:       }
williamr@2:   }
williamr@2:   
williamr@2:   /**
williamr@2:    * Unlike lengauer_tarjan_dominator_tree_without_dfs,
williamr@2:    * dfs is run in this function and
williamr@2:    * the result is written to dfnumMap, parentMap, vertices.
williamr@2:    *
williamr@2:    * If the result of dfs required after this algorithm,
williamr@2:    * this function can eliminate the need of rerunning dfs.
williamr@2:    */
williamr@2:   template<class Graph, class IndexMap, class TimeMap, class PredMap, 
williamr@2:            class VertexVector, class DomTreePredMap>
williamr@2:   void
williamr@2:   lengauer_tarjan_dominator_tree
williamr@2:     (const Graph& g,
williamr@2:      const typename graph_traits<Graph>::vertex_descriptor& entry,
williamr@2:      const IndexMap& indexMap,
williamr@2:      TimeMap dfnumMap, PredMap parentMap, VertexVector& verticesByDFNum,
williamr@2:      DomTreePredMap domTreePredMap)
williamr@2:   {
williamr@2:     // Typedefs and concept check
williamr@2:     typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;
williamr@2: 
williamr@2:     function_requires< BidirectionalGraphConcept<Graph> >();
williamr@2: 
williamr@2:     // 1. Depth first visit
williamr@2:     const VerticesSizeType numOfVertices = num_vertices(g);
williamr@2:     if (numOfVertices == 0) return;
williamr@2: 
williamr@2:     VerticesSizeType time =
williamr@2:       (std::numeric_limits<VerticesSizeType>::max)();
williamr@2:     std::vector<default_color_type> 
williamr@2:       colors(numOfVertices, color_traits<default_color_type>::white());
williamr@2:     depth_first_visit
williamr@2:       (g, entry,
williamr@2:        make_dfs_visitor
williamr@2:          (make_pair(record_predecessors(parentMap, on_tree_edge()),
williamr@2:                     detail::stamp_times_with_vertex_vector
williamr@2:                       (dfnumMap, verticesByDFNum, time, on_discover_vertex()))),
williamr@2:        make_iterator_property_map(colors.begin(), indexMap));
williamr@2: 
williamr@2:     // 2. Run main algorithm.
williamr@2:     lengauer_tarjan_dominator_tree_without_dfs(g, entry, indexMap, dfnumMap, 
williamr@2:                                                parentMap, verticesByDFNum, 
williamr@2:                                                domTreePredMap);
williamr@2:   }
williamr@2: 
williamr@2:   /**
williamr@2:    * Use vertex_index as IndexMap and make dfnumMap, parentMap, verticesByDFNum
williamr@2:    * internally.
williamr@2:    * If we don't need the result of dfs (dfnumMap, parentMap, verticesByDFNum),
williamr@2:    * this function would be more convenient one.
williamr@2:    */
williamr@2:   template<class Graph, class DomTreePredMap>
williamr@2:   void
williamr@2:   lengauer_tarjan_dominator_tree
williamr@2:     (const Graph& g,
williamr@2:      const typename graph_traits<Graph>::vertex_descriptor& entry,
williamr@2:      DomTreePredMap domTreePredMap)
williamr@2:   {
williamr@2:     // typedefs
williamr@2:     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
williamr@2:     typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;
williamr@2:     typedef typename property_map<Graph, vertex_index_t>::const_type IndexMap;
williamr@2:     typedef
williamr@2:       iterator_property_map<typename std::vector<VerticesSizeType>::iterator,
williamr@2:                             IndexMap> TimeMap;
williamr@2:     typedef
williamr@2:       iterator_property_map<typename std::vector<Vertex>::iterator, IndexMap>
williamr@2:       PredMap;
williamr@2: 
williamr@2:     // Make property maps
williamr@2:     const VerticesSizeType numOfVertices = num_vertices(g);
williamr@2:     if (numOfVertices == 0) return;
williamr@2: 
williamr@2:     const IndexMap indexMap = get(vertex_index, g);
williamr@2: 
williamr@2:     std::vector<VerticesSizeType> dfnum(numOfVertices, 0);
williamr@2:     TimeMap dfnumMap(make_iterator_property_map(dfnum.begin(), indexMap));
williamr@2: 
williamr@2:     std::vector<Vertex> parent(numOfVertices, 
williamr@2:                                graph_traits<Graph>::null_vertex());
williamr@2:     PredMap parentMap(make_iterator_property_map(parent.begin(), indexMap));
williamr@2: 
williamr@2:     std::vector<Vertex> verticesByDFNum(parent);
williamr@2: 
williamr@2:     // Run main algorithm
williamr@2:     lengauer_tarjan_dominator_tree(g, entry,
williamr@2:                                    indexMap, dfnumMap, parentMap, 
williamr@2:                                    verticesByDFNum, domTreePredMap);
williamr@2:   }
williamr@2: 
williamr@2:   /**
williamr@2:    * Muchnick. p. 182, 184
williamr@2:    *
williamr@2:    * using iterative bit vector analysis
williamr@2:    */
williamr@2:   template<class Graph, class IndexMap, class DomTreePredMap>
williamr@2:   void
williamr@2:   iterative_bit_vector_dominator_tree
williamr@2:     (const Graph& g,
williamr@2:      const typename graph_traits<Graph>::vertex_descriptor& entry,
williamr@2:      const IndexMap& indexMap,
williamr@2:      DomTreePredMap domTreePredMap)
williamr@2:   {
williamr@2:     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
williamr@2:     typedef typename graph_traits<Graph>::vertex_iterator vertexItr;
williamr@2:     typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;
williamr@2:     typedef
williamr@2:       iterator_property_map<typename std::vector< std::set<Vertex> >::iterator,
williamr@2:                             IndexMap> vertexSetMap;
williamr@2: 
williamr@2:     function_requires<BidirectionalGraphConcept<Graph> >();
williamr@2: 
williamr@2:     // 1. Finding dominator
williamr@2:     // 1.1. Initialize
williamr@2:     const VerticesSizeType numOfVertices = num_vertices(g);
williamr@2:     if (numOfVertices == 0) return;
williamr@2: 
williamr@2:     vertexItr vi, viend;
williamr@2:     tie(vi, viend) = vertices(g);
williamr@2:     const std::set<Vertex> N(vi, viend);
williamr@2: 
williamr@2:     bool change = true;
williamr@2:                 
williamr@2:     std::vector< std::set<Vertex> > dom(numOfVertices, N);
williamr@2:     vertexSetMap domMap(make_iterator_property_map(dom.begin(), indexMap));
williamr@2:     get(domMap, entry).clear();
williamr@2:     get(domMap, entry).insert(entry);
williamr@2: 
williamr@2:     while (change)
williamr@2:       {
williamr@2:         change = false;
williamr@2:         for (tie(vi, viend) = vertices(g); vi != viend; ++vi)
williamr@2:           {
williamr@2:             if (*vi == entry) continue;
williamr@2: 
williamr@2:             std::set<Vertex> T(N);
williamr@2:                                 
williamr@2:             typename graph_traits<Graph>::in_edge_iterator inItr, inEnd;
williamr@2:             for (tie(inItr, inEnd) = in_edges(*vi, g); inItr != inEnd; ++inItr)
williamr@2:               {
williamr@2:                 const Vertex p = source(*inItr, g);
williamr@2: 
williamr@2:                 std::set<Vertex> tempSet;
williamr@2:                 std::set_intersection(T.begin(), T.end(), 
williamr@2:                                       get(domMap, p).begin(), 
williamr@2:                                       get(domMap, p).end(),
williamr@2:                                       std::inserter(tempSet, tempSet.begin()));
williamr@2:                 T.swap(tempSet);
williamr@2:               }
williamr@2: 
williamr@2:             T.insert(*vi);
williamr@2:             if (T != get(domMap, *vi))
williamr@2:               {
williamr@2:                 change = true;
williamr@2:                 get(domMap, *vi).swap(T);
williamr@2:               }
williamr@2:           } // end of for (tie(vi, viend) = vertices(g)
williamr@2:       } // end of while(change)
williamr@2: 
williamr@2:     // 2. Build dominator tree
williamr@2:     for (tie(vi, viend) = vertices(g); vi != viend; ++vi)
williamr@2:       get(domMap, *vi).erase(*vi);
williamr@2: 
williamr@2:     Graph domTree(numOfVertices);
williamr@2: 
williamr@2:     for (tie(vi, viend) = vertices(g); vi != viend; ++vi)
williamr@2:       {
williamr@2:         if (*vi == entry) continue;
williamr@2: 
williamr@2:         // We have to iterate through copied dominator set
williamr@2:         const std::set<Vertex> tempSet(get(domMap, *vi));
williamr@2:         typename std::set<Vertex>::const_iterator s;
williamr@2:         for (s = tempSet.begin(); s != tempSet.end(); ++s)
williamr@2:           {
williamr@2:             typename std::set<Vertex>::iterator t;
williamr@2:             for (t = get(domMap, *vi).begin(); t != get(domMap, *vi).end(); )
williamr@2:               {
williamr@2:         typename std::set<Vertex>::iterator old_t = t;
williamr@2:         ++t; // Done early because t may become invalid
williamr@2:                 if (*old_t == *s) continue;
williamr@2:                 if (get(domMap, *s).find(*old_t) != get(domMap, *s).end())
williamr@2:                   get(domMap, *vi).erase(old_t);
williamr@2:               }
williamr@2:           }
williamr@2:       }
williamr@2: 
williamr@2:     for (tie(vi, viend) = vertices(g); vi != viend; ++vi)
williamr@2:       {
williamr@2:         if (*vi != entry && get(domMap, *vi).size() == 1)
williamr@2:           {
williamr@2:             Vertex temp = *get(domMap, *vi).begin();
williamr@2:             put(domTreePredMap, *vi, temp);
williamr@2:           }
williamr@2:       }
williamr@2:   }
williamr@2: 
williamr@2:   template<class Graph, class DomTreePredMap>
williamr@2:   void
williamr@2:   iterative_bit_vector_dominator_tree
williamr@2:     (const Graph& g,
williamr@2:      const typename graph_traits<Graph>::vertex_descriptor& entry,
williamr@2:      DomTreePredMap domTreePredMap)
williamr@2:   {
williamr@2:     typename property_map<Graph, vertex_index_t>::const_type
williamr@2:       indexMap = get(vertex_index, g);
williamr@2:     
williamr@2:     iterative_bit_vector_dominator_tree(g, entry, indexMap, domTreePredMap);
williamr@2:   }
williamr@2: } // namespace boost
williamr@2: 
williamr@2: #endif // BOOST_GRAPH_DOMINATOR_HPP