Connected components of bipartite graphs in matlab

Question

I have two types of data, X and Y. Every x in X is associated with some number of Ys, and every y in Y may or may not be associated with some number of Xs.

Xs don't associate with other Xs and Ys don't associate with other Ys. So the situation looks like this:

with Xs on the left and Ys on the right.

I know how to find the connected components of a graph when I only have one type of data: create a N-by-N matrix and call graphconncomp on it. How do I find all connected components when I have two types of data?

Answer 1

How to construct the graph's affinity matrix as a sparse matrix:

G = sparse( length(X)+length(Y), length(X)+length(Y) );

This creates an "all zeros" sparse matrix of size |X|+|Y|-by-|X|+|Y|.
If you type

>> whos G

You'll see that despite the fact that G has roughly 50K^2 it takes almost no memory.

Now all you got to do is use your function to set 1 between the corresponding nodes of X and Y and then you'll be able to run graphconncomp on G

---

The bipartite case

To construct an adjacency matrix for a bipartite graph you can work (initially) with a much smaller (still sparse) matrix B of size |X|-by-|Y|. Let x=length(X) and y=length(Y), then

 B = sparse( x, y ); % if you have an estimate of the number of edges, you can preallocate here

The entry B( ix, jy ) is set to 1 iff node X(ix) is connected to node Y(jy).
Once you finished constructing B, you can use it to form G simply by

 G = [ sparse( x, x ), B; B.', sparse(y, y)];

Note that I do not use zeros to create matrices of all zeros but sparse so the construction will be memory-efficient.

Now you can run graphconncomp on G.