Home > matpower5.0 > connected_components.m

connected_components

PURPOSE ^

CONNECTED_COMPONENTS Returns the connected components of a graph

SYNOPSIS ^

function [groups, unvisited] = connected_components(C, groups, unvisited)

DESCRIPTION ^

CONNECTED_COMPONENTS Returns the connected components of a graph
   [GROUPS, ISOLATED] = CONNECTED_COMPONENTS(C)

   Returns the connected components of a directed graph, specified by
   a node-branch incidence matrix C, where C(I, J) = -1 if node J is
   connected to the beginning of branch I, 1 if it is connected to
   the end of branch I, and zero otherwise. The return value GROUPS
   is a cell array of vectors of the node indices for each component.
   The second return value ISOLATED is a vector of indices of isolated
   nodes that have no connecting branches.

CROSS-REFERENCE INFORMATION ^

This function calls: This function is called by:

SOURCE CODE ^

0001 function [groups, unvisited] = connected_components(C, groups, unvisited)
0002 %CONNECTED_COMPONENTS Returns the connected components of a graph
0003 %   [GROUPS, ISOLATED] = CONNECTED_COMPONENTS(C)
0004 %
0005 %   Returns the connected components of a directed graph, specified by
0006 %   a node-branch incidence matrix C, where C(I, J) = -1 if node J is
0007 %   connected to the beginning of branch I, 1 if it is connected to
0008 %   the end of branch I, and zero otherwise. The return value GROUPS
0009 %   is a cell array of vectors of the node indices for each component.
0010 %   The second return value ISOLATED is a vector of indices of isolated
0011 %   nodes that have no connecting branches.
0012 
0013 %   Can also be called with a current GROUP and list of as-yet
0014 %   UNVISITED nodes:
0015 %   [GROUPS, UNVISITED] = CONNECTED_COMPONENTS(C, GROUPS, UNVISITED)
0016 %   Internally, this is used recursively.
0017 
0018 %   MATPOWER
0019 %   $Id: connected_components.m 2454 2014-12-05 21:07:50Z ray $
0020 %   by Ray Zimmerman, PSERC Cornell
0021 %   Copyright (c) 2012 by Power System Engineering Research Center (PSERC)
0022 %
0023 %   This file is part of MATPOWER.
0024 %   See http://www.pserc.cornell.edu/matpower/ for more info.
0025 %
0026 %   MATPOWER is free software: you can redistribute it and/or modify
0027 %   it under the terms of the GNU General Public License as published
0028 %   by the Free Software Foundation, either version 3 of the License,
0029 %   or (at your option) any later version.
0030 %
0031 %   MATPOWER is distributed in the hope that it will be useful,
0032 %   but WITHOUT ANY WARRANTY; without even the implied warranty of
0033 %   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
0034 %   GNU General Public License for more details.
0035 %
0036 %   You should have received a copy of the GNU General Public License
0037 %   along with MATPOWER. If not, see <http://www.gnu.org/licenses/>.
0038 %
0039 %   Additional permission under GNU GPL version 3 section 7
0040 %
0041 %   If you modify MATPOWER, or any covered work, to interface with
0042 %   other modules (such as MATLAB code and MEX-files) available in a
0043 %   MATLAB(R) or comparable environment containing parts covered
0044 %   under other licensing terms, the licensors of MATPOWER grant
0045 %   you additional permission to convey the resulting work.
0046 
0047 %% initialize groups and unvisited list
0048 nn = size(C, 2);        %% number of nodes
0049 Ct = C';
0050 visited = zeros(1, nn); %% start with nothing visited
0051 if nargin < 2
0052     groups = {};
0053     unvisited = 1:nn;
0054     isolated = find(sum(abs(C), 1) == 0);   %% find isolated nodes
0055     unvisited(isolated) = [];   %% remove isolated nodes from unvisited
0056 end
0057 
0058 %% traverse graph, starting with first unvisited node
0059 cn = unvisited(1);      %% set current node to first unvisited node
0060 visited(cn) = 1;        %% mark current node as visited
0061 %% use FIFO queue for breadth-first, LIFO stack for depth-first
0062 qs = zeros(1, nn);      %% initialize queue/stack
0063 f = 1; N = 0;           %% queue starts at position f, has N elements
0064 % t = 0;                  %% top of stack at position t
0065 
0066 %% push current node to queue/stack
0067 qs(mod(f+N-1, nn)+1) = cn; N = N + 1;       %% FIFO / BFS
0068 % t = t + 1; qs(t) = cn;                      %% LIFO / DFS
0069 
0070 while N                 %% FIFO / BFS
0071 % while t                 %% LIFO / DFS
0072     %% pop next node
0073     cn = qs(f); N = N - 1; f = mod(f, nn) + 1;  %% FIFO / BFS
0074 %     cn = qs(t); t = t - 1;                      %% LIFO / DFS
0075 
0076     %% find all nodes connected to current node
0077     %% (finding rows of column-indexed Ct, rather than cols of row-indexed C,
0078     %%  because row-indexing a sparse matrix is sloooowww, results in ~30x
0079     %%  speed up on ~60k bus network)
0080     [jj, junk] = find(Ct(:, C(:, cn) ~= 0));    %% non-zeros in rows connected to cn
0081 %    [jj, ~] = find(Ct(:, C(:, cn) ~= 0));   %% non-zeros in rows connected to cn
0082 %    [~, jj] = find(C(C(:, cn) ~= 0, :));    %% non-zeros in rows connected to cn
0083     cnn = jj(visited(jj) == 0); %% indices of non-visited cols (may contain dups)
0084 
0085     %% mark them as visited and queue them
0086     for k = 1:length(cnn)
0087         if visited(cnn(k)) == 0         %% if not yet visited
0088             visited(cnn(k)) = 1;        %% mark as visited
0089             %% push it to queue/stack
0090             N = N + 1; qs(mod(f+N-2, nn)+1) = cnn(k);   %% FIFO / BFS
0091 %             t = t + 1; qs(t) = cnn(k);                  %% LIFO / DFS
0092         end
0093     end
0094 end
0095 
0096 %% add visited nodes to group
0097 group = find(visited);
0098 groups{end+1} = group;
0099 
0100 %% update unvisited
0101 v = ones(nn, 1);
0102 v(unvisited) = 0;
0103 v(group)     = 1;
0104 unvisited    = find(v == 0);
0105 
0106 %% recurse to traverse remaining components
0107 if isempty(unvisited)       %% sort groups by cardinality
0108     l = cellfun('length', groups);
0109     [junk, i] = sort(l, 2, 'descend');
0110 %     [~, i] = sort(l, 2, 'descend');
0111     groups = groups(i);
0112 else                        %% recurse
0113     [groups, unvisited] = connected_components(C, groups, unvisited);
0114 end
0115 
0116 %% prepare to return isolated nodes
0117 if nargin < 2
0118     unvisited = isolated;
0119 end

Generated on Mon 26-Jan-2015 15:21:31 by m2html © 2005