# Connected Components

# pypi
import networkx
from networkx import (
draw,
DiGraph,
Graph,
)

% matplotlib inline


## 1 Undirected Graphs

### 1.1 Connected Graphs

An unconnected graph is connected if every pair of nodes has a path between them.

left = tuple("AAAAABBCDFFFGGGHIJKKKLLLN")
right = tuple("BECGNCDDEGIJHIJIJOLMOMNOO")
undirected = Graph()
draw(undirected, with_labels=True) Is this graph connected? It looks like it, since every node has an edge to it.

print(networkx.is_connected(undirected))

True


To make this graph unconnected you need to remove some edges that connect sub-graphs.

undirected.remove_edges_from([("A", "G"), ("A", "N")])
draw(undirected, with_labels=True) print(networkx.is_connected(undirected))

False


### 1.2 Connected Components

A connected component is a subset of nodes where:

• Every node in the subset has a path to every other node
• No node outside the subset has a path to a node in the subset

Let's break the graph a little more.

undirected.remove_edge("J", "O")
draw(undirected, with_labels=True) We now have three connected components.

print(networkx.number_connected_components(undirected))

3


Which we can inspect.

for component in networkx.connected_components(undirected):
print(component)

{'J', 'I', 'G', 'H', 'F'}
{'N', 'M', 'O', 'K', 'L'}
{'D', 'B', 'C', 'E', 'A'}


We can also pick out a node from one of the components and get the sub-set.

print(networkx.node_connected_component(undirected, "A"))

{'B', 'D', 'C', 'A', 'E'}


Which you can see is the third connected component in the example above.

## 2 Directed Graphs

Directed graphs have similar ideas with regard to connectivity when compared to undirected graphs, but with a strong and weak version for each.

### 2.1 Strongly Connected

A strongly connected graph is a directed graph where for every pair of nodes there is a directed path in both directions.

left = tuple("AABCDD")
right = tuple("BDDBCA")

directed = DiGraph()
draw(directed, with_labels=True) For some reason networkx uses boxes instead of arrow-heads, but hopefully you get the idea.

print(networkx.is_strongly_connected(directed))

True


### 2.2 Weakly Connected

A directed graph is weakly connected if, when all the edges are replaced by undirected edges (converting it to an undirected graph) then the graph is connected.

directed.remove_edge("B", "D")
print(networkx.is_strongly_connected(directed))
print(networkx.is_weakly_connected(directed))

False
True

draw(directed, with_labels=True) Our new graph isn't strongly connected because there's no path from B to A (or B to C, etc.). But it is weakly connected since removing the directions just makes it a loop.

### 2.3 Strongly Connected Component

This is a subset of nodes in a directed graph where:

• Every node in the subset has a directed path to every other node
• No node outside the subset has a directed path to and from every node in the subset
left = tuple("ADDDEFFFFGGH")
right = tuple("HBFGGABGHHCE")
directed_2 = DiGraph()
draw(directed_2, with_labels=True) print(networkx.is_strongly_connected(directed_2))

False


You can see that the graph is not strongly connected (there's no path to E, for instance) but is there a strongly connected component within it?

for component in networkx.strongly_connected_components(directed_2):
print(component)

{'C'}
{'H', 'G', 'E'}
{'A'}
{'B'}
{'F'}
{'D'}


In this case H, G, and E are a strongly connected component (as are each of the other individual nodes). What if we add a path from B to D?

directed_2.add_edge("B", "D")
draw(directed_2, with_labels=True) for component in networkx.strongly_connected_components(directed_2):
print(component)

{'C'}
{'H', 'G', 'E'}
{'A'}
{'B', 'F', 'D'}


Now there are two interesting strongly connected components and two not so interesting ones.

### 2.4 Weakly Connected Components

A weakly connected component is one where a directed graph is converted into an undirected graph and the sub-set of nodes is a connected component.

directed_2.remove_edges_from([("F", "A"), ("F", "H"), ("F", "G"), ("D", "G"), ("B", "D"), ("E", "G")])
draw(directed_2, with_labels=True) for component in networkx.strongly_connected_components(directed_2):
print(component)

{'C'}
{'E'}
{'H'}
{'A'}
{'B'}
{'F'}
{'D'}
{'G'}

undirected_2 = directed_2.to_undirected()
draw(undirected_2, with_labels=True) Looking at the converted graph you can see that there are two connected components.

for component in networkx.connected_components(undirected_2):
print(component)

{'A', 'H', 'G', 'C', 'E'}
{'D', 'B', 'F'}


An important thing to note is that A and C are part of their connected component, even though visually they look like they're dangling out there.

You can also skip the conversion and let network x do it for you.

for component in networkx.weakly_connected_components(directed_2):
print(component)

{'G', 'C', 'H', 'E', 'A'}
{'B', 'F', 'D'}