x
Yes
No
Do you want to visit DriveHQ English website?
Inicio
Características
Precios
Prueba gratuita
Software cliente
Acerca de nosotros
Servidor de archivos
|
Solución de copias de seguridad
|
Servidor FTP
|
Servidor de correo electrónico
|
Alojamiento web
|
Software cliente
Servidor de archivos
Solución de copia de seguridad
Servidor FTP
Servidor de correo electrónico
Alojamiento web
Software cliente
dominator_tree.hpp - Hosted on DriveHQ Cloud IT Platform
Arriba
Subir
Descargar
Compartir
Publicar
Nueva carpeta
Nuevo archivo
Copiar
Cortar
Eliminar
Pegar
Clasificación
Actualizar
Ruta de la carpeta: \\game3dprogramming\materials\GameFactory\GameFactoryDemo\references\boost_1_35_0\boost\graph\dominator_tree.hpp
Girar
Efecto
Propiedad
Historial
//======================================================================= // Copyright (C) 2005 Jong Soo Park
// // 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
#include
#include
#include
namespace boost { namespace detail { /** * An extended time_stamper which also records vertices for each dfs number */ template
class time_stamper_with_vertex_vector : public base_visitor< time_stamper_with_vertex_vector
> { public : typedef Tag event_filter; time_stamper_with_vertex_vector(TimeMap timeMap, VertexVector& v, TimeT& t) : timeStamper_(timeMap, t), v_(v) { } template
void operator()(const typename property_traits
::key_type& v, const Graph& g) { timeStamper_(v, g); v_[timeStamper_.m_time] = v; } private : time_stamper
timeStamper_; VertexVector& v_; }; /** * A convenient way to create a time_stamper_with_vertex_vector */ template
time_stamper_with_vertex_vector
stamp_times_with_vertex_vector(TimeMap timeMap, VertexVector& v, TimeT& t, Tag) { return time_stamper_with_vertex_vector
(timeMap, v, t); } template
class dominator_visitor { typedef typename graph_traits
::vertex_descriptor Vertex; typedef typename graph_traits
::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
::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
::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
::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
::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
semi_, ancestor_, samedom_, best_; PredMap semiMap_, ancestorMap_, bestMap_; std::vector< std::deque
> buckets_; iterator_property_map
>::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
::null_vertex in parentMap. * @pre Unreachable nodes must be masked as * (std::numeric_limits
::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
void lengauer_tarjan_dominator_tree_without_dfs (const Graph& g, const typename graph_traits
::vertex_descriptor& entry, const IndexMap& indexMap, TimeMap dfnumMap, PredMap parentMap, VertexVector& verticesByDFNum, DomTreePredMap domTreePredMap) { // Typedefs and concept check typedef typename graph_traits
::vertex_descriptor Vertex; typedef typename graph_traits
::vertices_size_type VerticesSizeType; function_requires< BidirectionalGraphConcept
>(); const VerticesSizeType numOfVertices = num_vertices(g); if (numOfVertices == 0) return; // 1. Visit each vertex in reverse post order and calculate sdom. detail::dominator_visitor
visitor(g, entry, domTreePredMap); VerticesSizeType i; for (i = 0; i < numOfVertices; ++i) { const Vertex u(verticesByDFNum[numOfVertices - 1 - i]); if (u != graph_traits
::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
::null_vertex()) continue; Vertex u = get(visitor.samedomMap, n); if (u != graph_traits
::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
void lengauer_tarjan_dominator_tree (const Graph& g, const typename graph_traits
::vertex_descriptor& entry, const IndexMap& indexMap, TimeMap dfnumMap, PredMap parentMap, VertexVector& verticesByDFNum, DomTreePredMap domTreePredMap) { // Typedefs and concept check typedef typename graph_traits
::vertices_size_type VerticesSizeType; function_requires< BidirectionalGraphConcept
>(); // 1. Depth first visit const VerticesSizeType numOfVertices = num_vertices(g); if (numOfVertices == 0) return; VerticesSizeType time = (std::numeric_limits
::max)(); std::vector
colors(numOfVertices, color_traits
::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
void lengauer_tarjan_dominator_tree (const Graph& g, const typename graph_traits
::vertex_descriptor& entry, DomTreePredMap domTreePredMap) { // typedefs typedef typename graph_traits
::vertex_descriptor Vertex; typedef typename graph_traits
::vertices_size_type VerticesSizeType; typedef typename property_map
::const_type IndexMap; typedef iterator_property_map
::iterator, IndexMap> TimeMap; typedef iterator_property_map
::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
dfnum(numOfVertices, 0); TimeMap dfnumMap(make_iterator_property_map(dfnum.begin(), indexMap)); std::vector
parent(numOfVertices, graph_traits
::null_vertex()); PredMap parentMap(make_iterator_property_map(parent.begin(), indexMap)); std::vector
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
void iterative_bit_vector_dominator_tree (const Graph& g, const typename graph_traits
::vertex_descriptor& entry, const IndexMap& indexMap, DomTreePredMap domTreePredMap) { typedef typename graph_traits
::vertex_descriptor Vertex; typedef typename graph_traits
::vertex_iterator vertexItr; typedef typename graph_traits
::vertices_size_type VerticesSizeType; typedef iterator_property_map
>::iterator, IndexMap> vertexSetMap; function_requires
>(); // 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
N(vi, viend); bool change = true; std::vector< std::set
> 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
T(N); typename graph_traits
::in_edge_iterator inItr, inEnd; for (tie(inItr, inEnd) = in_edges(*vi, g); inItr != inEnd; ++inItr) { const Vertex p = source(*inItr, g); std::set
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
tempSet(get(domMap, *vi)); typename std::set
::const_iterator s; for (s = tempSet.begin(); s != tempSet.end(); ++s) { typename std::set
::iterator t; for (t = get(domMap, *vi).begin(); t != get(domMap, *vi).end(); ) { typename std::set
::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
void iterative_bit_vector_dominator_tree (const Graph& g, const typename graph_traits
::vertex_descriptor& entry, DomTreePredMap domTreePredMap) { typename property_map
::const_type indexMap = get(vertex_index, g); iterative_bit_vector_dominator_tree(g, entry, indexMap, domTreePredMap); } } // namespace boost #endif // BOOST_GRAPH_DOMINATOR_HPP
dominator_tree.hpp
Dirección de la página
Dirección del archivo
Anterior
24/95
Siguiente
Descargar
( 17 KB )
Comments
Total ratings:
0
Average rating:
No clasificado
of 10
Would you like to comment?
Join now
, or
Logon
if you are already a member.