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