File: dominator_tree.hpp

package info (click to toggle)
boost1.62 1.62.0+dfsg-4
  • links: PTS, VCS
  • area: main
  • in suites: stretch
  • size: 686,420 kB
  • sloc: cpp: 2,609,004; xml: 972,558; ansic: 53,674; python: 32,437; sh: 8,829; asm: 3,071; cs: 2,121; makefile: 964; perl: 859; yacc: 472; php: 132; ruby: 94; f90: 55; sql: 13; csh: 6
file content (494 lines) | stat: -rw-r--r-- 17,790 bytes parent folder | download | duplicates (10)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
//=======================================================================
// 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)
//=======================================================================

#ifndef BOOST_GRAPH_DOMINATOR_HPP
#define BOOST_GRAPH_DOMINATOR_HPP

#include <boost/config.hpp>
#include <deque>
#include <set>
#include <boost/graph/depth_first_search.hpp>
#include <boost/concept/assert.hpp>

// Dominator tree computation

namespace boost {
  namespace detail {
    /**
     * An extended time_stamper which also records vertices for each dfs number
     */
    template<class TimeMap, class VertexVector, class TimeT, class Tag>
    class time_stamper_with_vertex_vector
      : public base_visitor<
      time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT, Tag> >
    {
    public :
      typedef Tag event_filter;
      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,
                 const Graph& g)
      {
        timeStamper_(v, g);
        v_[timeStamper_.m_time] = v;
      }

    private :
      time_stamper<TimeMap, TimeT, Tag> timeStamper_;
      VertexVector& v_;
    };

    /**
     * A convenient way to create a time_stamper_with_vertex_vector
     */
    template<class TimeMap, class VertexVector, class TimeT, class Tag>
    time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT, Tag>
    stamp_times_with_vertex_vector(TimeMap timeMap, VertexVector& v, TimeT& t,
                                   Tag)
    {
      return time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT,
                                             Tag>(timeMap, v, t);
    }

    template<class Graph, class IndexMap, class TimeMap, class PredMap,
             class DomTreePredMap>
    class dominator_visitor
    {
      typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
      typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;

    public :
      /**
       * @param g [in] the target graph of the dominator tree
       * @param entry [in] the entry node of g
       * @param indexMap [in] the vertex index map for g
       * @param domTreePredMap [out] the immediate dominator map
       *                             (parent map in dominator tree)
       */
      dominator_visitor(const Graph& g, const Vertex& entry,
                        const IndexMap& indexMap,
                        DomTreePredMap domTreePredMap)
        : semi_(num_vertices(g)),
          ancestor_(num_vertices(g), graph_traits<Graph>::null_vertex()),
          samedom_(ancestor_),
          best_(semi_),
          semiMap_(make_iterator_property_map(semi_.begin(),
                                              indexMap)),
          ancestorMap_(make_iterator_property_map(ancestor_.begin(),
                                                  indexMap)),
          bestMap_(make_iterator_property_map(best_.begin(),
                                              indexMap)),
          buckets_(num_vertices(g)),
          bucketMap_(make_iterator_property_map(buckets_.begin(),
                                                indexMap)),
          entry_(entry),
          domTreePredMap_(domTreePredMap),
          numOfVertices_(num_vertices(g)),
          samedomMap(make_iterator_property_map(samedom_.begin(),
                                                indexMap))
      {
      }

      void
      operator()(const Vertex& n, const TimeMap& dfnumMap,
                 const PredMap& parentMap, const Graph& g)
      {
        if (n == entry_) return;

        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<Graph>::in_edge_iterator inItr, inEnd;
        for (boost::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<Vertex>::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<Graph>::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<Vertex> semi_, ancestor_, samedom_, best_;
      PredMap semiMap_, ancestorMap_, bestMap_;
      std::vector< std::deque<Vertex> > buckets_;

      iterator_property_map<typename std::vector<std::deque<Vertex> >::iterator,
                            IndexMap> bucketMap_;

      const Vertex& entry_;
      DomTreePredMap domTreePredMap_;
      const VerticesSizeType numOfVertices_;

    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<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)
   *
   * @note reference Appel. p. 452~453. algorithm 19.9, 19.10.
   *
   * @todo : Optimization in Finding Dominators in Practice, Loukas Georgiadis
   */
  template<class Graph, class IndexMap, class TimeMap, class PredMap,
           class VertexVector, class DomTreePredMap>
  void
  lengauer_tarjan_dominator_tree_without_dfs
    (const Graph& g,
     const typename graph_traits<Graph>::vertex_descriptor& entry,
     const IndexMap& indexMap,
     TimeMap dfnumMap, PredMap parentMap, VertexVector& verticesByDFNum,
     DomTreePredMap domTreePredMap)
  {
    // Typedefs and concept check
    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
    typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;

    BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph> ));

    const VerticesSizeType numOfVertices = num_vertices(g);
    if (numOfVertices == 0) return;

    // 1. Visit each vertex in reverse post order and calculate sdom.
    detail::dominator_visitor<Graph, IndexMap, TimeMap, PredMap, DomTreePredMap>
      visitor(g, entry, indexMap, domTreePredMap);

    VerticesSizeType i;
    for (i = 0; i < numOfVertices; ++i)
      {
        const Vertex u(verticesByDFNum[numOfVertices - 1 - i]);
        if (u != graph_traits<Graph>::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<Graph>::null_vertex())
          continue;

        Vertex u = get(visitor.samedomMap, n);
        if (u != graph_traits<Graph>::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<class Graph, class IndexMap, class TimeMap, class PredMap,
           class VertexVector, class DomTreePredMap>
  void
  lengauer_tarjan_dominator_tree
    (const Graph& g,
     const typename graph_traits<Graph>::vertex_descriptor& entry,
     const IndexMap& indexMap,
     TimeMap dfnumMap, PredMap parentMap, VertexVector& verticesByDFNum,
     DomTreePredMap domTreePredMap)
  {
    // Typedefs and concept check
    typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;

    BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph> ));

    // 1. Depth first visit
    const VerticesSizeType numOfVertices = num_vertices(g);
    if (numOfVertices == 0) return;

    VerticesSizeType time =
      (std::numeric_limits<VerticesSizeType>::max)();
    std::vector<default_color_type>
      colors(numOfVertices, color_traits<default_color_type>::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<class Graph, class DomTreePredMap>
  void
  lengauer_tarjan_dominator_tree
    (const Graph& g,
     const typename graph_traits<Graph>::vertex_descriptor& entry,
     DomTreePredMap domTreePredMap)
  {
    // typedefs
    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
    typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;
    typedef typename property_map<Graph, vertex_index_t>::const_type IndexMap;
    typedef
      iterator_property_map<typename std::vector<VerticesSizeType>::iterator,
                            IndexMap> TimeMap;
    typedef
      iterator_property_map<typename std::vector<Vertex>::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<VerticesSizeType> dfnum(numOfVertices, 0);
    TimeMap dfnumMap(make_iterator_property_map(dfnum.begin(), indexMap));

    std::vector<Vertex> parent(numOfVertices,
                               graph_traits<Graph>::null_vertex());
    PredMap parentMap(make_iterator_property_map(parent.begin(), indexMap));

    std::vector<Vertex> 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<class Graph, class IndexMap, class DomTreePredMap>
  void
  iterative_bit_vector_dominator_tree
    (const Graph& g,
     const typename graph_traits<Graph>::vertex_descriptor& entry,
     const IndexMap& indexMap,
     DomTreePredMap domTreePredMap)
  {
    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
    typedef typename graph_traits<Graph>::vertex_iterator vertexItr;
    typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType;
    typedef
      iterator_property_map<typename std::vector< std::set<Vertex> >::iterator,
                            IndexMap> vertexSetMap;

    BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph> ));

    // 1. Finding dominator
    // 1.1. Initialize
    const VerticesSizeType numOfVertices = num_vertices(g);
    if (numOfVertices == 0) return;

    vertexItr vi, viend;
    boost::tie(vi, viend) = vertices(g);
    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();
    get(domMap, entry).insert(entry);

    while (change)
      {
        change = false;
        for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi)
          {
            if (*vi == entry) continue;

            std::set<Vertex> T(N);

            typename graph_traits<Graph>::in_edge_iterator inItr, inEnd;
            for (boost::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(),
                                      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 (boost::tie(vi, viend) = vertices(g)
      } // end of while(change)

    // 2. Build dominator tree
    for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi)
      get(domMap, *vi).erase(*vi);

    Graph domTree(numOfVertices);

    for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi)
      {
        if (*vi == entry) continue;

        // We have to iterate through copied dominator set
        const std::set<Vertex> tempSet(get(domMap, *vi));
        typename std::set<Vertex>::const_iterator s;
        for (s = tempSet.begin(); s != tempSet.end(); ++s)
          {
            typename std::set<Vertex>::iterator t;
            for (t = get(domMap, *vi).begin(); t != get(domMap, *vi).end(); )
              {
        typename std::set<Vertex>::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 (boost::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<class Graph, class DomTreePredMap>
  void
  iterative_bit_vector_dominator_tree
    (const Graph& g,
     const typename graph_traits<Graph>::vertex_descriptor& entry,
     DomTreePredMap domTreePredMap)
  {
    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

#endif // BOOST_GRAPH_DOMINATOR_HPP