class scc_iterator

Declaration

template <class GraphT, class GT = GraphTraits<GraphT>>
class scc_iterator { /* full declaration omitted */ };

Description

Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG. This is implemented using Tarjan's DFS algorithm using an internal stack to build up a vector of nodes in a particular SCC. Note that it is a forward iterator and thus you cannot backtrack or re-visit nodes.

Declared at: llvm/include/llvm/ADT/SCCIterator.h:46

Templates

GraphT
GT = GraphTraits<GraphT>

Member Variables

private unsigned int visitNum
nodeVisitNumbers are per-node visit numbers, also used as DFS flags.
private DenseMap<llvm::scc_iterator::NodeRef, unsigned int> nodeVisitNumbers
private std::vector<NodeRef> SCCNodeStack
Stack holding nodes of the SCC.
private llvm::scc_iterator::SccTy CurrentSCC
The current SCC, retrieved using operator*().
private std::vector<StackElement> VisitStack
DFS stack, Used to maintain the ordering. The top contains the current node, the next child to visit, and the minimum uplink value of all child

Method Overview

Methods

void DFSVisitChildren()

Description

The stack-based DFS traversal; defined below.

Declared at: llvm/include/llvm/ADT/SCCIterator.h:91

void DFSVisitOne(llvm::scc_iterator::NodeRef N)

Description

A single "visit" within the non-recursive DFS traversal.

Declared at: llvm/include/llvm/ADT/SCCIterator.h:88

Parameters

llvm::scc_iterator::NodeRef N

void GetNextSCC()

Description

Compute the next SCC using the DFS traversal.

Declared at: llvm/include/llvm/ADT/SCCIterator.h:94

void ReplaceNode(llvm::scc_iterator::NodeRef Old,
                 llvm::scc_iterator::NodeRef New)

Description

This informs the \c scc_iterator that the specified \c Old node has been deleted, and \c New is to be used in its place.

Declared at: llvm/include/llvm/ADT/SCCIterator.h:139

Parameters

llvm::scc_iterator::NodeRef Old
llvm::scc_iterator::NodeRef New

static scc_iterator<GraphT, GT> begin(
    const GraphT& G)

Declared at: llvm/include/llvm/ADT/SCCIterator.h:105

Parameters

const GraphT& G

static scc_iterator<GraphT, GT> end(const GraphT&)

Declared at: llvm/include/llvm/ADT/SCCIterator.h:108

Parameters

const GraphT& 

bool hasCycle() const

Description

Test if the current SCC has a cycle. If the SCC has more than one node, this is trivially true. If not, it may still contain a cycle if the node has an edge back to itself.

Declared at: llvm/include/llvm/ADT/SCCIterator.h:135

bool isAtEnd() const

Description

Direct loop termination test which is more efficient than comparison with \c end().

Declared at: llvm/include/llvm/ADT/SCCIterator.h:112

scc_iterator<GraphT, GT>(
    llvm::scc_iterator::NodeRef entryN)

Declared at: llvm/include/llvm/ADT/SCCIterator.h:96

Parameters

llvm::scc_iterator::NodeRef entryN

scc_iterator<GraphT, GT>()

Description

End is when the DFS stack is empty.

Declared at: llvm/include/llvm/ADT/SCCIterator.h:102