Reorder nodes of a directed SCC by decreasing edge weight.

Synopsis

Declared in <llvm/ADT/SCCIterator.h>

template<
    class GraphT,
    class GT = GraphTraits<GraphT>>
class scc_member_iterator;

Description

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.

Member Functions

Name

Description

scc_member_iterator [constructor]

Construct an iterator that reorders InputNodes by edge weight.

operator*

Return the SCC nodes ordered by decreasing edge weight.

Created with MrDocs