ITE / code / shared / embedded / MatlabBGL / mst.m

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166``` ```function [out1 out2 out3] = mst(A,varargin) % MST Compute a minimum spanning tree for an undirected graph A. % % There are two ways to call MST. % T = mst(A) % [i j v] = mst(A) % The first call returns the minimum spanning tree T of A. % The second call returns the set of edges in the minimum spanning tree. % The calls are related by % T = sparse(i,j,v,size(A,1), size(A,1)); % T = T + T'; % The optional algname parameter chooses which algorithm to use to compute % the minimum spanning tree. Note that the set of edges returned is not % symmetric and the final graph must be explicitly symmetrized. % % This method works on undirected graphs. % % ... = mst(A,...) takes a set of % key-value pairs or an options structure. See set_matlab_bgl_options % for the standard options. % options.algname: the minimum spanning tree algorithm % ['prim' | {'kruskal'}] % options.edge_weight: a double array over the edges with an edge % weight for each node, see EDGE_INDEX and EXAMPLES/REWEIGHTED_GRAPHS % for information on how to use this option correctly, see Note 1. % [{'matrix'} | length(nnz(A)) double vector] % options.root: specify the root or starting vertex for the algorithm % This option only applies to prim's algorithm. % [{'none'} | any vertex number] % options.fix_diag: remove any diagonal entries to get correct output % from Prim's algorithm [0 | {1}]; beware this option with the % edge_weight option too. % % Note: the input to this function must be symmetric, so this function % ignores the 'notrans' default option and never transposes the input. % % Note 1: see EXAMPLES/REWEIGHTED_GRAPHS for how to reweight a symmetric % graph correctly. There are a few complicated details. % % Example: % load graphs/clr-24-1.mat % mst(A) % % See also PRIM_MST, KRUSKAL_MST % David Gleich % Copyright, Stanford University, 2006-2008 %% History % 2006-05-03: Changed to using kruskal as the default following problems % with prim due to negative edge weights. % 2006-05-31: Added full2sparse option % 2006-06-15: Fixed error with graph symmetric (T+T') instead of max(T,T') % found by Mark Cummins % 2006-11-09: Temporary fix for disconnected graphs and the number of edges % in the mst is LESS than n-1. % 2006-11-10: Added warning for prim with disconnected graphs. % 2007-04-09: Fixed documentation typos. (Thanks Chris Maes.) % 2007-04-09: Fixed bug with 0 weighted graphs. (Thanks Chris Maes.) % 2007-04-20: Added edge weight option % 2007-07-12: Fixed edge_weight documentation % Added note about symmetric edge weights % 2007-12-14: Added rooted option for prim's algorithm % 2008-10-07: Changed options parsing % Addressed issue with incorrect prim output and fixed matrix diagonal %% [trans check full2sparse] = get_matlab_bgl_options(varargin{:}); if full2sparse && ~issparse(A), A = sparse(A); end if trans, end % no trans check options = struct('algname', 'kruskal', 'edge_weight', 'matrix', ... 'root', 'none', 'fix_diag', 1); options = merge_options(options,varargin{:}); fixed_diag= 0; if options.fix_diag && strcmp(options.algname,'prim') ... && any(diag(A)), A = A - diag(diag(A)); fixed_diag= 1; end % edge_weights is an indicator that is 1 if we are using edge_weights % passed on the command line or 0 if we are using the matrix. edge_weights = 0; edge_weight_opt = 'matrix'; if strcmp(options.edge_weight, 'matrix') % do nothing if we are using the matrix weights else edge_weights = 1; edge_weight_opt = options.edge_weight; if fixed_diag, warning('matlab_bgl:fix_diag',... 'the diagonal was adjusted, the edge_weight option may be incorrect'); end end if check % make sure the matrix is symmetric if ~edge_weights check_matlab_bgl(A,struct('sym',1,'values',1,... 'noneg', strcmp(options.algname,'prim'))); else check_matlab_bgl(A,struct()); if strcmp(options.algname,'prim') && any(edge_weights < 0) error('matlab_bgl:invalidParameter', ... 'the edge_weight array must be non-negative'); end % check for symmetry [i j] = find(A); Av = sparse(i,j,edge_weight_opt,size(A,1), size(A,2)); check_matlab_bgl(Av,struct('sym',1,'nodefault',1)); end if strcmp(options.algname,'prim') if max(components(A)) > 1 warning('mst:connected', ... ['The output from MST using Prim''s algorithm\n' ... 'on a disconnected graph is only a partial spanning tree.']); end end end % old temporary fix for incorrect number of edges % num_components = max(components(A)); if strcmp(options.root,'none') root = 0; % a flag used to denote "no root" to the mex elseif isa(options.root, 'double') root = options.root; else error('matlab_bgl:invalidParameter', ... 'options.root is not ''none'' or a vertex number.'); end [i j v] = mst_mex(A,lower(options.algname),edge_weight_opt,root); % old temporary fix for disconnected graphs % if (num_components > 1) % i = i(1:end-(num_components-1)); % j = j(1:end-(num_components-1)); % v = v(1:end-(num_components-1)); % end if (nargout == 1 || nargout == 0) T = sparse(i,j,v,size(A,1),size(A,1)); T = T + T'; out1 = T; if nnz(T) == 0 && nnz(A) > 0 warning('mst:empty', ... ['MST is empty. This can occur if you have reweighted\n' ... 'the matrix with 0 edge weights. Try the [i j v] = mst(...)\n' ... 'call instead for that case.']); end else out1 = i; out2 = j; out3 = v; end; ```