Home > matpower5.1 > 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-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

Generated on Fri 20-Mar-2015 18:23:34 by m2html © 2005