networkit.components

class networkit.components.BiconnectedComponents

Bases: networkit.base.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: networkit.base.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: networkit.components.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
  • graph (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: networkit.components.ComponentDecomposition

Determines and updates the connected components of an undirected graph.

Parameters

G (networkit.Graph) – The input graph.

update(event)

Updates the connected components after an edge insertion or deletion.

Parameters

event (networkit.dynamics.GraphEvent) – The event that happened (edge deletion or insertion).

updateBatch(batch)

Updates the connected components after a batch of edge insertions or deletions.

Parameters

batch (list(networkit.dynamics.GraphEvent)) – A list that contains a batch of edge insertions or deletions.

class networkit.components.DynWeaklyConnectedComponents(G)

Bases: networkit.components.ComponentDecomposition

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

Parameters

G (networkit.Graph) – The input graph.

update(event)

Updates the connected components after an edge insertion or deletion.

Parameters

event (networkit.dynamics.GraphEvent) – The event that happened (edge deletion or insertion).

updateBatch(batch)

Updates the connected components after a batch of edge insertions or deletions.

Parameters

batch (list(networkit.dynamics.GraphEvent)) – A vector that contains a batch of edge insertions or deletions.

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

Bases: networkit.components.ComponentDecomposition

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

Parameters
  • graph (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.

class networkit.components.StronglyConnectedComponents(G)

Bases: networkit.components.ComponentDecomposition

Computes the strongly connected components of a directed graph.

class networkit.components.WeaklyConnectedComponents(G)

Bases: networkit.components.ComponentDecomposition

Determines the weakly connected components of a directed graph.

Parameters

G (networkit.Graph) – The graph.