Code covered by the BSD License  

Highlights from
Graph adjacency matrix to incidence matrix

5.0

5.0 | 2 ratings Rate this file 39 Downloads (last 30 days) File Size: 2.05 KB File ID: #24661

Graph adjacency matrix to incidence matrix

by

 

08 Jul 2009 (Updated )

Conversion from graph adjacency matrix to incidence matrix.

| Watch this File

File Information
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 "out-going" edge.
If the graph is undirected, the incidence matrix mInc contains only 1s.

MATLAB release MATLAB 7.6 (R2008a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (6)
22 Mar 2011 Sergio

Oops! Forget my latter question :-)

22 Mar 2011 Sergio

Please, how could I modify it in order to contain +1 and -1 instead of only logical values? Thanks!

10 Jul 2009 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.

10 Jul 2009 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.

08 Jul 2009 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.

08 Jul 2009 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.

Updates
08 Jul 2009

Error handling added + new comments

08 Jul 2009

Major speed-up update thanks to Wolfgang Schwanghart

10 Jul 2009

Self-loops check added (Thanks to Wolfgang Schwanghart)

23 Mar 2011

warning identifier added + minor comments

24 Mar 2011

faster check for matrix symmetry (minor speed-up)

26 Mar 2011

function renamed to adj2inc() + speed-up

06 Jul 2011

new optional parameter: adj2inc(A,0)= directed, graph,adj2inc(A,1) = undirected graph

Contact us