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.
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