SCCIterator.h File Reference

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/iterator.h"
#include <vector>

Include dependency graph for SCCIterator.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	llvm::scc_iterator< GraphT, GT >
	Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG. More...
struct	llvm::scc_iterator< GraphT, GT >::StackElement
	Element of VisitStack during DFS.
Namespaces
namespace	llvm
	List of target independent CodeGen pass IDs.
Functions
template<class T >
scc_iterator< T >	llvm::scc_begin (const T &G)
	Construct the begin iterator for a deduced graph type T.
template<class T >
scc_iterator< T >	llvm::scc_end (const T &G)
	Construct the end iterator for a deduced graph type T.
template<class T >
scc_iterator< Inverse< T > >	llvm::scc_begin (const Inverse< T > &G)
	Construct the begin iterator for a deduced graph type T's Inverse<T>.
template<class T >
scc_iterator< Inverse< T > >	llvm::scc_end (const Inverse< T > &G)
	Construct the end iterator for a deduced graph type T's Inverse<T>.

---

Detailed Description

This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a graph in O(N+E) time using Tarjan's DFS algorithm.

The SCC iterator has the important property that if a node in SCC S1 has an edge to a node in SCC S2, then it visits S1 *after* S2.

To visit S1 *before* S2, use the scc_iterator on the Inverse graph. (NOTE: This requires some simple wrappers and is not supported yet.)

Definition in file SCCIterator.h.