Description of slsymgraph

Home > sltoolbox > graph > slsymgraph.m

slsymgraph

PURPOSE

SLSYMGRAPH Forces symmetry of the adjacency matrix of a graph

SYNOPSIS

function As = slsymgraph(A, symmethod)

DESCRIPTION

SLSYMGRAPH Forces symmetry of the adjacency matrix of a graph

 $ Syntax $
   - As = slsymgraph(A)
   - As = slsymgraph(A, symmethod)

 $ Arguments $
   - A:            The adjacency matrix of the original graph
   - symmethod:    The method to symmetrize the graph
   - As:           The symmetry adjacency matrix
 
 $ Description $
   - As = slsymgraph(A) makes a symmetry version of the adjacency matrix
     A using default method.

   - As = slsymgraph(A, symmethod) symmetrizes the adjacency matrix by 
     using the specified method. 
     \*
     \t    Table. The method to symmetrizes adjacency matrix
     \h       name       &              description 
             'avgor'     & Force symmetry using the following rule:
                           if both aij and aji are non-zeros, then 
                           take their average
                           if only one of aij and aji is non-zero, then
                           take the non-zero one
                           if both aij and aji are zeros, then set zero
                           (for both logical and numeric)
             'avgand'    & Force symmetry using the following rule:
                           if both aij and aji are non-zeros, then 
                           take their average
                           if either one of aij and aji is zero, then
                           set zero
                           (for both logical and numeric)
             'or'        & Use or-rule: d = aij | aji
                           (for only logical)
             'and'       & Use and-rule: d = aij & aji
                           (for only logical)
             'simavg'    & make simple average: always take (aij+aji)/2
                           (for only numeric)
     \*
     The default method to use is 'avgor'. You can use your own function
     handle. It should be like the following form:
       v = f(v1, v2)
     v1 and v2 are arrays of equal size with corresponding values. For
     a reasonable function, it should satisfy that:
       f(v, v) == v && f(v1, v2) = f(v2, v1)

 $ Remarks $
   - A can be full matrix or sparse matrix, and As preserves the same 
     storage form.

   - A should be a square matrix.

   - When 'avgor' method is applied to logical, it is equivalent to 'or'
     when 'avgand' method is applied to logical, it is equivalent to
     'and'.

 $ History $
   - Created by Dahua Lin, on Sep 8, 2006

CROSS-REFERENCE INFORMATION

This function calls:

• slmakeadjmat SLMAKEADJMAT Makes an adjacency matrix using edges and corresponing values

This function is called by:

• sladjmat SLADJMAT Constructs the adjacency matrix representation of a graph
• sledges2adjmat SLEDGES2ADJMAT Creates an adjacency matrix from edge set
• slnngraph SLNNGRAPH Constructs a nearest neighborhood based graph
• slisomap SLISOMAP Performs ISOMAP manifold embedding

SUBFUNCTIONS

• function vd = compsym_avgor(v1, v2)
• function vd = compsym_avgand(v1, v2)
• function vd = compsym_or(v1, v2)
• function vd = compsym_and(v1, v2)

SOURCE CODE

0001 function As = slsymgraph(A, symmethod)
0002 %SLSYMGRAPH Forces symmetry of the adjacency matrix of a graph
0003 %
0004 % $ Syntax $
0005 %   - As = slsymgraph(A)
0006 %   - As = slsymgraph(A, symmethod)
0007 %
0008 % $ Arguments $
0009 %   - A:            The adjacency matrix of the original graph
0010 %   - symmethod:    The method to symmetrize the graph
0011 %   - As:           The symmetry adjacency matrix
0012 %
0013 % $ Description $
0014 %   - As = slsymgraph(A) makes a symmetry version of the adjacency matrix
0015 %     A using default method.
0016 %
0017 %   - As = slsymgraph(A, symmethod) symmetrizes the adjacency matrix by
0018 %     using the specified method.
0019 %     \*
0020 %     \t    Table. The method to symmetrizes adjacency matrix
0021 %     \h       name       &              description
0022 %             'avgor'     & Force symmetry using the following rule:
0023 %                           if both aij and aji are non-zeros, then
0024 %                           take their average
0025 %                           if only one of aij and aji is non-zero, then
0026 %                           take the non-zero one
0027 %                           if both aij and aji are zeros, then set zero
0028 %                           (for both logical and numeric)
0029 %             'avgand'    & Force symmetry using the following rule:
0030 %                           if both aij and aji are non-zeros, then
0031 %                           take their average
0032 %                           if either one of aij and aji is zero, then
0033 %                           set zero
0034 %                           (for both logical and numeric)
0035 %             'or'        & Use or-rule: d = aij | aji
0036 %                           (for only logical)
0037 %             'and'       & Use and-rule: d = aij & aji
0038 %                           (for only logical)
0039 %             'simavg'    & make simple average: always take (aij+aji)/2
0040 %                           (for only numeric)
0041 %     \*
0042 %     The default method to use is 'avgor'. You can use your own function
0043 %     handle. It should be like the following form:
0044 %       v = f(v1, v2)
0045 %     v1 and v2 are arrays of equal size with corresponding values. For
0046 %     a reasonable function, it should satisfy that:
0047 %       f(v, v) == v && f(v1, v2) = f(v2, v1)
0048 %
0049 % $ Remarks $
0050 %   - A can be full matrix or sparse matrix, and As preserves the same
0051 %     storage form.
0052 %
0053 %   - A should be a square matrix.
0054 %
0055 %   - When 'avgor' method is applied to logical, it is equivalent to 'or'
0056 %     when 'avgand' method is applied to logical, it is equivalent to
0057 %     'and'.
0058 %
0059 % $ History $
0060 %   - Created by Dahua Lin, on Sep 8, 2006
0061 %
0062 
0063 %% parse and verify input
0064 
0065 if ndims(A) ~= 2 || size(A,1) ~= size(A,2)
0066     error('sltoolbox:invalidarg', ...
0067         'The A should be a square 2D matrix');
0068 end
0069 n = size(A, 1);
0070 
0071 if nargin < 2 || isempty(symmethod)
0072     symmethod = 'avgor';
0073 end
0074 
0075 if ischar(symmethod)
0076     switch symmethod
0077         case 'avgor'
0078             fcs = @compsym_avgor;
0079         case 'avgand'
0080             fcs = @compsym_avgand;
0081         case 'or'
0082             fcs = @compsym_or;
0083             if isnumeric(A)
0084                 error('sltoolbox:rterror', ...
0085                     'The or method is not applicable to numerical matrix');
0086             end
0087         case 'and'
0088             fcs = @compsym_and;
0089             if isnumeric(A)
0090                 error('sltoolbox:rterror', ...
0091                     'The and method is not applicable to numerical matrix');
0092             end
0093         otherwise
0094             error('sltoolbox:invalidarg', ...
0095                 'Invalid method for symmetrization: %s', method);
0096     end
0097 elseif isa(symmethod, 'function_handle')
0098     fcs = symmethod;
0099 else
0100     error('sltoolbox:invalidarg', ...
0101         'Invalid method for symmetrization.');
0102 end
0103             
0104 
0105 %% main skeleton
0106 
0107 % prepare all indices with aij or aji non-zero
0108 
0109 [I0, J0] = find(A);
0110 
0111 % single out diagonal ones
0112 is_diag = (I0 == J0);
0113 if any(is_diag)
0114     inds_diag = sub2ind([n, n], I0(is_diag), J0(is_diag));
0115 else
0116     inds_diag = [];
0117 end
0118 
0119 % process the non-diagonal ones
0120 not_diag = ~is_diag;
0121 clear is_diag;
0122 
0123 if any(not_diag)
0124     % filter indices
0125     I0 = I0(not_diag);
0126     J0 = J0(not_diag);
0127     clear not_diag;
0128 
0129     % merge to down triangular part
0130     I = I0;
0131     J = J0;
0132     idx_ut = find(I0 > J0);
0133     if ~isempty(idx_ut)
0134         I(idx_ut) = J0(idx_ut);
0135         J(idx_ut) = I0(idx_ut);
0136     end
0137     clear I0 J0 idx_ut;
0138 
0139     % unique and expand to up triangular part
0140     inds_dt = sub2ind([n, n], I, J);
0141     [inds_dt, si] = unique(inds_dt);
0142     I = I(si);
0143     J = J(si);
0144     inds_ut = sub2ind([n, n], J, I);
0145     clear I J si;
0146 else
0147     inds_dt = [];
0148     inds_ut = [];
0149 end
0150 
0151 % get original values
0152 
0153 if ~isempty(inds_dt)
0154     v_dt = A(inds_dt);
0155     v_ut = A(inds_ut);
0156 else
0157     v_dt = [];
0158     v_ut = [];
0159 end
0160 
0161 % compute the symmetrized value
0162 
0163 v = fcs(v_dt, v_ut);
0164 clear v_dt v_ut;
0165 
0166 % combine diagonal value and non-diagonal value
0167 
0168 if ~isempty(inds_diag)
0169     v_diag = A(inds_diag);
0170 else
0171     v_diag = [];
0172 end
0173 
0174 s_inds = vertcat(inds_diag, inds_dt, inds_ut);
0175 clear inds_diag inds_dt inds_ut;
0176 s_vals = vertcat(v_diag, v, v);
0177 clear v_diag v;
0178 
0179 % create matrix
0180 
0181 As = slmakeadjmat(n, n, s_inds, s_vals, islogical(A), issparse(A));
0182     
0183 
0184 %% symmetry value computation functions
0185 
0186 function vd = compsym_avgor(v1, v2)
0187 
0188 if isnumeric(v1)        
0189     has_both = v1 & v2;
0190     only_v1 = v1 & ~v2;
0191     only_v2 = v2 & ~v1;
0192     
0193     vd = zeros(size(v1));
0194     vd(has_both) = (v1(has_both) + v2(has_both)) / 2;
0195     vd(only_v1) = v1(only_v1);
0196     vd(only_v2) = v2(only_v2);        
0197 else
0198     vd = v1 | v2;            
0199 end
0200 
0201 
0202 function vd = compsym_avgand(v1, v2)
0203 
0204 if isnumeric(v1)
0205     has_both = v1 & v2;
0206     
0207     vd = zeros(size(v1));
0208     vd(has_both) = (v1(has_both) + v2(has_both)) / 2;
0209 else
0210     vd = v1 & v2;
0211 end
0212 
0213 
0214 function vd = compsym_or(v1, v2)
0215 
0216 vd = v1 | v2;
0217 
0218 
0219 function vd = compsym_and(v1, v2)
0220 
0221 vd = v1 & v2;
0222 
0223 
0224

---

Generated on Wed 20-Sep-2006 12:43:11 by m2html © 2003