Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r52506 - trunk/boost/graph
From: asutton_at_[hidden]
Date: 2009-04-20 09:43:44


Author: asutton
Date: 2009-04-20 09:43:43 EDT (Mon, 20 Apr 2009)
New Revision: 52506
URL: http://svn.boost.org/trac/boost/changeset/52506

Log:
Applied performance patch from Jongsoo Park.

Text files modified:
   trunk/boost/graph/dominator_tree.hpp | 73 ++++++++++++++++++++-------------------
   1 files changed, 38 insertions(+), 35 deletions(-)

Modified: trunk/boost/graph/dominator_tree.hpp
==============================================================================
--- trunk/boost/graph/dominator_tree.hpp (original)
+++ trunk/boost/graph/dominator_tree.hpp 2009-04-20 09:43:43 EDT (Mon, 20 Apr 2009)
@@ -1,19 +1,21 @@
 //=======================================================================
-// Copyright (C) 2005 Jong Soo Park <jongsoo.park -at- gmail.com>
+// 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)
 //=======================================================================
-// Dominator tree computation
+
 #ifndef BOOST_GRAPH_DOMINATOR_HPP
 #define BOOST_GRAPH_DOMINATOR_HPP
 
-#include <boost/config.hpp>
 #include <deque>
 #include <set>
+#include <boost/config.hpp>
 #include <boost/graph/depth_first_search.hpp>
 
+// Dominator tree computation
+
 namespace boost {
   namespace detail {
     /**
@@ -26,13 +28,13 @@
     {
     public :
       typedef Tag event_filter;
- time_stamper_with_vertex_vector(TimeMap timeMap, VertexVector& v,
+ 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,
+ void
+ operator()(const typename property_traits<TimeMap>::key_type& v,
                  const Graph& g)
       {
         timeStamper_(v, g);
@@ -52,7 +54,7 @@
     stamp_times_with_vertex_vector(TimeMap timeMap, VertexVector& v, TimeT& t,
                                    Tag)
     {
- return time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT,
+ return time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT,
                                              Tag>(timeMap, v, t);
     }
 
@@ -76,29 +78,29 @@
           ancestor_(num_vertices(g), graph_traits<Graph>::null_vertex()),
           samedom_(ancestor_),
           best_(semi_),
- semiMap_(make_iterator_property_map(semi_.begin(),
+ semiMap_(make_iterator_property_map(semi_.begin(),
                                               get(vertex_index, g))),
- ancestorMap_(make_iterator_property_map(ancestor_.begin(),
+ ancestorMap_(make_iterator_property_map(ancestor_.begin(),
                                                   get(vertex_index, g))),
- bestMap_(make_iterator_property_map(best_.begin(),
+ bestMap_(make_iterator_property_map(best_.begin(),
                                               get(vertex_index, g))),
           buckets_(num_vertices(g)),
- bucketMap_(make_iterator_property_map(buckets_.begin(),
+ bucketMap_(make_iterator_property_map(buckets_.begin(),
                                                 get(vertex_index, g))),
           entry_(entry),
           domTreePredMap_(domTreePredMap),
- samedomMap(make_iterator_property_map(samedom_.begin(),
+ numOfVertices_(num_vertices(g)),
+ samedomMap(make_iterator_property_map(samedom_.begin(),
                                                 get(vertex_index, g)))
       {
       }
-
- void
- operator()(const Vertex& n, const TimeMap& dfnumMap,
+
+ 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);
 
@@ -113,14 +115,14 @@
         // 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)
+ if (get(dfnumMap, v) < 0 || get(dfnumMap, v) >= numOfVertices_)
               continue;
 
             Vertex s2;
@@ -147,7 +149,7 @@
         // * 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;
@@ -171,7 +173,7 @@
       /**
        * Evaluate function in Tarjan's path compression
        */
- const Vertex
+ const Vertex
       ancestor_with_lowest_semi_(const Vertex& v, const TimeMap& dfnumMap)
       {
         const Vertex a(get(ancestorMap_, v));
@@ -199,9 +201,10 @@
 
       const Vertex& entry_;
       DomTreePredMap domTreePredMap_;
+ const VerticesSizeType numOfVertices_;
 
     public :
-
+
       PredMap samedomMap;
     };
 
@@ -219,7 +222,7 @@
    * 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)
    *
@@ -227,7 +230,7 @@
    *
    * @todo : Optimization in Finding Dominators in Practice, Loukas Georgiadis
    */
- template<class Graph, class IndexMap, class TimeMap, class PredMap,
+ template<class Graph, class IndexMap, class TimeMap, class PredMap,
            class VertexVector, class DomTreePredMap>
   void
   lengauer_tarjan_dominator_tree_without_dfs
@@ -274,7 +277,7 @@
           }
       }
   }
-
+
   /**
    * Unlike lengauer_tarjan_dominator_tree_without_dfs,
    * dfs is run in this function and
@@ -283,7 +286,7 @@
    * 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,
+ template<class Graph, class IndexMap, class TimeMap, class PredMap,
            class VertexVector, class DomTreePredMap>
   void
   lengauer_tarjan_dominator_tree
@@ -304,7 +307,7 @@
 
     VerticesSizeType time =
       (std::numeric_limits<VerticesSizeType>::max)();
- std::vector<default_color_type>
+ std::vector<default_color_type>
       colors(numOfVertices, color_traits<default_color_type>::white());
     depth_first_visit
       (g, entry,
@@ -315,8 +318,8 @@
        make_iterator_property_map(colors.begin(), indexMap));
 
     // 2. Run main algorithm.
- lengauer_tarjan_dominator_tree_without_dfs(g, entry, indexMap, dfnumMap,
- parentMap, verticesByDFNum,
+ lengauer_tarjan_dominator_tree_without_dfs(g, entry, indexMap, dfnumMap,
+ parentMap, verticesByDFNum,
                                                domTreePredMap);
   }
 
@@ -353,7 +356,7 @@
     std::vector<VerticesSizeType> dfnum(numOfVertices, 0);
     TimeMap dfnumMap(make_iterator_property_map(dfnum.begin(), indexMap));
 
- std::vector<Vertex> parent(numOfVertices,
+ std::vector<Vertex> parent(numOfVertices,
                                graph_traits<Graph>::null_vertex());
     PredMap parentMap(make_iterator_property_map(parent.begin(), indexMap));
 
@@ -361,7 +364,7 @@
 
     // Run main algorithm
     lengauer_tarjan_dominator_tree(g, entry,
- indexMap, dfnumMap, parentMap,
+ indexMap, dfnumMap, parentMap,
                                    verticesByDFNum, domTreePredMap);
   }
 
@@ -397,7 +400,7 @@
     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();
@@ -411,15 +414,15 @@
             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(),
+ std::set_intersection(T.begin(), T.end(),
+ get(domMap, p).begin(),
                                       get(domMap, p).end(),
                                       std::inserter(tempSet, tempSet.begin()));
                 T.swap(tempSet);
@@ -480,7 +483,7 @@
   {
     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


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk