Fork me on GitHub

Class StronglyConnectedComponents¶

Defined in File StronglyConnectedComponents.hpp

Inheritance Relationships¶

Base Type¶

public NetworKit::ComponentDecomposition (Class ComponentDecomposition)

Class Documentation¶

class StronglyConnectedComponents : public NetworKit::ComponentDecomposition ¶

Public Functions

StronglyConnectedComponents(const Graph &G)¶

Determines the strongly connected components of a directed graph using Tarjan’s algorithm.

Parameters:: G – Graph A directed graph.

virtual void run() override¶: Runs the algorithm.

Public Static Functions

static Graph extractLargestStronglyConnectedComponent(const Graph &G, bool compactGraph = false)¶

Constructs a new graph that contains only the nodes inside the largest strongly connected component.

Parameters:

G – The input graph.
compactGraph – If true, the node ids of the output graph will be compacted (i.e. re-numbered from 0 to n-1). If false, the node ids will not be changed.