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 % Copyright (c) 2012-2016, Power Systems Engineering Research Center (PSERC) 0020 % by Ray Zimmerman, PSERC Cornell 0021 % 0022 % This file is part of MATPOWER. 0023 % Covered by the 3-clause BSD License (see LICENSE file for details). 0024 % See https://matpower.org for more info. 0025 0026 %% initialize groups and unvisited list 0027 nn = size(C, 2); %% number of nodes 0028 Ct = C'; 0029 visited = zeros(1, nn); %% start with nothing visited 0030 if nargin < 2 0031 groups = {}; 0032 unvisited = 1:nn; 0033 isolated = find(sum(abs(C), 1) == 0); %% find isolated nodes 0034 unvisited(isolated) = []; %% remove isolated nodes from unvisited 0035 end 0036 0037 %% traverse graph, starting with first unvisited node 0038 cn = unvisited(1); %% set current node to first unvisited node 0039 visited(cn) = 1; %% mark current node as visited 0040 %% use FIFO queue for breadth-first, LIFO stack for depth-first 0041 qs = zeros(1, nn); %% initialize queue/stack 0042 f = 1; N = 0; %% queue starts at position f, has N elements 0043 % t = 0; %% top of stack at position t 0044 0045 %% push current node to queue/stack 0046 qs(mod(f+N-1, nn)+1) = cn; N = N + 1; %% FIFO / BFS 0047 % t = t + 1; qs(t) = cn; %% LIFO / DFS 0048 0049 while N %% FIFO / BFS 0050 % while t %% LIFO / DFS 0051 %% pop next node 0052 cn = qs(f); N = N - 1; f = mod(f, nn) + 1; %% FIFO / BFS 0053 % cn = qs(t); t = t - 1; %% LIFO / DFS 0054 0055 %% find all nodes connected to current node 0056 %% (finding rows of column-indexed Ct, rather than cols of row-indexed C, 0057 %% because row-indexing a sparse matrix is sloooowww, results in ~30x 0058 %% speed up on ~60k bus network) 0059 [jj, junk] = find(Ct(:, C(:, cn) ~= 0)); %% non-zeros in rows connected to cn 0060 % [jj, ~] = find(Ct(:, C(:, cn) ~= 0)); %% non-zeros in rows connected to cn 0061 % [~, jj] = find(C(C(:, cn) ~= 0, :)); %% non-zeros in rows connected to cn 0062 cnn = jj(visited(jj) == 0); %% indices of non-visited cols (may contain dups) 0063 0064 %% mark them as visited and queue them 0065 for k = 1:length(cnn) 0066 if visited(cnn(k)) == 0 %% if not yet visited 0067 visited(cnn(k)) = 1; %% mark as visited 0068 %% push it to queue/stack 0069 N = N + 1; qs(mod(f+N-2, nn)+1) = cnn(k); %% FIFO / BFS 0070 % t = t + 1; qs(t) = cnn(k); %% LIFO / DFS 0071 end 0072 end 0073 end 0074 0075 %% add visited nodes to group 0076 group = find(visited); 0077 groups{end+1} = group; 0078 0079 %% update unvisited 0080 v = ones(nn, 1); 0081 v(unvisited) = 0; 0082 v(group) = 1; 0083 unvisited = find(v == 0); 0084 0085 %% recurse to traverse remaining components 0086 if isempty(unvisited) %% sort groups by cardinality 0087 l = cellfun('length', groups); 0088 [junk, i] = sort(l, 2, 'descend'); 0089 % [~, i] = sort(l, 2, 'descend'); 0090 groups = groups(i); 0091 else %% recurse 0092 [groups, unvisited] = connected_components(C, groups, unvisited); 0093 end 0094 0095 %% prepare to return isolated nodes 0096 if nargin < 2 0097 unvisited = isolated; 0098 end