4 Ways to Check if a Graph is Fully Connected
Published
Graphs are very handy to represent and manipulate data and relationship between objects. In this post, I’ll share some methods to check whether a graph is fully connected and some recommendations on when and where I recommend each of them.
Perform Depth First Search on all Nodes
This is extremely simple: starting from any selected node, iterate on all other nodes to find them using a search algorithm, such as Depth First Search (DFS). If a node cannot be found, then the graph is not fully connected.
Why use this approach? It’s likely you already have experience using search algorithms and this method makes immediate sense. Still, this is a slow approach but it can be valid for smaller graphs or graphs relying on conditional access (for example, if you are generating a dungeon map and some rooms are only accessible once certain items or keys have been found).
Using the Adjacency Matrix
Another simple way to check whether a graph is fully connected is to use its adjacency matrix.
Starting from a list of N nodes, start by creating a 0-filled N-by-N square matrix, and fill the diagonal with 1. Then iterate on your list of nodes: if the node at index i in the list has a connection to the node at j, you can set the value of your square matrix to 1 at position [i, j].
Once this is done, the next step is to raise your matrix to the power of the number of nodes. For example, if you have 10 nodes, you would need to raise your matrix to the power 10 (raising this kind of matrix to the power N indicates whether a path exists between the 2 nodes with a length equal or lower than N).
Finally, check the rows of your matrix: if there is a row containing only strictly positive values, then your matrix is fully connected.
One disadvantage of this approach is that while this approach can be faster than using search algorithms, multiplying matrices in this fashion can become prohibitively expensive when the size becomes too large.
There are possible fixes for this:
- Use optimizations when possible, such as disabling bounds checking, or use specialized libraries.
- You can also offload the computations to your GPU instead of using your CPU, which should give you massive speedups.
If you’re using python and have a CUDA-capable GPU, I highly recommend using Numba as a fix. The documentation gives an implementation of GPU matrix multiplication: https://numba.pydata.org/numba-doc/dev/cuda/examples.html
Check the eigenvalues of the Laplacian Matrix
The Laplacian Matrix is defined as the difference between the Diagonal matrix and the Adjacency Matrix.
Once we know the Laplacian Matrix, our work is actually almost done. We’ll need to find the Fiedler value, which is simply the second smallest eigenvalue of our Laplacian matrix. If the Fiedler value is higher than zero, then this means the graph is fully connected. If it isn’t, then the graph isn’t fully connected and some nodes are isolated from the others, or form a subgraph.
In Python, good old Numpy has our back, and provides a function to compute the eigenvalues of a square matrix.
Using NetworkX
This last method is python-specific and a bit of a cheat. In case you don’t know, NetworkX is a Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks.
I won’t go into details of how to use NetworkX, but if you’re dealing with graphs in Python, chances are you may be using it at some point in your workflow. As such, I’ll just mention that NetworkX exposes several method to check a graph’s connectivity such as is_connected, is_strongly_connected, is_weakly_connected…