epoc32/include/stdapis/boost/graph/dominator_tree.hpp
author William Roberts <williamr@symbian.org>
Tue, 16 Mar 2010 16:12:26 +0000
branchSymbian2
changeset 2 2fe1408b6811
permissions -rw-r--r--
Final list of Symbian^2 public API header files
williamr@2
     1
//=======================================================================
williamr@2
     2
// Copyright (C) 2005 Jong Soo Park <jongsoo.park -at- gmail.com>
williamr@2
     3
//
williamr@2
     4
// Distributed under the Boost Software License, Version 1.0.
williamr@2
     5
// (See accompanying file LICENSE_1_0.txt or copy at
williamr@2
     6
// http://www.boost.org/LICENSE_1_0.txt)
williamr@2
     7
//=======================================================================
williamr@2
     8
// Dominator tree computation
williamr@2
     9
#ifndef BOOST_GRAPH_DOMINATOR_HPP
williamr@2
    10
#define BOOST_GRAPH_DOMINATOR_HPP
williamr@2
    11
williamr@2
    12
#include <boost/config.hpp>
williamr@2
    13
#include <deque>
williamr@2
    14
#include <set>
williamr@2
    15
#include <boost/graph/depth_first_search.hpp>
williamr@2
    16
williamr@2
    17
namespace boost {
williamr@2
    18
  namespace detail {
williamr@2
    19
    /**
williamr@2
    20
     * An extended time_stamper which also records vertices for each dfs number
williamr@2
    21
     */
williamr@2
    22
    template<class TimeMap, class VertexVector, class TimeT, class Tag>
williamr@2
    23
    class time_stamper_with_vertex_vector
williamr@2
    24
      : public base_visitor<
williamr@2
    25
      time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT, Tag> >
williamr@2
    26
    {
williamr@2
    27
    public :
williamr@2
    28
      typedef Tag event_filter;
williamr@2
    29
      time_stamper_with_vertex_vector(TimeMap timeMap, VertexVector& v, 
williamr@2
    30
                                      TimeT& t)
williamr@2
    31
        : timeStamper_(timeMap, t), v_(v) { }
williamr@2
    32
williamr@2
    33
      template<class Graph>
williamr@2
    34
      void 
williamr@2
    35
      operator()(const typename property_traits<TimeMap>::key_type& v, 
williamr@2
    36
                 const Graph& g)
williamr@2
    37
      {
williamr@2
    38
        timeStamper_(v, g);
williamr@2
    39
        v_[timeStamper_.m_time] = v;
williamr@2
    40
      }
williamr@2
    41
williamr@2
    42
    private :
williamr@2
    43
      time_stamper<TimeMap, TimeT, Tag> timeStamper_;
williamr@2
    44
      VertexVector& v_;
williamr@2
    45
    };
williamr@2
    46
williamr@2
    47
    /**
williamr@2
    48
     * A convenient way to create a time_stamper_with_vertex_vector
williamr@2
    49
     */
williamr@2
    50
    template<class TimeMap, class VertexVector, class TimeT, class Tag>
williamr@2
    51
    time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT, Tag>
williamr@2
    52
    stamp_times_with_vertex_vector(TimeMap timeMap, VertexVector& v, TimeT& t,
williamr@2
    53
                                   Tag)
williamr@2
    54
    {
williamr@2
    55
      return time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT, 
williamr@2
    56
                                             Tag>(timeMap, v, t);
williamr@2
    57
    }
williamr@2
    58
williamr@2
    59
    template<class Graph, class IndexMap, class TimeMap, class PredMap,
williamr@2
    60
             class DomTreePredMap>
williamr@2
    61
    class dominator_visitor
williamr@2
    62
    {
williamr@2
    63
      typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
williamr@2
    64
      typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;
williamr@2
    65
williamr@2
    66
    public :
williamr@2
    67
      /**
williamr@2
    68
       * @param g [in] the target graph of the dominator tree
williamr@2
    69
       * @param entry [in] the entry node of g
williamr@2
    70
       * @param domTreePredMap [out] the immediate dominator map
williamr@2
    71
       *                             (parent map in dominator tree)
williamr@2
    72
       */
williamr@2
    73
      dominator_visitor(const Graph& g, const Vertex& entry,
williamr@2
    74
                        DomTreePredMap domTreePredMap)
williamr@2
    75
        : semi_(num_vertices(g)),
williamr@2
    76
          ancestor_(num_vertices(g), graph_traits<Graph>::null_vertex()),
williamr@2
    77
          samedom_(ancestor_),
williamr@2
    78
          best_(semi_),
williamr@2
    79
          semiMap_(make_iterator_property_map(semi_.begin(), 
williamr@2
    80
                                              get(vertex_index, g))),
williamr@2
    81
          ancestorMap_(make_iterator_property_map(ancestor_.begin(), 
williamr@2
    82
                                                  get(vertex_index, g))),
williamr@2
    83
          bestMap_(make_iterator_property_map(best_.begin(), 
williamr@2
    84
                                              get(vertex_index, g))),
williamr@2
    85
          buckets_(num_vertices(g)),
williamr@2
    86
          bucketMap_(make_iterator_property_map(buckets_.begin(), 
williamr@2
    87
                                                get(vertex_index, g))),
williamr@2
    88
          entry_(entry),
williamr@2
    89
          domTreePredMap_(domTreePredMap),
williamr@2
    90
          samedomMap(make_iterator_property_map(samedom_.begin(), 
williamr@2
    91
                                                get(vertex_index, g)))
williamr@2
    92
      {
williamr@2
    93
      }
williamr@2
    94
                
williamr@2
    95
      void 
williamr@2
    96
      operator()(const Vertex& n, const TimeMap& dfnumMap, 
williamr@2
    97
                 const PredMap& parentMap, const Graph& g)
williamr@2
    98
      {
williamr@2
    99
        if (n == entry_) return;
williamr@2
   100
williamr@2
   101
        const VerticesSizeType numOfVertices = num_vertices(g);
williamr@2
   102
        const Vertex p(get(parentMap, n));
williamr@2
   103
        Vertex s(p);
williamr@2
   104
williamr@2
   105
        // 1. Calculate the semidominator of n,
williamr@2
   106
        // based on the semidominator thm.
williamr@2
   107
        // * Semidominator thm. : To find the semidominator of a node n,
williamr@2
   108
        //   consider all predecessors v of n in the CFG (Control Flow Graph).
williamr@2
   109
        //  - If v is a proper ancestor of n in the spanning tree
williamr@2
   110
        //    (so dfnum(v) < dfnum(n)), then v is a candidate for semi(n)
williamr@2
   111
        //  - If v is a non-ancestor of n (so dfnum(v) > dfnum(n))
williamr@2
   112
        //    then for each u that is an ancestor of v (or u = v),
williamr@2
   113
        //    Let semi(u) be a candidate for semi(n)
williamr@2
   114
        //   of all these candidates, the one with lowest dfnum is
williamr@2
   115
        //   the semidominator of n.
williamr@2
   116
                                
williamr@2
   117
        // For each predecessor of n
williamr@2
   118
        typename graph_traits<Graph>::in_edge_iterator inItr, inEnd;
williamr@2
   119
        for (tie(inItr, inEnd) = in_edges(n, g); inItr != inEnd; ++inItr)
williamr@2
   120
          {
williamr@2
   121
            const Vertex v = source(*inItr, g);
williamr@2
   122
            // To deal with unreachable nodes
williamr@2
   123
            if (get(dfnumMap, v) < 0 || get(dfnumMap, v) >= numOfVertices)
williamr@2
   124
              continue;
williamr@2
   125
williamr@2
   126
            Vertex s2;
williamr@2
   127
            if (get(dfnumMap, v) <= get(dfnumMap, n))
williamr@2
   128
              s2 = v;
williamr@2
   129
            else
williamr@2
   130
              s2 = get(semiMap_, ancestor_with_lowest_semi_(v, dfnumMap));
williamr@2
   131
williamr@2
   132
            if (get(dfnumMap, s2) < get(dfnumMap, s))
williamr@2
   133
              s = s2;
williamr@2
   134
          }
williamr@2
   135
        put(semiMap_, n, s);
williamr@2
   136
williamr@2
   137
        // 2. Calculation of n's dominator is deferred until
williamr@2
   138
        // the path from s to n has been linked into the forest
williamr@2
   139
        get(bucketMap_, s).push_back(n);
williamr@2
   140
        get(ancestorMap_, n) = p;
williamr@2
   141
        get(bestMap_, n) = n;
williamr@2
   142
williamr@2
   143
        // 3. Now that the path from p to v has been linked into
williamr@2
   144
        // the spanning forest, these lines calculate the dominator of v,
williamr@2
   145
        // based on the dominator thm., or else defer the calculation
williamr@2
   146
        // until y's dominator is known
williamr@2
   147
        // * Dominator thm. : On the spanning-tree path below semi(n) and
williamr@2
   148
        //   above or including n, let y be the node
williamr@2
   149
        //   with the smallest-numbered semidominator. Then,
williamr@2
   150
        //      
williamr@2
   151
        //  idom(n) = semi(n) if semi(y)=semi(n) or
williamr@2
   152
        //            idom(y) if semi(y) != semi(n)
williamr@2
   153
        typename std::deque<Vertex>::iterator buckItr;
williamr@2
   154
        for (buckItr = get(bucketMap_, p).begin();
williamr@2
   155
             buckItr != get(bucketMap_, p).end();
williamr@2
   156
             ++buckItr)
williamr@2
   157
          {
williamr@2
   158
            const Vertex v(*buckItr);
williamr@2
   159
            const Vertex y(ancestor_with_lowest_semi_(v, dfnumMap));
williamr@2
   160
            if (get(semiMap_, y) == get(semiMap_, v))
williamr@2
   161
              put(domTreePredMap_, v, p);
williamr@2
   162
            else
williamr@2
   163
              put(samedomMap, v, y);
williamr@2
   164
          }
williamr@2
   165
williamr@2
   166
        get(bucketMap_, p).clear();
williamr@2
   167
      }
williamr@2
   168
williamr@2
   169
    protected :
williamr@2
   170
williamr@2
   171
      /**
williamr@2
   172
       * Evaluate function in Tarjan's path compression
williamr@2
   173
       */
williamr@2
   174
      const Vertex 
williamr@2
   175
      ancestor_with_lowest_semi_(const Vertex& v, const TimeMap& dfnumMap)
williamr@2
   176
      {
williamr@2
   177
        const Vertex a(get(ancestorMap_, v));
williamr@2
   178
williamr@2
   179
        if (get(ancestorMap_, a) != graph_traits<Graph>::null_vertex())
williamr@2
   180
          {
williamr@2
   181
            const Vertex b(ancestor_with_lowest_semi_(a, dfnumMap));
williamr@2
   182
williamr@2
   183
            put(ancestorMap_, v, get(ancestorMap_, a));
williamr@2
   184
williamr@2
   185
            if (get(dfnumMap, get(semiMap_, b)) <
williamr@2
   186
                get(dfnumMap, get(semiMap_, get(bestMap_, v))))
williamr@2
   187
              put(bestMap_, v, b);
williamr@2
   188
          }
williamr@2
   189
williamr@2
   190
        return get(bestMap_, v);
williamr@2
   191
      }
williamr@2
   192
williamr@2
   193
      std::vector<Vertex> semi_, ancestor_, samedom_, best_;
williamr@2
   194
      PredMap semiMap_, ancestorMap_, bestMap_;
williamr@2
   195
      std::vector< std::deque<Vertex> > buckets_;
williamr@2
   196
williamr@2
   197
      iterator_property_map<typename std::vector<std::deque<Vertex> >::iterator,
williamr@2
   198
                            IndexMap> bucketMap_;
williamr@2
   199
williamr@2
   200
      const Vertex& entry_;
williamr@2
   201
      DomTreePredMap domTreePredMap_;
williamr@2
   202
williamr@2
   203
    public :
williamr@2
   204
                        
williamr@2
   205
      PredMap samedomMap;
williamr@2
   206
    };
williamr@2
   207
williamr@2
   208
  } // namespace detail
williamr@2
   209
williamr@2
   210
  /**
williamr@2
   211
   * @brief Build dominator tree using Lengauer-Tarjan algorithm.
williamr@2
   212
   *                It takes O((V+E)log(V+E)) time.
williamr@2
   213
   *
williamr@2
   214
   * @pre dfnumMap, parentMap and verticesByDFNum have dfs results corresponding
williamr@2
   215
   *      indexMap.
williamr@2
   216
   *      If dfs has already run before,
williamr@2
   217
   *      this function would be good for saving computations.
williamr@2
   218
   * @pre Unreachable nodes must be masked as
williamr@2
   219
   *      graph_traits<Graph>::null_vertex in parentMap.
williamr@2
   220
   * @pre Unreachable nodes must be masked as
williamr@2
   221
   *      (std::numeric_limits<VerticesSizeType>::max)() in dfnumMap.
williamr@2
   222
   * 
williamr@2
   223
   * @param domTreePredMap [out] : immediate dominator map (parent map
williamr@2
   224
   * in dom. tree)
williamr@2
   225
   *
williamr@2
   226
   * @note reference Appel. p. 452~453. algorithm 19.9, 19.10.
williamr@2
   227
   *
williamr@2
   228
   * @todo : Optimization in Finding Dominators in Practice, Loukas Georgiadis
williamr@2
   229
   */
williamr@2
   230
  template<class Graph, class IndexMap, class TimeMap, class PredMap, 
williamr@2
   231
           class VertexVector, class DomTreePredMap>
williamr@2
   232
  void
williamr@2
   233
  lengauer_tarjan_dominator_tree_without_dfs
williamr@2
   234
    (const Graph& g,
williamr@2
   235
     const typename graph_traits<Graph>::vertex_descriptor& entry,
williamr@2
   236
     const IndexMap& indexMap,
williamr@2
   237
     TimeMap dfnumMap, PredMap parentMap, VertexVector& verticesByDFNum,
williamr@2
   238
     DomTreePredMap domTreePredMap)
williamr@2
   239
  {
williamr@2
   240
    // Typedefs and concept check
williamr@2
   241
    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
williamr@2
   242
    typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;
williamr@2
   243
williamr@2
   244
    function_requires< BidirectionalGraphConcept<Graph> >();
williamr@2
   245
williamr@2
   246
    const VerticesSizeType numOfVertices = num_vertices(g);
williamr@2
   247
    if (numOfVertices == 0) return;
williamr@2
   248
williamr@2
   249
    // 1. Visit each vertex in reverse post order and calculate sdom.
williamr@2
   250
    detail::dominator_visitor<Graph, IndexMap, TimeMap, PredMap, DomTreePredMap>
williamr@2
   251
      visitor(g, entry, domTreePredMap);
williamr@2
   252
williamr@2
   253
    VerticesSizeType i;
williamr@2
   254
    for (i = 0; i < numOfVertices; ++i)
williamr@2
   255
      {
williamr@2
   256
        const Vertex u(verticesByDFNum[numOfVertices - 1 - i]);
williamr@2
   257
        if (u != graph_traits<Graph>::null_vertex())
williamr@2
   258
          visitor(u, dfnumMap, parentMap, g);
williamr@2
   259
      }
williamr@2
   260
williamr@2
   261
    // 2. Now all the deferred dominator calculations,
williamr@2
   262
    // based on the second clause of the dominator thm., are performed
williamr@2
   263
    for (i = 0; i < numOfVertices; ++i)
williamr@2
   264
      {
williamr@2
   265
        const Vertex n(verticesByDFNum[i]);
williamr@2
   266
williamr@2
   267
        if (n == entry || n == graph_traits<Graph>::null_vertex())
williamr@2
   268
          continue;
williamr@2
   269
williamr@2
   270
        Vertex u = get(visitor.samedomMap, n);
williamr@2
   271
        if (u != graph_traits<Graph>::null_vertex())
williamr@2
   272
          {
williamr@2
   273
            put(domTreePredMap, n, get(domTreePredMap, u));
williamr@2
   274
          }
williamr@2
   275
      }
williamr@2
   276
  }
williamr@2
   277
  
williamr@2
   278
  /**
williamr@2
   279
   * Unlike lengauer_tarjan_dominator_tree_without_dfs,
williamr@2
   280
   * dfs is run in this function and
williamr@2
   281
   * the result is written to dfnumMap, parentMap, vertices.
williamr@2
   282
   *
williamr@2
   283
   * If the result of dfs required after this algorithm,
williamr@2
   284
   * this function can eliminate the need of rerunning dfs.
williamr@2
   285
   */
williamr@2
   286
  template<class Graph, class IndexMap, class TimeMap, class PredMap, 
williamr@2
   287
           class VertexVector, class DomTreePredMap>
williamr@2
   288
  void
williamr@2
   289
  lengauer_tarjan_dominator_tree
williamr@2
   290
    (const Graph& g,
williamr@2
   291
     const typename graph_traits<Graph>::vertex_descriptor& entry,
williamr@2
   292
     const IndexMap& indexMap,
williamr@2
   293
     TimeMap dfnumMap, PredMap parentMap, VertexVector& verticesByDFNum,
williamr@2
   294
     DomTreePredMap domTreePredMap)
williamr@2
   295
  {
williamr@2
   296
    // Typedefs and concept check
williamr@2
   297
    typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;
williamr@2
   298
williamr@2
   299
    function_requires< BidirectionalGraphConcept<Graph> >();
williamr@2
   300
williamr@2
   301
    // 1. Depth first visit
williamr@2
   302
    const VerticesSizeType numOfVertices = num_vertices(g);
williamr@2
   303
    if (numOfVertices == 0) return;
williamr@2
   304
williamr@2
   305
    VerticesSizeType time =
williamr@2
   306
      (std::numeric_limits<VerticesSizeType>::max)();
williamr@2
   307
    std::vector<default_color_type> 
williamr@2
   308
      colors(numOfVertices, color_traits<default_color_type>::white());
williamr@2
   309
    depth_first_visit
williamr@2
   310
      (g, entry,
williamr@2
   311
       make_dfs_visitor
williamr@2
   312
         (make_pair(record_predecessors(parentMap, on_tree_edge()),
williamr@2
   313
                    detail::stamp_times_with_vertex_vector
williamr@2
   314
                      (dfnumMap, verticesByDFNum, time, on_discover_vertex()))),
williamr@2
   315
       make_iterator_property_map(colors.begin(), indexMap));
williamr@2
   316
williamr@2
   317
    // 2. Run main algorithm.
williamr@2
   318
    lengauer_tarjan_dominator_tree_without_dfs(g, entry, indexMap, dfnumMap, 
williamr@2
   319
                                               parentMap, verticesByDFNum, 
williamr@2
   320
                                               domTreePredMap);
williamr@2
   321
  }
williamr@2
   322
williamr@2
   323
  /**
williamr@2
   324
   * Use vertex_index as IndexMap and make dfnumMap, parentMap, verticesByDFNum
williamr@2
   325
   * internally.
williamr@2
   326
   * If we don't need the result of dfs (dfnumMap, parentMap, verticesByDFNum),
williamr@2
   327
   * this function would be more convenient one.
williamr@2
   328
   */
williamr@2
   329
  template<class Graph, class DomTreePredMap>
williamr@2
   330
  void
williamr@2
   331
  lengauer_tarjan_dominator_tree
williamr@2
   332
    (const Graph& g,
williamr@2
   333
     const typename graph_traits<Graph>::vertex_descriptor& entry,
williamr@2
   334
     DomTreePredMap domTreePredMap)
williamr@2
   335
  {
williamr@2
   336
    // typedefs
williamr@2
   337
    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
williamr@2
   338
    typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;
williamr@2
   339
    typedef typename property_map<Graph, vertex_index_t>::const_type IndexMap;
williamr@2
   340
    typedef
williamr@2
   341
      iterator_property_map<typename std::vector<VerticesSizeType>::iterator,
williamr@2
   342
                            IndexMap> TimeMap;
williamr@2
   343
    typedef
williamr@2
   344
      iterator_property_map<typename std::vector<Vertex>::iterator, IndexMap>
williamr@2
   345
      PredMap;
williamr@2
   346
williamr@2
   347
    // Make property maps
williamr@2
   348
    const VerticesSizeType numOfVertices = num_vertices(g);
williamr@2
   349
    if (numOfVertices == 0) return;
williamr@2
   350
williamr@2
   351
    const IndexMap indexMap = get(vertex_index, g);
williamr@2
   352
williamr@2
   353
    std::vector<VerticesSizeType> dfnum(numOfVertices, 0);
williamr@2
   354
    TimeMap dfnumMap(make_iterator_property_map(dfnum.begin(), indexMap));
williamr@2
   355
williamr@2
   356
    std::vector<Vertex> parent(numOfVertices, 
williamr@2
   357
                               graph_traits<Graph>::null_vertex());
williamr@2
   358
    PredMap parentMap(make_iterator_property_map(parent.begin(), indexMap));
williamr@2
   359
williamr@2
   360
    std::vector<Vertex> verticesByDFNum(parent);
williamr@2
   361
williamr@2
   362
    // Run main algorithm
williamr@2
   363
    lengauer_tarjan_dominator_tree(g, entry,
williamr@2
   364
                                   indexMap, dfnumMap, parentMap, 
williamr@2
   365
                                   verticesByDFNum, domTreePredMap);
williamr@2
   366
  }
williamr@2
   367
williamr@2
   368
  /**
williamr@2
   369
   * Muchnick. p. 182, 184
williamr@2
   370
   *
williamr@2
   371
   * using iterative bit vector analysis
williamr@2
   372
   */
williamr@2
   373
  template<class Graph, class IndexMap, class DomTreePredMap>
williamr@2
   374
  void
williamr@2
   375
  iterative_bit_vector_dominator_tree
williamr@2
   376
    (const Graph& g,
williamr@2
   377
     const typename graph_traits<Graph>::vertex_descriptor& entry,
williamr@2
   378
     const IndexMap& indexMap,
williamr@2
   379
     DomTreePredMap domTreePredMap)
williamr@2
   380
  {
williamr@2
   381
    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
williamr@2
   382
    typedef typename graph_traits<Graph>::vertex_iterator vertexItr;
williamr@2
   383
    typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;
williamr@2
   384
    typedef
williamr@2
   385
      iterator_property_map<typename std::vector< std::set<Vertex> >::iterator,
williamr@2
   386
                            IndexMap> vertexSetMap;
williamr@2
   387
williamr@2
   388
    function_requires<BidirectionalGraphConcept<Graph> >();
williamr@2
   389
williamr@2
   390
    // 1. Finding dominator
williamr@2
   391
    // 1.1. Initialize
williamr@2
   392
    const VerticesSizeType numOfVertices = num_vertices(g);
williamr@2
   393
    if (numOfVertices == 0) return;
williamr@2
   394
williamr@2
   395
    vertexItr vi, viend;
williamr@2
   396
    tie(vi, viend) = vertices(g);
williamr@2
   397
    const std::set<Vertex> N(vi, viend);
williamr@2
   398
williamr@2
   399
    bool change = true;
williamr@2
   400
                
williamr@2
   401
    std::vector< std::set<Vertex> > dom(numOfVertices, N);
williamr@2
   402
    vertexSetMap domMap(make_iterator_property_map(dom.begin(), indexMap));
williamr@2
   403
    get(domMap, entry).clear();
williamr@2
   404
    get(domMap, entry).insert(entry);
williamr@2
   405
williamr@2
   406
    while (change)
williamr@2
   407
      {
williamr@2
   408
        change = false;
williamr@2
   409
        for (tie(vi, viend) = vertices(g); vi != viend; ++vi)
williamr@2
   410
          {
williamr@2
   411
            if (*vi == entry) continue;
williamr@2
   412
williamr@2
   413
            std::set<Vertex> T(N);
williamr@2
   414
                                
williamr@2
   415
            typename graph_traits<Graph>::in_edge_iterator inItr, inEnd;
williamr@2
   416
            for (tie(inItr, inEnd) = in_edges(*vi, g); inItr != inEnd; ++inItr)
williamr@2
   417
              {
williamr@2
   418
                const Vertex p = source(*inItr, g);
williamr@2
   419
williamr@2
   420
                std::set<Vertex> tempSet;
williamr@2
   421
                std::set_intersection(T.begin(), T.end(), 
williamr@2
   422
                                      get(domMap, p).begin(), 
williamr@2
   423
                                      get(domMap, p).end(),
williamr@2
   424
                                      std::inserter(tempSet, tempSet.begin()));
williamr@2
   425
                T.swap(tempSet);
williamr@2
   426
              }
williamr@2
   427
williamr@2
   428
            T.insert(*vi);
williamr@2
   429
            if (T != get(domMap, *vi))
williamr@2
   430
              {
williamr@2
   431
                change = true;
williamr@2
   432
                get(domMap, *vi).swap(T);
williamr@2
   433
              }
williamr@2
   434
          } // end of for (tie(vi, viend) = vertices(g)
williamr@2
   435
      } // end of while(change)
williamr@2
   436
williamr@2
   437
    // 2. Build dominator tree
williamr@2
   438
    for (tie(vi, viend) = vertices(g); vi != viend; ++vi)
williamr@2
   439
      get(domMap, *vi).erase(*vi);
williamr@2
   440
williamr@2
   441
    Graph domTree(numOfVertices);
williamr@2
   442
williamr@2
   443
    for (tie(vi, viend) = vertices(g); vi != viend; ++vi)
williamr@2
   444
      {
williamr@2
   445
        if (*vi == entry) continue;
williamr@2
   446
williamr@2
   447
        // We have to iterate through copied dominator set
williamr@2
   448
        const std::set<Vertex> tempSet(get(domMap, *vi));
williamr@2
   449
        typename std::set<Vertex>::const_iterator s;
williamr@2
   450
        for (s = tempSet.begin(); s != tempSet.end(); ++s)
williamr@2
   451
          {
williamr@2
   452
            typename std::set<Vertex>::iterator t;
williamr@2
   453
            for (t = get(domMap, *vi).begin(); t != get(domMap, *vi).end(); )
williamr@2
   454
              {
williamr@2
   455
        typename std::set<Vertex>::iterator old_t = t;
williamr@2
   456
        ++t; // Done early because t may become invalid
williamr@2
   457
                if (*old_t == *s) continue;
williamr@2
   458
                if (get(domMap, *s).find(*old_t) != get(domMap, *s).end())
williamr@2
   459
                  get(domMap, *vi).erase(old_t);
williamr@2
   460
              }
williamr@2
   461
          }
williamr@2
   462
      }
williamr@2
   463
williamr@2
   464
    for (tie(vi, viend) = vertices(g); vi != viend; ++vi)
williamr@2
   465
      {
williamr@2
   466
        if (*vi != entry && get(domMap, *vi).size() == 1)
williamr@2
   467
          {
williamr@2
   468
            Vertex temp = *get(domMap, *vi).begin();
williamr@2
   469
            put(domTreePredMap, *vi, temp);
williamr@2
   470
          }
williamr@2
   471
      }
williamr@2
   472
  }
williamr@2
   473
williamr@2
   474
  template<class Graph, class DomTreePredMap>
williamr@2
   475
  void
williamr@2
   476
  iterative_bit_vector_dominator_tree
williamr@2
   477
    (const Graph& g,
williamr@2
   478
     const typename graph_traits<Graph>::vertex_descriptor& entry,
williamr@2
   479
     DomTreePredMap domTreePredMap)
williamr@2
   480
  {
williamr@2
   481
    typename property_map<Graph, vertex_index_t>::const_type
williamr@2
   482
      indexMap = get(vertex_index, g);
williamr@2
   483
    
williamr@2
   484
    iterative_bit_vector_dominator_tree(g, entry, indexMap, domTreePredMap);
williamr@2
   485
  }
williamr@2
   486
} // namespace boost
williamr@2
   487
williamr@2
   488
#endif // BOOST_GRAPH_DOMINATOR_HPP