LLVM  15.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 a BFS walk. First a maximum spanning tree (forest) is built based on all edges within the SCC collection. Then a BFS walk is initiated on tree nodes that do not have a predecessor. Finally, the BFS order computed is the traversal order of the nodes of the SCC. Such order ensures that high-weighted edges are visited first during the tranversal.

Definition at line 252 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 304 of file SCCIterator.h.

References assert(), and llvm::reverse().

Member Function Documentation

◆ operator*()

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

Definition at line 300 of file SCCIterator.h.


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