Description of incidence_matrix

Home > matgraph > @graph > incidence_matrix.m

incidence_matrix

PURPOSE

incidence_matrix(g) --- return the vertex/edge incidence matrix.

SYNOPSIS

function M = incidence_matrix(g,type)

DESCRIPTION

 incidence_matrix(g) --- return the vertex/edge incidence matrix.
 The matrix returned is always sparse. 

 We return an nv-by-ne matrix whose ij entry is 1 if vertex i is an
 end point of edge j.

 Optional: incidence_matrix(g,'signed') which is the same matrix but one
 entry in each column is negative and one is negative.

CROSS-REFERENCE INFORMATION

This function calls:

• edges edges(g) --- list the edges in g as a 2-column matrix
• size size(g) --- returns [nv,ne] for the graph
• sparse sparse(g) --- convert internal storage for g to sparse

This function is called by:

• alpha [a,S] = alpha(g) --- indepencence number
• bridges bridges(g,algo) --- find all cut edges in g
• color color(g,algo) --- color the graph g by a given algorithm

SOURCE CODE

0001 function M = incidence_matrix(g,type)
0002 % incidence_matrix(g) --- return the vertex/edge incidence matrix.
0003 % The matrix returned is always sparse.
0004 %
0005 % We return an nv-by-ne matrix whose ij entry is 1 if vertex i is an
0006 % end point of edge j.
0007 %
0008 % Optional: incidence_matrix(g,'signed') which is the same matrix but one
0009 % entry in each column is negative and one is negative.
0010 
0011 
0012 
0013 
0014 
0015 [n,m] = size(g);
0016 e = edges(g);
0017 
0018 if nargin<2
0019     type = 'unsigned';  % default type
0020 end
0021 
0022 signed = false;
0023 
0024 switch lower(type)
0025     case 'signed'
0026         signed = true;
0027     case 'unsigned'
0028         signed = false;
0029     otherwise
0030         error(['Unknown incidence matrix type:', type]);
0031 end
0032 
0033 i = [e(:,1);e(:,2)];
0034 j = [1:m,1:m]';
0035 
0036 if signed
0037     k = [ones(m,1);-ones(m,1)];
0038 else
0039     k = ones(2*m,1);
0040 end
0041 
0042 M = sparse(i,j,k,n,m);

---

Generated on Thu 13-Mar-2008 14:23:52 by m2html © 2003