wolffd@0: function [triangulated, order] = check_triangulated(G)
wolffd@0: % CHECK_TRIANGULATED Return 1 if G is a triangulated (chordal) graph, 0 otherwise.
wolffd@0: % [triangulated, order] = check_triangulated(G)
wolffd@0: % 
wolffd@0: % A numbering alpha is perfect if Nbrs(alpha(i)) intersect {alpha(1)...alpha(i-1)} is complete.
wolffd@0: % A graph is triangulated iff it has a perfect numbering.
wolffd@0: % The Maximum Cardinality Search algorithm will create such a perfect numbering if possible.
wolffd@0: % See Golumbic, "Algorithmic Graph Theory and Perfect Graphs", Cambridge Univ. Press, 1985, p85.
wolffd@0: % or Castillo, Gutierrez and Hadi, "Expert systems and probabilistic network models", Springer 1997, p134.
wolffd@0: 
wolffd@0: 
wolffd@0: G = setdiag(G, 1);
wolffd@0: n = length(G);
wolffd@0: order = zeros(1,n);
wolffd@0: triangulated = 1;
wolffd@0: numbered = [1];
wolffd@0: order(1) = 1;
wolffd@0: for i=2:n
wolffd@0:   U = mysetdiff(1:n, numbered); % unnumbered nodes
wolffd@0:   score = zeros(1, length(U));
wolffd@0:   for ui=1:length(U)
wolffd@0:     u = U(ui);
wolffd@0:     score(ui) = length(myintersect(neighbors(G, u), numbered));
wolffd@0:   end
wolffd@0:   u = U(argmax(score));
wolffd@0:   numbered = [numbered u];
wolffd@0:   order(i) = u;
wolffd@0:   nns = myintersect(neighbors(G,u), order(1:i-1)); % numbered neighbors
wolffd@0:   if ~isequal(G(nns,nns), ones(length(nns))) % ~complete(G(nns,nns))
wolffd@0:     triangulated = 0;
wolffd@0:     break;
wolffd@0:   end
wolffd@0: end
wolffd@0: