LLVM 20.0.0git
Classes | Namespaces | Functions
SCCIterator.h File Reference

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/DenseSet.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/iterator.h"
#include <cassert>
#include <cstddef>
#include <iterator>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <vector>

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...
 
class  llvm::scc_member_iterator< GraphT, GT >
 Sort the nodes of a directed SCC in the decreasing order of the edge weights. More...
 

Namespaces

namespace  llvm
 This is an optimization pass for GlobalISel generic memory operations.
 

Functions

template<class T >
scc_iterator< Tllvm::scc_begin (const T &G)
 Construct the begin iterator for a deduced graph type T.
 
template<class T >
scc_iterator< Tllvm::scc_end (const T &G)
 Construct the end iterator for a deduced graph type 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.