1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
function [triangulated, order] = check_triangulated(G)
% CHECK_TRIANGULATED Return 1 if G is a triangulated (chordal) graph, 0 otherwise.
% [triangulated, order] = check_triangulated(G)
%
% A numbering alpha is perfect if Nbrs(alpha(i)) intersect {alpha(1)...alpha(i-1)} is complete.
% A graph is triangulated iff it has a perfect numbering.
% The Maximum Cardinality Search algorithm will create such a perfect numbering if possible.
% See Golumbic, "Algorithmic Graph Theory and Perfect Graphs", Cambridge Univ. Press, 1985, p85.
% or Castillo, Gutierrez and Hadi, "Expert systems and probabilistic network models", Springer 1997, p134.
G = setdiag(G, 1);
n = length(G);
order = zeros(1,n);
triangulated = 1;
numbered = [1];
order(1) = 1;
for i=2:n
U = mysetdiff(1:n, numbered); % unnumbered nodes
score = zeros(1, length(U));
for ui=1:length(U)
u = U(ui);
score(ui) = length(myintersect(neighbors(G, u), numbered));
end
u = U(argmax(score));
numbered = [numbered u];
order(i) = u;
nns = myintersect(neighbors(G,u), order(1:i-1)); % numbered neighbors
if ~isequal(G(nns,nns), ones(length(nns))) % ~complete(G(nns,nns))
triangulated = 0;
break;
end
end
|
