Graph adjacency matrix to incidence matrix

Conversion from graph adjacency matrix to incidence matrix.

Description

Returns a sparse incidence matrix 'mInc' according to the adjacency matrix 'mAdj'. The edge ordering in the incidence matrix is according to the order of adjacent edges of vertices starting from the 1st vertex, i.e. first edges coincide with first vertex, next edges coincide with second vertex, etc.
If the graph is directed, the incidence matrix mInc contains -1s, indicating an "in-going" edge, and 1s indicating an "outgoing" edge.
If the graph is undirected, the incidence matrix mInc contains only 1s.

• MATLAB release: MATLAB 7.6 (R2008a)
• Other Files: incidence.m, ; license.txt

[Wolfgang Schwanghart]

At first sight, this function is quite good. It has a reasonable help, error checks and quite a few comments in the code. Yet, regarding its computational efficiency, there is a serious short-coming. It is heavily looped, both when extracting edges from the adjacency matrix and when building the incidence matrix. This makes the function slow and makes it even slower when you have a sparse adjacency matrix as input. You can easily vectorize this function using the find function with two outputs. Following lines have been written for a conversion from a (sparse) adjacency matrix B to a sparse incidence matrix A.

siz = size(B);
if siz(1)~=siz(2);
    error('B must be square');
end

nrknots = siz(1);
nredges = nnz(B);
[IXknots1,IXknots2] = find(B);
sones = ones(nredges,1);
IXedges = (1:nredges)';

A = sparse([IXedges; IXedges],...
             [IXknots1; IXknots2],...
             [-sones; sones],...
             nredges,nrknots);

Perhaps you have the time to modify your function so that it can handle sparse matrices efficiently. Right now, the function is very inefficient and hence I rate it with only one star. Yet, I am happy to change my rating when the above mentioned problems are fixed.

[Ondrej]

Well, thank you for pointing out those "bugs". You are right about all you said.Actually I already planned to change it to some more efficient algorithm without loops, but as I can see you basically already solved it:-). So thank you. I will soon really simplify the code and post it here.

[Wolfgang Schwanghart]

Now that's much better and much faster. Two minor things that can still be improved. First, if the adjacency matrix is supplied as full matrix, you don't really need to convert it to sparse. It should work without converting. Returning the incidence matrix as sparse however, is always a good idea since it likely contains many more zeros than the adjacency matrix.

Second, the function fails in case of nonzeros on the main diagonal. While this may rarely happen (except when your graph has 1-cycles), it may be worth an a-priori check using the function spdiags.

By the way, it might be nicer to write ~issparse(mAdj) instead of (issparse(mAdj)==0), but that's really not so important. And... providing a minimal example in the help block is always good.

Thanks for the update.

[Ondrej]

I just uploaded an updated version with self-loops checks and I also added an example. However, I left the conversion to sparse matrix unchanged, because I believe that in most cases the adjency matrix will contain "enough" zeros to have the computation more efficient.
btw. I didn't use spdiags because according to my simulations, it is slower than normal diag (and since I use it only for a check, it shouldn't last long).

P.S. Thank you once again Wolfgang for all those hints.