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.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