prim

PRIM Prim's algorithm for calculating a minimal spanning tree.
   [E] = PRIM(AADJ)
   
   Implementation of Prim's algorithm for calculating a minimal spanning
   tree from a graph adjacency matrix. This implementation can incorporate
   negative edge weights. Create a maximal spanning tree by specifying
   the negative of the graph adjacency matrix.

   Inputs:
       AADJ : A graph adjacency matrix, including the possibility of
           negative edge weights.

   Outputs:
       E : Matrix with two columns describing the resulting minimal weight
           spanning tree. Each row gives the maximal cliques for a branch
           of the tree.

0001 function [E] = prim(Aadj)
0002 %PRIM Prim's algorithm for calculating a minimal spanning tree.
0003 %   [E] = PRIM(AADJ)
0004 %
0005 %   Implementation of Prim's algorithm for calculating a minimal spanning
0006 %   tree from a graph adjacency matrix. This implementation can incorporate
0007 %   negative edge weights. Create a maximal spanning tree by specifying
0008 %   the negative of the graph adjacency matrix.
0009 %
0010 %   Inputs:
0011 %       AADJ : A graph adjacency matrix, including the possibility of
0012 %           negative edge weights.
0013 %
0014 %   Outputs:
0015 %       E : Matrix with two columns describing the resulting minimal weight
0016 %           spanning tree. Each row gives the maximal cliques for a branch
0017 %           of the tree.
0018 
0019 %   MATPOWER
0020 %   $Id: prim.m 2272 2014-01-17 14:15:47Z ray $
0021 %   by Daniel Molzahn, PSERC U of Wisc, Madison
0022 %   Copyright (c) 2013-2014 by Power System Engineering Research Center (PSERC)
0023 %
0024 %   This file is part of MATPOWER.
0025 %   See http://www.pserc.cornell.edu/matpower/ for more info.
0026 %
0027 %   MATPOWER is free software: you can redistribute it and/or modify
0028 %   it under the terms of the GNU General Public License as published
0029 %   by the Free Software Foundation, either version 3 of the License,
0030 %   or (at your option) any later version.
0031 %
0032 %   MATPOWER is distributed in the hope that it will be useful,
0033 %   but WITHOUT ANY WARRANTY; without even the implied warranty of
0034 %   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
0035 %   GNU General Public License for more details.
0036 %
0037 %   You should have received a copy of the GNU General Public License
0038 %   along with MATPOWER. If not, see <http://www.gnu.org/licenses/>.
0039 %
0040 %   Additional permission under GNU GPL version 3 section 7
0041 %
0042 %   If you modify MATPOWER, or any covered work, to interface with
0043 %   other modules (such as MATLAB code and MEX-files) available in a
0044 %   MATLAB(R) or comparable environment containing parts covered
0045 %   under other licensing terms, the licensors of MATPOWER grant
0046 %   you additional permission to convey the resulting work.
0047 
0048 
0049 Vnew = 1;
0050 E = [];
0051 nnode = size(Aadj,1);
0052 cols(1).c = sparse(Aadj(Vnew(1),:)~=0);
0053 cols(1).c(Vnew) = 0;
0054 while length(Vnew) < nnode
0055     % Choose an edge (u,v) with minimal weight so that u is in Vnew and
0056     % v is not
0057 
0058     % Find the best available edge
0059     bestedge.value = inf;
0060     bestedge.row = [];
0061     bestedge.col = [];
0062     for i=1:length(Vnew)
0063         
0064         [tempMaxVal,tempMaxCol] = min(Aadj(Vnew(i),cols(i).c));
0065         if tempMaxVal < bestedge.value
0066             bestedge.value = tempMaxVal;
0067             bestedge.row = Vnew(i);
0068             
0069             tempc = find(cols(i).c,tempMaxCol);
0070             bestedge.col = tempc(tempMaxCol);
0071         end
0072     end
0073     
0074     Vnew = [Vnew; bestedge.col];
0075     cols(length(Vnew)).c = sparse(Aadj(Vnew(end),:) ~= 0);
0076     cols(length(Vnew)).c(Vnew) = 0;
0077     
0078     for i=1:length(Vnew)-1
0079         cols(i).c(Vnew(end)) = 0;
0080     end
0081     
0082     E = [E; bestedge.row bestedge.col];
0083     
0084     if isempty(bestedge.row) || isempty(bestedge.col)
0085         error('prim: Error in Prim''s Algorithm. System is probably separated into multiple island. Ensure connected system and try again.');
0086     end
0087     
0088 end
0089 V = Vnew;