[LEFT]
[COLOR=#000000][FONT=Tahoma][FONT=monospace][COLOR=#0000FF]function[/COLOR] [COLOR=#008800][[/COLOR]T,pred[COLOR=#008800]][/COLOR] = graphminspantree[COLOR=#008800]([/COLOR]G,[COLOR=#0000FF]varargin[/COLOR][COLOR=#008800])[/COLOR]
[COLOR=#228B22]%GRAPHMINSPANTREE finds the minimal spanning tree in graph.[/COLOR]
[COLOR=#228B22]% [/COLOR]
[COLOR=#228B22]% [T, PRED] = GRAPHMINSPANTREE(G) finds an acyclic subset of edges that[/COLOR]
[COLOR=#228B22]% connects all the nodes in the undirected graph G and for which the total[/COLOR]
[COLOR=#228B22]% weight is minimized. Weights of the edges are all nonzero entries in the[/COLOR]
[COLOR=#228B22]% lower triangle of the n-by-n sparse matrix G. T is a spanning tree[/COLOR]
[COLOR=#228B22]% represented by a sparse matrix. The output PRED contains the predecessor[/COLOR]
[COLOR=#228B22]% nodes of the minimal spanning tree with the root node indicated by a[/COLOR]
[COLOR=#228B22]% zero. The root defaults to the first node in the largest connected[/COLOR]
[COLOR=#228B22]% component, which requires an extra call to the graphconncomp function.[/COLOR]
[COLOR=#228B22]% [/COLOR]
[COLOR=#228B22]% [T, PRED] = GRAPHMINSPANTREE(G,R) sets the root of the minimal spanning[/COLOR]
[COLOR=#228B22]% tree to node R.[/COLOR]
[COLOR=#228B22]%[/COLOR]
[COLOR=#228B22]% GRAPHMINSPANTREE(...,'METHOD',METHOD) selects the algorithm to use,[/COLOR]
[COLOR=#228B22]% options are: [/COLOR]
[COLOR=#228B22]% ['Prim'] - Prim's algorithm grows the MST one edge at a time by[/COLOR]
[COLOR=#228B22]% adding a minimal edge that connects a node in the[/COLOR]
[COLOR=#228B22]% growing MST with any other node. Time complexity is[/COLOR]
[COLOR=#228B22]% O(e*log(n)). [/COLOR]
[COLOR=#228B22]% 'Kruskal' - Kruskal's algorithm grows the MST one edge at a time by[/COLOR]
[COLOR=#228B22]% finding an edge that connects two trees in a spreading[/COLOR]
[COLOR=#228B22]% forest of growing MSTs. Time complexity is[/COLOR]
[COLOR=#228B22]% O(e+x*log(n)) where x is the number of edges no longer[/COLOR]
[COLOR=#228B22]% than the longest edge in the MST. [/COLOR]
[COLOR=#228B22]% [/COLOR]
[COLOR=#228B22]% Note: n and e are number of nodes and edges respectively.[/COLOR]
[COLOR=#228B22]% [/COLOR]
[COLOR=#228B22]% GRAPHMINSPANTREE(...,'WEIGHTS',W) provides custom weights for the edges,[/COLOR]
[COLOR=#228B22]% useful to indicate zero valued weights. W is a column vector with one[/COLOR]
[COLOR=#228B22]% entry for every edge in G, traversed column-wise.[/COLOR]
[COLOR=#228B22]% [/COLOR]
[COLOR=#228B22]% Remarks: When the graph is unconnected, Prim's algorithm only returns the[/COLOR]
[COLOR=#228B22]% tree that contains R, while Kruskal's algorithm returns an MST for every[/COLOR]
[COLOR=#228B22]% component. [/COLOR]
[COLOR=#228B22]% [/COLOR]
[COLOR=#228B22]% Example:[/COLOR]
[COLOR=#228B22]% % Create an undirected graph with 6 nodes[/COLOR]
[COLOR=#228B22]% W = [.41 .29 .51 .32 .50 .45 .38 .32 .36 .29 .21];[/COLOR]
[COLOR=#228B22]% DG = sparse([1 1 2 2 3 4 4 5 5 6 6],[2 6 3 5 4 1 6 3 4 2 5],W)[/COLOR]
[COLOR=#228B22]% UG = tril(DG + DG')[/COLOR]
[COLOR=#228B22]% view(biograph(UG,[],'ShowArrows','off','ShowWeights','on'))[/COLOR]
[COLOR=#228B22]% % Find the minimum spanning tree of UG[/COLOR]
[COLOR=#228B22]% [ST,pred] = graphminspantree(UG)[/COLOR]
[COLOR=#228B22]% view(biograph(ST,[],'ShowArrows','off','ShowWeights','on'))[/COLOR]
[COLOR=#228B22]%[/COLOR]
[COLOR=#228B22]% See also: GRAPHALLSHORTESTPATHS, GRAPHCONNCOMP, GRAPHISDAG,[/COLOR]
[COLOR=#228B22]% GRAPHISOMORPHISM, GRAPHISSPANTREE, GRAPHMAXFLOW, GRAPHPRED2PATH,[/COLOR]
[COLOR=#228B22]% GRAPHSHORTESTPATH, GRAPHTHEORYDEMO, GRAPHTOPOORDER, GRAPHTRAVERSE.[/COLOR]
[COLOR=#228B22]%[/COLOR]
[COLOR=#228B22]% References: [/COLOR]
[COLOR=#228B22]% [1] J. B. Kruskal. "On the shortest spanning subtree of a graph and the[/COLOR]
[COLOR=#228B22]% traveling salesman problem" In Proceedings of the American[/COLOR]
[COLOR=#228B22]% Mathematical Society, 7:48-50, 1956. [/COLOR]
[COLOR=#228B22]% [2] R. Prim. "Shortest connection networks and some generalizations"[/COLOR]
[COLOR=#228B22]% Bell System Technical Journal, 36:1389-1401, 1957.[/COLOR]
[COLOR=#228B22]% Copyright 2006-2008 The MathWorks, Inc.[/COLOR]
[COLOR=#228B22]% [FONT=MathJax_Math][I]R[/I][/FONT][FONT=MathJax_Math][I]e[/I][/FONT][FONT=MathJax_Math][I]v[/I][/FONT][FONT=MathJax_Math][I]i[/I][/FONT][FONT=MathJax_Math][I]s[/I][/FONT][FONT=MathJax_Math][I]i[/I][/FONT][FONT=MathJax_Math][I]o[/I][/FONT][FONT=MathJax_Math][I]n[/I][/FONT][FONT=MathJax_Main]:[/FONT][FONT=MathJax_Main]1.1.6.7[/FONT] [FONT=MathJax_Math][I]D[/I][/FONT][FONT=MathJax_Math][I]a[/I][/FONT][FONT=MathJax_Math][I]t[/I][/FONT][FONT=MathJax_Math][I]e[/I][/FONT][FONT=MathJax_Main]:[/FONT][FONT=MathJax_Main]2010[/FONT][FONT=MathJax_Main]/[/FONT][FONT=MathJax_Main]09[/FONT][FONT=MathJax_Main]/[/FONT][FONT=MathJax_Main]02[/FONT][FONT=MathJax_Main]13[/FONT][FONT=MathJax_Main]:[/FONT][FONT=MathJax_Main]28[/FONT][FONT=MathJax_Main]:[/FONT][FONT=MathJax_Main]55[/FONT][/COLOR]
algorithms = [COLOR=#008800]{[/COLOR][COLOR=#A020F0]'prim'[/COLOR],[COLOR=#A020F0]'kruskal'[/COLOR][COLOR=#008800]}[/COLOR];
algorithmkeys = [COLOR=#008800]{[/COLOR][COLOR=#A020F0]'pri'[/COLOR],[COLOR=#A020F0]'kru'[/COLOR][COLOR=#008800]}[/COLOR];
debug_level = [COLOR=#3333FF]0[/COLOR];
[COLOR=#228B22]% set defaults of optional input arguments[/COLOR]
W = [COLOR=#008800][[/COLOR][COLOR=#008800]][/COLOR]; [COLOR=#228B22]% no custom weights[/COLOR]
R = [COLOR=#008800][[/COLOR][COLOR=#008800]][/COLOR]; [COLOR=#228B22]% no root given[/COLOR]
algorithm = [COLOR=#3333FF]1[/COLOR]; [COLOR=#228B22]% defaults to prim[/COLOR]
[COLOR=#228B22]% find out signature of input arguments[/COLOR]
[COLOR=#0000FF]if[/COLOR] nargin>[COLOR=#3333FF]1[/COLOR] && isnumeric[COLOR=#008800]([/COLOR][COLOR=#0000FF]varargin[/COLOR][COLOR=#008800]{[/COLOR][COLOR=#3333FF]1[/COLOR][COLOR=#008800]}[/COLOR][COLOR=#008800])[/COLOR]
R = [COLOR=#0000FF]varargin[/COLOR][COLOR=#008800]{[/COLOR][COLOR=#3333FF]1[/COLOR][COLOR=#008800]}[/COLOR];
[COLOR=#0000FF]varargin[/COLOR][COLOR=#008800]([/COLOR][COLOR=#3333FF]1[/COLOR][COLOR=#008800])[/COLOR] = [COLOR=#008800][[/COLOR][COLOR=#008800]][/COLOR];
[COLOR=#0000FF]end[/COLOR]
[COLOR=#228B22]% read in optional PV input arguments[/COLOR]
nvarargin = numel[COLOR=#008800]([/COLOR][COLOR=#0000FF]varargin[/COLOR][COLOR=#008800])[/COLOR];
[COLOR=#0000FF]if[/COLOR] nvarargin
[COLOR=#0000FF]if[/COLOR] [COLOR=#0000FF]rem[/COLOR][COLOR=#008800]([/COLOR]nvarargin,[COLOR=#3333FF]2[/COLOR][COLOR=#008800])[/COLOR] == [COLOR=#3333FF]1[/COLOR]
[COLOR=#0000FF]error[/COLOR][COLOR=#008800]([/COLOR][COLOR=#A020F0]'Bioinfo:graphminspantree:IncorrectNumberOfArguments'[/COLOR],[COLOR=#008800]...[/COLOR]
[COLOR=#A020F0]'Incorrect number of arguments to %s.'[/COLOR],mfilename[COLOR=#008800])[/COLOR];
[COLOR=#0000FF]end[/COLOR]
okargs = [COLOR=#008800]{[/COLOR][COLOR=#A020F0]'method'[/COLOR],[COLOR=#A020F0]'weights'[/COLOR][COLOR=#008800]}[/COLOR];
[COLOR=#0000FF]for[/COLOR] [COLOR=#0000FF][COLOR=#3333FF]j[/COLOR][/COLOR]=[COLOR=#3333FF]1[/COLOR]:[COLOR=#3333FF]2[/COLOR]:nvarargin-[COLOR=#3333FF]1[/COLOR]
pname = [COLOR=#0000FF]varargin[/COLOR][COLOR=#008800]{[/COLOR][COLOR=#0000FF][COLOR=#3333FF]j[/COLOR][/COLOR][COLOR=#008800]}[/COLOR];
pval = [COLOR=#0000FF]varargin[/COLOR][COLOR=#008800]{[/COLOR][COLOR=#0000FF][COLOR=#3333FF]j[/COLOR][/COLOR]+[COLOR=#3333FF]1[/COLOR][COLOR=#008800]}[/COLOR];
k = [COLOR=#0000FF]find[/COLOR][COLOR=#008800]([/COLOR]strncmpi[COLOR=#008800]([/COLOR]pname,okargs,numel[COLOR=#008800]([/COLOR]pname[COLOR=#008800])[/COLOR][COLOR=#008800])[/COLOR][COLOR=#008800])[/COLOR];
[COLOR=#0000FF]if[/COLOR] isempty[COLOR=#008800]([/COLOR]k[COLOR=#008800])[/COLOR]
[COLOR=#0000FF]error[/COLOR][COLOR=#008800]([/COLOR][COLOR=#A020F0]'Bioinfo:graphminspantree:UnknownParameterName'[/COLOR],[COLOR=#008800]...[/COLOR]
[COLOR=#A020F0]'Unknown parameter name: %s.'[/COLOR],pname[COLOR=#008800])[/COLOR];
[COLOR=#0000FF]elseif[/COLOR] [COLOR=#0000FF]length[/COLOR][COLOR=#008800]([/COLOR]k[COLOR=#008800])[/COLOR]>[COLOR=#3333FF]1[/COLOR]
[COLOR=#0000FF]error[/COLOR][COLOR=#008800]([/COLOR][COLOR=#A020F0]'Bioinfo:graphminspantree:AmbiguousParameterName'[/COLOR],[COLOR=#008800]...[/COLOR]
[COLOR=#A020F0]'Ambiguous parameter name: %s.'[/COLOR],pname[COLOR=#008800])[/COLOR];
[COLOR=#0000FF]else[/COLOR]
[COLOR=#0000FF]switch[/COLOR][COLOR=#008800]([/COLOR]k[COLOR=#008800])[/COLOR]
[COLOR=#0000FF]case[/COLOR] [COLOR=#3333FF]1[/COLOR] [COLOR=#228B22]% 'method'[/COLOR]
algorithm = [COLOR=#0000FF]find[/COLOR][COLOR=#008800]([/COLOR]strncmpi[COLOR=#008800]([/COLOR]pval,algorithms,numel[COLOR=#008800]([/COLOR]pval[COLOR=#008800])[/COLOR][COLOR=#008800])[/COLOR][COLOR=#008800])[/COLOR];
[COLOR=#0000FF]if[/COLOR] isempty[COLOR=#008800]([/COLOR]algorithm[COLOR=#008800])[/COLOR]
[COLOR=#0000FF]error[/COLOR][COLOR=#008800]([/COLOR][COLOR=#A020F0]'Bioinfo:graphminspantree:NotValidMethod'[/COLOR],[COLOR=#008800]...[/COLOR]
[COLOR=#A020F0]'String "%s" is not a valid algorithm.'[/COLOR],pval[COLOR=#008800])[/COLOR]
[COLOR=#0000FF]elseif[/COLOR] numel[COLOR=#008800]([/COLOR]algorithm[COLOR=#008800])[/COLOR]>[COLOR=#3333FF]1[/COLOR]
[COLOR=#0000FF]error[/COLOR][COLOR=#008800]([/COLOR][COLOR=#A020F0]'Bioinfo:graphminspantree:AmbiguousMethod'[/COLOR],[COLOR=#008800]...[/COLOR]
[COLOR=#A020F0]'String "%s" is ambiguous.'[/COLOR],pval[COLOR=#008800])[/COLOR]
[COLOR=#0000FF]end[/COLOR]
[COLOR=#0000FF]case[/COLOR] [COLOR=#3333FF]2[/COLOR] [COLOR=#228B22]% 'weights'[/COLOR]
W = pval[COLOR=#008800]([/COLOR]:[COLOR=#008800])[/COLOR];
[COLOR=#0000FF]end[/COLOR]
[COLOR=#0000FF]end[/COLOR]
[COLOR=#0000FF]end[/COLOR]
[COLOR=#0000FF]end[/COLOR]
[COLOR=#228B22]% find manually the best root (if it was not given)[/COLOR]
[COLOR=#0000FF]if[/COLOR] isempty[COLOR=#008800]([/COLOR]R[COLOR=#008800])[/COLOR]
[COLOR=#008800][[/COLOR]num_comp,classes[COLOR=#008800]][/COLOR] = graphconncomp[COLOR=#008800]([/COLOR]G,[COLOR=#A020F0]'directed'[/COLOR],false[COLOR=#008800])[/COLOR];
[COLOR=#0000FF]if[/COLOR] num_comp==[COLOR=#3333FF]1[/COLOR]
R = [COLOR=#3333FF]1[/COLOR];
[COLOR=#0000FF]else[/COLOR]
R = [COLOR=#0000FF]find[/COLOR][COLOR=#008800]([/COLOR]classes==mode[COLOR=#008800]([/COLOR]classes[COLOR=#008800])[/COLOR],[COLOR=#3333FF]1[/COLOR],[COLOR=#A020F0]'first'[/COLOR][COLOR=#008800])[/COLOR];
[COLOR=#0000FF]end[/COLOR]
[COLOR=#0000FF]end[/COLOR]
[COLOR=#228B22]% call the mex implementation of the graph algorithms[/COLOR]
[COLOR=#0000FF]if[/COLOR] nargout>[COLOR=#3333FF]1[/COLOR]
[COLOR=#0000FF]if[/COLOR] isempty[COLOR=#008800]([/COLOR]W[COLOR=#008800])[/COLOR]
[COLOR=#008800][[/COLOR]T,pred[COLOR=#008800]][/COLOR] = graphalgs[COLOR=#008800]([/COLOR]algorithmkeys[COLOR=#008800]{[/COLOR]algorithm[COLOR=#008800]}[/COLOR],debug_level,false,G,R[COLOR=#008800])[/COLOR];
[COLOR=#0000FF]else[/COLOR]
[COLOR=#008800][[/COLOR]T,pred[COLOR=#008800]][/COLOR] = graphalgs[COLOR=#008800]([/COLOR]algorithmkeys[COLOR=#008800]{[/COLOR]algorithm[COLOR=#008800]}[/COLOR],debug_level,false,G,R,W[COLOR=#008800])[/COLOR];
[COLOR=#0000FF]end[/COLOR]
[COLOR=#0000FF]else[/COLOR]
[COLOR=#0000FF]if[/COLOR] isempty[COLOR=#008800]([/COLOR]W[COLOR=#008800])[/COLOR]
T = graphalgs[COLOR=#008800]([/COLOR]algorithmkeys[COLOR=#008800]{[/COLOR]algorithm[COLOR=#008800]}[/COLOR],debug_level,false,G,R[COLOR=#008800])[/COLOR];
[COLOR=#0000FF]else[/COLOR]
T = graphalgs[COLOR=#008800]([/COLOR]algorithmkeys[COLOR=#008800]{[/COLOR]algorithm[COLOR=#008800]}[/COLOR],debug_level,false,G,R,W[COLOR=#008800])[/COLOR];
[COLOR=#0000FF]end[/COLOR]
[COLOR=#0000FF]end[/COLOR][/FONT]
[/FONT][/COLOR][/LEFT]