There may be many legal triangulations of a graph, some more efficient
than others (in terms of the clique sizes). You can use the attached
matlab function to check if your graph is triangulated or not. It should
be easy to translate this to your favourite programming language.
HTH,
Kevin
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
This archive was generated by hypermail 2b29 : Wed Nov 22 2000 - 21:18:34 PST