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. More...
#include "llvm/ADT/DenseMap.h"#include "llvm/ADT/GraphTraits.h"#include "llvm/ADT/iterator.h"#include <cassert>#include <cstddef>#include <iterator>#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... | |
Namespaces | |
| llvm | |
| This class represents lattice values for constants. | |
Functions | |
| template<class T > | |
| scc_iterator< T > | llvm::scc_begin (const T &G) |
| Construct the begin iterator for a deduced graph type T. More... | |
| template<class T > | |
| scc_iterator< T > | llvm::scc_end (const T &G) |
| Construct the end iterator for a deduced graph type T. More... | |
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.
