include/Support/SCCIterator.h

   1 //===-- Support/TarjanSCCIterator.h - Tarjan SCC iterator -------*- C++ -*-===//
   2 //
   3 // This builds on the Support/GraphTraits.h file to find the strongly
   4 // connected components (SCCs) of a graph in O(N+E) time using
   5 // Tarjan's DFS algorithm.
   6 //
   7 // The SCC iterator has the important property that if a node in SCC S1
   8 // has an edge to a node in SCC S2, then it visits S1 *after* S2.
   9 //
  10 // To visit S1 *before* S2, use the TarjanSCCIterator on the Inverse graph.
  11 // (NOTE: This requires some simple wrappers and is not supported yet.)
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef SUPPORT_TARJANSCCITERATOR_H
  16 #define SUPPORT_TARJANSCCITERATOR_H
  17
  18 #include "Support/GraphTraits.h"
  19 #include "Support/Debug.h"
  20 #include "Support/iterator"
  21 #include <vector>
  22 #include <map>
  23
  24 //--------------------------------------------------------------------------
  25 // class SCC : A simple representation of an SCC in a generic Graph.
  26 //--------------------------------------------------------------------------
  27
  28 template<class GraphT, class GT = GraphTraits<GraphT> >
  29 struct SCC: public std::vector<typename GT::NodeType*> {
  30
  31   typedef typename GT::NodeType NodeType;
  32   typedef typename GT::ChildIteratorType ChildItTy;
  33
  34   typedef std::vector<typename GT::NodeType*> super;
  35   typedef typename super::iterator               iterator;
  36   typedef typename super::const_iterator         const_iterator;
  37   typedef typename super::reverse_iterator       reverse_iterator;
  38   typedef typename super::const_reverse_iterator const_reverse_iterator;
  39
  40   // HasLoop() -- Test if this SCC has a loop.  If it has more than one
  41   // node, this is trivially true.  If not, it may still contain a loop
  42   // if the node has an edge back to itself.
  43   bool HasLoop() const {
  44     if (size() > 1) return true;
  45     NodeType* N = front();
  46     for (ChildItTy CI=GT::child_begin(N), CE=GT::child_end(N); CI != CE; ++CI)
  47       if (*CI == N)
  48         return true;
  49     return false;
  50   }
  51 };
  52
  53 //--------------------------------------------------------------------------
  54 // class TarjanSCC_iterator: Enumerate the SCCs of a directed graph, in
  55 // reverse topological order of the SCC DAG.
  56 //--------------------------------------------------------------------------
  57
  58 template<class GraphT, class GT = GraphTraits<GraphT> >
  59 class TarjanSCC_iterator : public forward_iterator<SCC<GraphT, GT>, ptrdiff_t>
  60 {
  61   typedef SCC<GraphT, GT> SccTy;
  62   typedef forward_iterator<SccTy, ptrdiff_t> super;
  63   typedef typename super::reference reference;
  64   typedef typename super::pointer pointer;
  65   typedef typename GT::NodeType          NodeType;
  66   typedef typename GT::ChildIteratorType ChildItTy;
  67
  68   // The visit counters used to detect when a complete SCC is on the stack.
  69   // visitNum is the global counter.
  70   // nodeVisitNumbers are per-node visit numbers, also used as DFS flags.
  71   unsigned visitNum;
  72   std::map<NodeType *, unsigned> nodeVisitNumbers;
  73
  74   // SCCNodeStack - Stack holding nodes of the SCC.
  75   std::vector<NodeType *> SCCNodeStack;
  76
  77   // CurrentSCC - The current SCC, retrieved using operator*().
  78   SccTy CurrentSCC;
  79
  80   // VisitStack - Used to maintain the ordering.  Top = current block
  81   // First element is basic block pointer, second is the 'next child' to visit
  82   std::vector<std::pair<NodeType *, ChildItTy> > VisitStack;
  83
  84   // MinVistNumStack - Stack holding the "min" values for each node in the DFS.
  85   // This is used to track the minimum uplink values for all children of
  86   // the corresponding node on the VisitStack.
  87   std::vector<unsigned> MinVisitNumStack;
  88
  89   // A single "visit" within the non-recursive DFS traversal.
  90   void DFSVisitOne(NodeType* N) {
  91     ++visitNum;                         // Global counter for the visit order
  92     nodeVisitNumbers[N] = visitNum;
  93     SCCNodeStack.push_back(N);
  94     MinVisitNumStack.push_back(visitNum);
  95     VisitStack.push_back(make_pair(N, GT::child_begin(N)));
  96     //DEBUG(std::cerr << "TarjanSCC: Node " << N <<
  97     //      " : visitNum = " << visitNum << "\n");
  98   }
  99
 100   // The stack-based DFS traversal; defined below.
 101   void DFSVisitChildren() {
 102     assert(!VisitStack.empty());
 103     while (VisitStack.back().second != GT::child_end(VisitStack.back().first))
 104       { // TOS has at least one more child so continue DFS
 105         NodeType *childN = *VisitStack.back().second++;
 106         if (nodeVisitNumbers.find(childN) == nodeVisitNumbers.end())
 107           { // this node has never been seen
 108             DFSVisitOne(childN);
 109           }
 110         else
 111           {
 112             unsigned childNum = nodeVisitNumbers[childN];
 113             if (MinVisitNumStack.back() > childNum)
 114               MinVisitNumStack.back() = childNum;
 115           }
 116       }
 117   }
 118
 119   // Compute the next SCC using the DFS traversal.
 120   void GetNextSCC() {
 121     assert(VisitStack.size() == MinVisitNumStack.size());
 122     CurrentSCC.clear();                 // Prepare to compute the next SCC
 123     while (! VisitStack.empty())
 124       {
 125         DFSVisitChildren();
 126
 127         assert(VisitStack.back().second ==
 128                GT::child_end(VisitStack.back().first));
 129         NodeType* visitingN = VisitStack.back().first;
 130         unsigned minVisitNum = MinVisitNumStack.back();
 131         VisitStack.pop_back();
 132         MinVisitNumStack.pop_back();
 133         if (! MinVisitNumStack.empty() && MinVisitNumStack.back() > minVisitNum)
 134           MinVisitNumStack.back() = minVisitNum;
 135
 136         //DEBUG(std::cerr << "TarjanSCC: Popped node " << visitingN <<
 137         //      " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
 138         //      nodeVisitNumbers[visitingN] << "\n");
 139
 140         if (minVisitNum == nodeVisitNumbers[visitingN])
 141           { // A full SCC is on the SCCNodeStack!  It includes all nodes below
 142             // visitingN on the stack.  Copy those nodes to CurrentSCC,
 143             // reset their minVisit values, and return (this suspends
 144             // the DFS traversal till the next ++).
 145             do {
 146               CurrentSCC.push_back(SCCNodeStack.back());
 147               SCCNodeStack.pop_back();
 148               nodeVisitNumbers[CurrentSCC.back()] = ~0UL;
 149             } while (CurrentSCC.back() != visitingN);
 150             return;
 151           }
 152       }
 153   }
 154
 155   inline TarjanSCC_iterator(NodeType *entryN) : visitNum(0) {
 156     DFSVisitOne(entryN);
 157     GetNextSCC();
 158   }
 159   inline TarjanSCC_iterator() { /* End is when DFS stack is empty */ }
 160
 161 public:
 162   typedef TarjanSCC_iterator<GraphT, GT> _Self;
 163
 164   // Provide static "constructors"...
 165   static inline _Self begin(GraphT& G) { return _Self(GT::getEntryNode(G)); }
 166   static inline _Self end  (GraphT& G) { return _Self(); }
 167
 168   // Direct loop termination test (I.fini() is more efficient than I == end())
 169   inline bool fini() const {
 170     assert(!CurrentSCC.empty() || VisitStack.empty());
 171     return CurrentSCC.empty();
 172   }
 173
 174   inline bool operator==(const _Self& x) const {
 175     return VisitStack == x.VisitStack && CurrentSCC == x.CurrentSCC;
 176   }
 177   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 178
 179   // Iterator traversal: forward iteration only
 180   inline _Self& operator++() {          // Preincrement
 181     GetNextSCC();
 182     return *this;
 183   }
 184   inline _Self operator++(int) {        // Postincrement
 185     _Self tmp = *this; ++*this; return tmp;
 186   }
 187
 188   // Retrieve a pointer to the current SCC.  Returns NULL when done.
 189   inline const SccTy* operator*() const {
 190     assert(!CurrentSCC.empty() || VisitStack.empty());
 191     return CurrentSCC.empty()? NULL : &CurrentSCC;
 192   }
 193   inline SccTy* operator*() {
 194     assert(!CurrentSCC.empty() || VisitStack.empty());
 195     return CurrentSCC.empty()? NULL : &CurrentSCC;
 196   }
 197 };
 198
 199
 200 // Global constructor for the Tarjan SCC iterator.  Use *I == NULL or I.fini()
 201 // to test termination efficiently, instead of I == the "end" iterator.
 202 template <class T>
 203 TarjanSCC_iterator<T> tarj_begin(T G)
 204 {
 205   return TarjanSCC_iterator<T>::begin(G);
 206 }
 207
 208 template <class T>
 209 TarjanSCC_iterator<T> tarj_end(T G)
 210 {
 211   return TarjanSCC_iterator<T>::end(G);
 212 }
 213
 214 //===----------------------------------------------------------------------===//
 215
 216 #endif