I have N nodes, a node might have an undirected edge to other nodes, resulting in K connected components (K<=N, K unknown).
I can test if a given pair is connected. In each step in time, I can run N/2 such tests in parallel (a given node can be tested once per step). Each connected component is a cluster graph (it has no three-vertex induced path). The goal is to find all K components and list of nodes per component.
The actual application is nodes in a computer network, therefore I can run pairwise tests in parallel. I have ~256 nodes. How to approach this? A naive solution of N*(N-1)/2 tests is too costly. Hopefully I could reuse a library algorithm in Python a solution.
For example for detecting the graph below (7 nodes, 3 connected-components (CC)), I might need this set of tests:
Step1 tests: D-A, C-F, E-B Step2 tests: A-B, C-B, D-E (found CC: A-B-C) Step3 tests: D-F (Found CC: D) Step4 tests: E-F (Found CC: E-F) Done.