LLVM 20.0.0git
Classes | Public Member Functions | List of all members
llvm::scc_member_iterator< GraphT, GT > Class Template Reference

Sort the nodes of a directed SCC in the decreasing order of the edge weights. More...

#include "llvm/ADT/SCCIterator.h"

Public Member Functions

 scc_member_iterator (const NodesType &InputNodes)
 
NodesType & operator* ()
 

Detailed Description

template<class GraphT, class GT = GraphTraits<GraphT>>
class llvm::scc_member_iterator< GraphT, GT >

Sort the nodes of a directed SCC in the decreasing order of the edge weights.

The instantiating GraphT type should have weighted edge type declared in its graph traits in order to use this iterator.

This is implemented using Kruskal's minimal spanning tree algorithm followed by Kahn's algorithm to compute a topological order on the MST. First a maximum spanning tree (forest) is built based on all edges within the SCC collection. Then a topological walk is initiated on tree nodes that do not have a predecessor and then applied to all nodes of the SCC. Such order ensures that high-weighted edges are visited first during the traversal.

Definition at line 253 of file SCCIterator.h.

Constructor & Destructor Documentation

◆ scc_member_iterator()

template<class GraphT , class GT >
llvm::scc_member_iterator< GraphT, GT >::scc_member_iterator ( const NodesType &  InputNodes)

Definition at line 306 of file SCCIterator.h.

References assert().

Member Function Documentation

◆ operator*()

template<class GraphT , class GT = GraphTraits<GraphT>>
NodesType & llvm::scc_member_iterator< GraphT, GT >::operator* ( )
inline

Definition at line 302 of file SCCIterator.h.


The documentation for this class was generated from the following file: