Class ComponentDecomposition

Inheritance Relationships

Base Type

Derived Types

Class Documentation

class ComponentDecomposition : public NetworKit::Algorithm

Abstract class for algorithms that compute the components of a graph.

Subclassed by NetworKit::ConnectedComponents, NetworKit::DynConnectedComponents, NetworKit::DynWeaklyConnectedComponents, NetworKit::ParallelConnectedComponents, NetworKit::StronglyConnectedComponents, NetworKit::WeaklyConnectedComponents

Public Functions

ComponentDecomposition(const Graph &G)

Constructs the ComponentDecomposition class for the given Graph G.


G – The graph.

count numberOfComponents() const

Get the number of connected components.


The number of connected components.

count componentOfNode(node u) const

Get the component in which node u is situated.


u[in] The node whose component is asked for.

const Partition &getPartition() const

Get a Partition that represents the components.


A partition representing the found components.

std::map<index, count> getComponentSizes() const

Return the map from component to size

std::vector<std::vector<node>> getComponents() const

Vector of components, each stored as (unordered) set of nodes.

Protected Attributes

const Graph *G
Partition component