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