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 %   Copyright (c) 2013-2019, Power Systems Engineering Research Center (PSERC)
0021 %   by Daniel Molzahn, PSERC U of Wisc, Madison
0022 %
0023 %   This file is part of MATPOWER/mx-sdp_pf.
0024 %   Covered by the 3-clause BSD License (see LICENSE file for details).
0025 %   See https://github.com/MATPOWER/mx-sdp_pf/ for more info.
0026 
0027 
0028 Vnew = 1;
0029 E = [];
0030 nnode = size(Aadj,1);
0031 cols(1).c = sparse(Aadj(Vnew(1),:)~=0);
0032 cols(1).c(Vnew) = 0;
0033 while length(Vnew) < nnode
0034     % Choose an edge (u,v) with minimal weight so that u is in Vnew and
0035     % v is not
0036 
0037     % Find the best available edge
0038     bestedge.value = inf;
0039     bestedge.row = [];
0040     bestedge.col = [];
0041     for i=1:length(Vnew)
0042         
0043         [tempMaxVal,tempMaxCol] = min(Aadj(Vnew(i),cols(i).c));
0044         if tempMaxVal < bestedge.value
0045             bestedge.value = tempMaxVal;
0046             bestedge.row = Vnew(i);
0047             
0048             tempc = find(cols(i).c,tempMaxCol);
0049             bestedge.col = tempc(tempMaxCol);
0050         end
0051     end
0052     
0053     Vnew = [Vnew; bestedge.col];
0054     cols(length(Vnew)).c = sparse(Aadj(Vnew(end),:) ~= 0);
0055     cols(length(Vnew)).c(Vnew) = 0;
0056     
0057     for i=1:length(Vnew)-1
0058         cols(i).c(Vnew(end)) = 0;
0059     end
0060     
0061     E = [E; bestedge.row bestedge.col];
0062     
0063     if isempty(bestedge.row) || isempty(bestedge.col)
0064         error('prim: Error in Prim''s Algorithm. System is probably separated into multiple island. Ensure connected system and try again.');
0065     end
0066     
0067 end
0068 V = Vnew;