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