In this notebook we present some algorithms to analyze the connectivity properties of a graph. NetworKit’s components classes are grouped in the networkit.components module. They all have a `run`

method that must be called after the chosen algorithm has been initialised. The first step is to import Networkit.

```
[1]:
```

```
import networkit as nk
```

The ConnectedComponents(G) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph. The constructor expects a networkit.Graph.

The following function determines the connected components of a disconnected graph:

```
[2]:
```

```
# Read graph
G = nk.readGraph("../input/hep-th.graph", nk.Format.METIS)
```

```
[3]:
```

```
# Initialse algorithm
cc = nk.components.ConnectedComponents(G)
```

```
[4]:
```

```
# Run algorithm
cc.run()
print("number of components ", cc.numberOfComponents())
```

```
number of components 1332
```

```
[5]:
```

```
# Get components as unordered sets of nodes
v = 0
print("component of node ", v , ": " , cc.componentOfNode(v))
# Get all nodes in in v's component
print(cc.getComponents()[0])
```

```
component of node 0 : 0
[0, 7764]
```

Additionally, the connected components class has a function extractLargestConnectedComponent(G, compactGraph=False) which constructs a new graph that contains only the nodes inside the largest connected component. It expects an undirected graph as well. If `compactGraph`

is set to true the node ids of the output graph will be
renumbered; otherwise they will not be changed.

```
[6]:
```

```
newGraph = cc.extractLargestConnectedComponent(G, True)
```

The new graph containing only the nodes inside the largest the connected component can then be manipulated like any other graph.

A BiconnectedComponent(G) is a maximal biconnected subgraph of an undirected graph G. A biconnected graph is a connected and nonseparable graph, meaning that if any one vertex were to be removed, the graph will remain connected. The constructor expects an undirected networkit.Graph.

```
[7]:
```

```
# Read graph
G = nk.readGraph("../input/karate.graph", nk.Format.METIS)
```

```
[8]:
```

```
# Initialse algorithm
bicc = nk.components.BiconnectedComponents(G)
```

```
[9]:
```

```
# Run algorithm
bicc.run()
print("number of components: ", bicc.numberOfComponents())
```

```
number of components: 3
```

```
[10]:
```

```
# Get components as unordered sets of nodes
print(bicc.getComponents())
```

```
[[0, 1, 2, 3, 7, 8, 9, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33], [0, 4, 5, 6, 10, 16], [0, 11]]
```

A WeaklyConnectedComponent(G) is a maximal subgraph of a directed graph such that for every pair of vertices u, v in the subgraph, there is an undirected path from u to v and a directed path from v to u. The constructor expects a directed networkit.Graph.

```
[11]:
```

```
# Read graph
G = nk.readGraph("../input/jazz2_directed.gml", nk.Format.GML)
```

```
[12]:
```

```
wcc = nk.components.WeaklyConnectedComponents(G)
```

```
[13]:
```

```
wcc.run()
print("number of components: ", wcc.numberOfComponents())
```

```
number of components: 3
```

```
[14]:
```

```
# Get components as unordered sets of nodes
print(wcc.getComponents())
```

```
[[0, 1, 2], [3], [4]]
```

A StronglyConnectedComponent(G) of a directed graph G is a maximal strongly connected subgraph. A directed graph is strongly connected if there is a path between all pairs of vertices in the graph. The constructor expects a directed networkit.Graph as a mandatory parameter.

```
[15]:
```

```
# Read graph
G = nk.readGraph("../input/foodweb-baydry.konect", nk.Format.KONECT)
```

```
[16]:
```

```
scc = nk.components.StronglyConnectedComponents(G)
```

```
[17]:
```

```
#Run recursively
scc.run()
print("number of components: ", scc.numberOfComponents())
```

```
number of components: 26
```

```
[18]:
```

```
# Get sorted list of components
partition = scc.getPartition()
indexes = sorted(set(partition.getVector()))
# Print every member of each component
for cmp in indexes:
print("Members of component {} : {}".format(cmp, partition.getMembers(cmp)))
```

```
Members of component 0 : {56}
Members of component 1 : {19}
Members of component 2 : {15, 16, 17, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 74, 75, 76, 77, 78, 79, 80, 81, 84, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 124, 125, 126, 127}
Members of component 3 : {97}
Members of component 4 : {55}
Members of component 5 : {18}
Members of component 6 : {1}
Members of component 7 : {2}
Members of component 8 : {3}
Members of component 9 : {4}
Members of component 10 : {5}
Members of component 11 : {6}
Members of component 12 : {7}
Members of component 13 : {83}
Members of component 14 : {8}
Members of component 15 : {82}
Members of component 16 : {123}
Members of component 17 : {9}
Members of component 18 : {10}
Members of component 19 : {11}
Members of component 20 : {12}
Members of component 21 : {13}
Members of component 22 : {73}
Members of component 23 : {85}
Members of component 24 : {14}
Members of component 25 : {0}
```