Home > matpower7.1 > lib > 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 %   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

Generated on Fri 09-Oct-2020 11:21:31 by m2html © 2005