Code covered by the BSD License  

Highlights from
Graph adjacency matrix to incidence matrix

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

Graph adjacency matrix to incidence matrix

by

Ondrej (view profile)

 

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

Sergio (view profile)

Oops! Forget my latter question :-)

Comment only
22 Mar 2011 Sergio

Sergio (view profile)

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

Comment only
10 Jul 2009 Ondrej

Ondrej (view profile)

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.

Comment only
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

Ondrej (view profile)

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.

Comment only
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 1.1

Error handling added + new comments

08 Jul 2009 1.2

Major speed-up update thanks to Wolfgang Schwanghart

10 Jul 2009 1.4

Self-loops check added (Thanks to Wolfgang Schwanghart)

23 Mar 2011 1.5

warning identifier added + minor comments

24 Mar 2011 1.6

faster check for matrix symmetry (minor speed-up)

26 Mar 2011 1.10

function renamed to adj2inc() + speed-up

06 Jul 2011 1.11

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

Contact us