include/llvm/ADT/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 <stack>
  23 #include <map>
  24
  25 //--------------------------------------------------------------------------
  26 // class SCC : A simple representation of an SCC in a generic Graph.
  27 //--------------------------------------------------------------------------
  28
  29 template<class GraphT, class GT = GraphTraits<GraphT> >
  30 struct SCC: public std::vector<typename GT::NodeType*> {
  31
  32   typedef typename GT::NodeType NodeType;
  33   typedef typename GT::ChildIteratorType ChildItTy;
  34
  35   typedef std::vector<typename GT::NodeType*> super;
  36   typedef typename super::iterator               iterator;
  37   typedef typename super::const_iterator         const_iterator;
  38   typedef typename super::reverse_iterator       reverse_iterator;
  39   typedef typename super::const_reverse_iterator const_reverse_iterator;
  40
  41   // HasLoop() -- Test if this SCC has a loop.  If it has more than one
  42   // node, this is trivially true.  If not, it may still contain a loop
  43   // if the node has an edge back to itself.
  44   bool HasLoop() const {
  45     if (size() > 1) return true;
  46     NodeType* N = front();
  47     for (ChildItTy CI=GT::child_begin(N), CE=GT::child_end(N); CI != CE; ++CI)
  48       if (*CI == N)
  49         return true;
  50     return false;
  51   }
  52 };
  53
  54 //--------------------------------------------------------------------------
  55 // class TarjanSCC_iterator: Enumerate the SCCs of a directed graph, in
  56 // reverse topological order of the SCC DAG.
  57 //--------------------------------------------------------------------------
  58
  59 template<class GraphT, class GT = GraphTraits<GraphT> >
  60 class TarjanSCC_iterator : public forward_iterator<SCC<GraphT, GT>, ptrdiff_t>
  61 {
  62   typedef SCC<GraphT, GT> SccTy;
  63   typedef forward_iterator<SccTy, ptrdiff_t> super;
  64   typedef typename super::reference reference;
  65   typedef typename super::pointer pointer;
  66   typedef typename GT::NodeType          NodeType;
  67   typedef typename GT::ChildIteratorType ChildItTy;
  68
  69   // The visit counters used to detect when a complete SCC is on the stack.
  70   // visitNum is the global counter.
  71   // nodeVisitNumbers are per-node visit numbers, also used as DFS flags.
  72   unsigned long visitNum;
  73   std::map<NodeType *, unsigned long> nodeVisitNumbers;
  74
  75   // SCCNodeStack - Stack holding nodes of the SCC.
  76   std::stack<NodeType *> SCCNodeStack;
  77
  78   // CurrentSCC - The current SCC, retrieved using operator*().
  79   SccTy CurrentSCC;
  80
  81   // VisitStack - Used to maintain the ordering.  Top = current block
  82   // First element is basic block pointer, second is the 'next child' to visit
  83   std::stack<std::pair<NodeType *, ChildItTy> > VisitStack;
  84
  85   // MinVistNumStack - Stack holding the "min" values for each node in the DFS.
  86   // This is used to track the minimum uplink values for all children of
  87   // the corresponding node on the VisitStack.
  88   std::stack<unsigned long> MinVisitNumStack;
  89
  90   // A single "visit" within the non-recursive DFS traversal.
  91   void DFSVisitOne(NodeType* N) {
  92     ++visitNum;                         // Global counter for the visit order
  93     nodeVisitNumbers[N] = visitNum;
  94     SCCNodeStack.push(N);
  95     MinVisitNumStack.push(visitNum);
  96     VisitStack.push(make_pair(N, GT::child_begin(N)));
  97     //DEBUG(std::cerr << "TarjanSCC: Node " << N <<
  98     //      " : visitNum = " << visitNum << "\n");
  99   }
 100
 101   // The stack-based DFS traversal; defined below.
 102   void DFSVisitChildren() {
 103     assert(!VisitStack.empty());
 104     while (VisitStack.top().second != GT::child_end(VisitStack.top().first))
 105       { // TOS has at least one more child so continue DFS
 106         NodeType *childN = *VisitStack.top().second++;
 107         if (nodeVisitNumbers.find(childN) == nodeVisitNumbers.end())
 108           { // this node has never been seen
 109             DFSVisitOne(childN);
 110           }
 111         else
 112           {
 113             unsigned long childNum = nodeVisitNumbers[childN];
 114             if (MinVisitNumStack.top() > childNum)
 115               MinVisitNumStack.top() = childNum;
 116           }
 117       }
 118   }
 119
 120   // Compute the next SCC using the DFS traversal.
 121   void GetNextSCC() {
 122     assert(VisitStack.size() == MinVisitNumStack.size());
 123     CurrentSCC.clear();                 // Prepare to compute the next SCC
 124     while (! VisitStack.empty())
 125       {
 126         DFSVisitChildren();
 127
 128         assert(VisitStack.top().second==GT::child_end(VisitStack.top().first));
 129         NodeType* visitingN = VisitStack.top().first;
 130         unsigned long minVisitNum = MinVisitNumStack.top();
 131         VisitStack.pop();
 132         MinVisitNumStack.pop();
 133         if (! MinVisitNumStack.empty() && MinVisitNumStack.top() > minVisitNum)
 134           MinVisitNumStack.top() = 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.top());
 147               SCCNodeStack.pop();
 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