networkit.components¶

class networkit.components.BiconnectedComponents¶

Bases: Algorithm

Determines the biconnected components of an undirected graph as defined in Tarjan, Robert. Depth-First Search and Linear Graph Algorithms. SIAM J. Comput. Vol 1, No. 2, June 1972.

Parameters:

G (networkit.Graph) – The input graph.

getComponentSizes()¶

Returns the map from component id to size.

Returns:

dict(int – A dict that maps each component id to its size.

Return type:

int)

getComponents()¶

Returns all the components, each stored as (unordered) set of nodes.

Returns:

A vector of vectors. Each inner vector contains all the nodes inside the component.

Return type:

vector[vector[node]]

getComponentsOfNode(u)¶

Get the components that contain node u.

Parameters:

u (int) – The node.

Returns:

Components that contain node u.

Return type:

set

numberOfComponents()¶

Returns the number of components.

Returns:

The number of components.

Return type:

int

class networkit.components.ComponentDecomposition¶

Bases: Algorithm

componentOfNode(v)¶

Get the the component in which node v is situated.

Parameters:

v (int) – The node whose component is asked for.

Returns:

Component in which node v is situated.

Return type:

int

getComponentSizes()¶

Get the component sizes.

Returns:

A dict containing the component ids and their size.

Return type:

dict(int : int)

getComponents()¶

Get the connected components, each as a list of nodes.

Returns:

The connected components.

Return type:

list(int)

getPartition()¶

Get a Partition that represents the components.

Returns:

A partition representing the found components.

Return type:

networkit.Partition

numberOfComponents()¶

Get the number of connected components.

Returns:

The number of connected components.

Return type:

int

class networkit.components.ConnectedComponents(G)¶

Bases: ComponentDecomposition

Determines the connected components and associated values for an undirected graph. Create ConnectedComponents for Graph G.

Parameters:

G (networkit.Graph) – The graph.

static extractLargestConnectedComponent(graph, compactGraph=False)¶

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

Notes

Available for undirected graphs only.

Parameters:

• G (networkit.Graph) – The input graph.

• compactGraph (bool, optional) – 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. Default: False

Returns:

A graph that contains only the nodes inside the largest connected component.

Return type:

networkit.Graph

class networkit.components.DynConnectedComponents(G)¶

Bases: ComponentDecomposition, DynAlgorithm

Determines and updates the connected components of an undirected graph.

Parameters:

G (networkit.Graph) – The input graph.

class networkit.components.DynWeaklyConnectedComponents(G)¶

Bases: ComponentDecomposition, DynAlgorithm

Determines and updates the weakly connected components of a directed graph.

Parameters:

G (networkit.Graph) – The input graph.

class networkit.components.ParallelConnectedComponents(G, coarsening=True)¶

Bases: ComponentDecomposition

Determines the connected components and associated values for an undirected graph.

Parameters:

• G (networkit.Graph) – The input graph

• coarsening (bool, optional) – Specifies whether the main algorithm based on label propagation (LP) shall work recursively (true) or not (false) by coarsening/contracting an LP-computed clustering. Defaults to true since we saw positive effects in terms of running time for many networks. Beware of possible memory implications. Default: True

class networkit.components.StronglyConnectedComponents(G)¶

Bases: ComponentDecomposition

Computes the strongly connected components of a directed graph.

class networkit.components.WeaklyConnectedComponents(G)¶

Bases: ComponentDecomposition

Determines the weakly connected components of a directed graph.

Parameters:

G (networkit.Graph) – The graph.