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