.dot
file)
Find the connected components of a graph (that's represened as a digraph G {
x0 -> y0;
x0 -> z0;
x1 -> y1;
x1 -> z1;
x2 -> y2;
x2 -> z2;
}
The graph has three connected components:
Try it out:
- Clone or download this tiny repo
python3 -m venv venv
source venv/bin/activate
pip install requirements.txt
python print_connected_components.py
output
(venv) Matts-Mac-mini:DisconnectedGraphs mpayne$ python print_connected_components.py
Component 1: {'y0', 'z0', 'x0'}
Component 2: {'x1', 'z1', 'y1'}
Component 3: {'z2', 'x2', 'y2'}
(venv) Matts-Mac-mini:DisconnectedGraphs mpayne$
References (thanks to Justin R from the awesome community at Recurse.com)
- To read a graphviz
.dot
file https://networkx.org/documentation/stable/reference/drawing.html?highlight=nx_pydot#module-networkx.drawing.nx_pydot - To find the connect components of a graph https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.components.connected_components.html#networkx.algorithms.components.connected_components