File Exchange

image thumbnail

Graph adjacency matrix to incidence matrix

version 1.11 (2.05 KB) by

Conversion from graph adjacency matrix to incidence matrix.

11 Downloads

Updated

View License

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.

Comments and Ratings (6)

Sergio

Sergio (view profile)

Oops! Forget my latter question :-)

Sergio

Sergio (view profile)

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

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.

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

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.

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

1.11

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

1.10

function renamed to adj2inc() + speed-up

1.6

faster check for matrix symmetry (minor speed-up)

1.5

warning identifier added + minor comments

1.4

Self-loops check added (Thanks to Wolfgang Schwanghart)

1.2

Major speed-up update thanks to Wolfgang Schwanghart

1.1

Error handling added + new comments

MATLAB Release
MATLAB 7.6 (R2008a)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video