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}