Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers 2

up vote 3 down vote accepted

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]]
share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.