Description of slnngraph

Home > sltoolbox > graph > slnngraph.m

slnngraph

PURPOSE

SLNNGRAPH Constructs a nearest neighborhood based graph

SYNOPSIS

function G = slnngraph(X, X2, nnparams, varargin)

DESCRIPTION

SLNNGRAPH Constructs a nearest neighborhood based graph

 $ Syntax $
   - G = slnngraph(X, [], nnparams, ...)
   - G = slnngraph(X, X2, nnparams, ...)
 
 $ Arguments $
   - X:        The sample matrix of the (referenced) nodes
   - X2:       The sample matrix of the (query) nodes
   - nnparams: The cell array of parameters to slfindnn for determining
               neighborhoods.
   - G:        The adjacency matrix of the constructed graph

 $ Description $
   - G = slnngraph(X, [], nnparams, ...) constructs a graph with adjacency
     matrix representation using specified nearest neighbor strategy.
     You can further specify the following properties to control the
     process of adjacency matrix construction.
       \*
       \t   The Properties of Graph Matrix construction           \\
       \h     name         &      description                      \\
             'valtype'     & The type of the matrix values          \\
                             - 'logical':  using logical value
                             - 'numeric':  using numeric value (default)
             'sparse'      & Whether to construct sparse matrix 
                             (default = true)                      \\
             'tfunctor'    & The function to transform the distance
                             values to edge values. (default = [])  \\
             'sym'         & whether to symmetrizes the graph 
                             (default = false)                       \\
             'symmethod'   & The method used to symmetrization       
                             (default = [])                          \\
       \*

   - G = slnngraph(X, X2, nnparams, ...) constructs a bigraph with the
     source and target set respectively specified.

   - There are three configurations on X and X2:
       - construct graph with the same set X with all edges connecting
         the same node excluded. You can use the following syntax:
           slnngraph(X, [], ...)
       - construct graph with the same set X with the edges connecting
         the same node preserved. You can use the following syntax:
           slnngraph(X, X, ...)
       - construct graph with the different source and target sets X and
         X2, You can use the following syntax:
           slnngraph(X, X2, ...)

 $ Remarks $
   - tfunctor only takes effect for numeric value type.

   - The option sym and symmethod only take effect when X and X2 has the
     same number of elements.

 $ History $
   - Created by Dahua Lin, on Sep 8th, 2006
   - Modified by Dahua Lin, on Sep 11st, 2006
       - revise to conform to the defined neighborhood system
         representation
       - fix small bugs

CROSS-REFERENCE INFORMATION

This function calls:

• sladjlist2edgeset SLADJLIST2EDGESET Converts the adjacency list to edge set
• slfindnn SLFINDNN Finds the nearest neighbors using specified strategy
• slmakeadjmat SLMAKEADJMAT Makes an adjacency matrix using edges and corresponing values
• slsymgraph SLSYMGRAPH Forces symmetry of the adjacency matrix of a graph
• raise_lackinput RAISE_LACKINPUT Raises an error indicating lack of input argument
• slevalfunctor SLEVALFUNCTOR Evaluates a functor
• slparseprops SLPARSEPROPS Parses input parameters

This function is called by:

• slvechist SLVECHIST Makes the histogram on prototype vectors by voting
• slaffinitymat SLAFFINITYMAT Constructs an affinity matrix
• sllle SLLLE Performs Locally Linear Embedding

SOURCE CODE

0001 function G = slnngraph(X, X2, nnparams, varargin)
0002 %SLNNGRAPH Constructs a nearest neighborhood based graph
0003 %
0004 % $ Syntax $
0005 %   - G = slnngraph(X, [], nnparams, ...)
0006 %   - G = slnngraph(X, X2, nnparams, ...)
0007 %
0008 % $ Arguments $
0009 %   - X:        The sample matrix of the (referenced) nodes
0010 %   - X2:       The sample matrix of the (query) nodes
0011 %   - nnparams: The cell array of parameters to slfindnn for determining
0012 %               neighborhoods.
0013 %   - G:        The adjacency matrix of the constructed graph
0014 %
0015 % $ Description $
0016 %   - G = slnngraph(X, [], nnparams, ...) constructs a graph with adjacency
0017 %     matrix representation using specified nearest neighbor strategy.
0018 %     You can further specify the following properties to control the
0019 %     process of adjacency matrix construction.
0020 %       \*
0021 %       \t   The Properties of Graph Matrix construction           \\
0022 %       \h     name         &      description                      \\
0023 %             'valtype'     & The type of the matrix values          \\
0024 %                             - 'logical':  using logical value
0025 %                             - 'numeric':  using numeric value (default)
0026 %             'sparse'      & Whether to construct sparse matrix
0027 %                             (default = true)                      \\
0028 %             'tfunctor'    & The function to transform the distance
0029 %                             values to edge values. (default = [])  \\
0030 %             'sym'         & whether to symmetrizes the graph
0031 %                             (default = false)                       \\
0032 %             'symmethod'   & The method used to symmetrization
0033 %                             (default = [])                          \\
0034 %       \*
0035 %
0036 %   - G = slnngraph(X, X2, nnparams, ...) constructs a bigraph with the
0037 %     source and target set respectively specified.
0038 %
0039 %   - There are three configurations on X and X2:
0040 %       - construct graph with the same set X with all edges connecting
0041 %         the same node excluded. You can use the following syntax:
0042 %           slnngraph(X, [], ...)
0043 %       - construct graph with the same set X with the edges connecting
0044 %         the same node preserved. You can use the following syntax:
0045 %           slnngraph(X, X, ...)
0046 %       - construct graph with the different source and target sets X and
0047 %         X2, You can use the following syntax:
0048 %           slnngraph(X, X2, ...)
0049 %
0050 % $ Remarks $
0051 %   - tfunctor only takes effect for numeric value type.
0052 %
0053 %   - The option sym and symmethod only take effect when X and X2 has the
0054 %     same number of elements.
0055 %
0056 % $ History $
0057 %   - Created by Dahua Lin, on Sep 8th, 2006
0058 %   - Modified by Dahua Lin, on Sep 11st, 2006
0059 %       - revise to conform to the defined neighborhood system
0060 %         representation
0061 %       - fix small bugs
0062 %
0063 
0064 %% parse input
0065 
0066 if nargin < 3
0067     raise_lackinput('slnngraph', 3);
0068 end
0069 
0070 if ~isnumeric(X) || ndims(X) ~= 2 
0071     error('sltoolbox:invalidarg', ...
0072         'X should be a 2D numeric matrix');
0073 end
0074 
0075 if isempty(X2)
0076     X2 = [];
0077 else
0078     if ~isnumeric(X2) || ndims(X2) ~= 2 
0079         error('sltoolbox:invalidarg', ...
0080             'A non-empty X2 should be a 2D numeric matrix');
0081     end
0082 end
0083     
0084 if ~iscell(nnparams)
0085     error('stoolbox:invalidarg', ...
0086         'The parameters for slfindnn should be groupped in a cell array');
0087 end
0088 
0089 opts.valtype = 'numeric';
0090 opts.sparse = true;
0091 opts.tfunctor = [];
0092 opts.sym = false;
0093 opts.symmethod = [];
0094 opts = slparseprops(opts, varargin{:});
0095 
0096 switch opts.valtype
0097     case 'logical'
0098         islogic = true;
0099     case 'numeric';
0100         islogic = false;
0101     otherwise
0102         error('sltoolbox:invalidarg', ...
0103             'Invalid value type for graph: %s', opts.valtype);
0104 end
0105 
0106 
0107 %% Main
0108 
0109 n0 = size(X, 2);
0110 if isempty(X2)
0111     nq = n0;    
0112 else
0113     nq = size(X2, 2);
0114 end
0115 can_sym = (n0 == nq);
0116 
0117 % find nearest neighbor
0118 if ~islogic
0119     [nnidx, dists] = slfindnn(X, X2, nnparams{:});
0120 else
0121     nnidx = slfindnn(X, X2, nnparams{:});
0122 end
0123 
0124 % group edges and vectorizes distances
0125 edges = sladjlist2edgeset(nnidx, 0);
0126 edges = edges(:, [2,1]);  % flip in order to place source to left, target to right
0127 clear nnidx;
0128 if ~islogic
0129     dists = vertcat(dists{:});
0130 else
0131     dists = [];
0132 end
0133 
0134 % compute edge values
0135 if ~isempty(dists)
0136     if isempty(opts.tfunctor)
0137         vals = dists;
0138     else
0139         vals = slevalfunctor(opts.tfunctor, dists);
0140     end
0141 else
0142     vals = [];
0143 end
0144 clear dists;
0145 
0146 % make graph matrix
0147 G = slmakeadjmat(n0, nq, edges, vals, islogic, opts.sparse);
0148 
0149 % symmetrize the graph
0150 if opts.sym && can_sym
0151     G = slsymgraph(G, opts.symmethod);
0152 end
0153 
0154 
0155 
0156

---

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