Home > matpower5.1 > extras > sdp_pf > maxCardSearch.m

maxCardSearch

PURPOSE ^

MAXCARDSEARCH Determine graph chordality and maximal cliques.

SYNOPSIS ^

function [maxclique,ischordal] = maxCardSearch(Aadj)

DESCRIPTION ^

MAXCARDSEARCH Determine graph chordality and maximal cliques.
   [MAXCLIQUE,ISCHORDAL] = MAXCARDSEARCH(AADJ)

   Determine the maximal cliques for a chordal graph described by the
   adjacency matrix Aadj. Also test the graph for chordality. The
   algorithms for determining the maximal cliques and testing for
   chordality are described in [1].

   Inputs:
       AADJ : The adjacency matrix of a graph. If the graph is chordal,
           the maximal cliques for this graph are calculated.

   Outputs:
       MAXCLIQUE : If the graph described by Aadj is chordal, maxclique
           returns a matrix describing the maximal cliques of the graph.
           Each column of maxclique represents a clique with nonzero
           entries indicating the nodes included in the maximal clique. If
           Aadj is not chordal, maxclique is set to NaN.
       ISCHORDAL : Returns 1 if the graph described by Aadj is chordal,
           otherwise returns 0.

 [1] Tarjan, R. E., and M. Yannakakis. "Simple Linear-Time Algorithms to 
 Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and 
 Selectively Reduce Acyclic Hypergraphs." SIAM Journal on computing 13 
 (1984): 566.

CROSS-REFERENCE INFORMATION ^

This function calls: This function is called by:

SOURCE CODE ^

0001 function [maxclique,ischordal] = maxCardSearch(Aadj)
0002 %MAXCARDSEARCH Determine graph chordality and maximal cliques.
0003 %   [MAXCLIQUE,ISCHORDAL] = MAXCARDSEARCH(AADJ)
0004 %
0005 %   Determine the maximal cliques for a chordal graph described by the
0006 %   adjacency matrix Aadj. Also test the graph for chordality. The
0007 %   algorithms for determining the maximal cliques and testing for
0008 %   chordality are described in [1].
0009 %
0010 %   Inputs:
0011 %       AADJ : The adjacency matrix of a graph. If the graph is chordal,
0012 %           the maximal cliques for this graph are calculated.
0013 %
0014 %   Outputs:
0015 %       MAXCLIQUE : If the graph described by Aadj is chordal, maxclique
0016 %           returns a matrix describing the maximal cliques of the graph.
0017 %           Each column of maxclique represents a clique with nonzero
0018 %           entries indicating the nodes included in the maximal clique. If
0019 %           Aadj is not chordal, maxclique is set to NaN.
0020 %       ISCHORDAL : Returns 1 if the graph described by Aadj is chordal,
0021 %           otherwise returns 0.
0022 %
0023 % [1] Tarjan, R. E., and M. Yannakakis. "Simple Linear-Time Algorithms to
0024 % Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and
0025 % Selectively Reduce Acyclic Hypergraphs." SIAM Journal on computing 13
0026 % (1984): 566.
0027 
0028 %   MATPOWER
0029 %   Copyright (c) 2013-2015 by Power System Engineering Research Center (PSERC)
0030 %   by Daniel Molzahn, PSERC U of Wisc, Madison
0031 %
0032 %   $Id: maxCardSearch.m 2644 2015-03-11 19:34:22Z ray $
0033 %
0034 %   This file is part of MATPOWER.
0035 %   Covered by the 3-clause BSD License (see LICENSE file for details).
0036 %   See http://www.pserc.cornell.edu/matpower/ for more info.
0037 
0038 %% Setup
0039 
0040 nbus = size(Aadj,1);
0041 nline = nnz(Aadj)/2;
0042 
0043 %% Create a perfect elimination ordering
0044 
0045 % Store in s{i} all unnumbered vertices adjacent to exactly i numbered
0046 % vertices.
0047 s{nline} = [];
0048 s{1} = 1:nbus; % This corresponds to s{0} in the paper's notation
0049 
0050 % Maintain the largest index j such that s{j} is nonempty
0051 jidx = 1;
0052 
0053 % Candidate perfect elimination ordering, with vertex numbering in vnum.
0054 % Index of vnum corresponds to the original vertex number, and the value of
0055 % vnum indicates the new vertex number.
0056 alpha = zeros(nbus,1);
0057 
0058 % v2s stores which set contains a given vertex?
0059 v2s = ones(nbus,1);
0060 
0061 i = nbus;
0062 
0063 while i >= 1
0064     
0065     % To carry out a step of the search, we remove a vertex v from s(jidx)
0066     % and number it.
0067     v = s{jidx}(1);
0068     if length(s{jidx}(:)) > 1
0069         s{jidx} = s{jidx}(2:end);
0070     else
0071         s{jidx} = [];
0072     end
0073     alpha(v) = i;
0074     v2s(v) = 0; % This vertex is no longer in a set
0075     
0076     % For each unnumbered vertex w adjacent to v, we move w from the set
0077     % containing it to the next set
0078     vadj = find(Aadj(:,v));
0079     for k=1:length(vadj)
0080         % If this node isn't already numbered, remove it from the original set
0081         if v2s(vadj(k)) ~= 0
0082             s{v2s(vadj(k))} = s{v2s(vadj(k))}(s{v2s(vadj(k))}(:) ~= vadj(k));
0083         
0084             % Add it to the new set
0085             s{v2s(vadj(k))+1} = [s{v2s(vadj(k))+1}(:); vadj(k)];
0086 
0087             % Update v2s
0088             v2s(vadj(k)) = v2s(vadj(k)) + 1;
0089         end
0090     end
0091     
0092     % Add one to jidx and then decrease jidx until reaching a non-empty s(jidx)
0093     jidx = jidx + 1; 
0094     if jidx > length(s)
0095         jidx = jidx - 1;
0096     end
0097     while jidx >= 1 && isempty(s{jidx})
0098         jidx = jidx - 1;
0099     end
0100     
0101     i = i-1;
0102     
0103 end
0104 
0105 
0106 %% Check for chordality
0107 
0108 f = zeros(nbus,1);
0109 index = zeros(nbus,1);
0110 ischordal = 1;
0111 for i=1:nbus
0112     w = find(alpha == i);
0113     f(w) = w;
0114     index(w) = i;
0115     
0116     valid_v = find(Aadj(:,w));
0117     valid_v = valid_v(alpha(valid_v) < i);
0118     for vidx = 1:length(valid_v)
0119         v = valid_v(vidx);
0120         index(v) = i;
0121         if f(v) == v
0122             f(v) = w;
0123         end
0124     end
0125     
0126     for vidx = 1:length(valid_v)
0127         v = valid_v(vidx);
0128         if index(f(v)) < i
0129             ischordal = 0;
0130             break;
0131         end
0132     end
0133     
0134     if ~ischordal
0135         break;
0136     end
0137 end
0138 
0139 
0140 %% Determine maximal cliques
0141 
0142 % According to https://en.wikipedia.org/wiki/Chordal_graph
0143 % "To list all maximal cliques of a chordal graph, simply find a perfect
0144 % elimination ordering, form a clique for each vertex v together with the
0145 % neighbors of v that are later than v in the perfect elimination ordering,
0146 % and test whether each of the resulting cliques is maximal."
0147 
0148 % alpha is a candidate perfect elimination ordering. First form all
0149 % cliques. Then determine which cliques are maximal. Put maximal cliques in
0150 % the columns of the variable maxclique.
0151 
0152 if ischordal
0153     % Form a matrix representation of the cliques
0154     clique = speye(nbus,nbus);
0155     for i=1:nbus
0156         % neighbors of node i that are later in the ordering
0157         neighbors = find(Aadj(i,:)); 
0158         neighbors = neighbors(alpha(neighbors) > alpha(i));
0159 
0160         clique(i,neighbors) = 1;
0161     end
0162 
0163     % Test whether each clique is maximal. A clique is not maximal if a node
0164     % neighboring any of the nodes in the clique, but not in the clique, is
0165     % connected to all nodes in the clique.
0166     i=0;
0167     nclique = size(clique,1);
0168     while i < nclique
0169         i = i+1;
0170 
0171         neighbors = [];
0172         cliquei = find(clique(i,:));
0173         cliquei_bool = clique(i,:).';
0174         nnzi = sum(cliquei_bool);
0175 
0176         for k = 1:length(cliquei) % Check all nodes adjacent to nodes in the clique, but not included in the clique
0177             neighbors = [neighbors find(Aadj(cliquei(k),:))];
0178         end
0179         neighbors = unique(setdiff(neighbors,cliquei));
0180 
0181         not_maximal = 0;
0182         for m=1:length(neighbors)
0183             % If this neighbor is connected to all other nodes in the clique,
0184             % this is not a maximal clique
0185             if Aadj(neighbors(m),:) * cliquei_bool >= nnzi
0186                 not_maximal = 1;
0187                 break;
0188             end
0189         end
0190 
0191         if not_maximal
0192             clique = clique([1:i-1 i+1:nclique],:); % Delete this clique
0193             i = i-1; % After deletion, the next clique is really numbered i
0194             nclique = nclique - 1;
0195         end
0196     end
0197     maxclique = clique.'; % put maximal cliques in the columns
0198 else
0199     maxclique = nan; % maximal clique algorithm only works for chordal graphs
0200 end

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