# How to test if a graph is fully connected and finding isolated graphs from an adjacency matrix

I have large sparse adjacency matrices that may or maybe not be fully connected. I would like to find out if a matrix is fully connected or not and if it is, which groups of nodes belong to a group/cluster. I have an example matrix:

matnew =
0     1     1     0     0     0     0
1     0     0     0     0     0     0
1     0     0     1     0     0     0
0     0     0     0     0     0     0
0     0     0     0     0     1     1
0     0     0     0     1     0     0
0     0     0     0     0     1     0


There are bi-directional edges and directed edges which belong to 2 separate clusters: $1\leftrightarrow 2$, $1\leftrightarrow 3$, $3\rightarrow 4$, and in the next cluster $5\leftrightarrow 6$, $5\rightarrow 7$, $7\rightarrow 6$.

The first approach is to use a function to calculate the paths between nodes

>> floyd_warshall_all_sp(sparse(matnew))
ans =
0     1     1     2   Inf   Inf   Inf
1     0     2     3   Inf   Inf   Inf
1     2     0     1   Inf   Inf   Inf
Inf   Inf   Inf     0   Inf   Inf   Inf
Inf   Inf   Inf   Inf     0     1     1
Inf   Inf   Inf   Inf     1     0     2
Inf   Inf   Inf   Inf     2     1     0


That works great by looking off the diagonal for Inf and then clustering, but my matrices are in the size of thousands of nodes and it is slow (too slow for my needs). Is there a method/algorithm which just checks connectivity?*

I thought about checking the walk lengths as an approximation, but to be certain I would have to guess that they are not more than a number of jumps eg 10. Which may be reasonable but even then doing the matrix multiplication of a 1000x1000 many times is not so great for an approximation.

>> (matnew^1)+(matnew^2)+(matnew^3)+(matnew^4)+(matnew)^5
ans =
6     7     7     3     0     0     0
7     3     3     3     0     0     0
7     3     3     4     0     0     0
0     0     0     0     0     0     0
0     0     0     0     5     7     4
0     0     0     0     4     5     3
0     0     0     0     3     4     2


But it does reveal quite a bit about the connectivity.

-
Have you heard about DFS? Also, matrix multiplication is rather slow, but if you want to stick with it (e.g. you have some special algorithm for your case of spare matrix), you could just do with squaring $(A+I)$, that is, $((((A+I)^2)^2 \cdots)^2)$. – dtldarek Jan 25 '13 at 18:16
@dtldarek, you mean by recursively squaring $(A+I)$ I can get higher powers more quickly so that for instance 5 multiplication give $2^8$ walk length? I hadn't thought of DFS... I should have though, thanks – Vass Jan 25 '13 at 20:33
@dtldarek, I tried to use some DFS and Dijkstra but they don't seem to look from each node, they appear to find a node with a lead and don't find the other isolated island of nodes – Vass Jan 25 '13 at 21:04
I found this file which is relatively quick for Dijkstra mathworks.com/matlabcentral/fileexchange/20025 and is as fast as squaring 4 times recusively on a 2000x2000 adjacency matrix – Vass Jan 25 '13 at 21:21
Why would you use Dijkstra? The point of DFS is just to visit nodes, all you can visit generate one connected component. Then start with another, not-yet-visited node and search for corresponding group (that is all nodes that are reachable from the new starting vertex). – dtldarek Jan 25 '13 at 22:29

I don't know what language are you using, but in ruby it would look like this (for an input given by adjacency lists):

#!/usr/bin/ruby
# encoding: utf-8

def dfs_run(graph, visited, start)
return [] if visited[start]
visited[start] = true
output = [start]
graph[start].each do |neighbour|
output += dfs_run(graph, visited, neighbour)
end
output
end

def weakly_connected_components(input_graph)

# make the graph undirected
graph = input_graph.clone
input_graph.each do |vertex, neighbours|
neighbours.each do |n| graph[n] += [vertex] end
end
graph.each do |vertex, neighbours|
neighbours.sort!
neighbours.uniq!
end

# run dfs
output = []
visited = {}
graph.keys.each do |vertex|
output << dfs_run(graph, visited, vertex).sort unless visited[vertex]
end

# return an array of wcc
output
end

# an example
graph = {0=>[1, 2, 3, 5], 1=>[0, 2, 3], 2=>[0, 1, 3, 5], 3=>[0, 1, 2, 4, 5, 6], 4=>[0], 5=>[0, 1, 2, 3, 4, 6], 6=>[0, 2, 3, 5], 7=>[8], 8=>[0], 9=>[]}
# transformed to the following undirected graph: {0=>[1, 2, 3, 4, 5, 6, 8], 1=>[0, 2, 3, 5], 2=>[0, 1, 3, 5, 6], 3=>[0, 1, 2, 4, 5, 6], 4=>[0, 3, 5], 5=>[0, 1, 2, 3, 4, 6], 6=>[0, 2, 3, 5], 7=>[8], 8=>[0, 7], 9=>[]}

print weakly_connected_components(graph), "\n"
# outputs [[0, 1, 2, 3, 4, 5, 6, 7, 8], [9]]

-

The second smallest eigenvector (Fiedler vector) of the laplacian wiki to laplacian matrix can be used to reveal information about the number of disconnected components.

-